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;
  }

  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)});
}

14 comments:

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.

Unknown 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.

Unknown 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.

JP 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.

JP 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

JP 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

JP 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

Unknown 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.

Unknown said...

出会いサイト
自動車保険
自動車保険 比較
お見合いパーティー
チューリッヒ
自動車 保険 見積
不動産
ソニー損保
カード決済
インプラント
ショッピングカート
東京 ホームページ制作
不動産投資
アスクル

Unknown said...

埼玉 不動産
三井ダイレクト
カラーコンタクト
カーボンオフセット
コンタクトレンズ
知多半島 温泉
知多半島 旅館
プリンセスルーム
アクサダイレクト
賃貸
不動産
不動産投資
岡山 不動産
网络营销
輸入雑貨
セルライト

Anonymous said...

会社設立
転職
バイアグラ
結婚指輪
結婚式 演出
釣具
メタボ対策
データ復元
治験
データ復旧
RMT
フローリング
キャッシング
オーク
子宮筋腫
副業 清掃
ECサイト構築
ウィークリーマンション
マンスリーマンション 東京
就職ナビ
広告業界
永代供養
アンチエイジング 化粧品
アダルトグッズ
永代供養
特許事務所

会社設立
永代供養
納骨堂
別れさせ屋
マッスルトレーナー
ウォーキングシューズ
サウナスーツ
有料老人ホーム
美容学校
弁理士
アメリカ ビザ
メル友
法律事務所 求人
債務整理
オペレーティングリース
手 汗
手掌多汗症
マンションリフォーム
住宅リフォーム
医師 募集
医師 求人
医師 転職
脱腸
お見合い
東京都 墓地

Anonymous said...

パソコン自作
アフィリエイト
ブログアフィリエイト
多重債務
投資
お取り寄せグルメ
横浜中華街
不動産
ウィークリーマンション
復旧
発電
価格
toefl
データ復旧
ショッピング枠 現金化
テレマーケティング
横浜 賃貸
釣り
害虫駆除
株式投資
賃貸
データ復旧
介護
不動産担保ローン
ウエディング
ウエディングドレス
看護師