Assignment #9: (Not for submission) Toy Compiler

Same pairs, unless you let me know.

Update the course plugin for the language level for this assignment.

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.

In this homework, you will turn the extended TOY evaluator into a compiler. Do this in small steps, following the same process that was demonstrated in class, starting 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 up by using curried calls to compile instead of the previous two-argument calls.
• Start ‘pulling out’ the compile-time code out and push the (lambda (env) ...)s in. The goal, as shown in class, is to make the code never use compile at run-time.
• To make sure that this is the case, add a (boxed) global flag:

  ;; compiler-enabled? : (Box 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 "evaluation 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 all up. 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.
• 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.)

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 solution, use one of the following approaches.
• 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. 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 resultss. This is similar to the previous solution — the difference is only in the way that you compose the resulting compiled function.

When you pull out all dependencies on the input syntax, pay attention to the case of applying an rfun. In this case, there are two things that can be done at compile time:

1. Checking that the arguments are all identifier expressions,
2. Grabbing the list of symbols that are the given names.

Note that the check happens at compile-time, so you don't know whether the function that is applied is going to be a FunV or an RFunV. (There is no way to know that at compile time, since some function calls can be used with a variable function value that can be either one.) You should therefore only perform the check, but raise the error only if you actually get an RFunV function (at run-time).

Also, the list of symbols that you grab is used only in case of an RFunV application. You can use the fact that Scheme is dynamically typed and combine both of these by computing this:

This question is not required, do not submit a solution. Do it only if you think it will be fun. (You can talk to me about it if you did it and want to get some karma points.)

Going back in time, remember that we talked about de-Bruijn indices as an alternative for variable names. Now that you have an actual compiler, you combine the de-Bruijn preprocessor with your compiler. This is easy since they both operate on expressions: you will need to add an argument to the compiler that describes the names that are known in the current lexical scope (a list of lists, since each environment frame has a list of names (no need for the functional representation that was used in the BRANG* homework)), and use this value to precompute the position of names when they are looked up. As a result, you will not need to do any lookups at run-time, since you will know where to find the required value (the frame number and the index number in the frame). (Dealing with RFunVs will be a little tricky here.)
If you do this properly, you will notice that you no longer need the names in the environment, since you pull out the values directly. This makes it possible to change the environment implementation (as in the BRANG* homework) so it no longer contains names. Note that global names will require some special treatment — you can either make up a description of the global environment to start the compilation with, or you can ‘inline’ global values when the compiler sees them. In either of these, global lookups are also eliminated in the run-time (inlining requires forbidding mutation of global bindings). Also note that you can make closures keep only their arity, instead of a list of names that are not needed.
For an even better performance, you can use vectors for the implementation of frames. They are a little better because they have constant-time access to all elements, unlike lists. See make-vector, vector-ref, etc.
Throughout all this, you can use some code, like