Procedures

Scheme has procedures that are 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 can be written in Java as sub-classes of these helper classes. For example:

public class force extends Procedure1
{
  public Object apply1 (Object arg1) throws Throwable
  {
    if (arg1 instanceof Promise)
      return ((Promise)arg1).force ();
    return arg1;
  }
}

The Kawa compiler used to compile each user-defined procedure into a separate class just like the force function above. Thus a one-argument function would be compiled to a class that extends Procedure1, and that the body of the function compiled to the body of an apply1 method. This has the problem that compiling a Scheme file generates a lot of classes. This is wasteful both at run-time and in terms of size of compiled files, since each class has some overhead (including its own constant pool).

Early versions of Kawa were written before Sun added reflection to Java in JDK 1.1. Now, we can use reflection to call methods (and thus functions) not known at compile-time. However, invoking a function using reflection is a lot slower than normal method calls, so that is not a good solution. The next sections will discuss what Kawa does instead.

Compiling functions to methods

Each Scheme function defined in a module is compiled to one or more Java methods. If it's a named top-level function, the name of the method will match the name of the Scheme function. (If the Scheme name is not a valid Java name, it has to be mangled.) An anonymous lambda expression, or a non-toplevel named function, gets a generated method name. A function with a fixed number of parameters is compiled to a method with the same number of parameters:

(define (fun1 x y)
 (list x y))

Assuming the above is in mod1.scm, the generated bytecode is equivalent to this method:

public static Object fun1 (Object x, Object y)
{ return MakeList(x, y); }

The method can be an instance method or a static method, depending on compilation options. Here we'll assume it is static.

To compile a call to a known function in the same module, it is easy for Kawa to generate static method invocation. In certain cases, Kawa can search for a method whose name matches the function, and invoke that method.

If the function has parameter type specifiers, they get mapped to the corresponding Java argument and return types:

(define (safe-cons x (y :: <list>)) :: <pair>
  (cons x y))

The above compiles to:

public static gnu.lists.Pair safeCons (Object x, gnu.lists.LList y)
{ return Cons(x, y); }

Optional parameters

A function with optional parameters is compiled to a set of overloaded methods. Consider:

(define (pr x #!optional (y (random)))
  (+ x y))

This gets compiled to two overloaded method, one for each length of the actual argument list.

public static Object pr (Object x)
{ return pr(x, random());
public static Object pr (Object x, Object y)
{ return Plus(x, y));

Rest parameters

If there is a rest-parameter list that get compiled to either an Object[] or LList parameter. The method name gets an extra $V to indicate that the function takes a variable number of parameters, and that extra parameters should be passed as a list or array to the last method parameter. For example this Scheme function:

(define (rapply fun . args)
  (apply fun args))

This get compiled to:

public static Object rapply$V(Object fun, LList args)
{ return apply(fun, args); }

You can declare in Scheme that the rest parameter has type <Object[]>, in which case the method rest parameter is Object[].

Program bodies

Kawa compiles a Scheme module (a source file, or a standard-alone expression) to a Java class, usually one that extends ModuleBody.

class ModuleBody
{
  ...
}

Top-level forms (including top-level definitions) are treated as if they were nested inside a dummy procedure. For example assume a Scheme module mod1.scm:

(define (f x) ...)
(define (g x) ...)
(do-some-stuff)

This gets compiled to

class mod1 extends ModuleBody implements Runnable
{
  public Object f(Object x) { ... }
  public Object g(Object x) { ... }

  public Procedure f = ???; /* explained later */
  public Procedure g = ???;
  public void run() {
    define_global("f", f);
    define_global("g", g);
    do_some_stuff();
  }
}

When a file is loaded, an instance of the compiled class is created, and the run is invoked. This add the top-level definitions to the global environments, and runs any top-level expressions.

Alternatively, using the --module-static command-line flag generates a static module:

class mod1 extends ModuleBody
{
  public static Object f(Object x) { ... }
  public static Object g(Object x) { ... }

  public static Procedure f = ???;
  public static Procedure g = ???;
  static {
    define_global ("f", f);
    define_global ("g", g);
    do_some_stuff();
  }
}

In this case the top-level actons (including definitions) are performed during class initialization.

First-class functions

A Java method represents the actions of a Scheme function, and calling a known Scheme function is easily implemented by invoking the method. However, Scheme has first-class functions, so we need to be able wrap the Java method as an Object that can be passed around, and called from code where the compiler that doesn't know which function will get called at run-time. One solution is to use Java reflection, but that has high overhead. Another solution (used in older versions of Kawa) is to compile each Scheme function to its own class that extends Procedure, with an applyN method that evaluates the function body; this incurs the overhead of a class for each function.

The solution (as with all other problems in Computer Science [David Wheeler]) is to add an extra level of indirection. Every function in a module gets a unique integer selector. The utility ModuleMethod class is a Procedure that has a method selector code plus a reference to the ModuleBody context:

class ModuleMethod extends Procedure
{
  ModuleBody module;
  int selector;
  String name;
  public Object apply1(Object arg1) {
    return module.apply1(this, arg1);
  }
  public ModuleMethod(ModuleBody body, int selector, String name)
  { ... }
}
class ModuleBody
{
  public Object apply1(Object x) { throw Error(); }
}

The compiler generates a switch statement to map selector indexes to actual methods. Thus the previous example generates (in static mode):

class mod1 extends ModuleBody
{
  public static f(Object x) { ... }
  public static g(Object x) { ... }

  public static Procedure f = new ModuleMethod(this, 1, "f");
  public static Procedure g = new ModuleMethod(this, 2, "g");
  static {
    define_global ("f", f);
    define_global ("g", g);
    do_some_stuff();
  }
  public Object apply1(ModuleMethod proc, Object x) {
    switch (proc.selector) {
      case 1:  return f(x);
      case 2:  return g(x);
      default: return super.apply1(proc, this);
    }
  }
}

The symbol g resolves to the Procedure value of mod1.g. Invoking its apply1 method calls the method in ModuleMethod, which calls the 2-argument apply1 method in mod1. This switches on the selector 2, so we end up calling the g method. This is more expensive than calling g directly, but far less expensive than using reflection.

Closures

When a language combines first-class nested functions with lexical scoping (as Scheme does), then we have the problem that an inner function can reference a variable from an other scope, even when that outer scope has exited. In this simple example we say that the inner function f2 captures the variable a from the outer function f1:

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

The standard solution uses a closure to represent a function together with the environment of captured variables. Kawa does this by using the same ModuleBody mechanism used above for first-class functions.

class foo extends ModuleBody
{
  public Procedure f1 = new ModuleMethod(this, 1, "f1");
  public Object f1 (Object a) {
    foo$frame1 frame = new foo$frame1();
    frame.a = a;
    return cons(frame.a, frame.f2);
  }
  public Object apply1(ModuleMethod proc, Object x) {
    switch (proc.selector) {
      case 1:  return f1(x);
      default: return super.apply1(proc, this);
    }
}

This is as dicussed earlier, except for the body of the f1 functions. It create a new inner module or frame. The parameter a is copied to a field in the frame, and any references to the parameter are replaced by a reference to the field. The inner module is implemented by this class:

public class foo$frame1 extends ModuleBody
{
  Object a;
  public Procedure f2 = new ModuleMethod(this, 1, "f2");
  public Object f2 (Object b) {
    return list(this.a, b);
  }
  public Object apply1(ModuleMethod proc, Object x) {
    switch (proc.selector) {
      case 1:  return f2(x);
      default: return super.apply1(proc, this);
    }
}

This mechanism again requires an extra indirection when an inner function is called. We also require a distinct frame class for each scope that has one or more variables captured by some inner scopes. At run-time, we need to allocate the frame instance plus ModuleMethod instances for each inner function (that does capture an outer variable), when we enter the scope for the frame. It should be possible to use general-purpose (sharable) frame classes for the common case that only a few variables are captured; however, I have to investigated that optimization.

Aside: 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.

Old closure implementation

This section documents how Kawa implemented closures years ago. It is included for historical interest.

Kawa used to implement 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.apply2(heapFrame.a,
                      heapFrame);
  }
}

class F2 extends Procedure1
{
  // F2 closureEnv = this;
  Object a;
  public Object apply1(Object b)
  { // body of f2
    return List.apply2(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.apply2(heapFrame.a,
                      new F5(heapFrame));
  }
}

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

class F5 extends Procedure1
{
  F4 closureEnv;
  public F5 (F4 closureEnv)
  {
    this.closureEnv = closureEnv;
  }
  public Object apply1(Object c)
  { // body of f5
    return Cons.apply2(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(heapFrame.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.

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.

New tail-call convention

This is describing a work in progress.

To handle general tail-calls, and to be able to select between overloaded methods, we split a function call into two separate operations:

  1. The match operation is given the actual parameters, and matches them against the formal parameters. If the right number and types of arguments were given, a non-negative integer return code specifies success; otherwise a negative return code specifies a mis-match. On success the arguments are saved in the argument save area of the CallContext.

  2. The apply operation performs the actual work (function body) of the called function. It gets the actual parameters from the CallContext, where match previously saved it.