## Friday, November 09, 2007

### Infinite Streams using Java Closures

Neal Gafter's prototype of the closures implementation in Java has given us enough playground to fool around with. Of late, I have been dabbling around with a couple of idioms in functional programming trying to implement it in Java. Many of them have already been tried using functors, anonymous inner classes and the likes. Many of them work too, but at the cost of high accidental complexity. The following is an attempt to get a clear implementation of infinite streams in Java.

Infinite streams give you the illusion that it can contain infinite number of objects. The real kludge behind infinite streams is lazy evaluation. SICP introduces the term delayed evaluation, which enables us to represent very large (even infinite) sequences as streams. Functional languages like Haskell and Miranda employs laziness as the default paradigm of evaluation, while languages like Scheme implement the same concepts as library functions (delay and force).

Dominik Gruntz implements infinite streams in Java using the functor paradigm and inner classes. The obvious problem is verbosity resulting from the accidental complexity that they lend to the implementation. In this post, I attempt the same using Neal's closures prototype. So, without further ado ..

The Stream Interface

Here's the contract for lazy evaluation ..

class StreamTest {  interface Stream<E> {    E car();    Stream<E> cdr();    E get(int index);    <R> Stream<R> map(Unary<? super E, R> f);    Stream<E> filter(Unary<? super E, Boolean> f);  }  //..}

and a lazy implementation using Java closures ..

class StreamTest {  interface Stream<E> {    //.. as above  }  static class LazyStream<E> implements Stream<E> {    private E car;    private {=>Stream<E>} cdr;    // constructor    public LazyStream(E car, {=>Stream<E>} cdr) {      this.car = car;      this.cdr = cdr;    }    // accessors    public E car() { return car; }    public Stream<E> cdr() { return cdr.invoke(); }    // access at position    public E get(int index) {      Stream<E> stream = this;      while (index-- > 0) {      stream = stream.cdr();    }      return stream.car();    }    // map over the stream    public <R> Stream<R> map(Unary<? super E, R> f) {      return cons(f.invoke(car), {=>cdr().map(f)});    }    // filter the stream    public Stream<E> filter(Unary<? super E, Boolean> f) {      if (car() != null) {        if (f.invoke(car()) == true) {          return cons(car(), {=>cdr().filter(f)});        } else {          return cdr().filter(f);        }      }      return null;    }    // factory method cons    public static <E> LazyStream<E> cons(E val, {=>Stream<E>} c) {      return new LazyStream<E>(val, c);    }  }}

A couple of points bugging ..

I had to make up the Unary class since the closure did not allow me to specify ? super E in the left hand side. Ricky has clarified with Neal that this is due to the fact that things on the left hand side of a closure automatically have ? super in their types. Hence a little noise ..

static class Unary<T,R> {  private {T=>R} u;  public Unary({T=>R} u) {    this.u = u;  }  public R invoke(T arg) {    return u.invoke(arg);  }}

and now some tests ..

class StreamTest {  //.. all above stuff  //.. and the tests  // helper function generating sequence of natural numbers  static LazyStream<Integer> integersFrom(final int start) {    return LazyStream.cons(start, {=>integersFrom(start+1)});  }  // helper function for generating fibonacci sequence  static LazyStream<Integer> fibonacci(final int a, final int b) {    return LazyStream.cons(a, {=>fibonacci(b, a+b)});  }  public static void main(String[] args) {    // natural numbers    Stream<Integer> integers = integersFrom(0);    Stream<Integer> s = integers;    for(int i=0; i<20; i++) {      System.out.print(s.car() + " ");      s = s.cdr();    }    System.out.println("...");    // a map example over the stream    Stream<Integer> t = integers;    Stream<Integer> u = t.map(new Unary<Integer, Integer>({Integer i=>i*i}));    for(int i=0; i<20; i++) {      System.out.print(u.car() + " ");      u = u.cdr();    }    System.out.println("...");    // a filter over stream    Stream<Integer> x = integers;    Stream<Integer> y = x.filter(new Unary<Integer, Boolean>({Integer i=>i%2==0}));    for(int i=0; i<20; i++) {      System.out.print(y.car() + " ");      y = y.cdr();    }    System.out.println("...");  }}

Closures in Java will surely bring in a new paradigm of programming within the developers. The amount of excitement that the prototype has already generated is phenomenal. It'll be too bad if they do not appear in Java 7.

Update: Ricky Clarkson points out in the Comments that {? super E=>? extends R} is the same as {E=>R}. The covariance / contravariance stuff just blew off my mind when I compiled the post. Hence the Unary class is not required. Just remove the class and substitute the closure in map() and filter(). e.g.

public <R> Stream<R> map({E=>R} f) {  return cons(f.invoke(car), {=>cdr().map(f)});}

Ricky Clarkson said...

I'm not sure that Unary is necessary, can you put all the code together so that I can play with it (one or multiple files is fine)?

I've just been covering that sicp chapter, so this is interesting.

Debasish said...

@Ricky:

Here is the stuff in a single file .. http://docs.google.com/Doc?id=drm7v5q_11gv4m4p .. I would also love to get rid of Unary.

Ricky Clarkson said...

And here's my 'answer': http://pastebin.com/f5e4fd1ab

In short, because {A=>B} can be read as {? super A=>? extends B}, you don't need to add it yourself.

All I did was delete Unary and replace it with straight {A=>B}. Perhaps I missed something, but the code compiles and runs fine. If I missed something, add a test case that fails and I'll try again.

Debasish said...

Silly me ! It just blew off me that {? super E=>? extends R} is the same as {E=>R}. Thanks for reminding me. I would have required the
indirection in case I had an extends on the left hand side. I am not changing the post - just adding an Update on the changes.
Thanks for the comment.

Prashant Jalasutram said...

Good post debasish.

But can you please help me out most of my programs in closures won't run in windowsXP?

I always get
C:\closures\test\tools\javac\closures>java -Xbootclasspath/p:c:/closures/lib/javac.jar StreamTest
Exception in thread "main" java.lang.NoClassDefFoundError: javax/lang/function/OO

C:\closures\test\tools\javac\closures>

I could manage only very few closure examples to run.

Thanks
Prashant jalasutram
http://prashantjalasutram.blogspot.com/

Ricky Clarkson said...

Prashant:

What command are you using to compile? If you're not specifying the classpath on that command, what value does %CLASSPATH% have?

When you compile, some classes are created. For me, a javax/ directory appears in the same directory my .class file appears in (assuming no package statement in the source). You'll need to make sure that the directory above javax/ is on the classpath.

I think this is only a prototype issue, and that in a release the types will be generated by the VM as needed, much as array types are.

Prashant Jalasutram said...

Ricky,

I cannot see any folders getting created when it compiles successfully.

Command i am using:
C:\closures\test\tools\javac\closures>
javac -J-Xbootclasspath/p:c:/closures/lib/javac.jar -source 7 Demo.java

and then i try to run but fail almost all the times like

java -Xbootclasspath/p:c:/closures/lib/javac.jar Demo

Thanks
Prashant

Prashant Jalasutram said...

Ricky,

And value of %Classpath% is

C:\closures\test\tools\javac\closures>set classpath
CLASSPATH=C:\Program Files\Java\jdk1.6.0\lib;.;

C:\closures\test\tools\javac\closures>

Thanks
Prashant

Prashant Jalasutram said...

Ricky,

Thanks a lot for your gr8 tip and yes it worked finally and i am very happy that i can try a lot of examples now.

It worked when i added "-d ." which allowed as you suggested to create a new directory and added OO class.

so finally my javac looks like

javac -d . -J-Xbootclasspath/p:c:/closures/lib/javac.jar -source 7 *.java

and running in XP does not change any thing.

Debasish thanks a lot for allowing to act as mediator pattern between me and ricky to solve this :-)

Thanks
Prashant Jalasutram

Debasish said...

Hi Prashant -

It is good to find that ur problems have been fixed. I just now logged in and found the trail from Prashant. Thanks Ricky for all the help.

Closures indeed provide great power of abstractions. I will be extremely disappointed if we miss it out in Java 7.

Cheers.

plush said...
photo soft said...
said...
said...
said...
said...
Anonymous said...
Anonymous said...
Anonymous said...
moto said...
said...
said...
said...

said...

FX・外国為替証拠金取引の比較サイト「FX-外為比較.com」では、複数の条件からFX・外国為替会社の比較！また資料請求、口座開設もできます。

said...

said...

said...

Anonymous said...
Anonymous said...