Functional languages should be so much better at mutation than they are • Hacker News Board

Re: Functional languages should be so much better at mutation than they are

#121

Post by tsimionescu » Wed, Jul 31, 2024, 1:00 PM UTC

naasking wrote: post #96

tsimionescu wrote: post #76

Earlier quoted context omitted.

Almost all GCs used in practice today only scan the set of live objects, which in normal operation is much smaller than the entire heap. They also allow much more efficient allocation and de-allocation. The problems with GC are threefold, and why you might not want it in a systems language: 1. GC requires more memory than strictly necessary to be efficient (usually about 1.5x - 2x the amount you absolutely need). You…

> 2. GC performance is harder to predict and reason about than certain other allocation strategies I'm not sure what you mean by this being the least understood. It seems like it's very well understood: GC introduces latency if you want good throughput, or it reduces throughput if you want excellent latency (sub-100us is possible). Of course, that doesn't mean you can predict what specific throughput or latency prope…

The point is that it's very hard to predict how much of an impact the GC will have a priori. You can of course measure after the fact, and try to improve, but it's hard to architect your system in a way that you can more or less guarantee will get good GC performance (other than just not allocating any memory, of course). Malloc actually suffers from a similar problem: it's just hard to know a priori if your access patterns will work well with the internals of your allocator/GC.

Re: Functional languages should be so much better at mutation than they are

#122

Post by p_l » Wed, Jul 31, 2024, 1:49 PM UTC

tsimionescu wrote: post #121

naasking wrote: post #96

Earlier quoted context omitted.

> 2. GC performance is harder to predict and reason about than certain other allocation strategies I'm not sure what you mean by this being the least understood. It seems like it's very well understood: GC introduces latency if you want good throughput, or it reduces throughput if you want excellent latency (sub-100us is possible). Of course, that doesn't mean you can predict what specific throughput or latency prope…

The point is that it's very hard to predict how much of an impact the GC will have a priori. You can of course measure after the fact, and try to improve, but it's hard to architect your system in a way that you can more or less guarantee will get good GC performance (other than just not allocating any memory, of course). Malloc actually suffers from a similar problem: it's just hard to know a priori if your access p…

IBM Metronome and similar approaches provide very strong guarantees (if you keep a certain bound on garbage creation ofc) at the expense of throughput.

What they lose is that they introduce also a certain guaranteed loss of available cpu time, due to optimizing for latency and real-time predictability.

Re: Functional languages should be so much better at mutation than they are

#123

Post by p_l » Wed, Jul 31, 2024, 1:58 PM UTC

tsimionescu wrote: post #94

tome wrote: post #88

Earlier quoted context omitted.

> You're basically trading runtime efficiency for memory. What do you mean? Aren't GCs both less efficient at run time and use more memory?

No, the more memory you give them, the more efficient they are, and generally they are much more efficient than an equivalent program using malloc() + free() for every piece of memory that gets allocated. Take the extreme case of a program where every allocation is permanent. The GC allocation will be much much faster than malloc() (GC allocation is normally just bumping a pointer to the end of the heap, while malloc…

This is in fact heavily related to "ancient" Unix approach, and partially why it optimized so hard for many small processes.

PDP-11 unix (without split instruction/data space) had 32kB of memory for userland process, total, plus another 24kB for kernel (8kB are reserved for I/O devices).

The memory management interface that gave us malloc() and free() ultimately boiled down to brk() and sbrk() which simply set a pointer describing where stack and heap met in memory. Using many small programs, you'd have as little as possible of that 32kB used by code, and prefer to simply allocate using bump pointer and never free (better reuse object pools, which is also a technique used with GCs). A program in a pipeline would mostly allocate some stuff at the start plus buffers, and while some of the early bits might become garbage it doesn't really matter because you can't share parts of your 32kB block (or at best you can use 8kB segments). So you do "missile-style GC" and just use a bump-pointer allocator (brk() + sbrk() + sizeof combo), then exit to OS when your work is done and the entire memory space gets cleaned.

EDIT: Some GCs (like in later versions of Symbolics Lisp Machines, or presently in SBCL behind some experimental options) provided multiple arena support explicitly to be able to force-declare everything allocated in an area as garbage.

Re: Functional languages should be so much better at mutation than they are

#124

Post by cryptica » Wed, Jul 31, 2024, 2:10 PM UTC

IMO, Functional Programming was a zero interest rate phenomenon. Some mathematicians suffering from professional deformation believed that programming should adhere to the purity of mathematical conventions... Meanwhile, there was no proof whatsoever to support the hypothesis that constraining programming to such conventions would be beneficial in a practical sense.

FP proponents spotted a small number of problems which arose in certain specific OOP implementations and stubbornly decided that OOP itself was to blame.

Some FP proponents have pointed out that passing around instance references to different parts of the code can lead to 'spooky action at a distance.' For example, if references to the same child instance are held by two different parent modules and they both invoke state-mutating methods on the child instance, it becomes difficult to know which of the two parent modules was responsible for the mutation of state within the child instance...

The mistake of FP proponents is that they failed to recognize the real culprit of the flaws that they've identified. In the case of 'spooky action at a distance', the culprit is pass-by-reference.

If you keep that in mind and consider what OOP pioneers such as Alan Kay have said about OOP "It's about messaging," it becomes an irrefutable fact that this flaw has nothing to do with OOP but is merely a flaw in specific implementations of OOP... Flawed implementations which neglected the messaging aspect of OOP.

To summarize it simply; with OOP, you're not supposed to pass around instances to each other, especially not references. What you're supposed to pass around are messages. The state should be fully encapsulated. Messages are not state, instances are state. Instances shouldn't be moved around across multiple modules, messages should.

If you approach OOP with these principles in mind, and make the effort to architect your systems in such a way, you will see it solves all the problems that FP claims to solve abd it doesn't introduce any of its problems... Which are numerous and would require an entire article to enumerate.

Re: Functional languages should be so much better at mutation than they are

#125

Post by Leftium » Wed, Jul 31, 2024, 2:51 PM UTC

cryptica wrote: post #124

IMO, Functional Programming was a zero interest rate phenomenon. Some mathematicians suffering from professional deformation believed that programming should adhere to the purity of mathematical conventions... Meanwhile, there was no proof whatsoever to support the hypothesis that constraining programming to such conventions would be beneficial in a practical sense. FP proponents spotted a small number of problems wh…

Interesting: I came to a similar conclusion when I developed a state management system I coined "nation state." (A group of related variables with scope that is between local and global scope.)

Svelte has these stores that are globally reactive. The reactivity is convenient, but the stores can also be globally updated. This could result in chaos that I wished to corral.

So I tweaked stores so they remained globally reactive, but could only be directly updated internally (from "inside the nation").

To update the the state from outside the nation, an event (message) must be sent to the nation state, which handles the direct update.

Re: Functional languages should be so much better at mutation than they are

#126

Post by andrepd » Wed, Jul 31, 2024, 2:53 PM UTC

naasking wrote: post #96

tsimionescu wrote: post #76

Earlier quoted context omitted.

Almost all GCs used in practice today only scan the set of live objects, which in normal operation is much smaller than the entire heap. They also allow much more efficient allocation and de-allocation. The problems with GC are threefold, and why you might not want it in a systems language: 1. GC requires more memory than strictly necessary to be efficient (usually about 1.5x - 2x the amount you absolutely need). You…

> 2. GC performance is harder to predict and reason about than certain other allocation strategies I'm not sure what you mean by this being the least understood. It seems like it's very well understood: GC introduces latency if you want good throughput, or it reduces throughput if you want excellent latency (sub-100us is possible). Of course, that doesn't mean you can predict what specific throughput or latency prope…

100us counts as excellent latency? x) that's half a million CPU cycles!

Re: Functional languages should be so much better at mutation than they are

#127

Post by andrepd » Wed, Jul 31, 2024, 2:58 PM UTC

tsimionescu wrote: post #94

tome wrote: post #88

Earlier quoted context omitted.

> You're basically trading runtime efficiency for memory. What do you mean? Aren't GCs both less efficient at run time and use more memory?

No, the more memory you give them, the more efficient they are, and generally they are much more efficient than an equivalent program using malloc() + free() for every piece of memory that gets allocated. Take the extreme case of a program where every allocation is permanent. The GC allocation will be much much faster than malloc() (GC allocation is normally just bumping a pointer to the end of the heap, while malloc…

GC does force you into a memory layout for your objects that negates any advantage in the allocation routines proper.

Re: Functional languages should be so much better at mutation than they are

#128

Post by jmull » Wed, Jul 31, 2024, 3:04 PM UTC

> A lot of people think that functional programming is mostly about avoiding mutation at all costs.

People should try to stop thinking of mutation as something to be avoided, and start thinking of it as something to be managed.

Mutating state is good. That's usually the whole point.

What's bad is when you create "accidental state" that goes unmanaged or that requires an infeasible effort to maintain. What you want is a source of truth for any given bit of mutable state, plus a mechanism to update anything that depends on that state when it is changed.

The second part is where functional programming shines -- you have a simple way to just recompute all the derived things. And since it's presumably the same way the derived things were computed in the first place, you don't have to worry about its logic getting out-of-sync.

Re: Functional languages should be so much better at mutation than they are

#129

Post by narski » Wed, Jul 31, 2024, 3:08 PM UTC

juped wrote: post #114

narski wrote: post #29

I recently ran into this issue when trying to memoize a simple numerical sequence in Hoon (yes, that Hoon. I know, I know...). Let's use the fibonacci sequence as an example. Let's write it the classic, elegant way: f(n) = f(n-1) + f(n-2). Gorgeous. It's the sum of the two previous. With the caveat that f(n=0|1) = n. In Python: # fib for basic b's def fib(n): ## Base case if n == 0 or n == 1: return n return fib(n-1)…

Hoon has magic memoization, though (~+) ++ fib |= a=@ ^- @ ~+ ?: (lte a 1) a %+ add $(a (sub a 2)) $(a (sub a 1)) Try e.g. (fib 100) (don't try it without the ~+) The compiled code is itself memoizable at the VM execution level. This memo cache is transient within one system event (i.e., pressing enter after (fib 100) to get the result).

Ha! I read the docs for ~+ (https://docs.urbit.org/language/hoon/reference/rune/sig#-sig...) and fibonacci sequence is actually the example they use!

Thanks so much for this enlightening comment :3

Although I'm curious why Hoon doesn't just detect and cache identical computations by default. I guess it's a tradeoff, since using ~+ is more memory intensive, and you don't always want that either. Especially is Urbit itself is already fairly memory intensive.

Re: Functional languages should be so much better at mutation than they are

#130

Post by p_l » Wed, Jul 31, 2024, 3:11 PM UTC

bmacho wrote: post #95

ufo wrote: post #38

Earlier quoted context omitted.

One thing that many people miss is that Haskell's monadic style is a direct consequence of lazy evaluation. It all started because they thought lazyness was nice, and wanted to make a language that brought that front and center. But then they found out that they had to come up with a new way to do side-effects, because traditional side-effects don't work when the order of evaluation is unpredictable.

> One thing that many people miss is that Haskell's monadic style is a direct consequence of lazy evaluation. It all started because they thought lazyness was nice, and wanted to make a language that brought that front and center. But then they found out that they had to come up with a new way to do side-effects, because traditional side-effects don't work when the order of evaluation is unpredictable. But this is no…

The oldest mention of Haskell Monads that I ever had in my hands starts the description with "this nice hack from the Haskell group at University of Glasgow to make I/O nicer without bragging laziness"