FP²: Fully in-Place Functional Programming

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