The Source for Java Technology Collaboration
User: Password:
Register | Login help    

Search

Online Books:
java.net on MarkMail:


Rémi Forax

Rémi Forax is Maitre de Conférence at University of Marne-la-Vallée since 2003 where he obtained his PhD on multi-method in Java. He has been using Java for many years and enjoys himself hacking the JDK.

 

Rémi Forax's blog

Holy crap: JVM has coroutine/continuation/fiber etc.

Posted by forax on November 19, 2009 at 4:01 PM PST

Lukas Stadler is my hero, at last JVM summit, he just explain how coroutine and friends can be implemented in the VM and guess what, it now works (currently only with C1).
Let's try to implement something with it.

Generator

I have always wanted to have generator in Java. After all, Python have this feature, Ruby and C#(*) too.
A generator is a way to define an iterator but instead of implementing hasNext()/next(), you just implement a method (here generate) and use the keyword yield (or here a method yield) to send value that will be returned by next(). This is really useful because writing complex iterator is really like to write a state machine (not that fun), it's far easier to define the iterator as a method and use the stack of that method to store the state of the iterator.

The implementation is based on continuation, yield stops the current execution and saves the stack frames as an object, the value passed as argument to yield is received by the method next of the iterator. When next next is called, the continuation is resumed, so the execution is restarted just after the yield.
The current implementation of the continuation in the VM imposes that the methods corresponding to stack frames stored in a continuation must be marked with annotation @Continuable.

(*) There is some weird limitations in C# but a friend of mine says to me that C# 4 doesn't have them anymore.

By example, this generator specifies an iterator that will return the Fibonacci's numbers:

  public class FibonacciGenerator extends AbstractGenerator {
    @Override
    @Continuable
    protected void generate() {
      int last = 1;
      int current = 1;
      
      for(int i=0; i<5; i++) {
        yield(current);
        
        int tmp = current;
        current = current + last;
        last = tmp;
      }
    }
  
    public static void main(String[] args) {
      for(int value : new FibonacciGenerator()) {
        System.out.println("value "+value); 
      }
    }
  }

If you want to test it, there is two solutions:

  1. Build the Da Vinci VM with only callcc patch enable (comment all other patches). Don't forget that only C1 works.
  2. If you use a Linux (I use a Fedora 11), I've already compile a VM with callcc patch. So download jdk7-b75 binaries, and unzip coroutine-VM.zip in directory jre/lib/i386. You also need to download coroutine.jar that contains Java classes to play with the different kinds of continuations.
And to run it:

  $ /usr/jdk/jdk1.7.0b75/bin/java -coroutine -Xbootclasspath/p:coroutine.jar -cp classes FibonacciGeneratorTest
  value 1
  value 2
  value 3
  value 5
  value 8

The code of the abstract generator is here:

public abstract class AbstractGenerator implements Iterator, Iterable {
  final class GeneratorFiber extends Fiber {
    @Override
    @Continuable
    protected Object generate(Object arg) {
      AbstractGenerator.this.generate();
      return END;
    }
    
    @Continuable
    void doYield(Object o) {
      yield(o);
    }
  }
  
  @SuppressWarnings("unchecked")
  private E element = (E)NONE;
  private final GeneratorFiber fiber = new GeneratorFiber();
  
  private static final Object NONE = new Object();
  static final Object END = new Object();
  
  protected abstract void generate();
  
  @Continuable
  protected final void yield(E element) {
    fiber.doYield(element);
  }
  
  @Override
  @Continuable
  @SuppressWarnings("unchecked")
  public final boolean hasNext() {
    E element = this.element;
    if (element != NONE && element != END)
      return true;
    
    element = (E)fiber.resume(null);
    this.element = element;
    return element != END;
  }
  
  @Override
  @Continuable
  @SuppressWarnings("unchecked")
  public final E next() {
    if (!hasNext())
      throw new NoSuchElementException();
    E element = this.element;
    this.element = (E)NONE;
    return element;
  }
  
  @Override
  public final void remove() {
    throw new UnsupportedOperationException();
  }
  
  @Override
  public final Iterator iterator() {
    return this;
  }
}

Cheers,
Rémi

Related Topics >> Open JDK      Virtual Machine      
Comments
Comments are listed in date ascending order (oldest first)

GOTO on steroids

I find it quite interesting that language which has banned goto might be getting continuations, which are in certain way, superman non-local gotos. Still, I'm all for enabling it on JVM level - there are other languages than java. Add tail calls and value types and we might be getting somewhere...

Excellent news...

...not only for additional Java features, but for extra other-languages support (e.g. Scheme) and for interesting use cases like continuation-based web frameworks. I hope the delay in JDK 7 will have the side effect that a bigger number of interesting MLVM projects will have time to mature - I'm strongly interested in full tail call support - to be part of the JDK 7 FCS.

Re: Excellent news...

I wonder if a yield as a tail call can be optimized :)

Rémi

Holy crap indeed!

This is very cool. Thanks for sharing!
Syndicate content