I disagree with the premise of this article. Sometimes using a mutable variable really is the simplest way to implement something:
def min(foo: List[int]) -> Optional[int]:
min = None
for val in foo:
if min is None or val < min:
min = val
return min
I argue this is much easier to read than the recursive version without assignments:
def min(foo: List[int]) -> Optional[int]:
if not foo:
return None
else if len(foo) == 1:
return foo[0]
else:
rest_min = min(foo[1:])
return rest_min if rest_min < foo[0] else foo[0]
We're optimizing for readability, and sometimes readability means mutable variables. This is to says nothing about performance which is often much better with mutable variables in languages like C++.
Edit: people have posted better version of my code in the comments. Take a look for more pythonic examples.
I have changed my views since. I'm now much more okay with mutation than I used to be, under certain conditions. Ideally I want my mutations to stay local (at the function or module/class scope), and have as few cross module consequences as possible.
My view of a program is that of a dependence graph, ideally directed acyclic. Ideally we want that graph to be as sparse as possible: good old decoupling. Mutable state (not just global variables) tend to introduce hidden dependencies, making that graph denser than what it initially appears. That can be a killer.
Surprisingly though, as years pass, I am less and less certain what the "correct" structure of a program should be. I sure want to keep it small, simple, easy to maintain… but the method to achieve this still eludes me.
Yeah exactly, I think of this as "imperative in the small" and "functional in the large". There's no real cost to local state, but there's a big cost to tracking global state.
(Although game programmers seem to have necessarily built their mental models on global state, and think about it differently. Their programs generally don't get maintained for decades though.)
But "functional in the large" is basically the same thing as dependency injection in OOP languages. State and I/O are explicit parameters rather than globals.
Here is a comment I wrote about that a long time ago, on Disadvantages of Purely Functional Programming:
To me there's no real advantage to expressing something like "split a string by a delimiter" in a purely functional style. Either way, you have a trivial referentially transparent function you can reuse without causing complexity in your program. You might as well do the obvious imperative thing.
...
So both "functions and data" are effectively and usefully implemented as classes. The key is to make some classes like functions, and some classes like data. And have more of a bipartite dependency graph, where functions depend on data, and data depends on functions.
-----
I also explicitly structure the program as a graph, which I try to make acyclic, but again the problems and solutions are domain-specific. (Programming is very diverse and programmers tend to generalize from their own few examples.)
For example, Compilers and interpreters are inherently mutually recursive, which gives you cyclic dependencies. As far as I can tell, this is the essential reason that Fabrice Bellard's QuickJS has one file that's 70K lines of C. And you can see the same thing if you look at the Zig compiler.
In Oil I "modularize" the cyclic dependencies so you can plug them in and out at runtime (which is actually used in the program), but it has a performance cost.
> Yeah exactly, I think of this as "imperative in the small" and "functional in the large". There's no real cost to local state, but there's a big cost to tracking global state.
I think of it as having to deal with the fact that humans only have so much mental space/short term memory.
The problem with stateful everything is that you can't build a complete understanding of it; there's just too much. However, for short bits of code that don't leak their imperativeness to the outside world, it doesn't matter. You can read the whole function and understand it.
> Yeah exactly, I think of this as "imperative in the small" and "functional in the large". There's no real cost to local state, but there's a big cost to tracking global state.
That's the basis of what I call "faux-mutability", wherein you have an immutable type system, but all updates are expressed as mutations.
In the current docs for a language I'm working on, I give a brief example[1], but in a nutshell, you can transform an expression like so:
let x.a.b := 5
let x := set_rec(x, #a, set_rec(x.a, #b, 5))
It does prohibit[2] making arbitrary graphs, but for the use case I'm targeting this is fine.
(Also, as a prototype for how this can work, I wrote a python module[3] that implements it with the pyrsistent module.)
In general I share your increasing uncertainty, but I think it is safe to say that understanding a program is made much more difficult once one has the possibility that a variable might be modified outside of the scope it is created for. The idiom of using mutable variables to track the current state of affairs in a loop is harmless up to the point where one or more is passed by mutable reference to a subroutine or impure function; at that point, it has, almost literally, fallen down a rabbit-hole wherein almost anything could happen.
To have an honest comparison, don't compare imperative code in an imperative language with functional code in an imperative language. Compare with functional code in a functional language, e.g. ocaml:
let list_min l =
reduce min l
I find this crushingly simple to write and to reason about, much more than the convoluted and inefficient imperative code.
EDIT: for completeness, here's the definition of `reduce` and `min`:
let reduce op l =
match l with
| [] -> invalid_arg "reduce: empty list"
| [x] -> x
| hd::tl -> op (hd) (reduce op tl)
let min a b =
if a < b then a else b
While I agree with the sentiment with comparing apples to apples, I happened to notice this can be expressed nearly as elegantly in CoffeeScript:
list_min = (l) -> reduce min, l
With the definitions being:
min = (a, b) -> if a < b then a else b
reduce = (op, l) => switch
when l.length is 0 then throw "reduce: empty list"
when l.length is 1 then l[0]
else reduce op, [(op l[0], l[1]), l[2..]].flat()
reduce() used to be in the builtins in python 2.x. It was removed due to low usage. Keeping the builtins list tiny is a core principle of the language.
> So now reduce(). This is actually the one I've always hated most, because, apart from a few examples involving + or *, almost every time I see a reduce() call with a non-trivial function argument, I need to grab pen and paper to diagram what's actually being fed into that function before I understand what the reduce() is supposed to do. So in my mind, the applicability of reduce() is pretty much limited to associative operators, and in all other cases it's better to write out the accumulation loop explicitly.
Probably low usage because it sort of relies on lambdas (not exactly, you can define one-off functions, but most people don’t like to) and python lambdas are terrible.
What is inefficient about the for loop? It does the same amount of comparisons, the same amount of list accesses, and the same amount of assignments to temporaries.
I think the OP is referring to the imperative version using recursion as inefficient. It isn't tail-recursive, so the stack will grow to infinity, even though we only need a constant amount of memory (plus the memory to store the list) to calculate the result. Most likely, they will cause the program to crash, when invoked on moderately big input. Most implementations of "reduce" are tail-recursive (and if they're not, that's a bug), so they're more efficient.
Firstly, there's a nuance here that readability is heavily dependent upon the language. A language where recursion is the recommended approach to these sorts of problems will have far better syntax for doing so, such as in Haskell.
Secondly, I think there's something to be said for familiarity. I think looping is second nature to most of us not because it's superior or more intuitive, but because traditionally this is one of the first things we're all taught. If functional programming were the norm and people were taught recursion early on instead I think your notion of simplicity would differ.
I've been teaching a little bit of programming to a beginner lately, and they've often found functional approaches to problems easier to grasp than their imperative equivalents because they're more mathematical. It's like an expression of something they already know versus looping, mutability, et al which are new concepts entirely.
Donald Knuth has the opposite view: he thinks recursion is more fundamental. Funnily, he uses an example much like yours.
> On the other hand, recursion is quite fundamental. It is not inherently a high-level concept, suitable only for grownups but not for children. Most people actually grew up with an implicit understanding of rudimentary recursion long before they understood iteration—that is, before they understood how to carry out a loop of instructions. Given a list of tasks to do, the simplest mode of operation is a recursive approach that charges blindly ahead: […]
> It's only after we've gained experience with such an almost mindless method that we acquire a more global view of the process:
> Do Jobs = Do each job on the list. (2)
> […]
> Do a_k for 1 ≤ k ≤ n. (5)
> All computer programmers have in fact progressed from stage (1) to these later stages rather early in our lives, because of an inner desire to “see through” the entire chain of consequences that result from primitive actions.
> Furthermore, once we reached these later stages, we entirely forgot that they were actually elaborations of the recursive procedure in (1). There was no point in narrowing our perspective to the simple-minded form. The vast majority of recursive situations that faced us as children fell into very simple patterns that could readily be “seen through” and understood as a unit. Thus we came to understand iteration as an elementary idea.
> It was only later, when faced with difficult problems whose recursive structure cannot be visualized in straightforward terms such as operations on arrays of elements, that we re-learned the importance of recursion. Therefore we now tend to regard recursion as a high-level concept, although it is really fundamental.
Possibly these views of his are influenced by his early background in programming in assembly/machine language, where it takes some sophistication to translate recursive ideas into code (maintaining a stack etc), but it's an interesting point of view worth some consideration. This is from his draft of TAOCP Chapter 8 ("Recursion"), and is preceded by the following paragraph:
> High-level languages for computing—which themselves are de ned recursively, because algebraic formulas are built up from algebraic formulas—allow programmers to pretend that recursion is real, that a computer is somehow manufactured from recursive components. But programs that invoke themselves are actually implemented by means of a stack structure behind the scenes. A good programmer is able to understand such algorithms by viewing them simultaneously at a high level and at the machine level, and at many levels in between, thereby perceiving what a real computer can actually do well.
Honestly I'm going to disagree. Yes, when planning the task, I think about it as "I have to do this 100 times". But when I'm actually performing the task, I think "Ok, I have to get this stake in the ground, then proceed w/ the rest of my giant pile of stakes."
On the flipside, I have a lot of mathematical training, so maybe this is an uncommon perspective.
From a perspective of what we do in real life, I think looping and recursion are the same thing. Pound 100 fence posts into the ground is either "do this, then loop back and do it again until some stop point" (iterative) or "the base case is no posts left where you stop, otherwise pound the current posts into the ground" recursive.
Recursive has the advantage that when you use the tools for it, recursive is easier to read. If I see e.g. a map, I know we're converting a collection of things to some other things without restriction. With a look, I just have to read through it to see what it's doing.
> Looping has a huge advantage in terms of how we do things in real life.
Anthropomorphism is the bane of our craft. Our untrained intuitions don't really matter.
> Recursion is much more of a mathematical concept that we learn about long after preschool
Programming is applied mathematics. Different from the kind of maths you learn at school of course, and often even more rigorous.
I personally have no qualms about requiring some mathematical proficiency in programming. Makes you much more capable at a number of applications later on.
I didn't downvote your comment but your statement is a very misleading idea. Yes, the study of Computer Science is a discipline of mathematics but common programming done by most devs is not applied mathematics.
Sure, if we really wanted to, we could say baseball is "applied calculus" because when an outfielder chases after a fly ball to intercept it, he's tracking an inverted parabola... and cooking is "applied physics" because of thermodynamics ... but insisting on that is just being pedantic and academic. People do not need calculus and physics classroom training to play baseball and cook food.
> Sure, if we really wanted to, we could say baseball is "applied calculus" because when an outfielder chases after a fly ball to intercept it, he's tracking an inverted parabola... and cooking is "applied physics" because of thermodynamics ... but insisting on that is just being pedantic and academic. People do not need calculus and physics classroom training to play baseball and cook food.
No, we can't, because baseball and cooking aren't formal symbol manipulation, but both math and programming are. That is why all programming is applied mathematics, because it's all manipulating symbols in compliance with a set of formal rules.
Observably, many programmers manage to achieve considerable success without much or any mathematical sophistication. This is because the market places relatively little value on correctness, which is what math helps with, and far greater value on pleasantness, which doesn't require mathematical sophistication at all.
Plenty of people learn how to program without learning the requisite math first. I wrote my first program when I was 8 years old, long before I learned even algebra. I think it is still the case that most people learn how to program before they even know what the word recursion means.
Do you think, in the future, programmers will be mathematicians in the same way that the blacksmiths of centuries ago are now chemical and material engineers in steel plants?
Do you think this is the Bronze Age of artisinal craft, poised to be replaced by the dawn of brutally precise mechanized Haskell?
Humans are efficient, blacksmiths actually didn't become chemical and material engineers, my uncle spent his career working at an aluminum plant being useful without being an engineer. Many people will obtain just the necessary amount of knowledge and skill needed to accomplish their goals, which doesn't bode well for precise mechanized Haskell.
I think that's a stretch. Programming is the creation and/or maintenance of software based solutions. Familiarity with the problem domain that needs to be solved involves keeping track of details that in many cases have little to do with mathematical proficiency and much more necessarily to do with bureaucracy.
You need a certain kind of curiosity and general problem solving ability to get any further than mid level individual contributor that allows you to see around corners in terms of how large scale human socioeconomic systems function and think strategically. That's not to say that mathematical proficiency isn't indirectly useful -- I do think it's worthwhile in that it teaches a mind how to think in a structured manner and solve problems in a structured manner, and that process is useful and transferrable. But it only transfers so far. There are many challenges you face developing proficiency writing software that you cannot be prepared for in any other way than by using, building and studying software.
I have a huge problem with requiring mathematical proficiency in programming. It's sets an unreasonable barrier to entry.
Thousands of every day apps and services work just fine without anything more than simple arithmetic. 3 or 4 of the top 5 websites required no math to get started.
Spreading the idea that you need to know math before learning to program is elitist and counter productive IMO.
Maybe that's not such a bad thing? When a big chunk of our world runs on computers, maybe it's not such a bad thing to have standards and take things seriously, like it is done in every single other engineering profession.
So in order to post a youtube video you would need to take a camera operator course, study the history of movies and pass several advanced english courses?
The term professional programmer means the programmer is getting paid that's all. You want to put a barrier up? Are you worried about lives being lost? Professional programmers don't decide what to program that comes from the project owner. They translate human requirements to computers.
The people who decide what programmers write are defined by rules governing their project. If it's a health project laws around privacy restrict what the project owner can do.
So we don't allow kids to learn how to program until they take a lot of requisite math first? I was planning on teaching my kid some programming when he turned 5 or so, but should I hold off until he is 15 because obviously he isn't going to know all of that math before hand?
I believe that programming is a skill, not a profession. You can know how to program without being a professional programmer.
> You can know how to program without being a professional programmer.
Of course you can. You just… won't be a professional, and won't be held against professional standards (minimum output & quality, that kind of stuff). That's okay. But if you're going to get paid for it, you ought to be better than a random self taught amateur.
Though I suspect we aren't, in fact, much better than the average self taught amateur. That would be an indication that we still have progress to do.
Kids can learn how to build bridges out of legos and erector sets before they learn math and (intro to?) materials science and a host of other things. But we don't let them be civil engineers until they learn the basics of these things. It's entirely possible to learn about and "play with" something without the things that are considered prerequisites for being a professional at it.
Again, programming is not a profession. You might have a point with being a professional programmer (although a lot of programmers do useful things for money without much math), but programming is a skill that can be learned without a deep understanding of math, and often programming acts as a better lead into math rather than vice versa.
> often programming acts as a better lead into math rather than vice versa.
I suspect this is because programming is actually even more rigorous than maths. When you do maths, you can gloss over details, and sometimes delude yourself into thinking false things (that very same thing happened on my last HN submission: I failed to notice a data dependency in EdDSA, and thought an attack were possible, when in fact it wasn't).
Programming uses an external cognitive engine (the computer), that is faithful, exact, and ruthless. Your program has to work. And when it doesn't, you're forced to revisit your assumptions (as I was forced to revisit mine when I actually tried to implement that attack and failed miserably).
Neither is designing or building scale model bridges. But the minute you put a bridge or software project into a situation where many people depend on it and it can cause serious damage, it tends to become one. And that is when we would start applying stricter standards.
Sure, but this just brings up the fact that not all programming is the same. Some people are building small programs that don't need stricter standards, some people are building large ones that do. We just happen to call lots of activities that involve writing code programming, but they are fundamentally different.
What I was going to say. Yes little kids can learn to program, but I think 10 year old me and his shitty programs in Turbo Pascal aren't the standard we should be measuring professionals by.
”I have a huge problem with requiring mathematical proficiency in programming. It's sets an unreasonable barrier to entry.”
Whether that follows depends on how much and what kind of proficiency we require. We require programmers to be able to read and write, too, but we don’t require them to be excellent orators or literary writers.
I do think requiring some proficiency is OK. Basic arithmetic, for example, definitely is ‘in’. A bit of ability to think logically, too. That doesn’t mean all programmers have to know what a group or a ODE is.
> I have a huge problem with requiring mathematical proficiency in programming.
A program is a formal system whose overall structure is mostly a directed acyclic graph. Most good practices are about shaping this graph (we try to make it sparser overall, though we do tolerate isolated dense sub-graphs). If you know how to organise your programs, you've just demonstrated some proficiency with such graphs, even if you don't realise it.
Maths isn't a way to keep people out. It's a way to get them in. And remember: what we do in high school remains markedly different from what we do in programming. Calculus would be the worst possible introduction to programming. You want discrete maths, graphs, boolean algebra, group theory…
Tell that to the 6 yr old using Scratch. "Hey! Stop that fun stuff with shapes and animation an games and go study math for X years. When you're done maybe I'll let you program".
Are we talking about kids playing with toys, or professional engineers building serious machinery? I credit playing with Cuisenaire rods as a child for strengthening my mathematical intuition, but I wouldn't build my house out of them, eh?
In any event, I think it's possible to have your cake and eat it too. See http://iconicmath.com/ I think we can make mathematical toys.
You have completely ignored the most important parts of that graph, which are the inputs and outputs at its boundaries. Recall that the halting problem, Gödelian undecidability and the Church-Turing correspondence place very hard limits on the ability of axiomatic systems to define the truth, even in an abstract sense. But we see this all the time in computer science and programming. Something which takes so long to compute that you can't distinguish between whether it's accomplishing useful work for a given input case or not has a completely different kind of conceptual characteristic than "discrete maths, graphs, boolean algebra, group theory..." There's less universality. More details. More arbitrary, capricious conditions that you nevertheless have to not just work around, but determine how to build resilient systems in spite of.
It is almost cruel to taunt practitioners working around the hard, messy, ugly constraints of reality with the beautiful, elegant, and noble idea of not just conceptual mathematics, but the ability to immanentize it. But, this does little to solve the inherent messiness of the world that the software interacts with, and the messy things that people do which affect what it needs to do.
Most of the mess we have in programs is of our own making. Our inability to properly address changing (not complex) requirements.
And sure, the world is messy. But some things aren't worth automating. I've seen a talk about how the guy was writing a program to generate invoices. Turns out invoices are incredibly messy. The previous system was an overly complex brittle pile of code, that didn't quite work. His approach? Solve the common case first, and let human handle the messy bits. He started by something very simple, that could handle 60% of the invoices. Then 90%. Then 95%. Then 99%. The he stopped.
With 99% of the invoices handled, he had a simple, solid system. The messy part was handled by humans, and they had the time to do so because 99% of the grunt work was taken away from them. Plus, they could trust it works because since those invoices were relatively simple, they could be automated reliably. I believe that approach can be generalised. As Mike Acton said: "solve the common case first".
That I believe would work to "solve the inherent messiness of the world". Automate what you can, let humans deal with the rest. Or don't automate at all, just give tools & tricks so humans can work faster.
Alternatively, we could adapt around computers. Before electricity, factories used to have a giant engine that powered everything through mechanical transmission. Wen electricity first came along, we did the same thing. But it turns out electricity is much easier to distribute at a small scale. So factories adapted, and instead of having a big engine at the centre, they started to have lots of small engines everywhere, close to where they were needed. I believe computers are similar: we started using them as glorified paper, but as we understand what they can do, we employ them in more efficient ways. But the interface of a computer (it can do anything!) is much more complex than that of an engine (it can rotate!). I believe we haven't found how to best make use of them just yet.
I really like your point about solving the common cases, but what you're getting at there is exactly what is the challenging part, not the mathematical part of it. How do you figure out what is the most important 60%, then 90%, then 95%, then 99%? How do you develop the judgment to know when 99% is good enough, or 95%, or 90%, or 60%? How does mathematics help you out with that?
My point is that this judgment is the messy and valuable part. And to your point around the end, that you believe we haven't found how to best make use of them just yet -- I agree with that too, and that's why I think the work of writing software, or best practices, or sound theory is not fully established. To build good product does fundamentally require a pioneer spirit that can make compromises and negotiations and arrive at that sweet spot that's not quite 100% but high enough to be "good enough".
On the contrary, we have no choice but to use our intutions, at whatever level of training they are at, all the time. So it matters a lot. If A is easier than B iff we learn to think differently, but learning to think differently is harder than just doing B, then A isn't actually easier than B.
Becoming seriously proficient at anything seriously alters the way you think about it, no matter the field. For instance, I play the Cello. Lately, I noticed I only made progress when I understood something, or changed a habit, or let go of some subtle, but ultimately far reaching assumption.
I played the Witness. There's a time based challenge at some point, that I could only beat when I changed the way I thought about those puzzle just so I could go through them faster.
I learned to touch type. To do that, I stopped thinking visually, and instead think kinaesthetically. Then I developed some kind of intuition, where I think a word, and the letters just flow through my fingers. I don't really think at the letter level any more. Neither does anyone proficient with a keyboard. (50 WPM and up).
Our untrained intuitions don't really matter. Seriously learning anything trains us out of them. Programming is no different.
It's also probably the case that readability is not a primary concern when implementing things like "min" that will most likely be in the standard library of a programming language. From my limited experience looking at such source code, there tend to be a surprisingly large about of code for fixing edge cases, esoteric performance problems, etc.
It may be instructive to look at how readable a very naive implementation of a basic function like "min" is, but it probably doesn't actually matter that much in practice, because you'll be using what the standard library offers (and its implementation is probably much less straightforward than you might think).
As someone who learnt to program in Scheme, this was true for me, did so much Scheme that when doing some C or JS I had to pause for moment and think harder when writing imperative loops.
Recursion tends to strip context. That is one of the features, and one of the drawbacks. All problems are either a base case, or the general case.
If you are attempting to debug logic, it often helps to have all the context. To do that in recursion, you have to travel up and down the stack, examining local contexts one by one.
I'm not sure what you mean here. The only thing I can come up with is you're talking about writing specific code recursively but when doing functional programming we usually just use the applicable recursive function (e.g. map, filter, reduce) in which case we have better context than with a loop because a loop has a lot of irrelevant implementation details cluttering up the context.
This is a great example of how people who use ad-hoc languages can get distorted views of how recursion should be denoted. No functional programmer in the universe would write something that looks like your recursive example.
Here are two recursive ways to write a min function:
Idiomatic and structured, using (Maybe . Min) monoid:
min = foldMap (Just . Min)
Incidentally, the above works on any data structure where this operation makes sense, not just lists, which is nice.
Unstructured, ad-hoc
minimum [] = Nothing
minimum (x:xs) = case minimum xs of Nothing -> Just x; Just y -> Just (min x y)
This latter doesn’t even rely on anything unique to functional programming ecosystems (like folds or principled algebraic classes).
#!/usr/bin/env python3
from functools import reduce
from typing import List, Optional
def min_pair(min: Optional[int], val: Optional[int]) -> Optional[int]:
if min is None or val < min:
return val
else
return min
def min(foo: List[int]) -> Optional[int]:
return reduce(min_pair, foo)
It doesn't bother you that you're checking `min is None` even after you know it can't be (i.e., after one loop iteration)? Python doesn't make it pretty to get around this issue:
def min(foo):
it = iter(foo)
try:
m = next(it)
except StopIteration:
return None
for val in it:
if val < m:
m = val
return m
You could switch the order they're compared and due to short-circuiting the second eval would only ever take place once. Or initialize min to the zeroth item in the array.
I would have written two functions instead where one takes a default argument and the other returns None if the list is empty.
In pseudo-Haskell notation:
min1 : Int -> List Int -> Int
min1 def Nil = def
min1 def (Cons x xs) = min1 (def if def <= x else x) xs
min : List Int -> Maybe Int
min Nil = None
min (Cons x xs) = min1 x xs
I generally prefer expression-oriented programming like this, but it's hard to pass up the efficiency improvements of arrays and hashmaps. The purely functional list given in the article is actually an order of magnitude less efficient to iterate on modern caching pipelined processors.
What's the best way to have your expression-oriented programming and use cache-friendly data structures? How do Haskell et al handle this?
Local impurity. The key insight is that mutation/impurity isn't necessarily bad in and of itself. The important thing is that it is guaranteed to not cross API boundaries -- this prevents abstractions from leaking at least one way, and lets you reason about the code as if it were pure. (And in fact, from the outside it is.)
This allows mutation to remain the performance optimisation it is, without allowing it to seep into the design of systems, which is where it causes badness.
As far as I know, Haskell is one of the few languages (if not the only one) that supports local mutation that is guaranteed to not be visible in any way to the caller.
In an ideal world, Haskell would have a uniqueness type ala Clean or Idris which would allow for ‘in-place’ mutations of array and retain referential transparency.
I like this style in other languages, but unfortunately it's really hard to write this style in C, most of his examples with functions would be pretty inefficient, or at least have somewhat confusing lifetimes. For instance the functions returning a string on the stack which at a glance seem inefficient. I think modern C++ compilers might be able to use move semantics for the examples returning a string, but im not entirely sure and I personally don't like relying on compiler optimisations
This is great advice for many types of programs; for example, an application to be run in a web browser, or an interpreter. But there is a large class of programs for which “avoiding the assignment statement” does not apply. The author knows this, and mentions it in the “When you can't help it”
section:
“Sometimes, you just can't avoid the assignment statement or other side effects. Maybe you need so much efficiency that you have to mutate state to optimise your program”.
This class of programs includes all high performance numerical code. These programs compute by declaring large multidimensional arrays (usually distributed among multiple compute nodes), reading values from array elements, doing arithmetic on those values, and writing the results into array elements. These elements have fixed memory addresses, so the computation consists in changing the values stored in fixed memory locations. Efficiency comes from minimizing the movement of data and parallelizing as much as possible. It’s what Rich Hickey would call computing with places, not with values.
It’s important to understand where compiler optimization opportunities come from. They’re not magic; they’re determined by the information the compiler has available to it—information about constraints you’ve imposed on it, and information about guarantees it can make.
Using separate variables instead of reusing the same variable will sometimes actually increase the optimizations that compilers can do. Why? Because the version where you overwrite the variable is introducing additional constraints (e.g. keeping X1 and X2 in the very same stack slot called X) that have costs, but whose semantics you aren’t necessarily (or even usually!) relying upon.
For example: you know all that spare register spill space in the x64 calling convention that you’re allocating either way, and which deallocates as a block on function exit? Can’t make efficient use of that if you’re telling the compiler it has to keep both of your pointers successively in the same memory address!
On the other hand, the opposite is also true: sometimes overwriting a variable will free the compiler from a constraint it was under. This mostly comes about as the result of X1 and X2 both holding a shared or overlapping pointer, introducing aliasing (as often happens in the pure-functional data structures OP advocates for.) By overwriting X1 with X2 (or, equivalently, by freeing X1 as soon as you’re done with it!) you can allow the compiler to be more confident that nothing will access the shared pointer through X1.Y any more, only through X2.Y—which may allow e.g. smart pointer classes to elide a synchronization point.
(Note that this assumes a language with a model where a variable directly relates to memory, such that assigning to the same variable implies assigning to the same memory. This is true in most low-level languages, but not in functional languages; in e.g. Elixir, a second assignment to the same variable is actually creating a second variable with a mangled name, and leaving it to the compiler’s lifetime analysis to figure out that the first one is dead after that point.)
I don't think I really understand the question, but please bear with me.
Indeed both code snippets are the same computation.
The first snippet is SSA, the second is not. Notice that doing, for instance, constant propagation on the first snippet is straightforward:
int a = 5
int b = 2 * 5
You can do this because SSA form guarantees that the value of a is 5.
In non-SSA code, there is no such guarantee: you need to check the "history" of each variable before replacing it with a value.
I'm not totally convinced that SSA "increases the optimizations that compilers can do". However, it definitely makes optimization algorithms easier.
I guess my point was that the optimizations available are the same (between those two snippets of code) if you end up in SSA form. Thinking about it now, I don't know what optimizations would be done before going to SSA and how they would be affected.
Yeah, but in this context you have to hope the compiler realizes that you have self-imposed a static-only data model in a language that otherwise supports dynamic assignment.
That's what I'm saying—you don't have to "hope." You can look at what information you've provided to the compiler through your code, and deduce from that, what optimizations are possible to make on that code.
From there, you just have to know whether the compiler you're using supports those optimizations. If it does, and your code should have them, but it doesn't end up having them—well, that's a bug in your compiler, and you should report it as such!
If there were a clearly-more-efficient query plan possible to generate for a query of a particular data model in an RDBMS, and your RDBMS failed to come up with said query plan, you'd consider that a bug in your RDBMS, no? Well, same thing here.
Instead of changing the content of a variable, you can just declare a new one. By avoiding assignment, you can guarantee that your variables won't change. You can guarantee that the current value of x is the one it has been initialised with: init().
Hard to see the upside there. By adding another variable (y in the example), you've added another degree of freedom to your program state, arguably for no good reason. Now there's something else to go wrong that wasn't there before.
> The reason why the "wrong" way is used at all is because many old programming languages forced you to declare variables at the beginning of blocks. It was easier for compilers. It's no longer an issue, however. Not even in C.
It's still very much an issue for a certain compiler vendor without full support for C99.
I still have to write code that builds against earlier versions. Code that primarily targets a backwards embedded compiler that only does C++98 but has had usable C99 support since forever.
I wanted to say exactly the same thing. If you're going to these lengths, you might as well bite the bullet and use a language that supports that style of programming.
Is there a difference between this and functional programming? It's odd that this article doesn't mention the entire branch of programming it is talking about.
I believe I didn't want to scare readers away. But more importantly, functional programming is more than just removing the assignment statement. If you take a language and just remove the assignment statement, the language you get isn't functional, it's just crippled.
Functional programming involves other techniques to compensate. Higher order functions are critical, and often used to hide recursion under the rug (see map & reduce). I have a more complete guide to functional programming there: http://loup-vaillant.fr/tutorials/from-imperative-to-functio...
Something interesting that's happened since then: I've taken a job at a Python company, and I've noticed that, compared to JavaScript, assigning intermediate results into local variables seems to be much more idiomatic in Python for some reason. This is doubly surprising since JavaScript at least has the const keyword. I'm not sure yet how I feel about it.
One other anecdote: I personally relax my usage of assignment a lot more when using Rust, because a) it has rich, deep immutability at a type level, and b) its expressions tend to be longer than those in other languages due to all the monads and such.
Sometimes this is not possible or desirable. Libraries like MPFR pretty much demand that you pre-allocate and re-use variables.
Of course in this case despite the mutation there is no assignment statement, as variables are set using output parameters ;)
So in the example of the linked list, how do you add an element to the middle? I actually don't think you can make this work in a conventional sense - you'd copy the whole list and lose all linked-list advantages. Instead, my impression functional programming uses list objects that appear to copy the whole list, are efficient but actually use shared memory and are mutable "behind the scenes". And sure that works but it results in one's code being a few more levels of abstraction away from what's happening with the processor.
It seems that this implementation of a list is more useful when used like a stack. As a general list (with more operations than "pop" and "push"), not so great in terms of performance compared to one that is mutable.
I did like the article and how the author writes so simply. To the author's credit, right below, they do have the section on "When you can't help it", which if you do need insertion like that and performance matters, probably best to use a mutable data structure.
If you want that much to program in a functional style, maybe use a functional language. It will probably be more efficient, compile faster, and be easier to maintain.
“Declare New Variables... I see two possible reasons why one would want to do it the "wrong" way: efficiency, and conciseness.”
Correct me if I’m wrong, but isn’t this plain wrong? You are increasing the memory required for your program to run, and if the data saved to those variables are sufficiently large you can run into memory issues this way.
Kinda funny note, I realized that I forgot to add an assignment statement in my language. Like I just straight up forgot to add it in the grammar. Maybe I'll see how long I can avoid adding it.
I don't understand why someone would write a comment that contributes nothing to the discussion other than calling the post "dumb" with no evidence or context.
Programming with expressions instead of statements is actually a great way to structure things with as little mutable state as possible. It eliminates entire classes of bugs.
Edit: people have posted better version of my code in the comments. Take a look for more pythonic examples.