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

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

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

companies marketing mineral makeups and also get the best bargains in mineral makeup you can imagine,
find aout how to consolidate your students loans or just how to lower your actual rates.,
looking for breast enlargements? in Rochester,
homeopathy for eczema learn about it.,
Allergies, information about lipitor,
save big with great bargains in mineral makeup,

change edition interviewing motivational people preparing second
,

interviewing motivational people preparing second time
,

interviewing people motivational preparing for a second time
,

black mold exposure
,

black mold exposure symptoms
,

black mold symptoms of exposure
,

free job interview questions
,

free job interview answers
,

interview answers to get a job
,

lookfor hair styles for fine thin hair
,

search hair styles for fine thin hair
,

hair styles for fine thin hair
,

beach resort in the philippines
,

great beach resort in the philippines
,

luxury beach resort in the philippines
,
iron garden gates, here,
iron garden gates,
wrought iron garden gates
, here
,
wrought iron garden gates
,
You: The Owner's Manual: An Insider's Guide to the Body That Will Make You Healthier and Younger
,
eat eating mindless more than think we we why
,


texturizer,
texturizers here,
black hair texturizer,
find aout how care curly hair,
find about how to care curly hair,
care curly hair,
lipitor rash,
lipitor reactions,
new house ventura california,
the house new houston tx,
new house washington dc,
new house pa philadelphia,
san antonio tx house new,
house new pa philadelphia,
new house washington dc,
new house ventura california,
the house new houston tx,
house new san antonio tx,
the house new houston tx, that you are looking for,
new house ventura california, you need to buy,
new house washington dc,
house new pa philadelphia,
new house san antonio tx,

hair surgery transplant
,

air filter allergy
,

refurbished dell laptop computers
,

hair surgery transplant
,

air filter allergy
,

refurbished dell laptop computers
,

hair surgery transplant
,

air filter allergy
,

refurbished dell laptop computers
,

chocolate esophagus heartburn study
,

chocolate esophagus heartburn study
be informed,

digestion healing healthy heartburn natural preventing way
,

digestion healing healthy heartburn natural preventing way
,
sew skirts, 16simple styles you can make!,
sew what skirts 16 simple styles you,
rebates and discounts on sunsetter awnings,
sunsetter awnings discounts and rebates,
discount on sunsetter awnings


truck and bus tires 12r 22.5, get the best price,
tires truck and bus 12r 22.5 best price,
tires truck bus tires12r 22.5 best price,
plush car seat strap covers,
car seat strap covers,plush,
car seat strap, plush covers,
oscoda voip phone systems, the best!,
oscoda voip the phone system,
oscoda voip phone systems,
exterior iron gates,
oriental wrought iron gates,
powder coated iron garden fencing,

photo soft said...

black mold exposure,
black mold symptoms of exposure,

wrought iron garden gates,
your next iron garden gates, here,

hair styles for fine thin hair,
search hair styles for fine thin hair,

night vision binoculars,
buy, night vision binoculars,

lipitor reactions,
lipitor reactions,

luxury beach resort in the philippines,
beach resort in the philippines,

homeopathy for baby eczema.,
homeopathy for baby eczema.,

save big with great mineral makeup bargains,
companies marketing mineral makeups,

prodam iphone praha,
Apple prodam iphone praha,

iphone clone cect manual,
manual for iphone clone cect,

fero 52 binoculars night vision,
fero 52 night vision,

best night vision binoculars,
buy, best night vision binoculars,

computer programs to make photo albums,
computer programs, make photo albums,

said...

婚約指輪
成長ホルモン
広島 不動産
障害者
松山市 不動産
結婚相談所 東京
国際協力
結婚指輪

said...

浮気調査
募金
ゼネラリ
群馬 ハウスメーカー
埼玉 ハウスメーカー
盲導犬
治験
出産祝い
クレジットカード決済
24そんぽ24
アメリカンホームダイレクト
出会い
出会い系
出会い系サイト

said...

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

said...

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

dance said...

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

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

dance said...

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

Anonymous said...

shanghai hotel
guangzhou hotel
shenzhen hotel
beijing hotel
china hotel
guangzhou hotel
shenzhen hotel
shanghai hotel
beijing hotel
回转支承
转盘轴承
slewing ring
slewing bearing
slewing bearings
slewing ring
slewing bearing
slewing bearings

moto said...

競馬予想
三井ダイレクト
アルバイト 求人情報
ドロップシッピング
医院開業
派遣会社
ショッピング枠 現金化
有料老人ホーム
東京 土地
アーネスト
競馬
設計事務所
マンガ 専門学校
副業
行政書士
アクサ
アクサダイレクト
賃貸
ゲーム 専門学校
結婚式
現金化
看護
ウェディング
クレジットカード 現金化
外国為替
結婚式
クレジットカード 現金化
競馬予想
出会い系
引越
FX
ウェディング
マリッジリング
ローン
デザイン 専門学校

said...

派遣
不動産
インプラント
出会いサイト
クレジットカード 現金化
FX

said...

出会い
投資
データ復旧
出会い系サイト
不動産
コンタクトレンズ
アフィリエイト

said...

派遣情報サイトには、魅力的なお仕事をたくさん掲載しています。派遣お仕事をお探しの皆さまにとって、より使いやすく便利なサイトにするべく、アデコ派遣情報サイトをリニューアルしました。

said...

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

said...

美容整形することによって絶対的な美を得られるわけではありません。美容整形『自分は変わった』という事実を物理的に確認することで、気になって仕方がなかった自分 の体に対するコンプレックスから解放される。美容整形そこではじめて心を研ぎ澄まし、自分の内面を磨いていくことができるようになるのです。そうして人は美しく なっていく。美容整形外見だけ磨こうとする人は美しくなれない、というのが私の持論です」

said...

不動産 広島,岡山/四国(香川,徳島,愛媛,高知) 不動産 -あなぶき不産ナビ不動産四国4県、岡山の不動産、不動産広島の不動産など不動産情報検索(マンション・一戸建て・土地・収益物件等)サイトです不動産。穴吹不動産流通株式会社"

said...

外国為替証拠金取引は元本や利益を保証するものではなく、外国為替相場の変動や金利差により損失が生じる場合がございます。外国為替お取引の前に十分内容を理解し、外国為替ご自身の判断でお取り組みください

Anonymous said...

EH株式会社
エクセルヒューマン
EH株式会社
エクセルヒューマン
EH株式会社
エクセルヒューマン
EH株式会社
エクセルヒューマン
EH株式会社
エクセルヒューマン
EH株式会社
エクセルヒューマン
EH株式会社
エクセルヒューマン
株式会社
エクセルヒューマン
エクセルヒューマン
EH株式会社
エクセルヒューマン
EH株式会社

Anonymous said...

情趣用品,情趣用品,情趣用品,情趣用品,情趣,情趣,情趣,情趣,按摩棒,震動按摩棒,微調按摩棒,情趣按摩棒,逼真按摩棒,G點,跳蛋,跳蛋,跳蛋,性感內衣,飛機杯,充氣娃娃,情趣娃娃,角色扮演,性感睡衣,SM,潤滑液,威而柔,香水,精油,芳香精油,自慰套,自慰,性感吊帶襪,吊帶襪,情趣用品加盟AIO交友愛情館,情人歡愉用品,美女視訊,情色交友,視訊交友,辣妹視訊,美女交友,嘟嘟成人網,成人網站,A片,A片下載,免費A片,免費A片下載愛情公寓,情色,舊情人,情色貼圖,情色文學,情色交友,色情聊天室,色情小說,一葉情貼圖片區,情色小說,色情,色情遊戲,情色視訊,情色電影,aio交友愛情館,色情a片,一夜情,辣妹視訊,視訊聊天室,免費視訊聊天,免費視訊,視訊,視訊美女,美女視訊,視訊交友,視訊聊天,免費視訊聊天室,情人視訊網,影音視訊聊天室,視訊交友90739,成人影片,成人交友,美女交友,微風成人,嘟嘟成人網,成人貼圖,成人電影,A片,豆豆聊天室,聊天室,UT聊天室,尋夢園聊天室,男同志聊天室,UT男同志聊天室,聊天室尋夢園,080聊天室,080苗栗人聊天室,6K聊天室,女同志聊天室,小高聊天室,上班族聊天室,080中部人聊天室,同志聊天室,聊天室交友,中部人聊天室,成人聊天室,一夜情聊天室,情色聊天室,寄情築園小遊戲情境坊歡愉用品,情境坊歡愉用品,情趣用品,成人網站,情人節禮物,情人節,AIO交友愛情館,情色,情色貼圖,情色文學,情色交友,色情聊天室,色情小說,七夕情人節,色情,情色電影,色情網站,辣妹視訊,視訊聊天室,情色視訊,免費視訊聊天,美女視訊,視訊美女,美女交友,美女,情色交友,成人交友,自拍,本土自拍,情人視訊網,視訊交友90739,生日禮物,情色論壇,正妹牆,免費A片下載,AV女優,成人影片,色情A片,成人論壇,情趣,免費成人影片,成人電影,成人影城,愛情公寓,成人影片,保險套,舊情人,微風成人,成人,成人遊戲,成人光碟,色情遊戲,跳蛋,按摩棒,一夜情,男同志聊天室,肛交,口交,性交,援交,免費視訊交友,視訊交友,一葉情貼圖片區,性愛,視訊,視訊聊天,A片,A片下載,免費A片,嘟嘟成人網,寄情築園小遊戲,女同志聊天室,免費視訊聊天室,一夜情聊天室,聊天室