Reference counting to mutate values in place without losing referential transparency

Has there ever been a discussion about the feasibility of tracking references for values, statically determining if an update can safely be made in-place if there are no other references?

Roc-lang seems to use it to great effect - Hannes: "@haskman@functional.cafe The official answer from…" - JuliaLang, enabling a pure quicksort implementation to ostensibly be close in performance to an imperative solution written in C++.

As an experiment, I wrote a quick and dirty implementation of QuickSort, while performing reference counting at runtime using JS FFI hacks. I’m not sure if there’s a way to write an ergonomic library without compiler support for this, but the code is here in case it’s interesting - Anupam Jain / purescript-linear-experiments · GitLab

Incidentally I quickly ran into the problem with PureScript not supporting mutual tail recursion optimisation, and sorting large arrays blows the stack.

From the same Roc talk - here are some things to contribute to Roc being fast.

Of these, proper tail call optimisation also jumps out as something crucial for performance.

3 Likes

Accurate (and efficient!) reference counting relies on a lot of support from the runtime, so it isn’t possible for JavaScript. There’s nothing PureScript can do to work around it, especially with all the FFI where you don’t know what happens to those references.

1 Like

I’ll keep a reference to this chart for when people claim that targeting JS is too slow as compared to Haskell :smiley:

1 Like