Binary Operations and Conditionals

Based on these notes by Ben Lerner. Shortened/simplified a bit, changed the concrete syntax, swapped order, and skipped the development of ANF.

Our previous compiler could increment and decrement numbers, as well as handle let-bound identifiers. This is completely straight-line code; there are no decisions to make that would affect code execution. We need to support conditionals to incorporate such choices. Also, we’d like to be able to support compound expressions like binary operators (or eventually, function calls), and to do that we’ll need some more careful management of data.

Let’s start with binary operations, and move on to conditionals second.

1 Growing the language: adding infix operators

Again, we follow our standard recipe:

1. Its impact on the concrete syntax of the language

2. Examples using the new enhancements, so we build intuition of them

3. Its impact on the abstract syntax and semantics of the language

4. Any new or changed transformations needed to process the new forms

5. Executable tests to confirm the enhancement works as intended

1.1 The new concrete syntax

‹expr›: ... | ( + ‹expr› ‹expr› ) | ( - ‹expr› ‹expr› ) | ( * ‹expr› ‹expr› )

1.2 Examples and semantics

These new expression forms should be familiar from standard arithmetic notation. Note that there is no notion of operator precedence; instead, we use the tree structure to indicate grouping. For this language, we will decide that the order of evaluation should be leftmost-innermost: that is, in the expression (2 - 3) + (4 * 5), the evaluation order should step through

    (+ (- 2 3) (* 4 5))
==> (+ -1 (* 4 5))
==> (+ -1 20)
==> 19

rather than the possible alternative of doing the multiplication first.

1.3 Enhancing the abstract syntax

type prim2 =
  | Plus
  | Minus
  | Times

type expr = ...
  | Prim2 of prim2 * expr * expr

We simply add a new constructor describing our primitive binary operations, and an enumeration of what those operations might be.

1.4 Enhancing the transformations

Exercise

What goes wrong with our current naive transformations? How can we fix them?

Let’s try manually “compiling” some simple binary-operator expressions to assembly:

(+ (+ 2 3) 4)

mov RAX, 2
add RAX, 3
add RAX, 4

(- (- 4 3) 2)

mov RAX, 4
sub RAX, 3
sub RAX, 2

(* (- (- 4 3) 2) 5)

mov RAX, 4
sub RAX, 3
sub RAX, 2
mul RAX, 5

(+ (- 2 3) (* 4 5))

mov RAX, 2
sub RAX, 3
?????

Do Now!

Convince yourself that using a let-bound variable in place of any of these constants will work just as well.

So far, our compiler has only ever had to deal with a single active expression at a time: it moves the result into RAX, increments or decrements it, and then potentially moves it somewhere onto the stack, for retrieval and later use. But with the new compound expression forms that arise with binary operations, that won’t suffice: the execution of (+ (- 2 3) (* 4 5)) above clearly must stash the result of (- 2 3) somewhere, to make room in RAX for the subsequent multiplication. We might try to use another register (RBX, maybe?), but clearly this approach won’t scale up, since there are only a handful of registers available. What to do?

1.4.1 Approach 1: A-Normal Form

Do Now!

Why did the first few expressions compile successfully?

Notice that for the first few expressions, all the arguments to the operators were immediately ready:

• They required no further computation to be ready.

• They were either constants, or variables that could be read off the stack.

Perhaps we can salvage the final program by transforming it somehow, such that all its operations are on immediate values, too.

Do Now!

Try to do this: Find a program that computes the same answer, in the same order of operations, but where every operator is applied only to immediate values.

Note that conceptually, our last program is equivalent to the following:

let first = 2 - 3 in
let second = 4 * 5 in
first + second

This program has decomposed the compound addition expression into the sum of two let-bound variables, each of which is a single operation on immediate values. We can easily compile each individual operation, and we already know how to save results to the stack and restore them for later use, which means we can compile this transformed program to assembly successfully.

This transformation can be generalized and systematized, and thereby make the rest of compilation succeed where currently it would fail. Therefore, one possible approach is to first transform our program such that every operator is applied only to immediate values, such that every expression does exactly one thing with no other internal computation necessary. Such a form is known as A-Normal Form1Evidently the “A” doesn’t stand for anything in particular, and was originally \(\alpha\); it has been retroactively been defined as Administrative Normal Form. or ANF for short.

1.4.2 Approach 2: Using the Stack

Instead of converting our programs to ANF first, we could simply walk the tree of EPrim2 expressions, evaluate their left arguments and push them onto the stack. Then we evaluate the right argument, and push it onto the stack. We then can retrieve both arguments from the stack (since we know where they were placed) and operate on them as normal — effectively, we’ve made them into immediate arguments, without going through the motions of an ANF transformation. Then we can implicitly pop the two values off the stack, basically, by forgetting they even exist, just as we do with let-bound variables that go out of scope. Surely this is simpler!

A downside of this approach is that our stack frames now are of dynamic size, growing and shrinking depending on the complexity of the expression being evaluated. This isn’t inherently a bad thing — in fact, it helps ensure that our stack is “compact”, without holes for values we haven’t defined or used yet — but it will require remembering that our stack frame size can change, independently of the let-bound variables in scope.

Additionally, though it isn’t apparent so far, having code in A-normal form actually enables some subsequent compiler passes, like optimizations, that would be difficult to pull off otherwise.

In these notes, we won’t dive into ANF. But if you want to, you can follow this approach right away! It will simplify certain things, and make others more complex. See this repository for various implementations of an ANF transformation.

Choices!

1.5 Testing

Do Now!

Once you’ve completed the section below, run the given source programs through our compiler pipeline. It should give us exactly the handwritten assembly we intend. If not, debug the compiler until it does.

2 Growing the language: adding conditionals

Reminder: Every time we enhance our source language, we need to consider several things:

1. Its impact on the concrete syntax of the language

2. Examples using the new enhancements, so we build intuition of them

3. Its impact on the abstract syntax and semantics of the language

4. Any new or changed transformations needed to process the new forms

5. Executable tests to confirm the enhancement works as intended

2.1 The new concrete syntax

‹expr›: ... | ( if ‹expr› ‹expr› ‹expr› )

2.2 Examples and semantics

Currently our language includes only integers as its values. We’ll therefore define conditionals to match C’s behavior: if the condition evaluates to a nonzero value, the then-branch will execute, and if the condition evaluates to zero, the else-branch will execute. It is never the case that both branches should execute.

Unlike C, though, if-expressions are indeed expressions: they evaluate to a value, which means they can be composed freely with the other expression forms in our language. This is just like Scheme and OCaml (Java and Python both have different versions of conditionals, as a statement and as an expression).

Do Now!

Construct larger examples, combining if-expressions with each other or with let-bindings, and show their evaluation.

2.3 The new abstract syntax

type expr = ...
  | If of expr * expr * expr (* condition, then branch, else branch *)

An if-expression simply aggregates three expressions. Recall the semantics of evaluating an if-expression.

2.4 Enhancing the transformations: Jumping around

2.4.1 Comparisons and jumps

To compile conditionals, we need to add new assembly instructions that allow us to change the default control flow of our program: rather than proceeding sequentially from one instruction to the next, we need jumps to immediately go to an instruction of our choosing. The simplest such form is just jmp SOME_LABEL, which unconditionally jumps to the named label in our program. We’ve seen only one label so far, namely our_code_starts_here, but we can freely add more labels to our program to indicate targets of jumps. More interesting are conditional jumps, which only jump based on some test; otherwise, they simply fall through to the next instruction.

To trigger a conditional jump, we need to have some sort of comparison. The instruction cmp arg1 arg2 compares its two arguments, and sets various flags whose values are used by the conditional jump instructions:

Some conditional jumps are triggered by arithmetic operations, instead:

Do Now!

Consider the examples of if-expressions above. Translate them manually to assembly.

Let’s examine the last example above: ~hl:2:s~(if ~hl:1:s~(sub1 1)~hl:1:e~ ~hl:3:s~6~hl:3:e~ ~hl:4:s~7~hl:4:e~)~hl:2:e~. Which of the following could be valid translations of this expression?

  ~hl:1:s~mov RAX, 1
  sub1 RAX~hl:1:e~
  ~hl:2:s~cmp RAX, 0
  je if_false
if_true:
  ~hl:3:s~mov RAX, 6~hl:3:e~
  jmp done
if_false:
  ~hl:4:s~mov RAX, 7~hl:4:e~
done:~hl:2:e~

  ~hl:1:s~mov RAX, 1
  sub1 RAX~hl:1:e~
  ~hl:2:s~cmp RAX, 0
  je if_false
if_true:
  ~hl:3:s~mov RAX, 6~hl:3:e~

if_false:
  ~hl:4:s~mov RAX, 7~hl:4:e~
done:~hl:2:e~

  ~hl:1:s~mov RAX, 1
  sub1 RAX~hl:1:e~
  ~hl:2:s~cmp RAX, 0
  jne if_true
if_true:
  ~hl:3:s~mov RAX, 6~hl:3:e~
  jmp done
if_false:
  ~hl:4:s~mov RAX, 7~hl:4:e~
done:~hl:2:e~

  ~hl:1:s~mov RAX, 1
  sub1 RAX~hl:1:e~
  ~hl:2:s~cmp RAX, 0
  jne if_true
if_false:
  ~hl:4:s~mov RAX, 7~hl:4:e~
  jmp done
if_true:
  ~hl:3:s~mov RAX, 6~hl:3:e~
done:~hl:2:e~

The first two follow the structure of the original expression most closely, but the second has a fatal flaw: once the then-branch finishes executing, control falls through into the else-branch when it shouldn’t. The third version flips the condition and the target of the jump, but tracing carefully through it reveals there is no way for control to reach the else-branch. Likewise, tracing carefully through the first and last versions reveal they could both be valid translations of the original expression.

Working through these examples should give a reasonable intuition for how to compile if-expressions more generally: we compile the condition, check whether it is zero and if so jump to the else branch and fall through to the then branch. Both branches are then compiled as normal. The then-branch, however, needs an unconditional jump to the instruction just after the end of the else-branch, so that execution dodges the unwanted branch.

Do Now!

Work through the initial examples, and the examples you created earlier. Does this strategy work for all of them?

Let’s try this strategy on a few examples. For clarity, we repeat the previous example below, so that the formatting is more apparent.

~hl:2:s~(if ~hl:1:s~(sub1 1)~hl:1:e~
  ~hl:3:s~6~hl:3:e~
  ~hl:4:s~7~hl:4:e~)~hl:2:e~

  ~hl:1:s~mov RAX, 1
  sub1 RAX~hl:1:e~
  ~hl:2:s~cmp RAX, 0
  je if_false
if_true:
  ~hl:3:s~mov RAX, 6~hl:3:e~
  jmp done
if_false:
  ~hl:4:s~mov RAX, 7~hl:4:e~
done:~hl:2:e~

~hl:1:s~(if ~hl:2:s~10~hl:2:e~
  ~hl:3:s~2~hl:3:e~
  ~hl:4:s~(sub1 0)~hl:4:e~)~hl:1:e~

  ~hl:2:s~mov RAX, 10~hl:2:e~
  ~hl:1:s~cmp RAX, 0
  je if_false
if_true:
  ~hl:3:s~mov RAX, 2~hl:3:e~
  jmp done
if_false:
  ~hl:4:s~mov RAX, 0
  sub1 RAX~hl:4:e~
done:~hl:1:e~

~hl:1:s~(let (x ~hl:1:e~(if 10 2 0)~hl:1:s~)~hl:1:e~
 ~hl:3:s~(if ~hl:2:s~x~hl:2:e~
   ~hl:4:s~55~hl:4:e~
   ~hl:5:s~999~hl:5:e~)~hl:3:e~~hl:1:s~)~hl:1:e~

  mov RAX, 10
  cmp RAX, 0
  je if_false
if_true:
  mov RAX, 2
  jmp done
if_false:
  mov RAX, 0
done:
  ~hl:1:s~mov [RSP-8], RAX~hl:1:e~
  ~hl:2:s~mov RAX, [RSP-8]~hl:2:e~
  ~hl:3:s~cmp RAX, 0
  je if_false
if_true:
  ~hl:4:s~mov RAX, 55~hl:4:e~
  jmp done
if_false:
  ~hl:5:s~mov RAX, 999~hl:5:e~
done:~hl:3:e~

The last example is broken: the various labels used in the two if-expressions are duplicated, which leads to illegal assembly:

$ nasm -f elf64 -o output/test1.o output/test1.s
output/test1.s:20: error: symbol `if_true' redefined
output/test1.s:23: error: symbol `if_false' redefined
output/test1.s:25: error: symbol `done' redefined

We need to generate unique labels for each expression.

2.4.2 Approach 1: Gensym

One common approach is to write a simple function that generates unique symbols every time it’s called, by keeping track of a mutable counter:

let gensym =
  let counter = ref 0 in
  (fun basename ->
    counter := !counter + 1;
    sprintf "%s_%d" basename !counter);;

This approach works, is simple to implement and simple to understand. However, it does have a readability drawback: the generated names bear no connection to the expressions that produced them, making it hard to trace backwards from the generated output to the relevant source expressions. Additionally, it assumes that only one stream of names is ever needed in the compiler — but it might be nice for the generated names to start counting again from zero, in each subsequent phase of the compiler. Lastly, it is particularly tricky to use this gensym in testing, as the precise numbers it generates are dependent on the entire history of calls to gensym, which makes writing tests very brittle.

2.4.3 Approach 2: Tagging

An alternative is to enrich the definition of expr to parameterize it by an arbitrary type. This allows us to stash any data we wanted at the nodes of our AST:

type 'a expr =
  | Number of int64 * 'a
  | Id of string * 'a
  | Let of (string * 'a expr * 'a) list * 'a expr * 'a
  | Prim1 of prim1 * 'a expr * 'a
  ...

For instance, we can use this flexibility to tag every expression with its source location information, in order to give precisely-located error messages. But this parameter is more flexible than that: we might consider walking the expression and giving every node a unique identifier:

type tag = int
let tag (e : 'a expr) : tag expr =
  let rec help (e : 'a expr) (cur : tag) : (tag expr * tag) =
    match e with
    | Prim1(op, e, _) ->
      let (tag_e, next_tag) = help e (cur + 1) in
      (Prim1(op, tag_e, cur), next_tag)
    | ...
  in
  let (tagged, _) = help e 1 in tagged;;

This function is completely determined by its input, without relying on mutable state, making it much easier to work with in the context of testing. It also implicitly resets counting every time it’s called, making the successive phases of the compiler more readable and independent. Lastly, if we use these ids as the basis for our generated names, then our generated names are easily traceable back to the expressions that created them, making debugging much easier.

2.4.4 Putting it together: compiling if-expressions

If we use our decorated 'a expr definition and our tag function above, then compiling if-expressions becomes:

let rec compile_expr (e : tag expr) (env : env) =
  match e with
  ...
  | If(cond, thn, els, tag) ->
    let else_label = sprintf "if_false_%d" tag in
    let done_label = sprintf "done_%d" tag in
    (compile_expr cond) @
    [
      ICmp(Reg(RAX), Const(0));
      IJe(else_label)
    ]
    @ (compile_expr thn env)
    @ [ IJmp(done_label); ILabel(else_label) ]
    @ (compile_expr els env)
    @ [ ILabel(done_label) ]

let compile e =
  let tagged = tag e in
  let compiled = compile_expr tagged [] in
  (* ... surround compiled with prelude as needed ... *)

2.5 Testing

As always, we must test our enhancements. Properly testing if-expressions is slightly tricky right now: we need to confirm that

• We always generate valid assembly

• If-expressions compose properly with each other, and with other expressions in the language.

• The generated assembly only ever executes one of the two branches of an if-expression

Testing the first property amounts to testing the tag function, to confirm that it never generates duplicate ids in a given expression. Testing the next one can be done by writing a suite of programs in this language and confirming that they produce the correct answers. Testing the last requirement is hardest: we don’t yet have a way to signal errors in our programs (for example, the compiled equivalent of failwith "This branch shouldn't run!") For now, the best we can do is manually inspect the generated output and confirm that it is correct-by-construction, but this won’t suffice forever.

Exercise

Add a new unary operator to the language, that you can recognize and deliberately compile into invalid assembly that crashes the compiled program. Use this side-effect to confirm that the compilation of if-expressions only ever executes one branch of the expression. Hint: using the sys_exit(int) syscall is probably helpful.

1Evidently the “A” doesn’t stand for anything in particular, and was originally \(\alpha\); it has been retroactively been defined as Administrative Normal Form.