The “last” release - 0.4

Hi all!

That's right, this is it: the last modifications for the Google Summer of Code are in. From now on, and I still have until tomorrow, it'll be just writing API documentation (javadocs for the “public” classes) and bugs' squashing.

So, are you curious about what got in, and what not?

It pretty much covers everything on the initial proposal. A few things didn't make it though.

This version introduces the serialization of continuations. I've also moved the Ambivalence class to a “new” util package. This package will host classes implementing common uses of continuations. I've also added the Generator class, an implementation of generators, much like Python's.

And now, on to what doesn't work...

Synchronization doesn't work, as I've explained before. Since then I've found that this behavior (enforcing balanced locking) is optionally mandated by the JVM Spec, so some VMs may not even enforce it. Besides that, Sun VMs (which do enforce it) have ways to bypass it through sun.misc.Unsafe. So, there is hope.

Method invocations with the super keyword don't work either. In general invokespecial can only be used to call either private methods or constructors in interpreted code. All other uses are disallowed by the interpreter. This is so because it is not possible to call such methods through reflection: the overriding method is always called. I have currently no solution for this issue.

Winding protection (which was not part of the initial proposal, but had been promised afterwards) was not implemented. The problem is that continuing blocks could not be implemented that way, since executing them would destructively modify their frame. Winding guards will be implemented sometime in the future in an alternative way, but designing the solution will take its time, since the way we do this affects our synchronization policy as well.

Besides this three outstanding issues, everything should work - and I'd like to ear about it if it doesn't.

That does not however mean my work is anywhere near finished. There are options to work around those issues, and a lot can still be done in terms of performance. Work will continue and feedback is welcomed.

I'll be making another release tomorrow, either a 1.0 or something like a 1.0b1 (with which I'd be more confortable, as long as it doesn't clash with Google's goals, since the code has barely been tested).

Another release - 0.3

This release, if you've been following the blog, introduces continuations. Everything seems to work as it's supposed to, hence another release. Just don't forget it's pretty alpha, there may be serious bugs.

Besides the code for continuations I've also added a new test exemplifying them, and I'd like to call your attention to it, as I believe it shows the great power of continuations:

Ambivalence<Integer> amb = new Ambivalence<Integer>();

try {
    int h = amb.choose(range(1, N));
    int a = amb.choose(range(1, h));
    int b = amb.choose(range(a, h));

    amb.require(sqr(h) == sqr(a) + sqr(b));

    System.out.printf("%2d^2 + %2d^2 = %2d^2\n", a, b, h);

    amb.fail();
} catch (Exception e) {
}

Let's go through it step by step.

Firstly what is the code supposed to do? Well, the goal is to find Pythagorean Triplets, that is integer (a, b, h) triplets that satisfy the Pythagorean Theorem a²+b²=h².

Having set its goal, the code (or at least a portion of it) is quite easy to read:

1. you state that h is to be chosen from a range of 1 through a given N; (N exclusively)
2. you state that a is to be chosen from a range of 1 through h; (the hypotenuse is always larger than the legs)
3. you state that b is to be chosen from a range of a through h; (making b be greater than or equal to a removes the uninteresting solutions where a and b are interchanged)
4. you require that h squared is to be equal to the sum of a squared and b squared.

And then you go on to printing the solution. So, basically you've set out the rules and you hope the program will automagically give the right answer, and it does - that's amb. You can read about non-determinism and amb on two great Scheme books: SICP and TYS.

Ambivalence differs from it's Scheme's cousin in that it is not a macro, and so it evaluates it's arguments, but otherwise it's pretty much the same. Modulo that difference, it can be used in almost the same ways. It's code is part of the test, but it may be added to the general library, as a clean way to use continuations. I'll post it here for a good showcase, anyway:

public final class Ambivalence<T> {
    private Continuation failure;

    public @interpretable T choose(T... values) {
        if (values.length == 0) failure.returnTo();
        if (values.length == 1) return values[0];

        Continuation old = failure;
        Continuation success = new Continuation();

        for (T value : values) helper(value, success);

        failure = old;
        failure.returnTo();

        return null;
    }

    private @interpretable void helper(T value, Continuation success) {
        failure = new Continuation();
        success.returnTo(value);
    }

    public @interpretable void fail() {
        failure.returnTo();
    }

    public @interpretable void require(boolean condition) {
        if (!condition) failure.returnTo();
    }
}

That's it for today. I'm working on finally and continuing blocks, and hope to nail them soon. Keep tuned.

New release - 0.2

That's right, there's a new file release - version 0.2, see the downloads page.

So, what's new in so little time?

Well everything I intended to do before going into continuations is now in place. Besides that, lot of bugs have been corrected (hopefully more than those introduced).

Most notably in this release, exception handling is implemented, with stack-trace translation, source file and line numbers. This means debugging the interpreted code is now much easier.

I'll move into continuations soon, then into finally and continuing blocks with continuations, and hopefully finish serialization in time. Tight schedule until September 1, but now moving steadily towards the goal - or so it seems.

The first alpha release - 0.1

Following up on my last post, yesterday I made the project's first file release - alpha version 0.1, see the downloads page.

Now the code is most likely buggy, but at least (and modulo the unknown bugs) it already does a few things:

• it is able to interpret just about everything apart from throwing and catching exceptions
• and, most notably, it already does tail-calls optimization.

I've also added couple of tests where added and an ant target was created (test). To test the JauVM yourself download the file (jauvm-0.1-src.tgz) and do the following:

tar xfz jauvm-0.1-src.tgz
cd jauvm
ant test

Notes: you'll need a recent version of ant (mine is 1.6.2) and a 1.5 JDK (mine is 1.5.0_02); and, there will be some warnings about missing serialVersionUIDs.

The expected output should be amongst ant's own output and is something like:

[echo] ========== Fib ==========
[java] fib(25)=121393, O(N)
[java] fib(25)=121393, O(log(N))
[java] fib(25)=121393, O(exp(N))
[echo] ========= Parity ========
[java] even(65536)?=true
[java]  odd(65536)?=false
[java] even(65535)?=false
[java]  odd(65535)?=true
[echo] =========================

The sources for these tests are under the test directory, do take a look.

The interpreter is pretty slow and memory hungry right now, but there's a lot of room for improvement though that's not a priority - features and correct behaviour come first.

The only known issues (that are not easy problems) are synchronization (as I've said earlier) and some method invocations, like those with the super keyword (calling virtual methods of the super-class). Other known issues have to do with class garbage collection, but seem more manageable.

Under memory pressure the interpreter may throw a NullPointerException - this is being worked on. Other than that, all bug reports are welcomed.

Work will continue on implementing exceptions throwing and handling. That's it for today!

Wow - it's been two weeks!

Indeed... But what have I been up to?

Well, if you'd kept up with CVS, you'd know that a week ago I was dealing with symbolic name resolution as per the JVM Spec.

I was kinda delayed by a bug in javac's compile-time field resolution. I kept testing my algorithm against javac's, and so I had to redo it to match the JVM's dynamic resolution method - which is the correct one, according to the specification. I filed a bug with Sun (no response yet) - but it's a corner case (not that important). I just wanted to get it right the first time.

That's not the main reason for this post, though. I've just committed a version of the code that finally does something - like visible stuff.

The interpreter now “loads” the necessary classes (that was the step following resolution), parsing the bytecode and building a structure suitable for the interpretation process.

I was going to go with an int[] and the traditional switch interpreter, but after implementing just “a couple” of opcodes I was rapidly approaching the maximum method size limit (besides having a huge source file, but that's manageable with code folding).

So I gave up, and I'm using an Insn[] - that's an “instructions” array. Insns are objects that represent an instruction and all its arguments, and which have an execute(...) virtual method.

The interpreter cycle is now just this (code which I believe explains itself):

while (this.frame != null) this.code[this.cp++].execute(this);

I've implemented a couple of opcodes already, quite enough for dear “Hello World!” - which was in fact the initial goal:

• static and virtual, interpreted and native invocations;
• static and instance field getting and setting;
• local variable loading and storing
• constant loading;
• simple stack operations.

It's not much (no math yet, amongst other things) but as I said enough to test.

Want to give it a try? Easy steps then:

cvs -d:pserver:anonymous@cvs.sourceforge.net:/cvsroot/jauvm login
cvs -z3 -d:pserver:anonymous@cvs.sourceforge.net:/cvsroot/jauvm co -P jauvm
cd jauvm
ant dist

Notes: leave the password blank; you'll need a recent version of ant (mine is 1.6.2) and a 1.5 JDK (mine is 1.5.0_02); and, there will be some warnings about missing serialVersionUIDs.

Hopefully, and if all goes out as expected, you'll have 3 files in the dist folder:

• jauvm.jar (java archive, no dependencies);
• jauvm-all.jar (java archive, all dependencies included);
• and, jauvm-src.tgz (source tarball).

You'll want the jauvm-all.jar. Add that to your classpath, compile and run the following example:

Test.java

import net.sf.jauvm.Interpreter;
import net.sf.jauvm.interpretable;

public class Test implements Runnable {
    public static void main(String[] args) {
        new Interpreter(new Test()).run();
    }

    public @interpretable void run() {
        System.out.println("Hello World!");
        System.out.println(System.currentTimeMillis());
        iprint(Math.PI);
        nprint(Math.E);
        itest();
        ntest();
    }

    public @interpretable void itest() {
        System.out.println(this);
    }

    public void ntest() {
        itest();
    }

    public static @interpretable void iprint(double d) {
        System.out.println(d);
    }

    public static void nprint(double d) {
        iprint(d);
    }
}

The output should be something like:

Hello World!
1123726157960
3.141592653589793
2.718281828459045
Test@e0b6f5
Test@e0b6f5

I'll leave it up to you to figure out what's being interpreted and what's not.

Next steps will be: getting interface and special invocations working (including constructors and private methods - super invocations may be a problem). In the process I hope to implement tail-calls (which seem pretty easy) and a bunch more opcodes, and soften a few rough edges. That's all before getting into continuations.

This will now get exiting, at least for me!