Live data from Hacker News

Two Vexing Problems in Functional Programming

matthewbutterick.com

211–217 of 217 posts

Re: Two Vexing Problems in Functional Programming

#211

Earlier quoted context omitted.

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…

What you are trying to describe is not Haskell the language but an implementation, and right now the de facto implementation is GHC. I really can't talk about how GHC works internally, but when it comes to the language you need to think your program as a value, just like `5` or `[1,2,3]` or `{ "name": "susan" }`. That is, effects are values, you compose those effects, and, your program being some kind of effect, is a…

Right. I was thinking of how to write a game in Haskell or similar. I need to write some kind of loop to keep my program/game running indefinitely. And I need to avoid "blowing up" the stack by writing my program as a set of calls to tail-recursive functions. No?

The program must keep the previous state somewhere and then modify it based on the player's inputs and again store that new state somewhere somehow so it is remembered when next input comes. If loops which keep and modify state are not allowed, then I don't see how it could be done without tail-recursive functions.

Re: Two Vexing Problems in Functional Programming

#212

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

Not necessarily. Depends on the underlying hardware implementation (with different answers for e.g. x86 vs ARM) since software CAS usually is implemented as a single CPU instruction.

This is also stretching the definition of "lock" quite a bit because usually CAS is used to implement lock-free and wait-free concurrency.

But regardless at most, even in hardware, it's a single top-level lock, and sometimes not even that. Not one along every level of a data structure.

Re: Two Vexing Problems in Functional Programming

#213
post #49

Earlier quoted context omitted.

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

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

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

Re: Two Vexing Problems in Functional Programming

#214

Earlier quoted context omitted.

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

In Haskell you can you Lenses to easily manipulate sub-trees, individual values, or a selection of values in tree like data structures. It is very powerful.

Re: Two Vexing Problems in Functional Programming

#215
post #116

Tangential but what is the most successful and most complex example of a fully FP-based application where I can view the source-code today? I feel like I still don't quite grasp the essence of the conflict between FP and whatever it seems to be opposing. I also feel like I use what a lot of FP people claim as FP in my day-to-day. I think if I can see some code beyond the old map/reduce toy examples it might click. No…

I used to be in your shoes. What helped me was learning Haskell and watching all YouTube videos by the Clojure creator (what’s his name again?) It was hard for me to get it (old dog learning new tricks). But I persisted and suddenly the light bulb went off and it all became super simple and easy. It was a hard journey but worth it. I am a much better programmer today, in any language, because of it.

Re: Two Vexing Problems in Functional Programming

#216
post #125

Earlier quoted context omitted.

But it's a pain to write out assembly, so we go via LLVM and SSA. In SSA, rather than modelling your program using 16 mutable registers (imperative folk love talking about "the real world" or "real computer"), we use an infinite number of immutable registers. Infinite registers won't fit in a computer (we only have 16), and not being able to overwrite registers must kill performance right?

I'm not sure what your point is. Yes, it is possible to build "functional" layers of abstraction on top of real hardware. The hardware itself is not "functional", that's why you need layers of abstraction.

The hardware is also not C style imperative. C/Haskell/Clojure/… are all abstractions that gets mapped to a very complicated extremely parallel hardware state machine. None of the main stream programming languages maps to real hardware. Which is a good thing! We want to use an abstraction that helps us getting the job done faster/better. It does not matter how much the abstraction you use maps to real hardware. As long as it gets the job done who cares?

Re: Two Vexing Problems in Functional Programming

#217
post #34
post #4

So, as the trend of forcing functional programming into imperative languages continues on its inexorable path, I just can't help but bring the old joke to mind more and more often: "Doctor, it hurts when I do this." "Well, then, don't do that." You mean, jamming a foreign paradigm into a language, where the advantages of the foreign paradigm are reduced and the disadvantages greatly magnified, hurts sometimes? Have y…

The question I am left with, as someone who has a bit of experience with functional languages but much more in imperative/OOP languages, is does it ever make sense to develop something like the GUI applications the author was talking about using a primarily functional paradigm ? Assume you get to pick whatever FP language you want so the issue here isn't with shoehorning FP techniques into a language that doesn't sup…

Elm is a great example of UI done right. And it is 100% functional.
Post reply on HN