Kawa

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); }

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

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

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

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

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.

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.

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.

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

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);
  }
}

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

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);
  }
}

(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))

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);
  }
}

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.

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: