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

51–60 of 188 posts

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

#51

Post by sans-seraph »

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…

> Ability to temporarily borrow exclusively owned objects as either shared or exclusive-mutable adds enough flexibility.

Rust quietly has several other features in order to improve the quality-of-life of its ownership model. Two examples: if you have a mutable reference then Rust will coerce it to an immutable reference if one is required, and if you have a mutable reference then Rust will transparently re-borrow it when calling functions that accept mutable references in order to allow you to use the mutable reference more than once despite the fact that they do not implement Copy.

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

#52

Post by plorkyeran »

nmadden wrote: post #12

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…

In Swift you occasionally have to introduce a temporary local variable to avoid accidentally quadratic behavior, but I've never seen it require anything complicated or hard to explain.

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

#53

Post by pornel »

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?

There are a couple of proof-of-concept libraries adding a `Gc where T: Traceable`, so it is doable. You can't change the existing Rc, because it's a concrete type. Making it use a tracing GC internally would require a lot of compiler magic.

However, I don't think a GC will catch on in Rust in its current form. Rust's userbase likes it as a no-GC language. Plus a 3rd party library GC wrapper type can't save you from having to learn ownership and lifetimes used by literally everything else. Once you invest time to learn the "zero-cost" references, a runtime Gc is less appealing, and won't be as ergonomic than the built-in references.

Swift, OCaml, and Mojo are trying to add some subset of Rust-like ownership and borrowing, but in a simpler form.

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

#54

Post by gloria_mundi »

dullcrisp wrote: post #49
codebje wrote: post #35

Earlier quoted context omitted.

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).

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`.

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

#55

Post by nine_k »

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

The standard way to expel stated mutable state us to push it into function parameters and returned values.

With Fibonacci numbers, you cab just compute two if them outright:

  def fib_(n: int) -> tuple[int, int]:
    if n == 0:
      return (1, 1)
    prev, this = fib_(n - 1)
    return (this, this + prev)

  def fib(n): return fib_(n)[0]
Now there is no mutable state that survives between function calls, the performance is linear.

With true memoization though accessing a previously computed value.would be constant time.

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

#56

Post by devit »

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 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 and use borrowing normally) due to the absurd behavior of scanning most of the heap at arbitrary times, there is no Rust GC crate in widespread use.

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

#57

Post by wittystick »

rocqua wrote: post #26
dave4420 wrote: post #2

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.

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?

Clean has been doing this for nearly as long as people have been using monads, but it never got the attention Haskell did, which I think is quite unfortunate. Rather than implictly keeping track of references, uniqueness types are marked explicitly to inform that their values cannot be aliased. They can also be used with monads to improve ergonomics a bit.

Granule has uniqueness types like Clean built onto a linear type system, which offers some additional advantages.

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

#58

Post by burntcaramel »

plorkyeran wrote: post #52
nmadden wrote: post #12

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…

In Swift you occasionally have to introduce a temporary local variable to avoid accidentally quadratic behavior, but I've never seen it require anything complicated or hard to explain.

Curious about an example of this in Swift? Is it a variable holding a collection like an Array?

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

#59

Post by projektfu »

wittystick wrote: post #57
rocqua wrote: post #26

Earlier quoted context omitted.

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?

Clean has been doing this for nearly as long as people have been using monads, but it never got the attention Haskell did, which I think is quite unfortunate. Rather than implictly keeping track of references, uniqueness types are marked explicitly to inform that their values cannot be aliased. They can also be used with monads to improve ergonomics a bit. Granule has uniqueness types like Clean built onto a linear t…

Is Clean being used anywhere? Last time I looked at it was 1999 and, while cool, I haven't ever heard of anyone using it.

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

#60

Post by astrange »

runeblaze wrote: post #7
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 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 understandi…

Haskell almost seems like it was intentionally designed to perform poorly on real computers, primarily because of space leaks and secondarily because the non-strict evaluation gets compiled into a lot of function pointer jumps, which branch predictors hate.

I think it's funny that they make you write linked list code as a metaphor for generators, but it seems like it should be the other way round.

(Also, it has exceptions which are a bad language feature, and typed throws which are a worse one.)

Post reply on HN