Stack reification via trampolines

I've been spending a couple weeks now on getting Időrégész to Android in the best possible way. Időrégész is the Hungarian text adventure game from the '80s that I reverse-engineered and then re-implemented in Inform. My original plan was to just implement a Glulx interpreter; however, initial experiments with a Clojure implementation weren't too promising on the performance front.

I decided to turn to compilation instead of interpretation, then: take the Inform-emitted Glulx image, and compile that directly to the JVM. Of course, that approach would have its own problems with self-modifying code, but my goal is just to get it working well enough that I can compile Időrégész, which is very vanilla as far as Inform programs go.

Most instructions of Glulx map to JVM instructions in a relatively straightforward manner; some unsigned integer operations are implemented by hand in Java and then called via invokestatic. The rather baroque string compression is currently handled at compile time, by just emitting a single Java function that looks like this:

public String resolveString(int ptr)
{
  switch (ptr) {
    case 32851 : return "Class" ;
    case 32857 : return "Object" ;
    case 32863 : return "Routine" ;
    // and so on...
}

However, there is one aspect of Glulx that makes the compilation trickier than a straightforward mapping of procedures to procedures and calls to calls: some Glulx opcodes provide fairly detailed access to the runtime state. For example, save must be able to serialize enough of the state that it can later load that back and continue with the next instruction.

In an interpreter, this is a trival matter, since things like the VM's memory and the stack are already reified data structures. However, if it's compiled to JVM, the state of the Glulx program and the state of the JVM is one and the same; so how do you then save it — from the inside?

The solution is to not use the JVM's stack as the Glulx stack; rather, function calls are compiled to areturn instructions that return a small Java object describing which function to call and where to jump back once its result is available. Returns are also compiled to areturn instructions, but this time returning an object describing the result value. Function-local variables and the per-function stack are passed to the generated JVM code as function arguments:

Each Glulx function is compiled into a class that extends the Glulx.Fun class, defined in Kotlin as:

package Glulx

abstract class Fun {
  abstract class Cont {
    class Return(val value : Int) : Cont()
    class Call(val args: IntArray, val nextFun : Fun, val contPC : Short) : Cont()
  }

  class Result(val value : Int, val contPC : Short)

  abstract fun enter(stub: Stack.CallStub?, args: IntArray): Stack.CallFrame
  abstract fun exec(result: Result?, localVars: IntArray): Cont
}

Since the JVM doesn't support computed jumps, the continuation address contPC is handled by starting the exec of each Fun with a big tableswitch. Here's an example of a recursively defined factorial function (using the Krakatau JVM assembler's syntax):

.method public exec : (LGlulx/Fun$Result;[I)LGlulx/Fun$Cont;
  .code stack 10 locals 10
    aload_1
    ifnull LSTART

    aload_1
    invokevirtual Method Glulx/Fun$Result getContPC ()S
    tableswitch 0
      LCONT0
      default: LSTART

  LSTART:
    ;; if V0=0, jump to base case
    aload_2
    ldc 0
    iaload

    ifeq L0

    ;; START call FACT(V0-1)
    ldc 1
    newarray int
    dup
    ldc 0
    aload_2
    ldc 0
    iaload
    ldc 1
    isub
    iastore

    new Glulx/Fun$Cont$Call
    swap
    dup2
    getstatic Field Glulx/Image/FACT fun LGlulx/Fun;
    ldc 0
    invokespecial Method Glulx/Fun$Cont$Call <init> ([ILGlulx/Fun;S)V
    pop
    areturn

  LCONT0:
    aload_1
    invokevirtual Method Glulx/Fun$Result getValue ()I
    ;; END call FACT(V0-1)
    ;; Note the code generated for the call spans an areturn!

    ;; Multiply result by V0
    aload_2
    ldc 0
    iaload
    imul

    ;; Return result -- this is the "real" return
    new Glulx/Fun$Cont$Return    
    swap
    dup2
    invokespecial Method Glulx/Fun$Cont$Return <init> (I)V
    pop
    areturn

  L0:
    ;; For the base case, we just return 1
    new Glulx/Fun$Cont$Return
    dup
    ldc 1
    invokespecial Method Glulx/Fun$Cont$Return <init> (I)V
    areturn
  .end code
.end method

Running these functions then becomes a matter of mere stack juggling, implemented again in Kotlin:

package Glulx

class Stack {
  class CallFrame(val parent: CallStub?, val localVars: IntArray) {
    constructor(parent: CallStub?, localVarCount: Int):
      this(parent, IntArray(localVarCount))
        
    fun storeArgs(args: IntArray) {
      for(i in args.zip(localVars).indices)
        localVars[i] = args[i]
    }
  }
  
  class CallStub(val parent: CallFrame, val parentFun: Fun, val parentPC : Short)
}

fun run(startFun: Fun) {
  var frame = startFun.enter(null, IntArray(0))
  var fn = startFun
  var result : Fun.Result? = null

  while (true) {
    val cont = fn.exec(result, frame.localVars)
    when (cont) {
      is Fun.Cont.Return -> {
         val stub = frame.parent
         if (stub == null) return

         frame = stub.parent
         fn = stub.parentFun
         result = Fun.Result(cont.value, stub.parentPC)
      }
      is Fun.Cont.Call -> {
        val stub = Stack.CallStub(frame, fn, cont.contPC)
        fn = cont.nextFun
        frame = fn.enter(stub, cont.args)
        result = null
      }
    }
  }
}

In the real implementation, there's slightly more state to pass around: Fun.exec also gets as argument an instance of a generic Environment class which it can use to e.g. access the main Glulx memory, or to issue Glk calls; and there are some boring details about handling both 32-, 16- and 8-bit local variables.

Note that the exact same technique can also be used to implement tail recursion (even mutual tail recursion) on a platform that doesn't support it, like the JVM. I am not using it here, but Glulx actually has a tailcall instruction (not used by Időrégész, or sane Inform code in general), so it might come handy if I want to increase feature coverage.

How I learned about Java's lack of type erasure the hard way

This week, I started playing around with the Android platform. I've been eyeing Yeti, an ML dialect that compiles to JVM and features structural typing. Even though I only have very limited experience in ML (mostly just reading the snippets in the Okasaki, and having helped Maya once with some F# code), it has to be better than Java, right?

After getting the hang of Yeti (integrating it into Android's ant build system, writing Hello World, etc.) I wanted to write something more substantial to evaluate the language for serious use. However, yesterday evening I started getting weird errors as soon as I started creating non-trivial closures in member functions. This is the chronicle of how I tracked down the problem with just some rudimentary Java knowledge and lots of reverse engineering.