Two Vexing Problems in Functional Programming • Hacker News Board

Re: Two Vexing Problems in Functional Programming

#151

Post by evilotto » Fri, Apr 01, 2022, 9:20 PM UTC

I rather like tcl's solution: copy on write, with reference counting. Values are immutable, so if you to alter a value in place, it gets copied; but iff nothing else is pointing to the same value it can get modified in place because the end result is indistinguishable. This does lead to the occasional need to explictly unshare things for performance[1], at least until the compiler gets smart enough to prove that the value is unshared.

[1] https://wiki.tcl-lang.org/page/K#c2a6014c2d129837889d8a8000d...

Re: Two Vexing Problems in Functional Programming

#152

Post by dahfizz » Fri, Apr 01, 2022, 9:22 PM UTC

mirceal wrote: post #144

dahfizz wrote: post #109

Earlier quoted context omitted.

That works for simple circuits. Actual computers have oodles of state - we usually call it "main memory". Assembly is a language that can only do one thing: mutate this state.

that’s the point. more complex circuits are made from simple circuits. principle still applies. if you think about it, most problems with writing code stem from state management.

> more complex circuits are made from simple circuits. principle still applies.

And humans are made out of carbon, but you are never going to understand human emotion by studying carbon atoms really hard.

Assembly is the interface to the hardware. Assembly is imperitive. The abstraction that assembly exposes is a machine with global, mutable state. That's the way the hardware works.

Re: Two Vexing Problems in Functional Programming

#153

Post by nightski » Fri, Apr 01, 2022, 9:23 PM UTC

dahfizz wrote: post #135

nightski wrote: post #118

Earlier quoted context omitted.

No, I don't believe you could argue C is purely functional by framing memory as the output of the function because C doesn't treat it as such. Memory in C can be changed even if it is not listed in the inputs or outputs of the function. He's not really stretching the definition, that's just the lens through which FP looks at the world. Of course there is state. FP doesn't prohibit state, it just makes it explicit and…

> Memory in C can be changed even if it is not listed in the inputs or outputs of the function. If we are going to nitpick syntax, nothing about `mov eax ebx` lists main memory as output. In fact, mov doesn't even have an 'output'. If you want to model mov as a function with the implicit output of "all of main memory", then you can do the same with any arbitrary C function. If you can't make that leap for C, then you…

It's not syntax, it is semantics. There is a lot to programming language theory/design and this is all formalized. C does not have the semantics you are describing in the formal specifications (C99, etc..). Could they have developed a version of C with these semantics? Possibly. Rust was a step in that direction with it's borrow checker.

Re: Two Vexing Problems in Functional Programming

#154

Post by Sinidir » Fri, Apr 01, 2022, 9:27 PM UTC

"When a functional update on a child structure occurs, the mediator is updated with the reference to the new child. But all the parents still point at the same mediator".

This is literally atoms in clojure.

Re: Two Vexing Problems in Functional Programming

#155

Post by Sinidir » Fri, Apr 01, 2022, 9:29 PM UTC

mumblemumble wrote: post #150

closeparen wrote: post #138

Earlier quoted context omitted.

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

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…

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

Re: Two Vexing Problems in Functional Programming

#156

Post by codebje » Fri, Apr 01, 2022, 9:30 PM UTC

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…

No language will tell you at compile time whether an arbitrary list filter operation will have an effect or not. If it can, it's because the list filter isn't arbitrary, it's probably always a no-op.

The generalisation is that you have some type parent with a way to select a type child, plus a function that modifies a child, you want to lift your child -> child function to a parent -> parent function.

Optics help a lot with this class of problem.

Because you're in the world of persistent data structures, and you're doing a modify operation, there is no avoiding the 'modify hashtable' part of 'modify an element within a hashtable'. You always create a 'new' hashtable.

If it's common that your update operation has no effect it may be worth switching to a function like child -> Modified child for Modified a = NoOp | Mutated a, so the hashtable modify function can determine if it can skip its own update. A list filter is a trivial thing to write, and one that can return NoOp if no elements are filtered is no less efficient.

Re: Two Vexing Problems in Functional Programming

#157

Post by pyrale » Fri, Apr 01, 2022, 9:32 PM UTC

dahfizz wrote: post #101

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…

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

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.

Re: Two Vexing Problems in Functional Programming

#158

Post by dahfizz » Fri, Apr 01, 2022, 9:33 PM UTC

nightski wrote: post #153

dahfizz wrote: post #135

Earlier quoted context omitted.

> Memory in C can be changed even if it is not listed in the inputs or outputs of the function. If we are going to nitpick syntax, nothing about `mov eax ebx` lists main memory as output. In fact, mov doesn't even have an 'output'. If you want to model mov as a function with the implicit output of "all of main memory", then you can do the same with any arbitrary C function. If you can't make that leap for C, then you…

It's not syntax, it is semantics. There is a lot to programming language theory/design and this is all formalized. C does not have the semantics you are describing in the formal specifications (C99, etc..). Could they have developed a version of C with these semantics? Possibly. Rust was a step in that direction with it's borrow checker.

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

Re: Two Vexing Problems in Functional Programming

#159

Post by zelphirkalt » Fri, Apr 01, 2022, 9:36 PM UTC

dahfizz wrote: post #112

mirceal wrote: post #107

Earlier quoted context omitted.

immutability is amazing. you can make assumptions about the data that you have received, it's friendly to caching, it's friendly to crashes, it's very easy to reason about. it's even more amazing when you enter a territory of multithreading/multi processor.

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.

At some point you need to break the paradigm to do anything useful, be it some IO, or whatever. Working in a FP way for as long as appropriate will make large parts of your program better testable and avoid large amounts of unwelcome surprises. If at some point you got some result, which you want to let affect the real world, then you can still limit mutation to that place, where you got the result. I would avoid that for as long as possible, to have larger parts of my program be easy to reason about.

GUI has been one of the strongholds of mutation-encouraging paradigms though. It should be said. I would use it as an example, where one probably might need mutation for performance reason and for the reason, that I find it a bit too overheady to create a new widget for every small change. I don't know enough about how some languages try to solve this and stay declarative or functional, to comment on that.

Re: Two Vexing Problems in Functional Programming

#160

Post by pyrale » Fri, Apr 01, 2022, 9:39 PM UTC

voxl wrote: post #113

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…

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.

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.