The language for this homework is:
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.
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.
First, turn the
eval function to its curried form, and rename it as
compile. Remember to change the type declaration and the purpose
The code will not work now — fix it by using curried calls to
compile instead of the previous two-argument calls to
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
and get rid of it. You’d be left with two inconvenient uses in two
map expressions. A convenient utility for this is:
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 verify that the compiler is not used at runtime, add a (boxed) global flag:
run to allow compilation only when needed:
and add the following to the beginning of
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
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 (= Racket closures) rather than raw AST
values. (See also the next section.)
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
run. You should therefore write a test case (for
for additional compilation functions that will be described below) using
direct calls to the
compile function to test the error.
There is a problem that you will need to deal with: 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 option 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 — and it’s not really compiling the
code, so we need a better approach.
A better solution is to turn
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 Racket function.
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. You can
even do this with
foldl that does the compilation. (But note that
foldl should be doing the compilation, not running through a
list of compiled expressions which would essentially be the first
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.
When you pull out all dependencies on the input syntax, pay attention to
the case of applying an
FunV value with the flag on) — it
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-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
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
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:
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
— we don’t know which branch will need to run, so we compile both.