A VM in Java with tail-calls and continuations

Friday, August 26, 2005

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.

No comments:

Archive