Kawa

R5RS defines a procedure values, which allows an expression or a function to yield multiple (or zero) values, rather then being restricted to a single result. However, the multiple values can only be passed to the call-with-values procedure. There is no automatic coercion from a multiple values to a single value, as in Common Lisp. This makes it easy to implement multiple values in a way that does not slow down code that does not use the feature, which is most Scheme code. Kawa uses a helper class Values:

class Values
{ ...
  private Object[] vals;
  public static final Values empty
    = new Values(new Object[0]);
}

The values procedure just creates a new Values object using its arguments. However, if there is only a single value, it returns the value unchanged. If there are zero values, Values.empty is returned. (This value is the same as #!void, which in Kawa is used for the result of a definition or assignment, and whose print-out is suppressed.) The Values instance is returned, with no special handling. The only part of Kawa that needs to know about Values is the call-with-values procedure; it needs to check if it was passed a Values object, or just a regular Scheme value.

This implementation satisfies the goal of no extra overhead for programs that do not use multiple values, and the cost is reasonable for programs that do. It is not as good a returning the multiple results on the stack, as some Scheme and Lisp implementations do, but that is not do-able in a Java context.

Another implementation would be needed if we want the Common Lisp behavior where multiple values are automatically coerced to the first value in single-value contexts. One way to implement that would be move the apply methods to always take an extra "continuation" parameter. Then values can check the kind of continuation it is returning to. Having the return context explicitly passed has other uses too, though it adds some extra overhead to the common case.

Scheme continuations “capture” the current execution state. They can be implemented by copying the stack, but this requires non-portable native code. Kawa continuations are implemented using Java exceptions, and can be used to prematurely exit (throw), but not to implement co-routines (which should use threads anyway).

class callcc extends Procedure1
{ ...;
  public Object apply1(Object arg1)
  {
    Procedure proc = (Procedure) arg1;
    Continuation cont
       = new Continuation ();
    try { return proc.apply1(cont); }
    catch (CalledContinuation ex)
      {
        if (ex.continuation != cont)
             throw ex;  // Re-throw.
        return ex.value;
      }
    finally
      {
        cont.mark_invalid();
      }
  }
}

This is the Procedure that implements call-with-current-continuation. It creates cont, which is the “current continuation”, and passes it to the incoming proc. If callcc catches a CalledContinuation exception it means that proc invoked some Continuation. If it is “our” continuation, return the value passed to the continuation; otherwise re-throw it up the stack until we get a matching handler.

The method mark_invalid marks a continuation as invalid, to detect unsupported invocation of cont after callcc returns. (A complete implementation of continuations would instead make sure the stacks are moved to the heap, so they can be returned to an an arbitarry future time.)

class Continuation extends Procedure1
{ ...;
  public Object apply1(Object arg1)
  {
    throw new CalledContinuation
	      (arg1, this);
  }
}

A Continuation is the actual continuation object that is passed to callcc's argument; when it is invoked, it throws a CalledContinuation that contains the continuation and the value returned.

class CalledContinuation
    extends RuntimeException
{ ...;
  Object value;
  Continuation continuation;
  public CalledContinuation
    (Object value, Continuation cont)
  {
    this.value = value;
    this.continuation = cont;
  }
}

CalledContinuation is the exception that is thrown when the continuation is invoked.

Scheme requires that tail-calls be implemented without causing stack growth. This means that if the last action of a procedure is another function call, then the called function's activation frame needs to be discarded before the new function's frame is allocated. In that case, unbounded tail-recursion does not grow the stack beyond a bounded size, and iteration (looping) is the same as tail-recursion. Making this work is easy using a suitable procedure calling convention, but this is difficult to do portably in Java (or for that matter in C), since implementing it efficiently requires low-level procedure stack manipulation.

Compiler optimizations can re-write many tail-calls into gotos. The most important case is self-tail-calls or tail recursion. Kawa rewrites these to be a simple goto to the start of the procedure, when it can prove that is safe. Specifically, it does optimize Scheme's standard looping forms do and named-let.

Implementing general tail-calls and continuations require being able to manipulate the procedure call stack. Many environments, including the Java VM, do not allow direct manipulation of stack frames. You have the same problem if you want to translate to portable C, without assembly language kludges. Hence, you cannot use the C or Java stack for the call stack, but instead have to explicitly manage the call graph and return addresses. Such re-writing has been done before for ML [MLtoC] and Scheme [RScheme].

In Java we have the extra complication that we do not have function addresess, and no efficient way to work with labels. Instead, we can simulate code labels by using switch labels. This is more overhead than regular method calls, so the regular Procedure interface discussed earlier will probably remain the default. Thus some procedures use the regular calling convention, and others the “CPS” (Continuation Passing Style) calling convention. The rest of this section explains the planned CPS calling convention.

public abstract class CpsFrame
{
  CpsFrame caller;
  int saved_pc;
}

Each CpsFrame represents a procedure activation. The caller field points to the caller's frame, while saver_pc is a switch label representing the location in the caller.

There is a single “global” CpsContext which owns the generalized call “stack”. There may be many CpsContext if there are multiple threads, and in fact one CpsContext is allocated each time a regular (non-CPS) method calls a procedure that uses the CPS calling convention.

public class CpsContext
{
  CpsFrame frame;
  int pc;
  Object value;

  Object run()
  {
    while (frame != null)
      frame.do_step(this);
    return value;
  }
}

Each CpsContext has a frame which points to the currently executing procedure frame, and pc which is a case label for the code to be executed next in the current procedure. The result of a function is left in the value field. All of these these fields may be imagined as global (or per-thread) registers, which is how you would ideally like to implement a CPS calling convention if you had access to machine registers. The frame, pc, and value fields simulate the frame pointer register, the program counter, and the function result register in a typical computer. After creating a CpsContext with an initial frame and pc, you would call run, which uses the do_step method to execute each step of a function until we return from the initial frame with a final value.

Consider a simple Scheme source file, which defines two functions:

(define (f)
  (g)
  (h))
(define (g)
  ...)

This would get compiled into:

public foo extends CpsFrame
{
  void do_step(CpsContext context)
  {
    CpsFrame fr;
    switch (context.pc)
    {
      case 0: // top-level code
        define("f", new CpsProc(this, 1);
        define("g", new CpsProc(this, 3);
        return;
      case 1: // beginning of f
        // do a (non-tail) call of g:
        fr = g.allocFrame(context);
        fr.caller = this;
        fr.saved_pc = 2;
        context.frame = fr;
        return;
      case 2:
        // then do a tail call of h:
        fr = h.allocFrame(context);
        fr.caller = this.caller;
        fr.saved_pc = this.saved_pc;
        context.frame = fr;
        return;
      case 3:  /* beginning of g */
        ...;
    }
  }
}

The entire code of the Scheme compilation unit is compiled into one large switch statement. Case 0 represents the top-level actions of the program, which defines the functions f and g. Next comes the code for f, followed by the (omitted) code for g. When f is called, a new foo frame is allocated, and the context's pc is set to 1, the start of f.

The body of f makes two function calls, one a non-tail function, and finally a tail-call. Either call allocates a CpsFrame and makes it the current one, before returning to the the main loop of CpsContext's run method. The regular (non-tail) call saves the old current frame in the new frame's return link. In contrast, the tail call makes the return link of the new frame be the old frame's return link. When we return then from do_step, the old frame is not part of the call chain (unless it has been captured by callcc), and so it has become garbage that can be collected.

At the time of writing, the CPS calling convention has not been implemented, but I am filling in the details. It has some extra overhead, but also a few side benefits. One is that we compile an entire source file to a single Java class, and it is more convenient when there is a one-to-one correspondence between source files and binary files (for example in Makefiles).

Another exciting possibility is that we can write a debugger in pure Java, because we can run do_step until some condition (break-point), examine the CpsFrame stack, and optionally continue.