Practical compilation of fexprs using partial evaluation: Fexprs can performantly replace macros in purely-functional Lisp

Abstract

Macros are a common part of Lisp languages, and one of their most lauded features. Much research has gone into making macros both safer and more powerful resulting in developments in multiple areas, including maintaining hygiene, and typed program staging. However, macros do suffer from various downsides, including being second-class. Particularly egregious for eager functional programming, they are unable to be passed to higher-order functions or freely composed. Fexprs, as reformulated by John Shutt, provide a first-class and more powerful alternative to macros that meshes well with pure functional programming. Unfortunately, naive execution of fexprs is much slower than macros due to re-executing unoptimized operative combiner code at runtime that, in a macro-based language, would have been expanded and then optimized at compile time. To show that fexprs can be practical replacements for macros, we formulate a small purely functional fexpr based Lisp, Kraken, with an online partial evaluation and compilation framework that supports first-class, partially-static-data environments and can completely optimize away fexprs that are used and written in the style of macros. We show our partial evaluation and compilation framework produces code that is more than 70,000 times faster than naive interpretation due to the elimination of repeated work and exposure of static information enabling additional optimization. In addition, our Kraken compiler performs better compared to existing interpreted languages that support fexprs, including improving on NewLisp's fexpr performance by 233x on one benchmark.