[js8]

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]

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?

[throwaway81523]

> 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]

Minor nitpick, but it's actually *Chris Okasaki

[closeparen]

This is why Clojure’s big thing is to also, at the language level, emphasize copy-on-write data structures.

[mumblemumble]

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]

Creation of new versions of datastructures are done in log32(N) time in clojure. The performance even for frequent updates is fine.

[closeparen]

All programming paradigms are at some level implemented in terms of assembly.

[harperlee]

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]

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)

[lupire]

"in-place updates" are handled by the compiler and garbage collector, using liveness analysis, not by the programmer managing memory explicitly.

[saeranv]

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.

[zodiac]

Using the interpreter example in the article, would it be accurate to say that the author's inefficient "each instruc­tion 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 even­tu­ally be garbage-collected)" is "manipulating the state directly"?

[vnorilo]

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]

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)

[dllthomas]

Translating naively, in Haskell I might use https://hackage.haskell.org/package/containers-0.6.5.1/docs/..., which does use sharing to reduce copying.

[tromp]

A simple Brankfuck interpreter in Haskell using state monads may be found at https://tromp.github.io/cl/Binary_lambda_calculus.html#Brain...

[dllthomas]

Yeah, for something where changes are local like that, using two stacks for your tape makes a lot of sense.

[vnorilo]

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]

Writing efficient interpreters in a functional style is not easy. I write interpreters in OCaml for a living and we had to switch to a mutation-heavy style for performance and memory usage reasons. It can be done though.

When you think about it, any dependently typed language has to have an interpreter inside it, because you can put function applications inside a type and the typechecker will probably need to evaluate the application at some point. The go-to technique is to use Normalization by Evaluation [0], where you convert the AST version of a function in the interpreted language to an actual function in the host language, and piggyback off the host language's (presumably very fast) function application.

[0]: https://en.wikipedia.org/wiki/Normalisation_by_evaluation

[Quekid5]

I suspect you already know this, but other readers might be interested to know that in Haskell you can also use the ST monad which can do local (actual) mutation which is guaranteed to not escape the function's scope.

(Of course you can only access the actual local state and not do I/O or anything like that.)

[vnorilo]

Sure, but there are many kinds of interpreters!

I was involved with one that wasn't really demanding in terms of computation, but was distributed in a way that required a lot of speculation and rollbacks. The functional approach was pretty sweet.

Highest speed bytecode interpreter is actually one of the few loops where I prefer assembly to C, as the instruction mix, branch prediction and even the use of stack can be weird from the PoV of a modern optimizing compiler.

[agumonkey]

Isn't there a way to derive efficient/in-place interpretation from pure total recursive functions ?

reading lisp in small pieces, the author migrates interpreters from naive recursive eval to bytecode. It felt there was an underlying model to extract.

[mbrodersen]

I am also in the compiler/interpreter business. Can you tell me more about what you are working on? It sounds interesting.

[lupire]

No, its not manipulating the state, which is why it is inefficient.

An example of what parent was talking about is instead of looking over a list 10 times calling different functions that build a new result list each time, you compose those inti one big function that visits each element once.

[ChadNauseam]

> 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.

[munificent]

> 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.

I suspect the contortions required to fit your code into that affine type style will likely lead to code that is just as hard to understand and maintain as the equivalent imperative code (though with better static checking, which might be nice).

[ChadNauseam]

It's surprisingly convenient when you get used to it. A very large proportion of values are only used once, so if a function only uses a value once you can mark it as being linear in that argument and get the relevant guarantees for very little mental overhead. You can still pass any value you want to the function, the only restriction is that the function must consume the value exactly once. It's tricky to write performant functional code, but personally I find linearity tagging a small price to pay for salvation (see this article I wrote, posted here: https://news.ycombinator.com/item?id=30762281 ). (Note that GHC currently doesn't use linearity for any performance optimizations, this is just a promising possible route.)

One tidbit you might find interesting. Linear logic requires you use the value exactly once, but if you relax that requirement to "once or zero times" you get affine logic. (Values that don't have the any restriction on how much you can use them are called "exponentials".) With both linear and affine logic, you can pass an exponential to a function that's linear or affine in its argument – the only requirement is that the function uses the value in a linear or affine way. That's not quite the same as what Rust does, which I do find a bit annoying. What rust does is called "uniquenes typing", where a function can always do whatever it wants with any values it gets, but it can mark its parameters as "unique" and the caller has to make sure that any value passed as a parameter to that function is never used anywhere else. This is arguably the more useful of the two, because it means that you can mutate any argument marked as unique and no one can tell, but if you design a language around that you get Rust and I find Rust a bit less pleasant to program in than Haskell.

[munificent]

Interesting! This reminds of me of what it feels like to write const-correct code in C++.

[lupire]

It's like unique_ptr<T> and move() semantics in C++.

[lupire]

> the caller has to make sure that any value passed as a parameter to that function is never used anywhere else.

you mean the compiler, right?

[ChadNauseam]

The compiler checks that you don't write code where the caller disobeys that restriction :p

[dahfizz]

> 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.

This still only works if a child has one / a known-ahead-of-time number of parents. If you need to update an object that N objects point to, you need to update all N references.

[pyrale]

It just doesn't really happen that much in functional programs, to be honest.

The very concept of n objects pointing to the same, commonly mutated data is something that can be adressed easily by having that data contained by a parent structure. Since functional programs don't think in terms of "methods" within each object trying to access data, but in terms of external function manipulating all the data you need, the only change is the way you'll pass your data to your functions.

[voxl]

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]

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.