Procedures

Scheme has procedures as first-class values. Java does not. However, we can simulate procedure values, by overriding of virtual methods.

class Procedure
{ ...;
  public abstract Object applyN
    (Object[] args);
  public abstract Object apply0();
  ...;
  public abstract Object apply4
    (Object arg1, ..., Object arg4);
}

We represent Scheme procedures using sub-classes of the abstract class Procedure. To call (apply) a procedure with no arguments, you invoke its apply0 method; to invoke a procedure, passing it a single argument, you use its apply1 method; and so on using apply4 if you have 4 arguments. Alternatively, you can bundle up all the arguments into an array, and use the applyN method. If you have more than 4 arguments, you have to use applyN.

Notice that all Procedure sub-classes have to implement all 6 methods, at least to the extent of throwing an exception if it is passed the wrong number of arguments. However, there are utility classes Procedure0 to Procedure4 and ProcedureN:

class Procedure1 extends Procedure
{
  public Object applyN(Object[] args)
  {
    if (args.length != 1)
        throw new WrongArguments();
    return apply1(args[0]);
  }
  public Object apply0()
  { throw new WrongArguments();}
  public abstract Object apply1
    (Object arg1);
  public Object apply2
    (Object arg1, Object arg2)
  { throw new WrongArguments();}
  ...;
}

Primitive procedures are generally written in Java as sub-classes of these helper classes. For example:

class car extends Procedure1
{ // Return first element of list.
  public Object apply1(Object arg1)
    { return ((Pair) arg1).car; }
}

Program bodies

A user-defined Scheme procedure is compiled to a class that is descended from Procedure. For example, a variable-argument procedure is implemented as a sub-class of ProcedureN, with an applyN method comprising the bytecode compiled from the Scheme procedure body. Thus primitive and user-defined procedure have the same calling convention.

Top-level forms (including top-level definitions) are treated as if they were nested inside a dummy procedure. They are compiled as sub-classes of ModuleBody:

class ModuleBody extends Procedure0
{ ...;
  public Object apply0()
  { return run(Environment.current());}
  public abstract Object run
    (Environment env);
}

When a file is loaded, the result is a ModuleBody; invoking run causes the top-level actions to be executed.

Inlining

Kawa has various hooks for inlining procedures. This can allow substantial speedups, at the cost of some generality and strict standards-compliance, since it prevents re-assigning the inlined procedures. Most of these hooks work by having the compiler notice that a name in function call position is not lexically bound, yet it is declared in the (compile-time) global scope.

The most powerful and low-level mechanism works by having the compiler note that the procedure implements the Inlineable interface. That means it implements the specical compile method, which the compiler calls at code generation time; it can generate whatever bytecode it wants. This is a way for special procedues to generate exotic bytecode instructions. This hook is only available for builtin procedures written in Java.

Another mechanism uses the Java reflective facilities. If the compiler notices that the class of the procedure provides a static method with the right name (apply), and the right number of parameters, then it generates a direct call to that static method. This is not inlining per se, but it does by-pass the (currently significant) overhead of looking up the name in the global symbol-table, casting the value to a procedure, and then making a virtual function call. Also, because the procedure is replaced by a call to a statically known method, that call could actually be inlined by a Java bytecode optimizer. Another advantage of calling a known static method is that the parameter and return types can be more specific than plain Object, or even be unboxed primitive types. This can avoid many type conversions.

The Kawa compiler generates a suitable apply method for all fixed-arity procedures that do not require a closure, so this optimization is applicable to a great many procedures.

Finally, Kawa has preliminary support for true inlining, where a procedure that is only called in one place except for tail-calls, is inlined at the call-site. I plan to add an analysis pass to detect when this optimization is applicable. For now, there is a special case to handle the do special looping form, and these are now always implemented in the natural way (as inlined loops). The “named let” cannot always be implemented as an inlined loop, so implementing that equally efficiently will need the planned analysis phase.

Closures

Languages that provide first-class nested functions with lexical scoping have to deal with variables that an inner function “captures” from surrounding lexical scopes. The standard solution uses a “closure” to represent a function together with the environment of captured variables. The original Java language definition did not support nested functions. However, it did have objects and classes, and it turns out the objects and first-class functions are similar in power, since a closure can be represented using an object and vice versa. The “inner classes” added to Java in JDK 1.1 are an object-oriented form of first-class functions. The Java compiler translates the nested classes into plain objects and non-nested classes, very much like Kawa represents nested Scheme functions.

Kawa implements a closure as a Procedure object with a “static link” field that points to the inherited environment. Older versions of Kawa represented the environment as an array. The most recent version uses the Procedure instance itself as the environment. Let us look at how this works, starting with a very simple example:

(define (f1 a)
  (define (f2 b)
    (list a b))
  (cons a f2))

This gets compiled to the bytecode equivalent of:

class F1 extends Procedure1
{
  public Object apply1(Object a)
  { // body of f1
    F2 heapFrame = new F2();
    heapFrame.a = a;
    return Cons.apply(heapFrame.a,
                      heapFrame);
  }
}

class F2 extends Procedure1
{
  // F2 closureEnv = this;
  Object a;
  public Object apply1(Object b)
  { // body of f2
    return List.apply(this.a, b);
  }
}

Note that the instance of F2 that represents the f2 procedure contains both the code (the apply1 methods), and the captured instance variable a as a Java field. Note also that the parent function f1 must in general use the same field instance when accessing a, in case one or the other function assigned to a using a set!.

Next, a slightly more complex problem:

(define (f3 a)
  (define (f4 b)
    (cons a b))
  (define (f5 c)
    (cons a c))
  (cons a f5))

In this case all three functions refers to a. However, they must all agree on a single location, in case one of the functions does a set! on the variable. We pick f4 as the home of a (for the simple but arbitrary reason that the compiler sees it first).

class F3 extends Procedure1
{
  public Object apply1(Object a)
  { // body of f3
    F4 heapFrame = new F4();
    heapFrame.a = a;
    return Cons.apply(heapFrame.a,
                      new F5(heapFrame));
  }
}

class F4 extends Procedure1
{
  // F4 closureEnv = this;
  Object a;
  public Object apply(Object b)
  { // body of f4
    return Cons.apply(this.a, b);
  }
}

class F5 extends Procedure1
{
  F4 closureEnv;
  public F5 (F4 closureEnv)
  {
    this.closureEnv = closureEnv;
  }
  public Object apply(Object c)
  { // body of f5
    return Cons.apply(closureEnv.a, c);
  }
}

If a variables is captured through multiple levels of nested functions, the generated code need to follow a chain of static links, as shown by the following function.

(define (f6 a)
  (define (f7 b)
    (define (f8 c)
      (define (f9 d)
        (list a b c d))
      (list a b c f9))
    (list a b f8))
  (list a f7))

That gets compiled into bytecodes equivalent to the following.

class F6 extends Procedure1
{
  public Object apply1(Object a)
  { // body of f6
    F7 heapFrame = new F7();
    heapFrame.a = a;
    return List.apply2(frameFrame.a,
                       heapFrame);
  }
}

class F7 extends Procedure1
{
  Object a;
  public Object apply1(Object b)
  { // body of f7
    F8 heapFrame = new F8(this);
    heapFrame.b = b;
    return List.apply3(this.a,
        heapFrame.b, heapFrame);
  }
}

class F8 extends Procedure1
{
  Object b;
  F7 staticLink;
  public F8(F7 staticLink)
  {
    this.staticLink = staticLink;
  }
  public Object apply1(Object c)
  { // body of f8
    F9 heapFrame = new F9(this);
    heapFrame.c = c;
    return List.apply4(staticLink.a,
        this.b, heapFrame.c, heapFrame);
  }
}

class F9 extends Procedure1
{
  Object c;
  F8 staticLink;
  public F9(F8 staticLink)
  {
    this.staticLink = staticLink;
  }
  public Object apply1(Object d)
  { // body of f9
    return List.apply4
      (staticLink.staticLink.a,
        staticLink.b, this.c, d);
  }
}

Handling tail-recursion is another complication. The basic idea is to divide the procedure prologue into the actions before the loop head label, and those after. (Note that allocating a heapFrame has to be done after the head label.) Handling inlining also requires care.