Making of Tiger #1, Intro

Recently I’ve started reading the book by Andrew W. Appel titled Modern compiler implementation in ML. I’ve picked it up because I’ve heard some really good reviews about the ML version of it. Also there are other editions available that use C and Java. Each chapter covers a single phase of the compilation process and comes with some initial ML code and programming excercies. At the end you will have a working optimizing compiler.

I’m building a compiler for the first time and it is a lot of fun. In these blog post series, I’ll be working through the book and explaining my solutions to each chapter.

Getting started

The author describes Tiger as a simple (but nontrivial) language of the Algol family, which could be easily modified to be functional or object-oriented (maybe I’ll skip the OO-part of the book).

type tree = {
  key: string,
  left: tree,
  right: tree
}

function prettyprint(tree: tree) : string =
  let
    var output := ""

    function write(s: string) =
      output := concat(output, s)

    function show(n: int, t: tree) =
      let
        function indent(s: string) = (
          for i := 1 to n do
             write(" ");
             output := concat(output, s);
             write("\n")
        )
      in
        if t = nil
        then ident(".")
        else (
          indent(t.key);
          show(n + 1, t.left);
          show(n + 1, t.right)
        )
      end
  in
    show(0, tree);
    output
  end

For my implementation I’ve decided to use OCaml. It is close enough to SML so with even basic ML experience it should be fairly straightforward to port the code examples.

Straight-line programs

The first “warm-up” assignment is to implement a program analyzer and interpreter for the straight-line programming language. We have the following types:

type id = string

type binop = Plus | Minus | Times | Div

type stm = Compound of stm * stm
         | Assign of id * exp
         | Print of exp list

 and exp = Id of id
         | Num of int
         | Op of exp * binop * exp
         | Eseq of stm * exp

So for the following sample straight-line program

a := 5 + 3;
b := (print(a, a - 1), a * 10);
print(b)

The corresponding AST would be

Compound(
  Assign("a", Op(Num 5, Plus, Num 3)),
  Compound(
    Assign("b",
      Eseq(
        Print [Id "a"; Op(Id "a", Minus, Num 1)],
        Op(Num 10, Times, Id "a"))),
    Print [Id "b"]))

The first task is to write a function

val maxargs : stm -> int

This function tells the maximum number of args of any print statement within any subexpression of a given statement.

Sounds easy, right? The implementation is pretty straightforward too:

open Base
open Straightline

let rec maxargs stm =
  let maxargs_exp = function
    | Eseq (stm, _) -> maxargs stm
    | _ -> 0
  in match stm with
  | Print exps ->
    let len = List.length exps in
    let exp_lens = List.map ~f:maxargs_exp exps in
    let max_exp_len = List.max_elt ~compare:Int.compare exp_lens in
    Int.max len (Option.value ~default:0 max_exp_len)
  | Compound (exp1, exp2) ->
    let l1 = maxargs exp1 in
    let l2 = maxargs exp2 in
    Int.max l1 l2
  | Assign (_, exp) ->
    maxargs_exp exp

Next, we need to write another function that “interprets” program in this language.

val eval : stm -> unit

A simple interpreter could look like this:

open Base
open Stdio
open Straightline

let eval x op y =
  match op with
  | Plus  -> x + y
  | Minus -> x - y
  | Times -> x * y
  | Div   -> x / y

let rec interp_stm stm env =
  let print env0 exp =
    let (v, env1) = interp_exp exp env0 in
    print_endline (Int.to_string v);
    env1
  in
  match stm with
  | Print exps ->
    List.fold_left ~init:env ~f:print exps
  | Assign (key, exp) ->
    let (data, env1) = interp_exp exp env in
    Map.set env1 ~key ~data
  | Compound (stm1, stm2) ->
    let env1 = interp_stm stm1 env in
    interp_stm stm2 env1

and interp_exp exp env =
  match exp with
  | Id k ->
    let v = Map.find_exn env k in (v, env)
  | Num x -> (x, env)
  | Op (exp1, op, exp2) ->
    let (x, env1) = interp_exp exp1 env in
    let (y, env2) = interp_exp exp2 env1 in
    let r = eval x op y in
    (r, env2)
  | Eseq (stm, exp) ->
    let env1 = interp_stm stm env in
    interp_exp exp env1

Here we’re just recursively traversing a tree, keeping a map of identifiers, evaluating arithmetic operations and printing values.

Excersises

A couple of more excercises about trees, nothing super exciting. So I won’t paste the rest of my solutions here. To implement a balanced-tree (ex. d) I’ve read the chapter about Red-Black Trees in Okasaki book. The code is here.

Well, thats all for part 1! The next one is about lexical analysis where we’ll write a simple lexer for the Tiger language.

Conclusion

By the time I’ve decided to start writing this post I’ve already finished reading 6th chapter and here are some first impressions:

• The book is clear and enjoyable to read. Programming assignments and exercises are well thought out
• Implementing the typechecker (chapter 5) wasn’t easy, for me it took a week to make it work and typecheck correctly every given example program
• Chapter 6 feels easier (less code to write), but requires some basic knowledge about microprocessor architectures (SPARK, MIPS)

I wouldn’t recommend starting with this book to someone with zero compiler design knowledge. But it is definitely a must read for people who already know the basics of compiler construction.