Sebastian Ullrich, Leonardo de Moura
2019 · arXiv
Most functional languages rely on some garbage collection for automatic memory management. They usually eschew reference counting in favor of a tracing garbage collector, which has less bookkeeping overhead at runtime. On the other hand, having an exact reference count of each value can enable optimizations, such as destructive updates. We explore these optimization opportunities in the context of an eager, purely functional programming language. We propose a new mechanism for efficiently reclaiming memory used by nonshared values, reducing stress on the global memory allocator. We describe an approach for minimizing the number of reference counts updates using borrowed references and a heuristic for automatically inferring borrow annotations. We implemented all these techniques in a new compiler for an eager and purely functional programming language with support for multi-threading. Our preliminary experimental results demonstrate our approach is competitive and often outperforms state-of-the-art compilers.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
8 selected excerpts · 8 total mentions
There might even be some possibility for cross-pollination with ideas such as Counting Immutable Beans [0]. I’ve long wondered if there could be a functional programming language that made static memory management less verbose and easier to manage without monads and other explicit structures. [0] https://arxiv.org/abs/1908.05647
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
Yeah, I believe they said they intend for it to be used as a general purpose programming language. I used it to complete Advent of Code last year. There are some really interesting features for general purpose programming in there. For example: you can code updates to arrays in a functional style (change a value, get a new array back), but if the refcount is 1, it updates in place. This works for inductive types and structures, too. So I was able to efficiently use C-style arrays (O(1) update/lookup) while writing functional code. (paper: https://arxiv.org/abs/1908.05647 ) Another interesting feature is that the "do" blocks include mutable variables and for loops (with…
continue / break / return), that gets compiled down to monad operations. (paper: https://dl.acm.org/doi/10.1145/3547640 ) And I'm impressed that you can add to the syntax of the language, in the same way that the language is implemented, and then use that syntax in the next line of code. (paper: https://lmcs.episciences.org/9362/pdf ). There is an example in the source repository that adds and then uses a JSX-like syntax. (https://github.com/leanprover/lean4/blob/master/tests/playgr... )
I'm sure the details are different, but the general idea, to me, seems the same as the one descibed by Leo and Sebastian in https://arxiv.org/abs/1908.05647. Both Koka and Lean 4 use reference counting to know if it's safe to reuse a structure. This paper (Daan is a collegue of Leo at MS Research) gives a different formalization and proofs. The file is still named "fbip.pdf" though :)
> When I think of how the java streams API is used, it generates lots of garbage (i.e. lots of intermediary allocs) Not extremely relevant because it’s Lean 4 and not Java, but destructive updates can help with that: https://arxiv.org/pdf/1908.05647.pdf Edit: Now linking to the right paper.
I am really enjoying lean 3 as a theorem prover; lean 4 as a programming language is a really intriguing/enticing prospect. The "functional but in place" paradigm is something quite new, as far as I can tell. For reference, see the "Counting Immutable Beans" paper[1] by the designers of the language, that details how the runtime makes use of reference counts to do destructive updates in pure code whenever possible. [1]: https://arxiv.org/pdf/1908.05647.pdf
The Lean developers put out a paper about v4's reference counting last year which shows that in basic benchmarks, Lean 4 is in the same ballpark as Haskell, Swift, and ML. https://arxiv.org/abs/1908.05647
A paper I quite enjoyed on automatic reference counting for pure, immutable functional programming: https://arxiv.org/abs/1908.05647 It can be quite "fast."
More from the same topics.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
David Manheim, Scott Garrabrant
There are several distinct failure modes for overoptimization of systems on the basis of metrics.
Ross Mcilroy, Jaroslav Sevcik, Tobias Tebbi +2
The recent discovery of the Spectre and Meltdown attacks represents a watershed moment not just for the field of Computer Security, but also of Programming Languages.
Daniel Ingalls
This paper presents a personal view of the evolution of six generations of Smalltalk in which the author played a part, starting with Smalltalk-72 and progressing through Smalltalk-80 to Squeak and Etoys.