FP^2: Fully in-Place Functional Programming (TR)

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. We describe a linear _fully in-place_ (FIP) calculus where we prove that we can always execute such functions in way that requires no (de)allocation and uses constant stack space. Of course, such calculus is only relevant if we can express interesting algorithms, and we show many examples, including splay trees, finger trees, 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 and uses neither heap- nor stack space. We consider two approaches to embed the FIP calculus in a larger language, either a static approach based on uniqueness typing, or a dynamic approach based on precise reference counting. We have a full implementation based on the dynamic approach in the Koka language and all examples in the paper can be checked and executed fully in-place.