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

• 404 Blog Not Found:javascript - にも無限リストを

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

• vallog: PAIP の pipe でエラトステネスの篩（ふるい）
• エラトステネスの篩 - Wikipedia

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

	function car (ls){
	return ls[0];
	}
	function cdr (ls){
	return ls[1];
	}
	function functionp (v){
	return typeof(v) === 'function';
	}
	function nullp(a) {
	return null === a || typeof(a) === 'undefined';
	}
	function makePipe (head, tail){
	return [head, tail];
	}
	function pipeEmptyp (pipe){
	return nullp(pipe) || pipe.length === 0;
	}
	function head (pipe){
	return car(pipe);
	}
	function tail (pipe){
	var kdr = cdr(pipe);
	return functionp(kdr) ? pipe[1] = kdr(): kdr;
	}
	function pipeElt(pipe, i){
	return i === 0 ? head(pipe) : pipeElt(tail(pipe), i - 1);
	}
	function integers (){
	var start = arguments[0] | 0;
	var end = arguments[1];
	return (nullp(end) || start <= end)
	? makePipe(start, function (){ return integers(start + 1, end); })
	: [];
	}
	function enumerate (pipe){
	var count = arguments[1];
	var result = nullp(arguments[2]) ? pipe : arguments[2];
	var ncount = count - 1;
	return (pipeEmptyp(pipe) || count === 0)
	? result
	: enumerate(tail(pipe), ncount, result);
	}
	function filter (pred, pipe){
	return pred(head(pipe))
	? makePipe(head(pipe), function (){ return filter(pred, tail(pipe)); })
	: filter(pred, tail(pipe));
	}
	function sieve (pipe){
	return makePipe(head(pipe), function (){ return filter(function (x){
	return 0 !== x % head(pipe); }, sieve(tail(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));}]

view raw pipe.js hosted with ❤ by GitHub

階乗のリストだとこうでしょうか。

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はSICPの影響を受けて開発した - ヤドカリデンキ商会（第一倉庫）

伝統的なマクロじゃないにしろ、それっぽいものがあったら JavaScript ももっと強力だったでしょうに。

そういえば

Rhino だと Scheme 由来の継続（continuation）や let が使えるそうで。

• Rhino - Wikipedia

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
 */

• 継続 - Wikipedia
• なんでも継続

追記

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

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

• Emacs+JavaScript - 紫藤のWiki
• Inferior JS - 紫藤のWiki
• js2-mode - 紫藤のWiki

追記2

いつも教えて頂いてます！ありがとうございます！

• Twitter / SaitoAtsushi: @valvallow ジェネレータが実装されてない処 ...

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

	function Primes() {
	this.index=3;
	this.nums=[2];
	}
	Primes.prototype.next=function() {
	var i;
	for(i=this.index; !(this.primep(i)); i++);
	this.index=i+1;
	this.nums.push(i);
	return this.nums[this.nums.length-2];
	};
	Primes.prototype.primep=function(x) {
	var limit=Math.floor(Math.sqrt(x));
	var i;
	for(i=0; this.nums[i]<=limit && x%this.nums[i]; i++){};
	return this.nums[i]>limit;
	};
	function enumerate(ps, n) {
	var r=[];
	for(var i=0; i<n; i++) r.push(ps.next());
	return r;
	}
	var primes = new Primes();
	print(enumerate(primes, 10));

view raw gistfile1.js hosted with ❤ by GitHub