ICFP 2023
Mon 4 - Sat 9 September 2023 Seattle, Washington, United States
Thu 7 Sep 2023 11:00 - 11:30 at A - Grand Ballroom 2 - Language design Chair(s): Peter Thiemann

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.

Thu 7 Sep

Displayed time zone: Pacific Time (US & Canada) change

10:30 - 12:00
Language designICFP Papers and Events at A - Grand Ballroom 2
Chair(s): Peter Thiemann University of Freiburg, Germany
The Verse Calculus: A Core Calculus for Deterministic Functional Logic ProgrammingDistinguished Paper
ICFP Papers and Events
Lennart Augustsson Epic Games , Joachim Breitner unaffiliated, Koen Claessen Epic Games, Ranjit Jhala Epic Games, Simon Peyton Jones Epic Games , Olin Shivers Epic Games, Guy L. Steele Jr. Oracle Labs, Tim Sweeney Epic Games
FP²: Fully in-Place Functional Programming
ICFP Papers and Events
Anton Lorenzen University of Edinburgh, Daan Leijen Microsoft Research, Wouter Swierstra Utrecht University, Netherlands
DOI Pre-print
LURK: Lambda, the Ultimate Recursive Knowledge (Experience Report)Experience Report
ICFP Papers and Events
Nada Amin Harvard University, John Burnham Lurk Lab, François Garillot Lurk Lab, Rosario Gennaro Protocol Labs, Chhi’mèd Künzang Lurk Lab, Daniel Rogozin University College London, Cameron Wong