compile-arith

Arithmetic expression compiler

An interpreter and compiler for a language of arithmetic expressions.

The correctness of compilation and pretty printing are tested with property-based tests implemented using the qcheck library.

Compiler overview

Language	Description
Tree_lang	Arithmetic expressions as a tree of nested subexpressions
Anf_lang	Arithmetic expressions in A-Normal Form
Stack_lang	Arithmetic expressions as stack machine instructions

Translation		Source		Target
Tree_to_anf	:	Tree_lang	→	Anf_lang
Tree_to_stack	:	Tree_lang	→	Stack_lang

Compilation Targets

The compiler currently targets the following intermediate languages:

Stack machine instructions

This is similar to what can be found in stack based languages like Forth and Java bytecode:

$ arith compile --target=stack <<< "1 + -2 * 7"
int 1;
int 2;
neg;
int 7;
mul;
add;

A-Normal Form

This defines an intermediate binding for each computation. This is close to the three-address code found in many optimising compilers.

$ arith compile --target=anf <<< "1 + -2 * 7"
let e0 := neg 2;
let e1 := mul e0 7;
add 1 e1

A-Normal Form

This defines an intermediate binding for each computation. This is close to the three-address code found in many optimising compilers.

$ arith compile --target=anf <<< "1 + -2 * 7"
let e0 := neg 2;
let e1 := mul e0 7;
add 1 e1

This implementation is extended with conditionals and let expressions in the compile-arithcond project.

Resources

Stack Machines

• “Efficiently Implementing the Lambda Calculus With Zinc”, Andre Popovitch 2021 [URL]
• “Functional programming languages, Part II: abstract machines”, Xavier Leroy 2015 [Slides]
• “From Krivine’s machine to the Caml implementations”, Xavier Leroy 2005 [Slides]

A-Normal Form

• “A-Normalization: Why and How”, Matt Might [URL]
• “The essence of compiling with continuations”, Flanagan et al. 1993 [DOI]

Property based testing for compilers

• “Effect-Driven QuickChecking of Compilers“, Midtgaard et al. 2017 [DOI] [Github]