2010/10/06

Re: javascript - にも無限リストを （遅延ストリーム pipe 編）

PAIP(実用 Common Lisp (IT Architects’Archive CLASSIC MODER))に載ってる pipe は JavaScript でもいけそうだなぁと思って書いてみました。わりと強引に書きました。JavaScript には Lisp/Scheme のマクロのように引数の評価を遅らせるような機能（？）がないので、しかたなく呼び出し側で無名関数で包みました。よくないスタイルですが、取りあえず動くので良いんじゃないでしょうか。他に何か良い方法があれば、教えていただけると助かります。

で、その pipe でエラトステネスの篩をやってみると以下のような感じです。
var primes = sieve(integers(2));
enumerate(primes, 10);
// ->  [2,3,5,7,11,13,17,19,23,29,31,function () { return filter(pred, tail(pipe));}]

JavaScript による pipe とエラトステネスの篩のソースは以下のもの。JavaScript っぽさとかないかもしれませんし、突っ込みどころも多々あるでしょうが多めに見てください。。


階乗のリストだとこうでしょうか。
function facts (pipe) {
  var rec = function (p, acc){
    var h = head(p);
    var cur = 0 === h ? 1 : h * acc;
    return makePipe(cur, function () { return rec(tail(p), cur); });
  };
  return rec(pipe, 1);
}

enumerate(facts(integers(0)), 5);
// -> [1,1,2,6,24,120,function () { return rec(tail(p), cur); }]

enumerate(facts(integers(0)), 10);
// [1,1,2,6,24,120,720,5040,40320,362880,3628800,function () { return rec(tail(p), cur); }

ところで

JavaScript の生みの親であるブレンダン・アイクが、実は
ブラウザで動く Scheme が作れると聞いて！
ということでネスケに入ったなんて話もあるらしいですね。
伝統的なマクロじゃないにしろ、それっぽいものがあったら JavaScript ももっと強力だったでしょうに。

そういえば

Rhino だと Scheme 由来の継続（continuation）や let が使えるそうで。
Scheme 以外で明示的に継続に触れたことが無いので、試して見ます。
（ruby にも call/cc があるんでしたっけ）

例えば、何の変哲もない、というかただ再帰するだけの deep 関数を例に取ると、
function deep (n){
  var ret;
  if (n === 0){
    ret = n;
  } else {
    ret =  deep(n - 1);
  }
  print(n);
  return ret;
}
deep(10);
/*
0
1
2
3
4
5
6
7
8
9
10
0
*/

再帰の基底条件に達した後は、今まで潜った再帰を戻るわけですよね。そのときに n が print されている状態です。
で、継続のお決まりの例である脱出をしてみたいので、以下のように書き換えて見ます。

ポイントは、実際の再帰を内部で定義した rec 関数に任せている点と、deep の先頭で継続オブジェクトを取得している点。
function deep (n){
  var cont = new Continuation();
  var rec = function (n){
    var ret;
    if (n === 0){
      ret = n;
      cont(ret);
    } else {
      ret =  rec(n - 1);
    }
    print(n);
    return ret;
  };
  return rec(n);
}

deep(10);
// -> 0
print されませんね。結果である 0 だけが表示されています。この結果が意図通りのものです。

基底条件に達した時点で保存しておいた継続に結果を渡して呼び出しているので、潜った再帰はなかったことに。なかったことに、と言うと語弊があるでしょうか。まぁ、気になったら Scheme でもやってみてください。

一応確認するために、rec の下で print すると、ちゃんと再帰していることがわかります。基底条件、つまり最深部まで再帰を潜って cont に渡された値が cont が宣言された以降の処理の結果となるわけです。何を言ってるかわから（ｒｙ。
function deep (n){
  var cont = new Continuation();
  var rec = function (n){
    print(n);
    var ret;
    if (n === 0){
      ret = n;
      cont(ret);
    } else {
      ret =  rec(n - 1);
    }
    print(n);
    return ret;
  };
  return rec(n);
}
deep(10);
/*
10
9
8
7
6
5
4
3
2
1
0
0
 */

追記

あ、今回使った JavaScript の処理系は
Rhino 1.7 release 2 2009 03 22
です。

Emacs + Rhino + js2.el + js-comint.el 最強です。

追記2

いつも教えて頂いてます！ありがとうございます！
@valvallow ジェネレータが実装されてない処理系も多いみたいですね。 とりあえず、無限リストとかの考え方は無視して典型的な JavaScript らしい書き方で書いてみました。 http://gist.github.com/613523


実用 Common Lisp (IT Architects’Archive CLASSIC MODER)
written by time:
labels : , ,

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)