5.1 Overview🔗

A compiler is just one (optional!) component of a programming language. So if you want to make a compiler, you must first settle on a programming language to compile.

The specification of a programming language consists of two parts: the syntax, which specifies the form of programs, and semantics, which specifies the meaning of programs.

Syntax, while important, is a fairly superficial aspect of programming languages. The real heart of a programming language is its semantics and we will spend more time concerned this aspect.

There are a few common ways a language’s meaning is specified:

• By example.

• By informal description.

• By reference to an implementation, often an interpreter.

• By formal (mathematical) definition.

Each approach has its advantages and disadvantages. Examples are concise and unambiguous, but incomplete. Informal (prose) descriptions can be intuitive, but open to interpretation and ambiguity. Reference implementations provide precise, executable specifications, but may over specify language details by tying them to implementation artifacts. Formal definitions balance precision while allowing for under-specification, but require detailed definitions and training to understand.

For the purposes of this course, we will use interpreters to specify the meaning of programs. The interpreters provide a specification for the compilers we write and make precise what means for a compiler to be correct. Any time the compiler produces code that, when run, produces a different result that the interpreter produces for the same program, the compiler is broken (or the specification is wrong). Interpreters are useful for specifying what the compiler should do and sometimes writing interpreters is also useful for informing how it should do it.

To begin, let’s start with a dead simple programming language called Abscond. The only kind of expression in Abscond are integer literals. Running an abscond program just produces that integer. (Told you it was simple.)

5.2 Concrete syntax for Abscond🔗

We will simplify matters of syntax by using the Lisp notation of s-expression for the concrete form of program phrases. The job of a parser is to construct an abstract syntax tree from the textual representation of a program. We will consider parsing in two phases:

• the first converts a stream of textual input into an s-expression, and

• the second converts an s-expression into an instance of a datatype for representing expressions called an AST.

For the first phase, we rely on the read function to take care of converting strings to s-expressions. In order to parse s-expressions into ASTs, we will write fairly straightforward functions that convert between the representations.

Abscond, like the other languages studied in this course, is designed to be a subset of Racket. This has two primary benefits:

• the Racket interpreter and compiler can be used as a reference implementation of the languages we build, and

• there are built-in facilities for reading and writing data in the parenthezised form that Racket uses, which we can borrow to make parsing easy.

The concrete form of an Abscond program will consist of, like Racket, the line of text:

followed by a (concrete) expression. The grammar of expressions is very simple:

So, 0, 120, -42, etc. are concrete Abscond expressions and a complete Abscond program looks like this:

abscond/42.rkt

#lang racket

42

Reading Abscond programs from ports, files, strings, etc. consists of reading (and ignoring) the #lang racket line and then using the read function to parse the concrete expression as an s-expression.

5.3 Abstract syntax for Abscond🔗

While not terribly useful for a language as overly simplistic as Abscond, we use an AST datatype for representing expressions and another syntactic categories. For each category, we will have an appropriate constructor. In the case of Abscond all expressions are integers, so we have a single constructor, Lit. A datatype for representing expressions can be defined as:

abscond/syntax/ast.rkt

#lang racket

(provide Lit)

;; type Expr = (Lit Integer)

(struct Lit (i) #:prefab)

Examples

> (parse 5)

'#s(Lit 5)

> (parse 42)

'#s(Lit 42)

> (parse #t)

parse error #t

5.4 Meaning of Abscond programs🔗

The meaning of an Abscond program is simply the number itself. So (Lit 42) evaluates to 42.

We can write an “interpreter” that consumes an expression and produces it’s meaning:

abscond/interpreter/interp.rkt

#lang racket

(provide interp)

(require "../syntax/ast.rkt")

;; Expr -> Integer

(define (interp e)

(match e

[(Lit i) i]))

The interp function specifies the meaning of expressions, i.e. elements of the type Expr. This language is so simple, the interp function really doesn’t do much of anything, but this will change as the langauge grows.

We can add a command line wrapper program for interpreting Abscond programs from stdin:

abscond/interpreter/interp-stdin.rkt

#lang racket

(provide main)

(require "../syntax/parse.rkt")

(require "interp.rkt")

;; -> Void

;; Parse and interpret contents of stdin,

;; print result on stdout

(define (main)

(read-line) ; ignore #lang racket line

(println (interp (parse (read)))))

The details here aren’t important (and you won’t be asked to write this kind of code), but this program reads the contents of a file given on the command line. If it’s an integer, i.e. a well-formed Abscond program, then it runs the intepreter and displays the result.

5.5 A Compiler for Abscond🔗

Writing a compiler is essentially a problem of translation. We want to translate programs in the source language into programs in the target language. For the compiler to be correct, we want this translation to preserve the original meaning of the source language.

This provides an alternative implementation of the language compared to the interpreter we wrote. Rather than interpret programs, we compile them into another language and then use the interpreter of that language to run the program.

For us, that target language is a86. To run target programs, we simply have the CPU execute the code. (In other words, the interpreter of our target language is implemented in hardware.) As a convenience, we can use asm-interp to carry out this execution from within Racket. This will be very useful for stating the specification of our compiler’s correctness and making examples.

Let’s say the Abscond program we have is 42. What would be an equivalent a86 program that, when run, would produce 42? Well every a86 program needs to have a globally declared label where execution will start when called. The result of running the program is communicated as whatever is in the rax register when the program returns, using the Ret instruction.

So, a possible translation of the Abscond program 42 is the a86 program:

(prog

(Global 'entry)

(Label 'entry)

(Mov rax 42)

(Ret))

To see that it is equivalent, i.e. that it produces 42, we just have to run it:

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov rax 42)     (Ret)))

42

From this example of a single compilation, it’s pretty easy to write a general compiler:

abscond/compiler/compile.rkt

#lang racket

(provide compile)

(require "../syntax/ast.rkt")

(require a86/ast a86/registers)

;; Expr -> Asm

(define (compile e)

(prog (Global 'entry)

(Label 'entry)

(match e

[(Lit i) (Mov rax i)])

(Ret)))

If we compile (Lit 42) we get exactly the code we wrote by hand:

Examples

> (compile (Lit 42))

(list  (Global 'entry)  (Label 'entry)  (Mov 'rax 42)  (Ret))

And we can now compile any Abscond program:

Examples

> (compile (Lit 0))

(list  (Global 'entry)  (Label 'entry)  (Mov 'rax 0)  (Ret))

> (compile (Lit 99))

(list  (Global 'entry)  (Label 'entry)  (Mov 'rax 99)  (Ret))

If we compose the compiler with the parser, we can write examples using the symbolic concrete syntax:

Examples

> (compile (parse '42))

(list  (Global 'entry)  (Label 'entry)  (Mov 'rax 42)  (Ret))

> (compile (parse '0))

(list  (Global 'entry)  (Label 'entry)  (Mov 'rax 0)  (Ret))

> (compile (parse '99))

(list  (Global 'entry)  (Label 'entry)  (Mov 'rax 99)  (Ret))

And by using asm-interp, we can confirm that these compiled programs mean the same thing as the original semantics according to interp:

Examples

> (asm-interp (compile (parse '42)))

42

> (asm-interp (compile (parse '99)))

99

5.6 But is it Correct?🔗

At this point, we have a compiler for Abscond. But is it correct? What does that even mean, to be correct? Since we have specified the meaning of Abscond with an interpreter and we can compose the compilation of Abscond programs with the running of a86 programs, we can state correctness as follows:

Compiler Correctness: For all e ∈ Expr and i ∈ Integer, if (interp e) equals i, then (asm-interp (compile e)) equals i.

One thing that is nice about specifying our language with an interpreter is that we can run it. So we can test the compiler against the interpreter. If the compiler and interpreter agree on all possible inputs, then the compiler is correct. We can turn this in a property-based test, i.e. a function that computes a test expressing a single instance of our compiler correctness claim:

abscond/correct.rkt

#lang racket

(provide check-compiler)

(require rackunit)

(require "interpreter/interp.rkt")

(require "compiler/compile.rkt")

(require a86/interp)

;; Expr -> Void

(define (check-compiler e)

(check-equal? (interp e)

(asm-interp (compile e))))

Examples

> (check-compiler (Lit 42))

> (check-compiler (Lit 37))

> (check-compiler (Lit -8))

This is a powerful testing technique when combined with random generation. Since our correctness claim should hold for all Abscond programs, we can randomly generate any Abscond program and check that it holds.

Examples

> (check-compiler (Lit (random 100)))

> (for ([i (in-range 10)])     (check-compiler (Lit (random 10000))))

The last expression is taking 10 samples from the space of Abscond programs in [0,10000) and checking the compiler correctness claim on them. If the claim doesn’t hold for any of these samples, a test failure would be reported.

Finding an input to check-compiler that fails would refute the compiler correctness claim and mean that we have a bug. Such an input is called a counter-example.

On the other hand we gain more confidence with each passing test. While passing tests increase our confidence, we cannot test all possible inputs this way, so we can’t be sure our compiler is correct by testing alone. To really be sure, we’d need to write a proof, but that’s beyond the scope of this class.

At this point we have not found a counter-example to compiler correctness. It’s tempting to declare victory. But... can you think of a valid input (i.e. some integer) that might refute the correctness claim?

5.7 Stand-alone execution🔗

From a conceptual point of view, we have covered the major elements of the Abscond compiler. We can translate programs into a86 and then execute them using asm-interp. But from a pragmatic view, this approach requires Racket to be available at run-time in order to run asm-interp. A more useful set-up here would be to use Racket at compile-time to generate a86 code, but then to produce a stand-alone executable that simply executes the code produced by the compiler. In this way we don’t need Racket around at all at run-time and we can more clearly see the phase distinction betwee compile- and run-time.

In order to directly run the assembly code produced by compiler without asm-interp, we will need a couple of things.

• We need to be able to assemble a86 code into object code.

• We need to be able to link this object code with code that fills in for what asm-interp was doing for us, namely: calling the compiled code and displaying the result when it returns.

To handle the first issue we can rely on the asm-display function, which displays a86 code using standard notation for x86:

Note: the printer takes care of the macOS vs Linux label convention by detecting the underlying system and printing appropriately.

We can turn this into a command-line utility that reads an Abscond program and prints out assembly code:

abscond/compiler/compile-stdin.rkt

#lang racket

(provide main)

(require "../syntax/parse.rkt")

(require "compile.rkt")

(require a86/printer)

;; -> Void

;; Compile contents of stdin,

;; emit asm code on stdout

(define (main)

(read-line) ; ignore #lang racket line

(asm-display (compile (parse (read)))))

shell

> cat 42.rkt | racket -t compiler/compile-stdin.rkt -m
        .intel_syntax noprefix
        .text
        .global "entry"
"entry":
        mov rax, 42
        ret

If we save this output to a file, we can then assemble it into an object file:

shell

> cat 42.rkt | racket -t compiler/compile-stdin.rkt -m > 42.s
> clang -c 42.s
> nm 42.o
0000000000000000 T entry

You can see that in 42.o we have an object file that defines a entry label.

To handle the second issue, we can write a small C helper program that will fulfill the role of what Racket’s asm-interp was doing for us.

runtime/main.c

#include <stdio.h>
#include <inttypes.h>

int64_t entry();

int main(int argc, char** argv)
{
  int64_t result = entry();
  printf("%" PRId64, result);
  putchar('\n');
  return 0;
}

Now we can use an existing C compiler to compile this into object code.

shell

> clang -c runtime/main.c
> nm main.o
0000000000000000 r .L.str
                 U entry
0000000000000000 T main
                 U printf
                 U putchar

Here you can see we get an object with a main label.

Finally to produce an executable we just use an existing linker to link the two objects together into an executable.

shell

> clang main.o 42.o
/usr/bin/ld: warning: 42.o: missing .note.GNU-stack section implies executable stack
/usr/bin/ld: NOTE: This behaviour is deprecated and will be removed in a future version of the linker
> ./a.out
42

Running a.out executes the code, first invoking the main procedure originally written in C, which calls entry, invoking the compiled code. When the compiled code returns, the result is printed.

It’s worth taking stock of what we have at this point, compared to the interpreter approach. To run the interpreter requires all of Racket in the run-time system.

When running a program using the interpreter, we have to parse the Abscond program, check the syntax of the program (making sure it’s an integer), then run the interpreter and print the result.

When running a program using the compiler, we still have to parse the Abscond program and check its syntax, but this work happens at compile-time. When we run the program this work will have already been done. While the compiler needs Racket to run, at run-time, Racket does not need to be available. All the run-time needs is our (very tiny) object file compiled from C. Racket doesn’t run at all – we could delete it from our computer or ship the executable to any compatible x86-64 machine and run it there. This adds up to much more efficient programs. Just to demonstrate, here’s a single data point measuring the difference between interpreting and compiling Abscond programs:

shell

> cat 42.rkt | time -p racket -t interpreter/interp-stdin.rkt -m
42
real 0.36
user 0.28
sys 0.07

Compiling:

shell

> time -p ./a.out
42
real 0.00
user 0.00
sys 0.00

Because Abscond is a subset of Racket, we can even compare results against interpreting the program directly in Racket:

shell

> touch 42.rkt # forces interpreter to be used
> time -p racket 42.rkt
42
real 0.36
user 0.28
sys 0.07

Moreover, we can compare our compiled code to code compiled by Racket:

shell

> raco make 42.rkt
> time -p racket 42.rkt
42
real 0.24
user 0.17
sys 0.06