12.3 Compiling Lambda Expressions

Until now we've assumed the existence of various procedures in the binding environment. To create new procedures, Scheme uses the lambda expression. One such lambda expression is

 (lambda (x) (* x x)) 

which produces the square of whatever number is fed into it.

To evaluate this expression, the compiler produces a new class. The class is a subclass of Procedure, and it implements call to evaluate the body of the lambda expression. The body of the lambda expression is the form

 (* x x) 

which compiles into the code

 ; Evaluate (* x x) aconst_1                                    ; Push the environment ldc "*"                                     ; Push the symbol invokevirtual Environment/lookup    (Ljava/lang/String;)Ljava/lang/Object;   ; Look up the *                                             ; symbol checkcast Procedure                         ; Ensure * evaluates                                             ; to a Procedure iconst_2                                    ; Create the array for anewarray java/lang/Object                  ; the arguments dup                                         ; Dup the array ref iconst_0                                    ; Store into element 0 aconst_1                                    ; Look up x ldc "x" invokevirtual Environment/lookup    (Ljava/lang/String;)Ljava/lang/Object; aastore                                     ; Store x into                                             ; array[0] dup                                     ; Dup the array ref iconst_1                                ; Store into element 1 aconst_1                                ; Look up x again ldc "x" invokevirtual Environment/lookup    (Ljava/lang/String;)Ljava/lang/Object; aastore                                 ; Store x into array[1] ; Call the * procedure on x and x invokevirtual Procedure/call    ([Ljava/lang/Object;)Ljava/lang/Object; 

This code evaluates the body of the lambda expression. It is created by using the patterns described earlier for symbol lookup and procedure calls.

To complete the procedure, a few things must be added to the body. First a new binding environment must be created to bind x to the argument. Then the new binding environment must be put into variable 1, where the code is expecting it. At the end, the result must be returned. The resulting procedure looks like this:

 ; The lambda expression doesn't specify a name, so we'll just ; call it anonymous. Subsequent lambdas will be compiled into ; anonymous2, anonymous3, etc. .class anonymous1 .super Procedure ; Define the call method .method public call ([Ljava/lang/Object;)Ljava/lang/Object; ; Create a new binding environment, which uses the env field as ; its ancestor new Environment dup aload_0                             ; Get this.env getfield Environment/env LEnvironment; invokespecial Environment/<init>(LEnvironment;)V ; The new binding environment is on the stack ; Now bind x in the new environment to the first argument dup ldc "x"                            ; Get symbol x aload_1                            ; Get the value of arg[0] iconst_0 aaload invokevirtual Environment/bind     ; Do the binding               (Ljava/lang/String;Ljava/lang/Object;)V astore_1                           ; Store the new binding                                    ; environment in var 1 ;; Insert the code shown for (* x x) areturn                            ; Return the result .end method 

The class will also require a constructor. The constructor takes a binding environment as its parameter. The superclass constructor is called, which stores the argument into the field env. The constructor is

 .method public <init>(LEnvironment;)V aload_0 aload_1 invokespecial Procedure/<init>(LEnvironment;)V return .end method 

The class is now complete. The Scheme evaluator loads this class, perhaps using the ByteArrayClassLoader discussed in chapter 8.

The evaluation of the lambda expression is not quite complete. A lambda expression is supposed to evaluate to a procedure. To complete the evaluation of the lambda expression, the evaluator must generate code to create an instance of the anonymous1 class and place it on the stack. It must also initialize the binding environment of that instance to the environment in which the code was compiled. The code looks like this:

 new anonymous1                 ; Create an instance dup aload_1                        ; Push the local environment invokespecial anonymous1/<init>(LEnvironment;)V 

When this code is executed, it creates an instance of the anonymous1 class and leaves it on the stack, matching the definition of a lambda expression: the value of the expression is a procedure that evaluates the body of the expression in a new binding environment.

To show how all this works together, this code applies a lambda expression to some arguments:

 ((lambda (x) (* x x)  5) 

This is a procedure application, much like those we discussed earlier. The first element is the lambda expression. The evaluator generates the new class anonymous1. To evaluate the whole expression, the evaluator generates and executes this code:

 new anonymous1                  ; Create the lambda object dup                             ; with the current                                 ; environment aload_1 invokespecial anonymous1/<init>(LEnvironment;)V iconst_1                        ; Create the argument array anewarray java/lang/Object dup                             ; Dup the array iconst_0                        ; Store the number 5 in new java/lang/Integer           ; element 0 dup iconst_5 invokespecial java/lang/Integer/<init>(I)V aastore ; Now the procedure and its argument are on the stack ; Call the procedure invokevirtual Procedure/call    ([Ljava/lang/Object;)Ljava/lang/Object; 

This code uses the local variable 1, which holds the binding environment. If this form is evaluated as part of some other form, then local variable 1 is initialized by the containing form. At the topmost level, there is a default binding environment.

This code causes the JVM to create an instance of the anonymous1 object, create an argument array containing the number 5, and invoke the call method of anonymous1. Going back to the definition of the anonymous1 class at the beginning of this section, you can see that this will bind x to 5 and then perform the computation (* x x), which will result in 25. This result is returned as the result of the procedure call, and the net effect of all of this code is to leave the value 25 on the stack. This is the correct answer.