Compiling with Command Trees

Bernard Bot


Date: Wed, May 19, 2021
Time: 10:00
Room: Eelco's Zoom Room
Note: This is a MSc thesis defense


Compilers translate high-level source code into low-level machine code. To represent source code a compiler uses a language called the intermediate representation. An intermediate representation for the compilation of functional languages is continuation-passing style [21, 2]. It provides convenient abstractions for both data flow and control flow.

In this thesis we develop an IR based on CPS using the command tree data structure [19]. Command trees allow us to express compiler transformations typically, declaratively and modularly. The monadic nature of command trees allows us to bind commands together in a succinct manner.

We test the usefulness of the new IR by building two versions of the LamToWat compiler that translates the lamdba calculus into WebAssembly. The first version will use a CPS IR and the second version a command tree IR.

[2] Andrew W. Appel. Compiling with Continuations (corr. version). Cambridge University Press, 2006. isbn: 978-0-521-03311-4. [19] Casper Bach Poulsen. Compilers for Free. http://casperbp.net/posts/2020-04-compilers-for-free/draft/#free-monad. Accessed: 2020-12-06. [21] Guy L Steele Jr. “Rabbit: A compiler for Scheme”. In: (1978).

Previous: |
Next: |