Hacker News Reader

Comment by yashrk | Hacker News Reader

If you are interested, «why yet another programming language?».

The unique selling point of Roc is clever optimization to convert purely functional source code to deep-imperative fast machine code, while keeping all the correctness of functional algorithms.

See this video of Richard Feldman for details — «Outperforming Imperative with Pure Functional Languages»: https://www.youtube.com/watch?v=vzfy4EKwG_Y

Among those clever optimizations:

- static reference counting (no GC, like in Rust, but with no borrowing and borrow problems);

- stack allocation of the data with no external links;

- hidden («opportunistic») mutability even in the cases, where Haskell or Lisp will copy the value.

edit:markup

View on HN

> convert purely functional source code to deep-imperative fast machine code, while keeping all the correctness of functional algorithms.

All functional language compilers, interpreters, and/or runtimes ultimately have to do this by definition. The efficiency of transpilation varies widely.

Definition of resulting code as _deeply_ imperative was crucial in my phrase.

The only «sine qua non» optimization through opportunistic mutablity is AFAIK tail call optimization. But it is probably too well-known to call it «clever optimization» in 2023.

But, for example, applying a function to a list will produce the code allocating new list in, say, OCaml and Haskell, at least by default. And Roc will produce the code for mutating the list in-place _from the source code with the same semantic_ (see example for the Quicksort algorithm in the video above).

Compile-time lifetime analysis (that probably is not needed at all in functional languages with GC) and widely used unboxed values are way not common in functional language implementations. For example, in OCaml those features are still experimental (and probably never will be used by default, as in Roc).

I’d say that’s one of a few unique selling points. Some others I noticed:

- side effects are strictly relegated to async effects, eg all I/O calls return a future

- declarative static loading as imports

> - static reference counting (no GC, like in Rust, but with no borrowing and borrow problems);

Does this mean that it's somewhat equivalent to Rust with everything behind a `Rc` or `Arc`?

Rc and Arc traits are implementations of the _runtime_ reference counters. Runtime reference counting is sometimes less efficient than tracing GC.

But Roc counts references in _compile_ time. So it's like _usual_ (not wrapped in Rc<>) values in Rust. But in Rust the value is deleted from the heap when the stack frame with the _only_ link to it («the owner») is deleted. And in Roc the value is deleted from the heap, when the _last_ link to it leaves the stack.

So we have the machine code _almost_ as efficient as a Rust-produced machine code, but the source code with a much simpler semantics.

Do you have a written source for this? What you're describing is nice, but I can see so many basic cases in which it doesn't work, at least not without a borrow analysis much more sophisticated than Rust's, that I imagine I'm missing something.

Example: A linked list.

Nitpick: Rc and Arc are not traits.

Two main papers about this topic AFAIK are: «Counting Immutable Beans» by Sebastian Ullrich and Leonardo de Moura (https://arxiv.org/pdf/1908.05647.pdf) and «Perceus: Garbage Free Reference Counting with Reuse» by Alex Reinking, Ningning Xie,Leonardo de Moura, Daan Leijen (https://dl.acm.org/doi/pdf/10.1145/3453483.3454032).

See also Anton Felix Lorenzen's master thesis: https://antonlorenzen.de/master_thesis_perceus_borrowing.pdf

Mr. Feldman also mentioned some «alias analysis» library «Morphic Solver» from Berkley University, but I cannot find anything about it.

BTW compile time reference counting was already discussed on HN, for example here: https://news.ycombinator.com/item?id=19567666

> Example: A linked list.

IIUC recursive data structures like linked list and trees are not the problem for the static reference counting. Mutation (and, therefore, link cycles) _is_ a problem, but Roc is a clean language with no explicit mutation. =)

> I can see so many basic cases in which it doesn't work

Sometimes runtime reference counting is still used. But, of course, in way more complex situations than just processing a linked list.

> Nitpick: Rc and Arc are not traits.

Of course, my fault. I haven't written on Rust for a long time (and never used this language in a serious project).

edit: link added

Thanks!

I found what is «Morphic», mentioned by Richard Feldman.

It's an another experimental programming language with the static reference counting. «Morphic uses a borrow-based reference counting scheme which is able to eliminate almost all reference count increments and decrements for a large class of programs»ⓒMorphic developer team.

Site: https://morphic-lang.org/

Paper: https://dl.acm.org/doi/10.1145/3591260

Thanks, it makes sense now!

I think I've read a post by Niko Matskakis (Rust lead) who suggested doing something similar. That would be exciting to see!

That sounds a lot like Koka. Is there any relationship?

See https://news.ycombinator.com/item?id=38350940

Reply on news.ycombinator.com