Two Vexing Problems in Functional Programming • Hacker News Board

Re: Two Vexing Problems in Functional Programming

#81

Post by dllthomas » Fri, Apr 01, 2022, 5:54 PM UTC

zodiac wrote: post #38

vnorilo wrote: post #36

Earlier quoted context omitted.

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.

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

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.

Re: Two Vexing Problems in Functional Programming

#82

Post by ChadNauseam » Fri, Apr 01, 2022, 5:54 PM UTC

munificent wrote: post #64

ChadNauseam wrote: post #39

Earlier quoted context omitted.

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

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

Re: Two Vexing Problems in Functional Programming

#83

Post by karmakaze » Fri, Apr 01, 2022, 5:54 PM UTC

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…

I was thinking along the same lines. Is an "atom" in Clojure like STM where the structure/reference is changed in a highly controlled manner?

Re: Two Vexing Problems in Functional Programming

#84

Post by TuringTest » Fri, Apr 01, 2022, 5:59 PM UTC

zodiac wrote: post #73

TuringTest wrote: post #53

Earlier quoted context omitted.

The thing is, functional and imperative programming are mathematically equivalent - to the point that you can express imperative code in a pure functional language, if that's what you really need. If you want a O(1) random access in a functional language, you can formally define it; the problem with this is that you may end up embedding a whole computer in your program to do it, if your program heavily depends on sid…

If you used the State monad for the author's interpreter example, and you did it in Racket (your "state of the world" is a cons-list), what would be the run-time of the resulting interpreter? Similar question for streams (although I'm not that familiar with streams, so I don't know how they would apply here, or if they can be implemented without changes to the base language)

A stream is in essence the same as the Observer pattern; every function that depends on the values of a mutable variable must use accessor methods to extract the most recent value when they need it, or pass it 'hook' callback functions that represent the next steps to take on new values.

So, in principle, it should have the same performance as the 'Children can issue notification events' method in the article, since it's using what in essence is the same structure (just with a much nicer syntax, better adapted to functional programs).

The advantage of using functional streams instead of OOP observable callbacks is that it tends to be easier to write the program's large structure as compositions of functions over streams, i.e. it is easy to build modular functions without the bugs introduced by side effects.

I learned this style of programming through the online 'Paradigms'[1] course by Peter Van Roy, which you can take for free if you don't want credits. It uses the multi-paradigm language Oz to explain the essence of each paradigm and the differences between them. The course distills the primitives of different programming languages in terms of how they see state (see Van Roy's diagram in [2]), and how deciding to incorporate and combine some of those primitives and not others gives rise to the different programming styles. I found it enlightening, in the way that programmers' koans refer to.

[1] https://www.edx.org/es/course/paradigms-of-computer-programm...

[2] https://en.wikipedia.org/wiki/Programming_paradigm#Overview

Re: Two Vexing Problems in Functional Programming

#85

Post by ChadNauseam » Fri, Apr 01, 2022, 5:59 PM UTC

vnorilo wrote: post #49

zodiac wrote: post #38

Earlier quoted context omitted.

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

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

Re: Two Vexing Problems in Functional Programming

#86

Post by blablablerg » Fri, Apr 01, 2022, 6:01 PM UTC

travisathougies wrote: post #22

marcosdumay wrote: post #18

Earlier quoted context omitted.

You mean, Haskell developers ditch the functional idiom and use a more imperative one when they need it for performance? And yes, they do, and it works nicely. But it's not solving any problem with the functional paradigm. Anyway, none of them is a problem with the semantics of FP. They are a problem of insufficient optimization. So they will probably get solved at some point.

ST is not 'imperative'. The monadic interface can look imperative sure, but then you can also use Applicative and friends and that's back to being functional. Of course, I prefer to think of what you call 'imperative' programming as function composition where >>= is the reverse of the 'normal' composition operator. Indeed, sequential imperative commands and function composition are isomorphic.

Yep it it is called declarative.

Re: Two Vexing Problems in Functional Programming

#87

Post by valcron1000 » Fri, Apr 01, 2022, 6:03 PM UTC

tgflynn wrote: post #34

jerf wrote: 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…

For GUI programming I found FRP to be a really good solution. And no, I don't consider React to actually do FRP.

The closest mainstream project to FRP is Angular using RxJS exclusively. You define how each component interacts with each other, and then you delegate to a runtime to actually perform the side effects (change the DOM in this case). Solutions like React + Redux/Elm involve a lot of plumbing that's not relevant to the issue: I just want to define relationships between components, not manually tread changes across a big state tree.

Re: Two Vexing Problems in Functional Programming

#88

Post by TuringTest » Fri, Apr 01, 2022, 6:05 PM UTC

For anyone interested in programming paradigms, I strongly recommend the online 'Paradigms'[1] course by Peter Van Roy, which you can take for free if you don't want to get certified. It uses the multi-paradigm language Oz to explain the essence of each paradigm and the differences between them. (Learning that new language makes sense in this case, as it prevents you from being distracted by the idioms of languages you already know).

The course distills the primitives of different programming languages in terms of how they see state (see Van Roy's diagram in [2]), and how deciding to incorporate and combine some of those primitives and not others gives rise to the different programming styles. I found it enlightening, in the way that programmers' koans refer to.

[1] https://www.edx.org/es/course/paradigms-of-computer-programm...

[2] https://en.wikipedia.org/wiki/Programming_paradigm#Overview

(This is a repost of a comment I made below, so that readers who don't read the whole thread can still see it).

Re: Two Vexing Problems in Functional Programming

#89

Post by memco » Fri, Apr 01, 2022, 6:06 PM UTC

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…

I really enjoyed this presentation on how roc-lang is being designed to handle optimization using opportunistic in-place mutation: https://yewtu.be/watch?v=vzfy4EKwG_Y&t=1328.

Re: Two Vexing Problems in Functional Programming

#90

Post by valenterry » Fri, Apr 01, 2022, 6:13 PM UTC

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…

Because it reduces the number of things you have to keep in your head and the uncertainty about what you don't know.

Using monads and a "state box", it's not enough to make a change to the context of the box, you also have to pass the box onto the next entity/process that wants to change it, or nothing will effectively change (other than burning cpu cycles).

This also means that it suddenly becomes easy to find out what things happened to the box content before, because all you have to do is check what the one who was passing the box to you was doing with it.

If your program is strictly linear than using state boxes is merely syntactic overhead. But as soon as that's not the case anymore, it suddenly becomes important.

I remember very well the time when I had to deal with bugs where I was operating on data that looked different than I expected and I had a hard time to figure out how it came to that.

But even worse are bugs from concurrency and also the "magic" and workarounds for dealing with it when "state boxes" are not available or known to the developer. Now you look at a line of code while knowing that stuff is running somewhere else, impacting what you are working on in a potentially uncontrolled manner.

I find that very unproductive.