Administrative

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.

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.

• 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 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 not-easy-to-remove uses in two map expressions. A convenient utility for this is:

  ;; convenient helper for running compiled code
  (: caller : ENV -> (ENV -> VAL) -> VAL)
  (define (caller 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 verify that the compiler is not used at runtime, 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)
    (define compiled (compile (parse str)))
    (set-box! compiler-enabled? #f)
    (let ([result (compiled global-environment)])
      (cases result
        [(RktV 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 (= Racket 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 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 use 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(s) to test the error.

Dealing with Multiple Expressions

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 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 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 the foldl should be doing the compilation, not running through a list of compiled expressions which would essentially be the first option. Don’t feel obliged to use foldl though, it can be overly confusing…)

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.

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

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:

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.