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

181–190 of 217 posts

Re: Two Vexing Problems in Functional Programming

#181

Post by dehrmann »

TuringTest wrote: post #169
dahfizz wrote: post #158

Earlier quoted context omitted.

Yes, and my whole point is that assembly does not have those semantics either. The computer is an imperative machine.

The computer is not an imperative machine. It's a physical machine that you describe with an imperative representation in your mind. Can you tell the difference, or are you unaware of the map-territory distinction going on? Functional programmers are simply choosing to use a different style of map, but we both represent the same reality.

According to Wikipedia, "the hardware implementation of almost all computers is imperative."

https://en.wikipedia.org/wiki/Imperative_programming

Re: Two Vexing Problems in Functional Programming

#182

Post by mirceal »

adamkl wrote: post #176
mirceal wrote: post #143

Earlier quoted context omitted.

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

i found that people are more open to this idea if they believe i am kidding.

Re: Two Vexing Problems in Functional Programming

#183

Post by hither_shores »

chriswarbo wrote: post #140
dehrmann wrote: post #44

Earlier quoted context omitted.

> You should not approach problems in functional languages with imperative techniques. It's fitting a square peg in a round hole. This might be part of the problem with FP. Every popular CPU architecture is imperative.

I find this unconvincing. Electronic circuits are well described as a Cartesian Closed Category; and hence by lambda calculus (i.e. we can give semantics to functional programs by interpreting them as descriptions of circuits; as opposed to the "usual" interpretations of x86_64 machine code, or symbolic values, etc.) Imperative systems are "fitting a square peg in a round hole" by introducing hacks like 'clock signal…

The category with linear circuits as its morphisms, labelled sets of electronic terminals as its objects, and laying circuits in parallel as the monoidal product (which is the usual notion of the category of circuits; perhaps you have something more sophisticated in mind, but if so you should specify that) is not cartesian closed.

One of the many ways to demonstrate this: all linear circuits have duals (voltage current, series parallel, and so on), but in a cartesian closed category only the terminal object is dualizable.

What you're probably thinking of is the fact that this category is compact closed. The corresponding internal language is going to be some sort of process calculus (I think the pi calculus is too strong, but not sure), not the lambda calculus.

Re: Two Vexing Problems in Functional Programming

#184

Post by throwaway81523 »

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?

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

Re: Two Vexing Problems in Functional Programming

#185

Post by joshlemer »

tomp wrote: post #121
nlitened wrote: post #120

Earlier quoted context omitted.

> you want to modify a list - how do you know if the inner list changed or not You know for sure that inner list did _not_ change, because it is immutable. Someone else might have a reference to an updated hashtable with an updated inner list, but the one you hold will never change—isn’t that the whole idea of immutable data structures?

No, I mean "update" in the persistent sense - create a new list, with some (or none) elements changed/added/removed. e.g. say you have a method remove_all_in_values that takes an int x and a hashmap of list of int, and returns a new hashmap of list of int, with x removed from each element of the hashmap. Obviously you'd use something like List.filter for the inner operation, but most functional programming languages…

You can pretty efficiently do this in Clojure

    (update-in
     {:foo [{:bar ["a"], :baz ["b" "c" "d"]}]}
     [:foo 0 :baz 1]
     clojure.string/capitalize)
    
    
    ;; => {:foo [{:bar ["a"], :baz ["b" "C" "d"]}]}

Re: Two Vexing Problems in Functional Programming

#186

Post by joshlemer »

nyanpasu64 wrote: post #180
tomp wrote: post #95

Earlier quoted context omitted.

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

I think a lot of the pain in Scala/Rust etc immutable data structures comes down to static typing. In Clojure for instance you can very ergonomically do deeply nested persistent updates.

    (update-in
     {:foo [{:bar ["a"] :baz ["b" "c" "d"]}]}
     [:foo 0 :baz 1]
     clojure.string/capitalize)

    => {:foo [{:bar ["a"], :baz ["b" "C" "d"]}]}

Re: Two Vexing Problems in Functional Programming

#187

Post by joshlemer »

Barrin92 wrote: post #69

Personally I never really understood the benefit of thinking in functional terms about things that are conceptually more naturally thought of as persistent objects. For example when the author picks "parents" or "children" or in general maybe any entity of any kind, I don't understand what functional thinking gets me. Sure instead of manipulating mutable objects I can think of every entity being 'one thing' at 'one m…

Rich Hickey made a great talk on this in 2009 https://youtu.be/ScEPu1cs4l0

An other way to think about it is that the programs we write do not literally simulate entities (users, other domain objects like books, students, professors, classes, etc). Our software simulates the record keeping devices that store /protect information regarding these entities. We are most of the time writing information processing systems, not simulation systems and information accumulates, rather than updates in places. Like, e.g. when there's a new president elected, we don't all go out with our erasers and remove all references to change sentences from "The President is Donald Trump" to say "The President is Joe Biden", instead we accumulate new facts without remembering the old.

Re: Two Vexing Problems in Functional Programming

#188

Post by throwaway81523 »

Article is overall unpersuasive. The first part is silly: copying a whole array instead of using a functional data structure such as a red-black tree is just asking for a huge slowdown. The second part doesn't give enough detail to really make its case. Author's solution was a big tree with mutable nodes, but there's a cautionary tale in an old article[0] by Ramsey and Dias about using a zipper[1] as a functional representation for the control node graph of a C-- compiler.

[0] https://doi.org/10.1016/j.entcs.2005.11.042

[1] https://en.wikipedia.org/wiki/Zipper_(data_structure)

Re: Two Vexing Problems in Functional Programming

#189

Post by hither_shores »

galaxyLogic wrote: post #131
valcron1000 wrote: post #92

Earlier quoted context omitted.

In my experience Haskell is a bad solution when you need fine control over memory usage and control flow. For those cases you should probably use something like C, C++ or Rust. For everything else I think is a viable option. The hard part is understanding how you should model your problem. I found that you could classify problems into two big groups: pipelines like compilers or web services where you get an input, do…

It took me some time to understand how Haskell performs its "magic" but now I think I do. Anybody please correct me if I'm still getting it wrong... Haskell main program in essence runs a big loop until it decides the program should exit. In Haskell syntax the loop is coded as a call to a tail-recursive function, which on a real hardware of course needs to be translated to do iteration. At the end of each loop it set…

No, that's not accurate. The final form of your Haskell program before it's compiled down to some assembly language (currently C-- or LLVM) is a graph reduction problem. The partially imperative part is the runtime system, which actually reduces the graph (= runs your program), but this is significantly more complicated than the sort of high level loop transformations you're talking about. Search "spineless tagless G-machine" for a (somewhat idealized) description of the core architecture of GHC.

Re: Two Vexing Problems in Functional Programming

#190

Post by fulafel »

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.

In Clojure the default associative data structure is a persistent map and cloning it with 0 changed nodes is basically a no-op.
Post reply on HN