Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

cohost.org

Post reply on HN
Print view View original

141–150 of 188 posts

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

#141

Post by nxobject »

tsimionescu wrote: post #76
devit wrote: post #56

Earlier quoted context omitted.

You can, but it turns out that, as one may intuitively expect, a GC is never needed unless implementing a VM for a GC-based language or an API that required GC like fd passing on unix domain sockets, and those generally want an ad-hoc GC instead tailored to whatever you are implementing. Since it's not needed and it's massively worse than reference counting (assuming you only change reference counts when essential an…

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…

Side question: does Azul still sell custom silicon/designs to accelerate JVM?

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

#142

Post by quotemstr »

andrepd wrote: post #127
tsimionescu wrote: post #94

Earlier quoted context omitted.

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.

No it doesn't. GCs need to be able to traverse objects. They don't impose object layout constraints.

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

#143

Post by juped »

narski wrote: post #129
juped wrote: post #114

Earlier quoted context omitted.

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…

There's a lot of reductions that happen during execution, and not many are usefully going to be repeated identically; you'd end up with an extremely large and nearly entirely useless cache if you tried to cache everything. So you hint the VM when it turns out that something does repeat.

What has to repeat is an identical subject (which will have a shape like [argument-to-fib other-local-context standard-library]) and formula (the compiled code for fib). Pretty much the only time this will ever happen is something recursing into itself. Most tail recursion doesn't reevaluate the exact same arguments multiple times. It just so happens that naive fib's exponential self-recursion into itself twice does do that.

So it wouldn't be useful to stick a ~+ on, say, factorial. Except! If you're, say, computing every factorial from 1 to 100 in a loop, it comes in handy - because now you can reuse your computation of, say, 50! when computing 51!, so it's just one multiplication.

But most Nock reductions by volume are not anything that repeats usefully.

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

#144

Post by jerf »

jmull wrote: post #128

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

I like to say that immutability is a really good idea in the 1990s, especially considering how counterculture it would have been at the time. I don't mean that as diminutive or patronizing, I'm serious. It was a good cutting edge idea.

However, nobody had any experience with it. Now we do. And I think what that experience generally says is that it's a bit overkill. We can do better. Like Rust. Or possibly linear types, though that is I think much more speculative right now. Or other choices. I like mutable islands in a generally immutable/unshared global space as a design point myself, as mutability's main problem is that it gets exponentially more complicated to deal with as the domain of mutability grows, but if you confine mutability into lots of little domains that don't cross (ideally enforced by compiler, but not necessarily) it really isn't that scary.

It was a necessary step in the evolution of programming ideas, but it's an awful lot to ask that it be The One True Idea for all time, in all places, and that nobody in the intervening decades could come up with anything that was in any way an improvement in any problem space.

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

#145

Post by naasking »

andrepd wrote: post #126
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…

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

That's fast enough for real-time audio, so yes, that's excellent. And that includes compaction and only a small hit to throughput. You can get sub-2us latency at a serious hit to throughput.

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

#146

Post by halter73 »

RandomThoughts3 wrote: post #4

The article utterly falls apart in its first paragraph where it itself acknowledges that the whole ML family including Ocaml has perfect support for mutation, rightfully assume most Ocaml programmers would choose to not use it most of the time but then assume incorrectly that it’s because the language makes it somehow uneasy. It’s not. It’s just that mutation is very rarely optimal. Even the exemple given fails: > Fo…

> The fact that most programming languages don’t give enough semantic information for their compiler to do a good job doesn’t mean it necessary has to be so. Functional programmers just trust that their compiler will properly optimize their code.

While everyone has to trust their compiler will make reasonable optimizations to some extent, there becomes a certain point of complexity where it becomes difficult to intuitively know if a "sufficiently smart compiler"[1] will properly optimize which is problematic.

I realize you're arguing Haskell is worse than Ocaml in this regard, but I'd argue it's harder to reason about how functional code will be translated into machine code than comparable procedural code in general.

[1]: https://prog21.dadgum.com/40.html

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

#147

Post by mrkeen »

taeric wrote: post #140
jmull wrote: post #128

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

This is a hill I will die on. Probably literally. If you are writing in a metaphor of equations, than yes, mutation is almost certainly going to bite you. If you are writing in a metaphor of process, you almost certainly want to manage, as you say. I feel that early texts were good at this. Turtle Geometry is my personal favorite book in this vein. I seem to recall we spent a long time going over how to double buffer…

> The entire point is to change things

We've other 'entire points' along the way.

Allocation and freeing of memory are fundamental to computing. We don't do malloc and free any more.

Control-flow (selecting which instruction to follow next) is also fundamental. We don't to goto anymore.

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

#148

Post by mrkeen »

Mathnerd314 wrote: post #136

There is a way to do FBIP without reference counting - use immutable store semantics (always copy). At that point you are doing a lot of copying but Haskell etc. are actually pretty good at managing this sort of profligate duplication. And of course it is possible to use RC-at-compile-time and other analyses to optimize away the copying - the difference is that runtime RC is not required like it is in Koka. There is…

> use immutable store semantics (always copy).

What does "always copy" mean? What and why would you copy?

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

#149

Post by devbent »

devit wrote: post #97
devbent wrote: post #77

Earlier quoted context omitted.

People often forget that the runtime of free is not trivially calculatable! I've worked on tiny embedded systems (.net micro framework) where for a given usage pattern the GC was perfectly predictable, as it should be.

What do you mean? Assuming you use a set of slabs of fixed size objects and keep free objects in a linked list, both malloc and free are trivial O(1) operations. Destructors with cascading deletions can take time bounded only by memory allocation, but you can solve that for instance by destroying them on a separate thread, or having a linked list of objects to be destroyed and destroying a constant number/memory size…

> Destructors with cascading deletions can take time bounded only by memory allocation, but you can solve that for instance by destroying them on a separate thread, or having a linked list of objects to be destroyed and destroying a constant number/memory size of them on each allocation.

Which means calculating how long free going to take for a given object is incredibly difficult. Which is my entire point. Of course it's not non-deterministic unless someone 's destructor call s some random code but it is not easy to calculate and in the real world is basically unpredictable.

Spitting up a separate thread and doing an unknown amount of work is no more predictable than doing on the main thread.

Fundamentally destructors can do whatever the hell they want which means you never know how long destruction is going to take.

And of course if you're freeing up an object that has a linked list inside of it and you need to clear out the link list, now you're jumping all around memory and that's never fun, and the run time sure as heck is not constant based on what needs to be paged in and out and what exists in cache lines where.

I'm not saying these problems are unsolvable for a given use case and there are good reasons why custom allocators abound throughout the industry, My main point is that manual memory management does not necessarily lead easy to predict run times for freeing up memory.

This especially true because a lot of developers think that malloc and free are just magic somehow.

In reality, garbage collectors often aren't that complicated, and when it comes to large complicated user applications, you're going to be spending a lot of time in the allocator and deallocator no matter what memory management schema you choose to use.

(Edit: and then there's fragmentation which is the death of many manually managed memory systems! A naively Java or c-sharp application can run for far longer than a naively written C++ application!)

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

#150

Post by derdi »

RandomThoughts3 wrote: post #131
derdi wrote: post #41

Earlier quoted context omitted.

> The point is that contrary to what the article states ML developers are not avoiding mutations because they are uneasy to use but because they trust their compiler when they know it will do good. Proof is that in other case they will use mutations when it makes sense to do so because the compiler does not do a good job. It will do a good job, yes. Will it do the best possible job compared to some other algorithm or…

No, not this. You are doing a map. A traversal of a data collection is not a map but a fold. The exemple in the article is specifically about collection which you would do by consing to a list (mostly free once optimised) in a fold_left (so tail call optimised to a loop). See my other comment. Also, List.map is not optimised in Ocaml. It uses a naive implementation and not a tail call. You have to use rev_map to get…

> A traversal of a data collection is not a map but a fold. The exemple in the article is specifically about collection which you would do by consing to a list (mostly free once optimised) in a fold_left (so tail call optimised to a loop).

The exact wording in the article is "let's say you're iterating over some structure and collecting your results in a sequence". You are interpreting a lot into this. Also, your description is of a map (reversed, and expressed as a fold). Anyway, where is your benchmark?

> Also, List.map is not optimised in Ocaml. It uses a naive implementation and not a tail call.

You are again contradicting yourself. Previously you were praising OCaml's optimization capabilities and now you are questioning them. Specifically in a case where there is a magic optimization that is explicitly motivated by List.map: https://ocaml.org/manual/5.2/tail_mod_cons.html . A magic optimization implemented using, guess what, mutation.

Post reply on HN