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

71–80 of 188 posts

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

#71

Post by deredede »

senorrib wrote: post #44
deredede wrote: post #24

Earlier quoted context omitted.

I think `Array.map` is a perfectly reasonable reading of "you're iterating over some structure and collecting your results in a sequence". But sure, in the `fold` scenario where you don't know the number of results in advance (you are more likely to know if you use imperative data structures, e.g. `Hashtbl.length` is constant-time whereas `Map.cardinal` is not), lists might be faster than growing arrays with copies.…

It isn’t. There’s no guarantee that .map will be processed in sequence. In fact, .map is usually a great candidate for parallelization.

The "sequence" in the problem statement does not refer to the order of operations but to the data structure storing the results.

A parallel `Array.map` still computes a sequence, even though it may not compute in sequence.

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

#72

Post by dllthomas »

dullcrisp wrote: post #61
gloria_mundi wrote: post #54

Earlier quoted context omitted.

Remember that transformers are "inside-out", i.e. `StateT (ExceptT e m) a` is isomorphic to `m (Except e (State a))`. If we want to keep state if an exception occurs, you need a `m (State (Except e a))` which is `ExceptT e (StateT m) a`.

Yeah I could never keep this straight

The way I remembered it, before I internalized it, was to think about applying the run functions one at a time. runSomethingT will take a `SomethingT ... m ... a` and give you some kind of `m (... a)`.

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

#73

Post by deredede »

bjourne wrote: post #48
deredede wrote: post #37

Earlier quoted context omitted.

You can benefit from TCO while building multiple lists. let rec f evens odds = function | [] -> (evens, odds) | x :: xs -> if x mod 2 = 0 then f (x :: evens) odds xs else f evens (x :: odds) xs OCaml optimizes this fairly well and will compil it down to a single loop with two variables. If you reverse the lists there is going to be additional loops (and corresponding allocations). However OCaml also provides the "tai…

I think HN ate some characters because that code doesn't look valid. But yeah, that's how you do it. In my opinion it is not pretty (e.g., what if you have some mutable context?). I also don't see how OCaml could turn the cons operations into dynamic array appends.

> I think HN ate some characters because that code doesn't look valid.

The OCaml compiler disagrees with you ;)

It also won't ever turn a cons operation into a dynamic array append.

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

#74

Post by kqr »

kccqzy wrote: post #5

The author didn't write a good objection to option 2. Both the ST monad (real mutations) and the variety of State monads (simulated mutations) work fine in practice. What's even better is the STM monad, the software transactional memory monad that is not only about mutations but also solves synchronization between threads in a way that's intuitive and easy to use. But let's stick to the ST monad. Has the author looke…

Also optics like lenses, traversals and prisms make State-based mutation very syntactically convenient.

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

#75

Post by injuly »

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…

> which is as performant than using mutable array.

I get what you're trying to say, but that is provably false. As great as the OCaml compiler is, it currently is not capable of the aggressive optimizations that GHC can do with lists.

More often than not, the compiler mostly won't have enough static assertions to reliably generate machine code like that in a real world application (unless explicit mutation is used, of course).

> Functional programmers just trust that their compiler will properly optimize their code.

Precisely. This is why having safe local mutation as a language level feature can give more control to the programmer. We no longer have to rely on the compiler to correctly guess whether a routine is better expressed as an array or a cons list.

> The whole article is secretly about Haskell.

and ML, Koka, Clean, Mercury. The article is about allowing local mutation without breaking referential transparency at the language level.

"Stop using haskell" is a very shallow conclusion, IMO.

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

#76

Post by tsimionescu »

devit wrote: post #56
Buttons840 wrote: post #45

Earlier quoted context omitted.

Aside: Could a Rust library provide an Rc interface but use a more sophisticated GC algorithm underneath?

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're basically trading runtime efficiency for memory.

2. GC performance is harder to predict and reason about than certain other allocation strategies

3. GC languages tend to encourage excessive heap allocation for various reasons, ending up with much more junk than a typical Rust or C program that has a similar amount of entities

Note that item 2 is the one that's least understood. The best part about GCs is that they make heap allocation trivial, and they make de-allocation a no-op. In contrast, both malloc() and free() are extremely complex and costly operations. The GC does impose a cost on every pointer write, similar to (but typically less than) the overhead of Arc over a T*, but that has a very uniform and predictable cost. The problem of unpredictability only comes in the collection phase, and is mostly related to (a) when the collection happens, (b) how much data actually has to be scanned (how many live objects are present on the heap and stack), and (c) what type of collection needs to happen (is it enough to collect from this thread's young generation, or do you need to collect all generations from all threads).

Note that many of these problems are in fact solvable, and there actually exist GCs with constant predictable collection times, suitable even for realtime applications (which malloc/free don't support). They are very sophisticated technology that no one is distributing for free though (e.g. you have to pay Azul for a realtime-compatible Java).

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

#77

Post by devbent »

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…

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.

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

#78

Post by Someone »

rocqua wrote: post #25

How come the CoW method requires runtime reference counting? A lot of the same benefit (but not all) should be available based on static analysis right? Especially if the approach isn't really Copy on Write, but Copy only when someone might want to use the old value. Default to trying to mutate in place, if you can prove that is safe. For most locals, that should be rather doable, and it would be a pretty big gain. F…

> How come the CoW method requires runtime reference counting?

Because it doesn’t do copy-on-read, you have to know whether there are references other than yours that can read the data. A single bit “at some time there were at least two references to it” doesn’t suffice, as it would mean you can’t detect when the last reference goes away, so it would leak memory (lots of it)

> A lot of the same benefit (but not all) should be available based on static analysis right?

That’s an (very important) implementation detail that makes reference counting perform reasonably well. You don’t want increase-decrease cycles in tight loops, for example.

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

#79

Post by fire_lake »

ufo wrote: post #38
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…

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.

I think this is historically wrong. Monads didn’t land until later in Haskell, no?

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

#80

Post by derdi »

derdi wrote: post #41
RandomThoughts3 wrote: post #20

Earlier quoted context omitted.

> This is one example why your statement above is not true. You are misreading my comment. I’m not intentionally contradicting myself in two paragraphs next to each other (I’m not always the brightest but still). 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 th…

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

Oops, this had a performance bug. Instead of:

    if d.length = Array.length d.values then begin
      d.values
the array reallocation should actually be:

    if d.length = Array.length d.values then begin
      let new_array = Array.make (Array.length d.values * 2) x in
      Array.blit d.values 0 new_array 0 (Array.length d.values);
      d.values
otherwise we allocate about a third more memory than needed. It's telling that even with this performance bug the dynamic array was broadly better than lists.

New results for the previously slowest cases:

    -- 25_000_000 elements --
    list:        0.977002 sec
    list:        0.963903 sec
    list:        0.950473 sec
    dynarray:    1.476165 sec
    dynarray:    1.281724 sec
    dynarray:    1.343222 sec
    my dynarray: 0.872558 sec
    my dynarray: 0.755902 sec
    my dynarray: 0.753746 sec
    
    -- 50_000_000 elements --
    list:        1.914777 sec
    list:        1.886989 sec
    list:        1.542614 sec
    dynarray:    2.922376 sec
    dynarray:    2.783559 sec
    dynarray:    2.537473 sec
    my dynarray: 1.725873 sec
    my dynarray: 1.545252 sec
    my dynarray: 1.515591 sec
    
    -- 75_000_000 elements --
    list:        2.827154 sec
    list:        2.835789 sec
    list:        2.318733 sec
    dynarray:    4.354404 sec
    dynarray:    4.150271 sec
    dynarray:    3.781488 sec
    my dynarray: 1.887360 sec
    my dynarray: 1.929286 sec
    my dynarray: 1.814873 sec
This turns an uneasy head-to-head into a clear win for dynamic arrays. Honestly, how could it be otherwise?
Post reply on HN