Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Two Vexing Problems in Functional Programming

matthewbutterick.com

Post reply on HN
Print view View original

171–180 of 217 posts

Re: Two Vexing Problems in Functional Programming

#171

Post by lupire »

jayd16 wrote: post #133
js8 wrote: post #2

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 imperat…

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?

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

Re: Two Vexing Problems in Functional Programming

#172

Post by lupire »

closeparen wrote: post #138
jayd16 wrote: post #133

Earlier quoted context omitted.

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?

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

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)

Re: Two Vexing Problems in Functional Programming

#173

Post by lupire »

zodiac wrote: post #31
js8 wrote: post #2

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 imperat…

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"?

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.

Re: Two Vexing Problems in Functional Programming

#174

Post by lupire »

ChadNauseam wrote: post #82
munificent wrote: post #64

Earlier quoted context omitted.

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

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 per…

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

Re: Two Vexing Problems in Functional Programming

#175

Post by lupire »

munificent wrote: post #126
ChadNauseam wrote: post #82

Earlier quoted context omitted.

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 per…

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

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

Re: Two Vexing Problems in Functional Programming

#176

Post by adamkl »

mirceal wrote: post #143
dahfizz wrote: post #112

Earlier quoted context omitted.

But the real world is mutable. The authors example of a GUI program is a good one: the user wants to change the state of the program, and expects the new state to be reflected in the GUI. You can model this in fp, but it feels like I'm standing on my head. The user wants to modify a glyph, and the program should modify that glyph. It's the simplest way of modeling what is happening.

this is me being cheeky, but how do you know that the real world is mutable? if you believe in super-determinism and that everything progresses based on predetermined laws you can take the view that space+time already exists in all its past and future and that nothing happens. or, quantum mechanics in the multiple world interpretations. you can say that the state of the world literally splits whenever there is an eve…

Late to the party here, but what you propose is not being cheeky.

Rich Hickey (Clojure creator) himself has a similar, interesting, and compelling take on time and mutability [0]. This perspective is the underlying basis of Datomic.

[0] - https://youtu.be/ScEPu1cs4l0

Re: Two Vexing Problems in Functional Programming

#177

Post by ChadNauseam »

lupire wrote: post #174
ChadNauseam wrote: post #82

Earlier quoted context omitted.

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 per…

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

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

Re: Two Vexing Problems in Functional Programming

#178

Post by UncleMeat »

tomp wrote: post #97
UncleMeat wrote: post #66

Earlier quoted context omitted.

Persistent data structures exist and work very well but they still remain way slower than alternatives that don't support persistence. This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks. Add in the GC overhead and you've got a meaningful problem. Yes, you aren't constructing an entirely new 30k byte a…

> This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks. Um, what? Persistent data structures don't require locks at all (because they're immutable), in fact using them in a multithreaded way is 100% safe and thus much easier than their mutable (and ordinarily more efficient) counterparts.

Refcounted gc means you need locking on refcounts or you can lose your tree during iteration.

Re: Two Vexing Problems in Functional Programming

#179

Post by UncleMeat »

dwohnitmok wrote: post #75
UncleMeat wrote: post #66

Earlier quoted context omitted.

Persistent data structures exist and work very well but they still remain way slower than alternatives that don't support persistence. This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks. Add in the GC overhead and you've got a meaningful problem. Yes, you aren't constructing an entirely new 30k byte a…

> Persistent data structures exist and work very well but they still remain way slower than alternatives that don't support persistence. Depending on your definition of "way" this is true. A lot of persistent vector-like structures can have quite good performance, but if your runtime is dominated by iteration and random updating, you will still get a speed up by using raw arrays, i.e. guaranteed contiguous blocks of…

CAS still has a lock in actual memory.

Re: Two Vexing Problems in Functional Programming

#180

Post by nyanpasu64 »

tomp wrote: post #95
dgreensp wrote: post #21

These problems have lots of other well-known solutions. For large objects: Persistent data structures with path-copying. Batching small mutations (and using mutation internally in a way that doesn’t leak out). Using the type system somehow to distinguish cases where copying is not necessary (experimental in certain new languages). Structuring your program around a “data store” that is mutable. For the “references” pr…

Persistent data structures are very hard. It's basically impossible to cleanly combine them. E.g. if you have an immutable hashtable that contains immutable lists, and you want to modify a list - how do you know if the inner list changed or not (you don't want to be creating new hashtables if the elements don't change). They work in the small, but don't truly scale.

I can't stand the standard update-based interface of persistent data structures either. https://lib.rs/crates/im wraps persistent structures in a standard vector interface, with instant clones (only copying a pointer to refcounted data) but slower assignments (which may copy data internally if other references exist), which is effectively equivalent to CoW. A persistent update is instead written as a clone followed by in-place assignment, and you can mutate in-place (which copies if there are other references to the data being modified). The nice part is that only IndexMut detaches the underlying data from other references.

I haven't used this crate yet, but if I have a need for persistent data structures I'd definitely try this since it's more accessible.

Post reply on HN