Abstract
As functional programmers we always face a dilemma: should we write purely functional code, or sacrifice
purity for efficiency and resort to in-place updates? This paper identifies precisely when we can have the
best of both worlds: a wide class of purely functional programs can be executed safely using in-place updates
without requiring allocation, provided their arguments are not shared elsewhere.
We describe a linear fully in-place (FIP) calculus where we prove that we can always execute such functions
in a way that requires no (de)allocation and uses constant stack space. Of course, such a calculus is only
relevant if we can express interesting algorithms; we provide numerous examples of in-place functions on
datastructures such as splay trees or finger trees, together with in-place versions of merge sort and quick sort.
We also show how we can generically derive a map function over any polynomial data type that is fully
in-place. Finally, we have implemented the rules of the FIP calculus in the Koka language. Using the Perceus
reference counting garbage collection, this implementation dynamically executes FIP functions in-place
whenever possible.
Why are you interested in it or why should it be a good idea?
Interesting topic for student project of a manageable scale.
FP^2: Fully in-Place Functional Programming Anton Lorenzen, Daan Leijen, Wouter Swierstra
ICFP 2023
PDF
Abstract As functional programmers we always face a dilemma: should we write purely functional code, or sacrifice purity for efficiency and resort to in-place updates? This paper identifies precisely when we can have the best of both worlds: a wide class of purely functional programs can be executed safely using in-place updates without requiring allocation, provided their arguments are not shared elsewhere.
We describe a linear fully in-place (FIP) calculus where we prove that we can always execute such functions in a way that requires no (de)allocation and uses constant stack space. Of course, such a calculus is only relevant if we can express interesting algorithms; we provide numerous examples of in-place functions on datastructures such as splay trees or finger trees, together with in-place versions of merge sort and quick sort.
We also show how we can generically derive a map function over any polynomial data type that is fully in-place. Finally, we have implemented the rules of the FIP calculus in the Koka language. Using the Perceus reference counting garbage collection, this implementation dynamically executes FIP functions in-place whenever possible.
Why are you interested in it or why should it be a good idea?
Interesting topic for student project of a manageable scale.