[HN Gopher] Functional programming languages should be better at...
___________________________________________________________________
Functional programming languages should be better at mutation than
they are
Author : thunderbong
Score : 52 points
Date : 2024-07-30 19:18 UTC (3 hours ago)
(HTM) web link (cohost.org)
(TXT) w3m dump (cohost.org)
| dave4420 wrote:
| A variant of option 4 is to keep track of references you know
| cannot possibly be shared, and update those by mutation. Compared
| to reference counting, it misses some opportunities for mutation,
| but avoids the false sharing.
|
| I think Roc is doing this.
| zellyn wrote:
| Came here to say this! Last I heard, the Roc folks were still
| curious to see whether this bet pays off for most/all
| codebases.
| sitkack wrote:
| For those following along https://github.com/roc-lang/roc
|
| https://github.com/multikitty/New-Programming-Languages-
| Show...
|
| https://www.youtube.com/watch?v=6qzWm_eoUXM
| cryptonector wrote:
| jq does this. But at the jq language level it looks like
| mutation creates new values without mutating the old ones.
| rocqua wrote:
| To what extent is this already being done by other functional
| blanguages that have CoW mutability? This seems like a legal
| compiler optimization to make in most cases no?
| RandomThoughts3 wrote:
| 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:
|
| > For example, let's say you're iterating over some structure and
| collecting your results in a sequence. The most efficient data
| structure to use here would be a mutable dynamic array and in an
| imperative language that's what pretty much everyone would use.
|
| 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.
|
| 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.
|
| It gets fairly obvious when you realise that most Ocaml
| developers switch to using array when they want to benefit from
| unboxed floats.
|
| The whole article is secretly about Haskell and fails to come to
| the obvious conclusion: Haskell choice of segregating mutations
| in special types and use monads was an interesting and fruitful
| research topic but ultimately proved to be a terrible choice when
| it comes to language design (my opinion obviously not some
| absolute truth but I think the many fairly convoluted tricks
| haskellers pull to somehow reintroduce mutations support it). The
| solution is simple: stop using Haskell.
| senorrib wrote:
| Came here to write exactly this. Thank you.
| runeblaze wrote:
| I second the conclusion as (a brutal conclusion, but still) to
| stop using Haskell. Haskell allows imperative-like code but the
| ergonomics for day-to-day big-tech engineering is far from
| good. The state monad or lens are excellent tools to re-create
| a controlled imperative language in a vacuum, and is frankly
| impressive how much mutation we can conjure up from purity, but
| the error messages or the required understanding of PLT-ish
| things makes it non-scalable to "real" teams.
| devmunchies wrote:
| 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.
| nickpeterson wrote:
| Yeah, F# in general is pretty mutation friendly given how
| functional it is.
| deredede wrote:
| I mostly agree with your sentiment but this:
|
| > 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.
|
| I disagree with. There are different ways to get close to the
| performance of `Array.map` with lists (best case scenario you
| don't care about order and can use `List.rev_map`), but you
| will always have memory (and GC) overhead and so lists are
| strictly inferior to arrays for the presented use case.
| RandomThoughts3 wrote:
| 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.
| deredede wrote:
| 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. They are still going to use more memory, and they
| are unlikely to to be faster than a rope-like structure
| that grows with no copies.
| bjourne wrote:
| 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.
| deredede wrote:
| 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 "tail mod cons"
| optimization that allows to get some of the benefits of
| TCO without needing to reverse the list (this is
| implemented as a program transformation that uses
| mutability under the hood), and that one will only work
| if you are building a single list.
| derdi wrote:
| > 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. Therefore, there is idiomatic code in
| OCaml that will not be as performant as arrays.
|
| > It gets fairly obvious when you realise that most Ocaml
| developers switch to using array when they want to benefit from
| unboxed floats.
|
| This is one example why your statement above is not true.
| RandomThoughts3 wrote:
| > 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 that in other case they will use
| mutations when it makes sense to do so because the compiler
| does not do a good job.
|
| The first paragraph refers to the specific case my comment
| quotes just before: data structure traversal and storage of
| elements in a set.
| senorrib wrote:
| Well, it doesn't make the substance wrong. This paragraph
| rightly summarizes it:
|
| "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."
| lmm wrote:
| > 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?
| ufo wrote:
| One thing that many people miss is that Haskell's monadic style
| is a direct consequence of lazy evaluation. Lazy evaluation has
| its benefits, but it is incompatible with side-effects because
| the order of evaluation is unpredictable.
| kccqzy wrote:
| 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 looked at how hash maps and hash sets
| are implemented in Haskell? It's arrays and mutation!
|
| > And if you only need mutation locally inside a function, using
| ST makes your code fundamentally more imperative in a way that
| really forces you to change your programming style. This isn't
| great either and doesn't exactly help with readability, so the
| mental overhead is rarely worth it.
|
| What?? You are explicitly opting into writing mutation code. Of
| course that's going to change your programming code. It is
| _expected_ to be different. Readability is increased because it
| clearly delineates a different coding style. And it 's not even
| that different from other monadic code, even when you compare to
| non-mutating monadic code.
|
| Terrible article.
| revskill wrote:
| Author wants to avoid ST Monad to do mutation i think.
| pornel wrote:
| > 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<T> and
| clone() to share them. For references, in practice it requires
| making separate `foo()` and `foo_mut()` functions for each type
| of the loan.
|
| Even though this sounds horribly clunky, it works okay in
| practice. Ability to temporarily borrow exclusively owned objects
| as either shared or exclusive-mutable adds enough flexibility.
|
| Rust is known for being difficult, but I think a lot of that is
| due to lack of GC. Rust can't make any reference live longer, and
| programmers have to manually get scopes of loans right, or
| manually use Rc<RefCell> to have a mini DIY GC. Perhaps a shared
| XOR mutable with a GC could be the best of both?
| PaulHoule wrote:
| I learned programming in the 1980s based on examples from the
| 1970s and I would see (and write JNI wrappers for) FORTRAN codes
| in the 1990s that were built around algorithms that could work on
| data in place with minimal duplication of data structures such as
| sorts, FFTs, even when it wasn't obvious that they could do so.
| nmadden wrote:
| I don't know how Swift and Koka handle things, but I've written a
| lot of Tcl that uses the same CoW reference-counting trick. (Tcl
| is an under-appreciated FP language: everything is a string, and
| strings are immutable, so it has had efficient purely declarative
| data structures for decades).
|
| The downside in Tcl is that if you refactor some code suddenly
| you can add a new reference and drop into accidentally quadratic
| territory because now everything is being copied. This leads to
| some cute/ugly hacks that are only explainable in terms of
| interpreter implementation details, purely to reduce a refcount
| in the right spot.
| jonathanyc wrote:
| I'm not even a big OCaml fan (you can use Algolia on my comment
| history...), but this article is just factually wrong.
|
| > For example, let's say you're iterating over some structure and
| collecting your results in a sequence. The most efficient data
| structure to use here would be a mutable dynamic array and in an
| imperative language that's what pretty much everyone would use.
|
| > But if you asked an OCaml programmer, they would almost
| certainly use a linked list instead.
|
| What? One of OCaml's most notable features as a functional
| programming language is how it was designed to support mutation
| (see "the value restriction", e.g.
| https://stackoverflow.com/questions/22507448/the-value-restr...)
| In my own OCaml programs I used mutation whenever appropriate (my
| only complaint would be that I wish there were a little more
| syntactic sugar around e.g. hash table access).
|
| I wanted to like this post but it seems like low-effort
| clickbait.
| ChadNauseam wrote:
| I enjoyed this article. As someone who has written too much
| haskell and ocaml, and now writes mostly Rust, I am biased but I
| think this problem is mostly solved by rust. (The author mentions
| rust in option 3, but I think underappreaciates it.)
|
| The author mentions linear types. This is a bit of a pet peeve of
| mine because, while very useful, linear types are not the concept
| that many people think they are and they are not implemented in
| rust (and neither are affine types). What rust implements is
| referred to as a "uniqueness type".
|
| The difference has to do with how they deal with what linear-
| types-people call "exponentials". A linear type, as the article
| mentions, is the type of a value must be "consumed" exactly once
| (where consuming means passing it into a function, returning it,
| or sometimes destructuring it). Of course, in this mad world of
| ours we sometimes need to consume a value more than once, and
| indeed a language with only linear types would not be turing-
| complete. This escape hatch is called an "exponential", I guess
| because exponential is kind of like the opposite of linear. A
| value with an exponential type can be used as often as you want.
| It is essentially most types in most programming languages.
|
| IF a function expects a value with a linear type, can you pass an
| a value with an exponential type to it? The answer is that you
| can. Try this in linear haskell if you don't believe me. A
| function taking a value with a linear type just says "I consume
| this value exactly once, but you can pass me whatever you want".
| The restriction is that values with linear types can only be
| passed to functions that expect linear types. A value with a
| linear type must be consumed exactly once, so you certainly can't
| pass it to a function that expects a value with an exponential
| type, because it might use that value twice. In other words, a
| linear type is a restriction on the callee.
|
| Those familiar with rust will notice that this is not how rust
| works. If a function takes T, and you have &T, you just cannot
| call that function. (Ignore Clone for now.) However, in the world
| of linear types, this would be allowed. This makes linear types
| not useful for the article's purposes, although they are still
| very useful for other things.
|
| What rust wants is a constraint not provided by linear types.
| Where linear types are a restriction on the callee, rust wants to
| be able to restrict the caller. It wants to be able to restrict
| the caller in such a way that it can know that there are no other
| references to a variable that's been passed into a function.
| People call this a "uniqueness type" because you can say "I want
| this type to be 'unique'" (where 'unique' means not-aliased).
| Honestly this name doesn't make a lot of sense, but it makes a
| little more sense when you think of it in terms of references. If
| a reference is unique, then it means that no other reference that
| points to the same object (which is the requirement rust imposes
| on mutable references). So while a linear type allows you to pass
| a non-linear variable to a function that expects a linear one,
| rust doesn't allow you to pass a non-unique variable to a
| function that expects a unique one.
|
| And adding this requirement to mutations resolves 90% of the
| issues that make mutability annoying. Mutability becomes
| challenging to understand when:
|
| 1. You have multiple references pointing to the same data in
| memory. 2. You change the data using one of these references. 3.
| As a result, the data appears to have changed when accessed
| through any of the other references.
|
| This simply cannot happen when mutability requires values to not
| be aliased.
| armchairhacker wrote:
| > IF a function expects a value with a linear type, can you
| pass an a value with an exponential type to it? The answer is
| that you can. Try this in linear haskell if you don't believe
| me.
|
| > Those familiar with rust will notice that this is not how
| rust works. If a function takes T, and you have &T, you just
| cannot call that function. (Ignore Clone for now.)
|
| I think this is wrong. An exponential type in Rust is a type
| that implements `Copy`. The analogy in Rust is:
| fn linear_fun<T>(x: T) { // ... }
| fn main() { let foo = 5;
| linear_fun(foo); println!(foo); }
|
| And that compiles fine: `foo` is implicitly copied to maintain
| that `linear_fun` owns its parameter.
|
| You can ignore `Clone`, but ignoring `Copy` destroys the
| premise, because without it Rust has no exponential types at
| all.
|
| EDIT: I agree Rust solves the issue of mutability fairly well.
| Furthermore, I think practical linear types can be added to a
| Rust-like type system with Vale's (https://vale.dev/) Higher
| RAII, where a "linear type" is an affine type that can't be
| implicitly dropped outside of its declaring module.
|
| I don't know if this is what Vale does, but to enforce "can't
| be implicitly dropped outside of its declaring module" in Rust
| I would add two changes:
|
| - Whenever the compiler tries to insert implicit drop code for
| a linear type outside of its declaring module, it instead
| raises an error.
|
| - Type parameters get an implicit `Affine` auto-trait, like
| `Sized`. If a type parameter is `?Affine`, the compiler will
| refuse to insert implicit drop code. Standard library generic
| parameters will be `?Affine` wherever possible, e.g. containers
| like `Vec` and `HashSet` will have `T: ?Affine`, but the
| methods that could implicitly destroy an element like
| `HashSet::insert` will have plain `T`.
| rocqua wrote:
| 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. For function parameters it probably gets hairy
| though.
| tome wrote:
| I'm not convinced about the dismissal of option 2. I agree ST is
| clunky but not for the reasons given. It's clunky because it's
| impossible to mix with other effects. What if I want ST _and_
| exceptions, for example, and I want the presence of both to be
| tracked in the type signature? ST can 't do that. But my effect
| system, Bluefin, can. In fact it can mix not only state
| references and exceptions, but arbitrary other effects such as
| streams and IO.
|
| * https://hackage.haskell.org/package/bluefin-0.0.2.0/docs/Blu...
|
| * https://hackage.haskell.org/package/bluefin-0.0.6.0/docs/Blu...
| gloria_mundi wrote:
| 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...
| codebje wrote:
| 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.
| mrkeen wrote:
| Nice, first I'm hearing of bluefin - I'll be sure to check it
| out.
|
| As an aside, I watched an Alexis King stream (which I can't now
| find) in which she did a deep dive into effect systems and said
| something along the lines of: algebraic effect systems should
| not change their behaviour depending on nesting order e.g.
| Either<State<>> vs State<Either<>>.
|
| Does bluefin have a particular philosophy about how to approach
| this?
| narski wrote:
| 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) + fib(n-2)
|
| Right off the bat, performance is O(n)=n*2. Every call to f(n-1)
| will _also_ need to compute f(n-2) anyways! It 's a mess. But
| since Python passes arrays and dictionaries as pointers ( _cough_
| , sorry! I meant to say _references_ ) it's super easy to
| memoize: # optimize-pilled memoize-chad version
| def fib(n, saved={}): if n in saved: return
| saved[n] if n == 0 or n == 1: saved[n]
| = n else: saved[n] = fib(n-1) + fib(n-2)
| return saved[n]
|
| Okay, now our version is nearly as fast as the iterative
| approach.
|
| This is the normal pattern in most languages, memoizing otherwise
| "pure" functions is easy because you can reference a shared
| object using references, right? Even with multithreading, we're
| fine, since we have shared memory.
|
| Okay, but in Hoon, there are no pointers! Well, there kinda are.
| The operating system lets you update the "subject" of your Urbit
| (the context in which your programs run), and you can do this via
| the filesystem (Clay) or daemons (Gall agents, which have their
| own state kind of).
|
| But to do this within a simple function, not relying on fancy OS
| features? It's totally possible, but a huge pain the Aslan.
|
| First, here's our bog-standard fib in Hoon: |=
| n=@ud ?: (lte n 1) n %+ add $(n
| (dec n)) $(n (sub n 2))
|
| Now, I memoize on the way down, by calculating just f(n-1) and
| memoizing those values, to acquire f(n-2): :-
| %say |= [* [n=@ud ~] [cache=(map @ud @ud) ~]] :-
| %noun ^- [sum=@ud cache=(map @ud @ud)] =/ has-n
| (~(get by cache) n) ?~ has-n ?: (lte n 1)
| [n (~(put by cache) n n)] =/ minus-1 $(n (dec n))
| =/ minus-2 =/ search (~(get by cache.minus-1) (sub
| n 2)) ?~ search 0 (need search) :-
| (add sum.minus-1 minus-2) (~(put by cache.minus-1) n (add
| sum.minus-1 minus-2)) [(need has-n) cache]
|
| and that works in the Dojo: > =fib-8 +fib 8
| > sum.fib-8 21
|
| but it sure is easier in Python! And I'm not picking on Hoon
| here, it's just pure functional programming that makes you think
| this way - which as a hacker is fun, but in practice is kinda
| inconvenient.
|
| I even wonder how much faster I actually made things. Let's see:
| > =old now > =res +fib 18 > sum.res 2.584
| > (sub now old) 1.688.849.860.263.936 :: now with the
| non-memoized code... > =before now > +fib 18
| 2.584 > (sub now before) 1.125.899.906.842.624
|
| Ha! My super improved memoized code is actually slower! That's
| because computing the copies of the map costs more than just
| recurring a bunch. This math should change if I try to compute a
| bigger fib number...
|
| Wait. Nevermind. My memoized version is faster. I tested it with
| the Unix time command. It's just that Urbit Dojo has a wierd way
| of handling time that doesn't match my intuition. Oh well, I
| guess I can learn how that works. But my point is, thinking is
| hard, and in Python or JS or C I only have to think in terms of
| values and pointers. And yes, that comes with subtle bugs where
| you think you have a value but you really have a pointer! But
| most of the time it's pretty easy.
|
| Btw sorry for rambling on with this trivial nonsense - I'm a
| devops guy so this is probably super boring and basic for all you
| master hn swe's. But it's just a tiny example of the constant
| frustrations I've had trying to do things that would be super
| simple if I could just grab a reference and modify something in
| memory, which for better or worse, is how every imperative
| language implicitly does things.
| sirsinsalot wrote:
| Note to self: never code Hoon
| anfelor wrote:
| Disclosure: I work on Koka's FBIP optimization (Option 4).
|
| > The most efficient data structure to use here would be a
| mutable dynamic array and in an imperative language that's what
| pretty much everyone would use. But if you asked an OCaml
| programmer, they would almost certainly use a linked list
| instead.
|
| I agree with this sentiment. However, OCaml does have mutable
| arrays that are both efficient and convenient to use. Why would a
| programmer prefer a list over them? In my opinion, the main
| benefit of lists in this context is that they allow pattern
| matching and inductive reasoning. To make functional programming
| languages more suited for array programming, we would thus need
| something like View Patterns for arrays.
|
| A related issue is that mutation can actually be slower than
| fresh allocations in OCaml. The reason for this is that the
| garbage collector is optimized for immutable datastructures and
| has both a very fast minor heap that makes allocations cheap and
| expensive tracking for references that do not go from younger to
| older elements. See: https://dev.realworldocaml.org/garbage-
| collector.html#scroll...
|
| > Unfortunately, this makes it impossible to use any standard
| functions like map on linear values and either makes linearity
| nearly useless or inevitably creates a parallel, incomplete
| universe of functions that also work on linear values.
|
| You can implement polymorphism over linearity: this is done in
| Frank Pfenning's SNAX language and planned for the uniqueness
| types in a branch of OCaml.
|
| > This might sound a little dangerous since accidentally holding
| on to a reference could turn a linear time algorithm quadratic
|
| No, the in-place reuse optimization does not affect the
| asymptotic time complexity. But it can indeed change the
| performance drastically if a value is no longer shared since
| copies are needed then.
|
| > A tracing garbage collector just doesn't give you this sort of
| information.
|
| It is possible to add One-bit Reference Counts to a garbage
| collector, see https://gitlab.haskell.org/ghc/ghc/-/issues/23943
|
| > for now even these struggle to keep up with tracing garbage
| collectors even when factoring in automatic reuse analysis.
|
| I investigated the linked benchmarks for a while. The gap between
| Koka and Haskell is smaller than described in that initial
| comment, but a tuned GHC is indeed a bit faster than Koka on that
| benchmark.
___________________________________________________________________
(page generated 2024-07-30 23:00 UTC)