12 ms·
How to Avoid the Assignment Statement (2010)
- recursive 7y agoHas anyone ever seen a linear-time algorithm to do a histogram without mutation? I mean like `Counter` from python. https://docs.python.org/3.8/library/collections.html#collections.Counter https://docs.python.org/3.8/library/collections.html#collect...
- QuinnWilton 7y agoIt's not exactly the same, but that's pretty comparable to a g-counter CRDT, which is very straightforward to implement in a purely-functional language: https://github.com/QuinnWilton/distsys_training/blob/master/shortener/lib/shortener/g_counter.ex#L1 https://github.com/QuinnWilton/distsys_training/blob/master/...
- whitehouse3 7y agoI think all of this is achievable in Python. I'd be interested in a linter that checks for unnecessary assignment statements.
- ch33zer 7y agoI 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.
- samhh 7y agoFirstly, 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.
- Scarbutt 7y agoAs 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.
- seanmcdirmid 7y agoLooping has a huge advantage in terms of how we do things in real life. We don’t think of “pound 100 fence posts into the ground” recursively. Recursion is much more of a mathematical concept that we learn about long after preschool, while my 3 year old already gets loops.
- jacksnipe 7y agoHonestly 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.
- deleted 7y ago
- m4r35n357 7y agoSometimes 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 ;)
- massysett 7y agoA much shorter version of this page: "Use Haskell."
- js8 7y agoI 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.
- Glavnokoman 7y agoI understand why somebody would take notes when learning the language and having some (mostly dumb) ideas about it. But why make it pubic and even promote... that I do not get.
- wffurr 7y agoI 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.
- wffurr 7y agoI 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?
- jhanschoo 7y agoYou'll have to do it with a compiler, and limit yourself to only certain access patterns, I suppose. To take full advantage of the functional paradigm most settle for logarithmic access with tries.
- kqr 7y agoLocal 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.
- throwaway17_17 7y agoIn 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.
- overgard 7y agoI 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
- kevin_thibedeau 7y ago> 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.
- asveikau 7y agoThe vendor you are likely referring to fixed mixed declarations and code in their 2015 release.
- kevin_thibedeau 7y agoI 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.
- leephillips 7y agoThis 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.
- joe_the_user 7y agoSo 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.
- mangodrunk 7y agoIt 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.
- _hardwaregeek 7y agoKinda 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.
- crystaln 7y agoSo you wrote a functional language... keep it that way.
- brundolf 7y agoI wrote a related post a few months back: http://www.brandonsmith.ninja/blog/procedures-functions-data http://www.brandonsmith.ninja/blog/procedures-functions-data 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.
- crystaln 7y agoIs 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.
- loup-vaillant 7y agoIt was 10 years ago, so my memory is a bit fuzzy. 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-functional http://loup-vaillant.fr/tutorials/from-imperative-to-functio...
- jandrese 7y agoDoes anybody else get nervous when the author goes "don't worry about efficiency, the compiler will fix that for you?"
- derefr 7y agoIt’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.)
- lou1306 7y ago> Using separate variables instead of reusing the same variable will sometimes actually increase the optimizations that compilers can do LLVM optimizations, for instance, often need the IR to be in SSA form (static single Assignment).
- CamperBob2 7y agoInstead 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.
- temac 7y agoIf 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.
- icedchocolate 7y ago“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.
- kazinator 7y agoTip o' the hat! http://www.kylheku.com/cgit/txr/tree/eval.c?id=txr-234#n2063 http://www.kylheku.com/cgit/txr/tree/eval.c?id=txr-234#n2063 http://www.kylheku.com/cgit/txr/tree/hash.c?id=txr-234#n901 http://www.kylheku.com/cgit/txr/tree/hash.c?id=txr-234#n901