6 ms·

Not sure if the author will read this, but there is a simple answer to both problems. In functional programming, you typically do not manipulate state directly

by js8 5y ago

Not sure if the author will read this, but there is a simple answer to both problems. In functional programming, you typically do not manipulate state directly, instead you compose functions that manipulate that state, into more complex functions. (In Haskell, for example, this composition is often done through monads.) Eventually, you get a function that represents the whole program. This is somewhat dual to imperative programming, and is kind of a shift of the frame of reference. We could make an analogy with an assembly line in a factory. Imperative programming is like looking standing at the factory floor, every machine (procedure) receives a thing (input), does something with it, and outputs it. Functional programming is like being together with the thing as it is manipulated through the factory, in its own frame of reference. So instead of passing the thing (data) around, you see passing of the machinery that modifies that thing (functions), in the opposite direction.

jayd16 5y ago
That's fine from a philosophical sense, but doesn't it make consecutive reads extremely heavy? You're throwing away the efficiency of in place updates at the language level, no?
- closeparen 5y ago
  This is why Clojure’s big thing is to also, at the language level, emphasize copy-on-write data structures.
  - mumblemumble 5y ago
    But Clojure also has a habit of implementing core functionality that needs to be fast in imperative Java. The thing about copy-on-write is that it's only a good solution when writes are infrequent. My sense is that Clojure largely deals with this by simply not targeting business domains where frequent writes to mutable data structures are particularly necessary. Which hints at my own opinion on how to deal with this Gordian knot: just acknowledge that there is no universally best programming paradigm. Some problems are, as a practical matter, best modeled in an imperative manner. That's fine. And I don't think it should be personally threatening to us fans of functional programming. John Backus openly discussed it in the paper where he originally proposed the paradigm, and I personally prefer, for moral reasons, his suggestion for how to solve it. In a world where everyone's trying to build the best spork, I think I'd rather have one good spoon and one good fork.
    - Sinidir 5y ago
      Creation of new versions of datastructures are done in log32(N) time in clojure. The performance even for frequent updates is fine.
      - deleted 5y ago
        [deleted]
    - closeparen 5y ago
      All programming paradigms are at some level implemented in terms of assembly.
      - harperlee 5y ago
        Yes, but paradigms can be different enough that an intelligent compiler fails to find the same optimal assembly for two solutions for the same problem. Thus the paradigm in which you express the solution matters. Otherwise we would just need to express the problem, and a trivial solution, and the compiler would work the rest (the idea behind declarative programming!)
  - lupire 5y ago
    Clojure's other big thing is "transient" local mutable state within a function, like Haskell's ST (State Transformer) monad (the more efficient alternative to the pure immutable state monad)
- saeranv 5y ago
  Yes, although I suppose even in languages where this isn't mitigated (i.e. Clojure example below), you can offset that inefficiency with the parallelism enabled by functional programming.
- lupire 5y ago
  "in-place updates" are handled by the compiler and garbage collector, using liveness analysis, not by the programmer managing memory explicitly.
- throwaway81523 5y ago
  > That's fine from a philosophical sense, but doesn't it make consecutive reads extremely heavy? You're throwing away the efficiency of in place updates at the language level, no? You use special data structures to deal with that. There's a great book about them, "Purely Functional Data Structures", by Jeff Okasaki. You generally don't get O(1) update like for traditional arrays, but you can usually get O(log n), like you would get for a database table with B-tree indexes.
  - zrkrlc 5y ago
    Minor nitpick, but it's actually *Chris Okasaki
zodiac 5y ago
Using the interpreter example in the article, would it be accurate to say that the author's inefficient "each instruction copies the existing bytes into a new array, change the byte of interest, return this new byte array, and abandon the old array (which would eventually be garbage-collected)" is "manipulating the state directly"?
- vnorilo 5y ago
  Yes, and also not a data structure that is suitable for the task. If you want to keep every version of the buffer as a value (which has nice properties like versioning) you would need a data structure that shares most of its structure with the previous versions. Like a persistent radix-n tree. Slower than mutable buffer for sure, but not pathological.
  - zodiac 5y ago
    Got it. I'm familiar with persistent data structures but I was more curious as to the "Haskell approach" of doing the same problem (which, I assume, doesn't use persistent data structures per se). Follow-up question: if you wanted to implement the interpreter (as in the author's article) in idiomatic Haskell, would using the State monad be one solution? (I assume that's what you meant by "compose functions that manipulate that state"). Then, if you translated that Haskell directly into Racket (something like: use the exact same functions, just delete the type annotations), what would be the run-time of the solution? (Not a trick question, I really don't know the answers. I've "understood" how the State, Reader, Writer work in the sense of reading the code, checking the types, and confirming that they do what they claim, but didn't think about how a compiler would compile them before)
    - vnorilo 5y ago
      Not sure there's any benefit in using the state monad for an interpreter. My first thought is to model a cycle of the interpreter as a function of old state into new state. I guess the state monad could be used to thread the state dataflow through the interpreter, but it would not make the copy-big-buffer any more efficient. Code using the state monad is still pure and uses immutable data. Now if you have to use a mutable buffer (only one fits in memory?) then you could use techniques like the IO monad to deal with it. Disclaimer: Am more Clojure than Haskell person.
ChadNauseam 5y ago
> In functional programming, you typically do not manipulate state directly, instead you compose functions that manipulate that state, into more complex functions. (In Haskell, for example, this composition is often done through monads.) Eventually, you get a function that represents the whole program. A bit more detail. In Haskell this is implemented very elegantly with list fusion. If you write map (\x -> x+1) mylist You'll map over a list and add one to every element. this allocates a whole new list where all the elements are increased by one [0]. Now let's say we take the output of that map and map over it again, but this time we multiply every element by two: map (\x -> x*2) (map (+1) mylist) Naively implemented that would copy allocate two lists, one where all the numbers are incremented and another where all the incremented numbers are multiplied by two. Any good dev will know that's performance poison. So the Haskell compiler implements "list fusion" – it sees that you don't use the intermediate list for anything, and rewrites your code so it's equivalent (in semantics and performance) to: map (\x -> (x+1) * 2) mylist) (For the compiler devs in here, this optimization is commonly known as deforestation.) This leads to huge speedups in many cases. But there's a problem. If elsewhere you use the result of `map (\x -> x+1) mylist` for anything besides mapping over it exactly once, this optimization is impossible! So list fusion has a reputation for being fragile – the compiler has to know with 100% certainty that you aren't going to use the list for anything else, and sometimes innocent-seeming changes (like moving the intermediate map into another module) can break it. The solution the Haskell community finds promising is to be able to give a tag to value, like a type only not quite, that says "I promise to use this value exactly once". If you use it twice or zero times, the compiler will yell at you. The compiler is still on the hook for doing the analysis of what's used once and what's used multiple times, but now the programmer and the compiler can be guaranteed to be on the same page. As for the other issue mentioned in the original post, of modifying a subelement of a tree: this is a well-known problem and there are many solutions. If the tree is only used once, the same optimization as list fusion can be applied to mutate the list in place (although the "you must use the value only once" restriction doesn't help quite as much as you'd think it would). The more common solution, that doesn't depend on compiler optimization at all, is to use a data structure that supports this efficiently. For example, if you have a tree and you want to change one leaf on the tree, the only thing you really need to copy is the part of the tree that's actually different now - for the unchanged branches, the new tree just has a pointer to branches of the old tree, so they can be (and are) reused without copying. That's why it's very common to see maps implemented in functional languages using trees, instead of hashmaps. With a hashmap, it's much harder to get around the need to copy the whole thing when you just want to change one part. [0]: Well, it might do that that once it gets around to it, laziness etc., but let's ignore that for now.
voxl 5y ago
Ah yes, monadic programming, liked by no one but championed by those who probably have never really had to do it. OCaml does state without monads the way it does for a reason, because working with monads is a massive headache.
- pyrale 5y ago
  You work with monads all day long, you just don't think about them as such. There is no such thing as "monadic programing", even in Haskell. The thing making haskellers harp about monads is that the std lib went a bit far in making sure that every fitting data structure implements the monad interface, which includes IO.

by js8 5y ago

jayd16 5y ago

That's fine from a philosophical sense, but doesn't it make consecutive reads extremely heavy? You're throwing away the efficiency of in place updates at the language level, no?

closeparen 5y ago
This is why Clojure’s big thing is to also, at the language level, emphasize copy-on-write data structures.
- mumblemumble 5y ago
  But Clojure also has a habit of implementing core functionality that needs to be fast in imperative Java. The thing about copy-on-write is that it's only a good solution when writes are infrequent. My sense is that Clojure largely deals with this by simply not targeting business domains where frequent writes to mutable data structures are particularly necessary. Which hints at my own opinion on how to deal with this Gordian knot: just acknowledge that there is no universally best programming paradigm. Some problems are, as a practical matter, best modeled in an imperative manner. That's fine. And I don't think it should be personally threatening to us fans of functional programming. John Backus openly discussed it in the paper where he originally proposed the paradigm, and I personally prefer, for moral reasons, his suggestion for how to solve it. In a world where everyone's trying to build the best spork, I think I'd rather have one good spoon and one good fork.
  - Sinidir 5y ago
    Creation of new versions of datastructures are done in log32(N) time in clojure. The performance even for frequent updates is fine.
    - deleted 5y ago
      [deleted]
  - closeparen 5y ago
    All programming paradigms are at some level implemented in terms of assembly.
    - harperlee 5y ago
      Yes, but paradigms can be different enough that an intelligent compiler fails to find the same optimal assembly for two solutions for the same problem. Thus the paradigm in which you express the solution matters. Otherwise we would just need to express the problem, and a trivial solution, and the compiler would work the rest (the idea behind declarative programming!)
- lupire 5y ago
  Clojure's other big thing is "transient" local mutable state within a function, like Haskell's ST (State Transformer) monad (the more efficient alternative to the pure immutable state monad)
saeranv 5y ago
Yes, although I suppose even in languages where this isn't mitigated (i.e. Clojure example below), you can offset that inefficiency with the parallelism enabled by functional programming.
lupire 5y ago
"in-place updates" are handled by the compiler and garbage collector, using liveness analysis, not by the programmer managing memory explicitly.
throwaway81523 5y ago
> That's fine from a philosophical sense, but doesn't it make consecutive reads extremely heavy? You're throwing away the efficiency of in place updates at the language level, no? You use special data structures to deal with that. There's a great book about them, "Purely Functional Data Structures", by Jeff Okasaki. You generally don't get O(1) update like for traditional arrays, but you can usually get O(log n), like you would get for a database table with B-tree indexes.
- zrkrlc 5y ago
  Minor nitpick, but it's actually *Chris Okasaki

zodiac 5y ago

Using the interpreter example in the article, would it be accurate to say that the author's inefficient "each instruction copies the existing bytes into a new array, change the byte of interest, return this new byte array, and abandon the old array (which would eventually be garbage-collected)" is "manipulating the state directly"?

vnorilo 5y ago
Yes, and also not a data structure that is suitable for the task. If you want to keep every version of the buffer as a value (which has nice properties like versioning) you would need a data structure that shares most of its structure with the previous versions. Like a persistent radix-n tree. Slower than mutable buffer for sure, but not pathological.
- zodiac 5y ago
  Got it. I'm familiar with persistent data structures but I was more curious as to the "Haskell approach" of doing the same problem (which, I assume, doesn't use persistent data structures per se). Follow-up question: if you wanted to implement the interpreter (as in the author's article) in idiomatic Haskell, would using the State monad be one solution? (I assume that's what you meant by "compose functions that manipulate that state"). Then, if you translated that Haskell directly into Racket (something like: use the exact same functions, just delete the type annotations), what would be the run-time of the solution? (Not a trick question, I really don't know the answers. I've "understood" how the State, Reader, Writer work in the sense of reading the code, checking the types, and confirming that they do what they claim, but didn't think about how a compiler would compile them before)
  - vnorilo 5y ago
    Not sure there's any benefit in using the state monad for an interpreter. My first thought is to model a cycle of the interpreter as a function of old state into new state. I guess the state monad could be used to thread the state dataflow through the interpreter, but it would not make the copy-big-buffer any more efficient. Code using the state monad is still pure and uses immutable data. Now if you have to use a mutable buffer (only one fits in memory?) then you could use techniques like the IO monad to deal with it. Disclaimer: Am more Clojure than Haskell person.

ChadNauseam 5y ago

> In functional programming, you typically do not manipulate state directly, instead you compose functions that manipulate that state, into more complex functions. (In Haskell, for example, this composition is often done through monads.) Eventually, you get a function that represents the whole program. A bit more detail. In Haskell this is implemented very elegantly with list fusion. If you write map (\x -> x+1) mylist You'll map over a list and add one to every element. this allocates a whole new list where all the elements are increased by one [0]. Now let's say we take the output of that map and map over it again, but this time we multiply every element by two: map (\x -> x*2) (map (+1) mylist) Naively implemented that would copy allocate two lists, one where all the numbers are incremented and another where all the incremented numbers are multiplied by two. Any good dev will know that's performance poison. So the Haskell compiler implements "list fusion" – it sees that you don't use the intermediate list for anything, and rewrites your code so it's equivalent (in semantics and performance) to: map (\x -> (x+1) * 2) mylist) (For the compiler devs in here, this optimization is commonly known as deforestation.) This leads to huge speedups in many cases. But there's a problem. If elsewhere you use the result of `map (\x -> x+1) mylist` for anything besides mapping over it exactly once, this optimization is impossible! So list fusion has a reputation for being fragile – the compiler has to know with 100% certainty that you aren't going to use the list for anything else, and sometimes innocent-seeming changes (like moving the intermediate map into another module) can break it. The solution the Haskell community finds promising is to be able to give a tag to value, like a type only not quite, that says "I promise to use this value exactly once". If you use it twice or zero times, the compiler will yell at you. The compiler is still on the hook for doing the analysis of what's used once and what's used multiple times, but now the programmer and the compiler can be guaranteed to be on the same page. As for the other issue mentioned in the original post, of modifying a subelement of a tree: this is a well-known problem and there are many solutions. If the tree is only used once, the same optimization as list fusion can be applied to mutate the list in place (although the "you must use the value only once" restriction doesn't help quite as much as you'd think it would). The more common solution, that doesn't depend on compiler optimization at all, is to use a data structure that supports this efficiently. For example, if you have a tree and you want to change one leaf on the tree, the only thing you really need to copy is the part of the tree that's actually different now - for the unchanged branches, the new tree just has a pointer to branches of the old tree, so they can be (and are) reused without copying. That's why it's very common to see maps implemented in functional languages using trees, instead of hashmaps. With a hashmap, it's much harder to get around the need to copy the whole thing when you just want to change one part. [0]: Well, it might do that that once it gets around to it, laziness etc., but let's ignore that for now.

voxl 5y ago

Ah yes, monadic programming, liked by no one but championed by those who probably have never really had to do it. OCaml does state without monads the way it does for a reason, because working with monads is a massive headache.

pyrale 5y ago
You work with monads all day long, you just don't think about them as such. There is no such thing as "monadic programing", even in Haskell. The thing making haskellers harp about monads is that the std lib went a bit far in making sure that every fitting data structure implements the monad interface, which includes IO.