12.2 Compiling Scheme into Bytecodes

In this section, we describe an implementation of a Scheme evaluator that works by compiling Scheme code into JVM bytecodes, then executing the bytecodes. We use the class Integer to represent numbers and String to represent symbols.

For procedures (the result of evaluating lambda expressions), we start with this base class:

 class abstract Procedure {    Environment env;    public abstract Object call(Object args[]); } 

When a lambda expression is evaluated, the evaluator creates a new subclass of Procedure. The new subclass implements the call method. The call method evaluates the body of the lambda expression and returns the result. The array args holds the arguments to the procedure.

The binding environment env is the environment in which the procedure was compiled. It is used to look up symbols. The definition of Environment is

 class Environment {    private Hashtable cache = new Hashtable();    private Environment ancestor;    /** Create the environment given the ancestor */    public Environment(Environment ancestor)    {         this.ancestor = ancestor;    }    /** Return the value of sym */    public Object lookup(String sym) throws UnboundSymbolException    {         Object o = cache.get(sym);         if(o == null)              return o;         if(ancestor == null)              throw new UnboundSymbolException(sym);         return ancestor.lookup(sym);    }    /** Bind the symbol to the value */    public void bind(String symbol, Object value)    {         cache.put(symbol, value);    } } 

The hash table cache maps symbols (Strings) to values (Objects). Each environment contains a pointer to the previous environment, called the ancestor. The lookup method looks up the symbol in the cache. If it is not found, it attempts to look it up in the ancestor. If it's not found in any environment, then an exception is thrown, indicating that the symbol is not bound.

The evaluator compiles each form into bytecodes that have the same semantics as the form. Each form evaluates to a value. The bytecodes leave the value of that form on the stack.

Numbers compile into instances of the class Integer. To compile the form

 5 

the compiler generates this code:

 new java/lang/Integer                         ; Create an integer dup iconst_5                                      ; Push the value invokespecial java/lang/Integer/<init>(I)V    ; Construct the                                               ; object 

To compile a symbol, the program looks up the symbol in the current binding environment using the lookup method. The compiler keeps the current binding environment in local variable 1. To compile the form

 x 

the compiler generates this code

 aconst_1                                   ; Push the environment ldc "x"                                    ; Push the symbol invokevirtual Environment/lookup    (Ljava/lang/String;)Ljava/lang/Object;  ; Call lookup 

The compiler generates a procedure application whenever it sees a form that is a list that is not one of the special forms like lambda or if. An example of an application is

 (+ 2 3) 

To compile an application, the generated code must first evaluate each form in the list. Each form in this list is either a symbol or a number. The three forms compile to three code fragments:

 ; Fragment 1: + aconst_1                                    ; Push the envionment ldc "+"                                     ; Push the symbol invokevirtual Environment/lookup    (Ljava/lang/String;)Ljava/lang/Object;   ; Look up the + symbol ; Fragment 2: 2 new java/lang/Integer                       ; Create the number 2 dup iconst_2 invokevirtual java/lang/Integer/<init>(I)V ; Fragment 3: 3 new java/lang/Integer                       ; Create the number 3 dup iconst_3 invokevirtual java/lang/Integer/<init>(I)V 

This code evaluates all the subforms of the procedure application. The first fragment must evaluate to a procedure. In the default Scheme environment, the + symbol is bound to a procedure that performs addition on its arguments. The default binding environment is explained in section 12.5.

To invoke the procedure, two things must be done. First the arguments must be put into an array, since the procedure accepts only a single array argument. Then the call method must be invoked. The resulting code is as follows:

 ;; Fragment 1 goes here ; Ensure that it is a procedure checkcast Procedure ; There is now a procedure on the stack ; Next, build up its arguments. There are going to be two of them, ; as can be seen by looking at the length of the form iconst_2                            ; Create a two-element anewarray java/lang/Object          ; array of Objects ; Store the result of fragment 2 into array element 0 dup                                 ; Dup the array iconst_0 ;; Fragment 2 goes here aastore                             ; Store the element ; The array is still on the stack, thanks to the dup ; Repeat for the second argument dup                                 ; Dup the array iconst_1 ;; Fragment 3 goes here aastore                             ; Store the element ; Now there are two things on the stack: the procedure and an ; array of arguments. Call the procedure invokevirtual Procedure/call    ([Ljava/lang/Object;)Ljava/lang/Object; 

This code begins by evaluating the first element of the list, which should evaluate to a Procedure. Then it evaluates each of the other elements, storing the results in an array. Finally, it uses invokevirtual to invoke the call method on the procedure, using the array as the list of arguments. This leaves the result of the method invocation on the stack.