3.2 Iteration 1: Towards a Declarative Language

3.2.1 Assignment Summary

The goal of this assignment is to introduce the process of designing, implementing, and reasoning about a compiler. In particular, we look at designing languages by abstracting away from annoying details, and implementing those abstractions by compilation.

In this assignment, you will implement a small abstraction layer on top of x64, called Paren-x64 v2, which allows easily writing a subset of x64 programs while ignoring some of the boilerplate and operating-system-specific details.

Then, we will abstract away from imperative instructions on locations to expressions on values, and abstract away from a small number of physical locations and replace them with an essentially unboundedly large number of abstract names.

Unit test appropriately, with tests for both failure and success for each compiler pass. You should look into the RackUnit: Unit Testing package. There should be a test module for each of the compiler passes next to the implementation of the pass. You can also test the whole compiler pipeline in the compiler.rkt file.

You can use the interrogator to get limited access to the reference solution: https://soft.vub.ac.be/compilers/interrogator?an=a1 and https://soft.vub.ac.be/compilers/interrogator?an=a2.

You can use the language diff tool to view differences between languages that aren’t typeset in the book: https://soft.vub.ac.be/compilers/differ.

3.2.1.1 Checklist

Completely new passes

• uniquify

• sequentialize-let

• normalize-bind

• select-instructions

• assign-fvars

• flatten-begins

• patch-instructions

• generate-x64

3.2.2 Reading

The reading for this iteration is A Compiler Begins with a Language, Abstracting Boilerplate (v1). Abstract Locations and Value Orientation.

This description links to the documentation for each exercise in the chapter for convenience, but you are responsible for the reading the entire chapter.

You should read first and work the relevant exercises as you read.

3.2.3 Assignment

Here are some useful notes:

• To implement uniquify and select-instructions you may find the functions name? and fresh from the support library helpful.

• The make-begin function from the support package is very useful to minimize the number of nested begin statements in all compiler passes, and in particular in the implementation of flatten-begins.

3.2.4 Validators and interpreters

In these exercises you extend the well-formedness checkers and the interpreters for the source and target language. Generic definitions are given for these by default which you have to replace with your own implementations. You should however prioritize the assignments above, which do not have default implementation and are therefore more important for obtaining a fully functioning compiler pipeline.

• Implement check-paren-x64 a validator for Paren-x64 v2.

  You should start by writing examples and tests for the specification, and adding match clauses following the design recipe. Test for both, success and failure.

• Implement interp-paren-x64 an interpreter for Paren-x64 v2.

  Examples:

  > (interp-paren-x64 '(begin (set! rax 42)))
  42
  > (interp-paren-x64 '(begin (set! rax 42) (set! rax (+ rax 0))))
  42
  > (interp-paren-x64    '(begin       (set! (rbp - 0) 0)       (set! (rbp - 8) 42)       (set! rax (rbp - 0))       (set! rax (+ rax (rbp - 8)))))
  42
  > (interp-paren-x64    '(begin       (set! rax 0)       (set! rbx 0)       (set! r9 42)       (set! rax (+ rax r9))))
  42
  > (interp-paren-x64    '(begin       (set! (rbp - 0) 42)       (set! rax (rbp - 0))))
  42

• Design and implement check-values-lang, a validator for Values-lang v3.

• Design and implement interp-values-lang, an interpreter for Values-lang v3.

  Examples:

  > (interp-values-lang '(module (+ 2 2)))

  4

  > (interp-values-lang    '(module       (let ([x 5]) x)))

  5

  > (interp-values-lang    '(module       (let ([x (+ 2 2)])         x)))

  4

  > (interp-values-lang    '(module       (let ([x 2])        (let ([y 2])          (+ x y)))))

  4

  > (interp-values-lang    '(module       (let ([x 2])        (let ([x 2])          (+ x x)))))

  4

  > (current-pass-list    (list     check-values-lang     uniquify     sequentialize-let     normalize-bind     select-instructions     assign-homes     flatten-begins     patch-instructions     implement-fvars     check-paren-x64     generate-x64     wrap-x64-run-time     wrap-x64-boilerplate))

  > (execute '(module (+ 2 2)))

  4

  > (execute    '(module       (let ([x 5])         x)))

  5

  > (execute    '(module       (let ([x (+ 2 2)])         x)))

  4

  > (execute    '(module       (let ([x 2])         (let ([y 2])           (+ x y)))))

  4

  > (execute    '(module       (let ([x 2])        (let ([x 2])         (+ x x)))))

  4

  > (define (compile-pre-runtime p)     (parameterize ([current-pass-list                     (list                      check-values-lang                      uniquify                      sequentialize-let                      normalize-bind                      select-instructions                      assign-homes                      flatten-begins                      patch-instructions                      implement-fvars                      check-paren-x64                      generate-x64)])       (compile p)))

  > (require racket/pretty)

  > (pretty-display    (compile-pre-runtime '(module (+ 2 2))))

  mov QWORD [rbp - 0], 2 mov r10, QWORD [rbp - 0] add r10, 2 mov QWORD [rbp - 0], r10 mov rax, QWORD [rbp - 0]

  > (pretty-display    (compile-pre-runtime     '(module        (let ([x 5])         x))))

  mov QWORD [rbp - 0], 5 mov rax, QWORD [rbp - 0]

  > (pretty-display    (compile-pre-runtime     '(module        (let ([x 2])          (let ([y 2])            (+ x y))))))

  mov QWORD [rbp - 8], 2 mov QWORD [rbp - 0], 2 mov r10, QWORD [rbp - 8] mov QWORD [rbp - 16], r10 mov r10, QWORD [rbp - 16] add r10, QWORD [rbp - 0] mov QWORD [rbp - 16], r10 mov rax, QWORD [rbp - 16]