2021 · 31 citations · 30 references
ComputingComputer EngineeringComputer ScienceAlgorithmsCompilersProgramming LanguagesControl-flow AnalysisData-flow AnalysisGarbage CollectionCode Reuse AnalysisFunctional Language DesignReference CountingTail Call Optimization
We introduce Perceus, an algorithm for precise reference counting with reuse and specialization. Starting from a functional core language with explicit control-flow, Perceus emits precise reference counting instructions such that (cycle-free) programs are _garbage free_, where only live references are retained. This enables further optimizations, like reuse analysis that allows for guaranteed in-place updates at runtime. This in turn enables a novel programming paradigm that we call _functional but in-place_ (FBIP). Much like tail-call optimization enables writing loops with regular function calls, reuse analysis enables writing in-place mutating algorithms in a purely functional way. We give a novel formalization of reference counting in a linear resource calculus, and prove that Perceus is sound and garbage free. We show evidence that Perceus, as implemented in Koka, has good performance and is competitive with other state-of-the-art memory collectors.
30
The Art of Computer Programming
W.J. Worlton · Nuclear Science and Engineering · 1968 · 2.3K citations
A Syntactic Approach to Type Soundness
Andy Wright, Matthias Felleisen · Information and Computation · 1994 · 1.1K citations
A dichromatic framework for balanced trees
Leo J. Guibas, Robert Sedgewick · 1978 · 658 citations