Homework #13: Toy Compiler
Out: ? Thursday, March 30th, Due: ? Monday, April 3rd, 11:00pm

Administrative

The language for this homework is:

#lang pl 13

In this homework you will build on the interpreter that was extended in the previous “Turbo Toy” homework, so begin by retrieving the posted solution to be used as a basis for this one.

What To Do

In this homework, you will turn the extended TOY evaluator into a compiler. Do this in small steps, using what we’ve seen in class to guide your work. Dividing the work into small steps where the code still runs and passes all tests after each step will make this homework significantly easier.

Start with the posted solution for the previous (Turbo TOY) homework.

Testing compiler disabled errors

Your compile function will throw a “compiler disabled” error if the compiler is disabled, and you will need to test this to get complete coverage. However, this is an internal check, and if an error is raised, it should be considered an internal error of your own code. In other words, when things run as they should, you will not have a way to test this error, so it is impossible to write a test case that simply uses run. You should therefore write a test case (for compile and for additional compilation functions that will be described below) using direct calls to the compile function to test the error.

Dealing with Multiple Expressions

One problem that you will need to deal with is the fact that the extended language has several places were multiple expressions are evaluated one by one, using eval-body. There are several possible ways to deal with compiling such multiple-expression bodies:

In any case, remember to write clear purpose statements, and document your code if there is anything non-trivial that it does. If the the second or third options are too difficult for you, you can use the first one (and write a comment saying that), but this will imply some penalty. If you’re using the second or third approaches, then you’re writing a piece of the compiler — so the new function should also check whether the compiler is enabled before it does anything (use the same unless check and error, with 'compile-body instead of 'compile).

Dealing with rfun Calls

When you pull out all dependencies on the input syntax, pay attention to the case of applying an rfun (a FunV value with the flag on) — it doesn’t use compile, but it does depend on the source expressions, so we still want to do the source-related work at compile-time. Actually, we can consider the get-boxes function as being yet another part of the compiler, so we need to deal with it in a similar way to eval and eval-body: we want to turn it to a compilation function.

Begin doing this by renaming it to compile-get-boxes, and currying it, then move the call to this function to the compile-time part in the compile function. The type for this function should be

(: compile-get-boxes : (Listof TOY)
                      -> (ENV -> (Listof (Boxof VAL))))

Now the only thing that is left is to pull out all the compile-time work that is done in compile-get-boxes — the work that deals with the input expressions, which should be done outside of the resulting compiled function. An easy way to do this is to do the iteration over the input expressions and produce a list of functions (each one consumes an env argument). Each of these functions will do one of two things — either it will be a function that returns the box that corresponds to the identifier expression, or, in case the expression was not an identifier, it will be a function that throws an error. Finally, since this function is also part of the compiler, it should also check that the compiler is enabled and throw an error otherwise.

Use the following template for this function:

(: compile-get-boxes : (Listof TOY)
                      -> (ENV -> (Listof (Boxof VAL))))
;; utility for applying rfun
(define (compile-get-boxes exprs)
  (: compile-getter : TOY -> (ENV -> (Boxof VAL)))
  (define (compile-getter expr)
    (cases expr
      [(Id name)
      (lambda ([env : ENV]) fill-in)]
      [else
      (lambda ([env : ENV]) fill-in)]))
  (unless (unbox compiler-enabled?)
    (error 'compile "compiler disabled"))
  (let ([getters (map compile-getter exprs)])
    (lambda (env)
      fill-in)))

Note that when we do all of this, what happens is that each function call gets compiled as a possible rfun call: there is no way for us to know at compile time whether the function value is going to be a plain function or a by-reference function, so all relevant code is getting compiled in advance. This is similar to compiling an if expression — we don’t know which branch will need to run, so we compile both.