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

41–50 of 188 posts

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

#41

Post by derdi »

RandomThoughts3 wrote: post #20
derdi wrote: post #16

Earlier quoted context omitted.

> Well, no, this is straight confusion between what’s expressed by the program and what’s compiled. The idiomatic code in Ocaml will end up generating machine code which is as performant than using mutable array. This cannot be true in general. There are machine code patterns for which arrays are faster than linked lists. The OCaml compiler, great as it is, won't turn linked list source code into array machine code.…

> 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 data structure? It can't. Not in general.

And maybe not in the specific case either:

> The first paragraph refers to the specific case my comment quotes just before: data structure traversal and storage of elements in a set.

So, this: https://ocaml.org/play#code=bW9kdWxlIE15X2R5bmFycmF5ID0gc3Ry...

    $ for len in 5_000_000 10_000_000 25_000_000; do echo "-- ${len} elements --"; ./a.out list $len; ./a.out dynarray $len; ./a.out my_dynarray $len; echo; done
    -- 5_000_000 elements --
    list:        0.191551 sec
    list:        0.196947 sec
    list:        0.192806 sec
    dynarray:    0.301362 sec
    dynarray:    0.268592 sec
    dynarray:    0.266118 sec
    my dynarray: 0.163004 sec
    my dynarray: 0.142986 sec
    my dynarray: 0.143634 sec
    
    -- 10_000_000 elements --
    list:        0.377447 sec
    list:        0.367951 sec
    list:        0.312575 sec
    dynarray:    0.607158 sec
    dynarray:    0.582378 sec
    dynarray:    0.538621 sec
    my dynarray: 0.319705 sec
    my dynarray: 0.296607 sec
    my dynarray: 0.286634 sec
    
    -- 25_000_000 elements --
    list:        0.971244 sec
    list:        0.953493 sec
    list:        0.922049 sec
    dynarray:    1.515892 sec
    dynarray:    1.319543 sec
    dynarray:    1.328461 sec
    my dynarray: 1.119322 sec
    my dynarray: 0.971288 sec
    my dynarray: 0.973556 sec
    
    -- 50_000_000 elements --
    list:        1.852812 sec
    list:        1.848514 sec
    list:        1.505391 sec
    dynarray:    3.065143 sec
    dynarray:    2.941400 sec
    dynarray:    2.672760 sec
    my dynarray: 2.115499 sec
    my dynarray: 1.963535 sec
    my dynarray: 1.995470 sec
    
    -- 75_000_000 elements --
    list:        2.942536 sec
    list:        2.910063 sec
    list:        2.354291 sec
    dynarray:    4.567284 sec
    dynarray:    4.342670 sec
    dynarray:    3.979809 sec
    my dynarray: 2.528073 sec
    my dynarray: 2.225738 sec
    my dynarray: 2.226844 sec
A simple dynamic array implementation (my_dynarray) beats a list over a wide range of lengths. But not at all lengths! OCaml's built-in Dynarray is not competitive, but that's because it wants to make certain strong guarantees.

To be clear, I agree with your general point that we can do just fine writing nice clean pure functional OCaml code for most of our code and can hand-optimize where needed. But your very specific claims rub me the wrong way.

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

#42

Post by derdi »

lmm wrote: post #28
derdi wrote: post #16

Earlier quoted context omitted.

> Well, no, this is straight confusion between what’s expressed by the program and what’s compiled. The idiomatic code in Ocaml will end up generating machine code which is as performant than using mutable array. This cannot be true in general. There are machine code patterns for which arrays are faster than linked lists. The OCaml compiler, great as it is, won't turn linked list source code into array machine code.…

> The OCaml compiler, great as it is, won't turn linked list source code into array machine code. Why not? If the compiler can see that you have a short-lived local linked list and are using it in a way for which an array would be faster, why would it not do the same thing that an array would do?

> Why not?

Because it doesn't. Doesn't mean it couldn't, if it tried hard enough. But it doesn't, as a statement of current fact.

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

#43

Post by kazinator »

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…

And not even always how the code is compiled. Canned runtime library routines can you destructive techniques to produce their outputs. The program doesn't see an aggregate object until the function returns it. (If we set aside lazy structures for a moment, but those are actually another example of something that can be built destructively under the hood. As you probably more deeply into the object it is mutated to make more of it materialize.)

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

#44

Post by senorrib »

deredede wrote: post #24
RandomThoughts3 wrote: post #17

Earlier quoted context omitted.

That’s not what the article is talking about. The proposed exemple is a traversal of a different data structure to collect results in an array. That’s a fold and will properly be tco-ed to something equivalent to adding to an array if you use list cons in the aggregation, might actually be better depending on how much resizing of the array you have to do while traversing.

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.

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

#45

Post by Buttons840 »

pornel wrote: post #8

> Rust's shared XOR mutable references […] makes linearity nearly useless or inevitably creates a parallel, incomplete universe of functions that also work on linear values. Yup. Rust can't abstract over mutability. For owned values, it defaults to exclusive ownership, and needs explicit Rc and clone() to share them. For references, in practice it requires making separate `foo()` and `foo_mut()` functions for each ty…

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

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

#46

Post by creata »

Buttons840 wrote: post #45
pornel wrote: post #8

> Rust's shared XOR mutable references […] makes linearity nearly useless or inevitably creates a parallel, incomplete universe of functions that also work on linear values. Yup. Rust can't abstract over mutability. For owned values, it defaults to exclusive ownership, and needs explicit Rc and clone() to share them. For references, in practice it requires making separate `foo()` and `foo_mut()` functions for each ty…

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

You probably already know this, but the gc crate is an implementation of a somewhat more sophisticated GC, but it uses `derive`s to implement tracing, so it's not exactly the Rc interface.

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

#47

Post by dllthomas »

codebje wrote: post #35
gloria_mundi wrote: post #31

Earlier quoted context omitted.

Isn't mixing of effects exactly what monad transformers are for? AFAICT you want an `ExceptT e ST` for some exception type `e`. https://hackage.haskell.org/package/mtl-2.3.1/docs/Control-M...

Yes, but transformers have a few drawbacks: the order of stacking alters behaviour, and you need to write n^2 instances for n transformers. Compare ExceptT e (StateT m a) and StateT (ExceptT e m a): if you just want your computation to have state and exceptions the difference shouldn’t matter.

> if you just want your computation to have state and exceptions the difference shouldn’t matter

But... you don't just want that. You almost certainly care whether state changes are discarded when an exception is thrown. I don't claim that the types there are the most obvious or natural way to specify that, but there is a meaningful difference that shouldn't be handwaved away.

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

#48

Post by bjourne »

deredede wrote: post #37
bjourne wrote: post #36

Earlier quoted context omitted.

Works if you are building one list, but what if you are building multiple? What's suggested on the OCaml site and what's taught in most of academia is to use a recursive function with accumulator arguments that are reversed before returning to make the function tco:able. I doubt OCaml can optimize that pattern well, but idk.

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.

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

#49

Post by dullcrisp »

codebje wrote: post #35
gloria_mundi wrote: post #31

Earlier quoted context omitted.

Isn't mixing of effects exactly what monad transformers are for? AFAICT you want an `ExceptT e ST` for some exception type `e`. https://hackage.haskell.org/package/mtl-2.3.1/docs/Control-M...

Yes, but transformers have a few drawbacks: the order of stacking alters behaviour, and you need to write n^2 instances for n transformers. Compare ExceptT e (StateT m a) and StateT (ExceptT e m a): if you just want your computation to have state and exceptions the difference shouldn’t matter.

I might have this wrong but I think if you want state and exceptions you probably want StateT (ExceptT e m a). The alternative would be to have state or exceptions, i.e. when you have an exception you no longer have state (which might be a legitimate type in some cases).

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

#50

Post by phillipcarter »

devmunchies wrote: post #10
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…

I use f# daily at my company and am actually glad that many dotnet api integrations use array buffers (e.g. a byte array for streaming) this forces me to optimize the f# code by thinking in terms of low-memory, mutable data structures when interfacing with external libraries.

Yep, and moreover, the combination of most library design and general culture around the language reinforces the dynamic of using mutability only when it's needed or the most straightforward way to implement something, and contain that with immutable interfaces wherever possible.

I like to think we helped with this several years ago when making official guidance: https://learn.microsoft.com/en-us/dotnet/fsharp/style-guide/...

Post reply on HN