FP2: Fully in-Place Functional Programming

Anton Lorenzen, Daan Leijen, Wouter Swierstra

Research output: Contribution to journalArticleAcademicpeer-review

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
Original languageEnglish
Article number198
Pages (from-to)275–304
Number of pages30
JournalProceedings of the ACM on Programming Languages
Volume7
Issue numberICFP
DOIs
Publication statusPublished - 30 Aug 2023

Keywords

  • FBIP
  • Tail Recursion Modulo Cons

Fingerprint

Dive into the research topics of 'FP2: Fully in-Place Functional Programming'. Together they form a unique fingerprint.

Cite this