Assignment #12: Toy Compiler

Out: Wednesday, April 7th, Due: Friday, April 16th, 9:00pm

Administrative

This assignment is only required for Master students. Undergrads can do it too, and you will be graded as usual — but you will not be able to withdraw a graded homework grade, so submit only if you think that your work is good enough to improve your grade. (Note: the homework grades are all weighted to compute your overall grade, so adding another grade means that you get smaller portions for more grades, which can serve as protection against local disasters.)
Note that while undergrads are not required to submit a solution, it will be a very good idea to read the homework and go through the solution when it is later posted — since you are expected to know the material.

The language for this homework is:

#lang pl 12

In this assignment you will build on the interpreter that was extended in the previous 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 test will make this homework significantly easier.

Start with the posted solution.

First, turn the eval function to its curried form, and rename it as compile. Remember to change the type declaration and the purpose statement.
The code will not work now — fix it by using curried calls to compile instead of the previous two-argument calls to eval.
Start ‘pulling out’ the compile-time code out and push the (lambda: ([env : ENV]) ...)s in. The goal, as shown in class, is to make the code never use compile at run-time.
It might be easier for you to first remove uses of the eval* helper, and get rid of it. You’d be left with two inconvenient uses in two map expressions. A convenient utility for this is:
;; convenient helper for running compiled code (: runner : ENV -> ((ENV -> VAL) -> VAL)) (define (runner env) (lambda (compiled) (compiled env)))
You can put it at the top of the compile function, since it doesn’t depend on the runtime env (it receives it as an argument instead).

To make sure that this is the case, add a (boxed) global flag:

(: compiler-enabled? : (Boxof Boolean)) ;; a global flag that can disable the compiler (define compiler-enabled? (box #f))

then change run to allow compilation only when needed:

(: run : String -> Any) ;; compiles and runs a TOY program contained in a string (define (run str) (set-box! compiler-enabled? #t) (let ([compiled (compile (parse str))]) (set-box! compiler-enabled? #f) (let ([result (compiled global-environment)]) (cases result [(ScmV v) v] [else (error 'run "the program returned a bad value: ~s" result)]))))

and add the following to the beginning of compile:

(unless (unbox compiler-enabled?) (error 'compile "compiler disabled"))

(unless is like an if with only the else part.)
Use this to find places where compile is used at run-time, and fix them. After each change, it will be a good idea to comment out the bit that disables the compiler, so you can make sure that your tests still pass.

You will also need to modify extend-rec — instead of receiving expressions, it should get compiled expressions.
Don’t forget that you will need to change the FunV type since it will hold compiled expressions (= Scheme closures) rather than raw AST values. (See also the next section.)

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 intenral 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:

One solution is to compile all expressions in places where there is a list of them, and at run-time send the compiled expressions to eval-body, which will use them one by one with a given environment. This is a cheap and bad solution, so use one of the following approaches instead.
A better solution is to turn eval-body into compile-body, which will get a list of expressions, convert it to a list of compiled expressions (a list of functions), and finally return a single compiled-expression function that runs them one by one and returns the last value. This works better since the list of expressions is compiled to a single Scheme procedure.
Yet another approach is to make a compile-body function that consumes a list of expressions and compiles them all into a single compiled function, without using a list of compiled expression functions. For this, consider the fact that you can compile the first expression as usual, compile the rest recursively, then generate an output function that is made of the previous two compiled results. This is similar to the previous solution — the difference is only in the way that you compose the resulting compiled function.

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).

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 shift all the compile-time work that is done in compile-get-boxes — the work that deals with the input expressions. This work 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.