Gauche Nightではしゃぎすぎたところにもってきて、昨日はEncodeをメンテしながらホームパーティーなんぞをしていたらどうやら風邪を引いてしまったみたい。
風邪で頭が痛いときには、λと戯れるに限る、ということでこの話題。
前回までのあらすじ
- 404 Blog Not Found:たらいを回すならHaskell
- 404 Blog Not Found:javascriptでもたらいを回してみた
- 404 Blog Not Found:gaucheでもたらいを回してみた
- 404 Blog Not Found:C - Judyでたらい回し
ここまでのあらすじでわかった事は、遅延評価(lazy evaluation)するHaskellがむちゃくちゃ優秀なこと、遅延評価がない言語でもmemoization(メモ化)でかなりの高速化が可能であること。
遅延評価ってHaskellでないと駄目なの?
実は、closureをサポートしている言語であれば、遅延評価は可能だったりする。明示的にやらなければならないものの、それを明示するのは実に簡単だ。
まず、遅延評価したい値は、ただclosureでくるめばいい。ここではschemeの例を示す。
gosh> (define (later expr) (lambda () expr)) later
そして、値を取り出すには、そのclosureを評価すればいい。
gosh> (define one (later 1)) one gosh> one #<closure (later later)> one gosh> (one) 1
これを利用することで、myif(p, t, f)
のようなことが、macroなしで実現できる。
gosh> (define (myif p t f) (if (p) (t) (f))) myif gosh> (define (lfact n) (myif (lambda () (= (n) 1)) (lambda () 1) (lambda () (* (n) (lfact (lambda () (- (n) 1))))))) lfact gosh> (lfact (lambda () 10)) 3628800
Lambdaのlはlazyのlでもあったのだ。
しかし、それは一体役に立つのだろうか?代表的なLLでたらいを「後回し」して検証してみよう。
Perl
まずは私の「母語」から。見ての通り、かなり簡潔に書ける。
sub ltak { no warnings 'recursion'; my ( $x, $y, $z ) = @_; return $y->() if $x->() <= $y->(); ltak( sub{ ltak( sub { $x->() - 1 }, $y, $z ) }, sub{ ltak( sub { $y->() - 1 }, $z, $x ) }, sub{ ltak( sub { $z->() - 1 }, $x, $y ) }); } sub tak{ my ($x, $y, $z) = @_; ltak(sub{$x}, sub{$y}, sub{$z}) }
実行速度はどうか。
% time /usr/bin/perl lazy-tak.pl 100 50 0tak(100, 50, 0) = 100 0.598u 0.007s 0:00.61 96.7% 0+0k 0+6io 0pf+0w
悪くない。が、メモ化の場合と比較すると見劣りする。perlではclosureの生成コストが比較的高いことに加え、no warnings 'recursion';
というpragmaがある通り、再帰の深さを監視している。「そのやり方もOKだけど、ちょっと苦手」といったところか。
Python
Perlと比較すると、sub{}
がlambda:
になった分遅延化はうっとうしく感じるが、逆に値を取り出す際に余計な、->
がないのはいい。
def ltak (x, y, z): if x() <= y(): return y() else: return ltak(lambda:ltak(lambda:x() - 1, y, z), lambda:ltak(lambda:y() - 1, z, x), lambda:ltak(lambda:z() - 1, x, y)) def tak (x, y, z): return ltak(lambda:x, lambda:y, lambda:z)
実行速度も、perlよりもよい。
% time /usr/bin/python lazy-tak.py 100 50 0 tak(100, 50, 0) = 100 0.328u 0.052s 0:00.38 97.3% 0+0k 0+0io 0pf+0w
とはいえ、メモ化に代えてこちらを利用するほどのご利益もない。
Ruby
以前「404 Blog Not Found:Haskellは難しくない--こともある。」でも触れたのだが、Rubyはなにげにlambdaを継子扱いしているように感じる。あれだけblockをびしばし使っているのに。
def ltak(x, y, z) if x.call <= y.call then y.call else ltak(lambda{ ltak(lambda{ x.call - 1 }, y, z) }, lambda{ ltak(lambda{ y.call - 1 }, z, x) }, lambda{ ltak(lambda{ z.call - 1 }, x, y) }) end end def tak(x, y, z) ltak(lambda{x},lambda{y},lambda{z}) end
実行速度にも、それが反映されている。
% time /usr/bin/ruby lazy-tak.rb 100 50 0 tak(100, 50, 0) = 100 4.328u 0.033s 0:04.41 98.6% 0+0k 0+1io 0pf+0w
JavaScript
function(){return /*...*/}
が実にうざいものの、尻に括弧をつけるだけで評価できる点は評価できる:-)
function ltak(x, y, z){ if (x() <= y()) return y(); else return ltak( function(){ return ltak( function(){ return x() - 1 }, y, z ) }, function(){ return ltak( function(){ return y() - 1 }, z, x ) }, function(){ return ltak( function(){ return z() - 1 }, x, y ) } ); } function tak(x, y, z){ return ltak(function(){ return x }, function(){ return y }, function(){ return z }); }
実行速度は、実装によってまちまち。Safariではtak(100, 50, 0)
はスタックを食いつぶしてしまう。FirefoxではRubyと同程度かかった。Operaが優秀で、0.7秒ほど。
tak(100,50,0) =
time: seconds
scheme (gauche)
ここまでが盛大な前振り。上記のLLでは、手作り遅延化は可能であったが、わざわざ苦労して値を手でくるむご利益は感じにくい。我らがgaucheではどうだろう?
(define (ltak x y z) (if (<= (x) (y)) (y) (ltak (lambda () (ltak (lambda () (- (x) 1)) y z)) (lambda () (ltak (lambda () (- (y) 1)) z x)) (lambda () (ltak (lambda () (- (z) 1)) x y))))) (define (tak x y z) (ltak (lambda () x) (lambda () y) (lambda () z)))
見ての通り、 (lambda () value)
というのは、くるむ手間はちょっとかかる。が、その手間は以下のように正しく報われる。
% time /usr/local/bin/gosh lazy-tak.scm 100 50 0 (= (tak 100 50 0) 100) 0.072u 0.011s 0:00.19 42.1% 0+0k 0+4io 0pf+0w
他と比べてずっと高速な上、メモ化した場合と遜色ない。しかも驚くべきことに、メモリーの消費量は遅延化版の方が少ないのだ。
% /usr/bin/time -l /usr/local/bin/gosh memo-tak.scm 400 200 0 (= (tak 400 200 0) 400) 3.81 real 3.72 user 0.05 sys 17164 maximum resident set size 12 average shared memory size 10784 average unshared data size 128 average unshared stack size 4010 page reclaims 0 page faults 0 swaps 1 block input operations 0 block output operations 0 messages sent 0 messages received 0 signals received 3 voluntary context switches 363 involuntary context switches % /usr/bin/time -l /usr/local/bin/gosh lazy-tak.scm 400 200 0 (= (tak 400 200 0) 400) 3.89 real 3.87 user 0.00 sys 3752 maximum resident set size 12 average shared memory size 2127 average unshared data size 128 average unshared stack size 659 page reclaims 0 page faults 0 swaps 0 block input operations 0 block output operations 0 messages sent 0 messages received 0 signals received 1 voluntary context switches 503 involuntary context switches
λかわいいよλ。
Dan the Lazy Evaluator
実は、組み込みのforceとdelayを使えば、さらに速くなる。
(define (ltak x y z) (if (<= (force x) (force y)) (force y) (ltak (delay (ltak (delay (- (force x) 1)) y z)) (delay (ltak (delay (- (force y) 1)) z x)) (delay (ltak (delay (- (force z) 1)) x y))))) (define (tak x y z) (ltak (delay x) (delay y) (delay z)))
% /usr/bin/time -l /usr/local/bin/gosh lazier-tak.scm 400 200 0 (= (tak 400 200 0) 400) 0.31 real 0.30 user 0.00 sys 3756 maximum resident set size 12 average shared memory size 2093 average unshared data size 131 average unshared stack size 660 page reclaims 0 page faults 0 swaps 0 block input operations 0 block output operations 0 messages sent 0 messages received 0 signals received 1 voluntary context switches 45 involuntary context switches
しかし、本entryではλを愛でたかったのであえてclosureの方でやってみた次第。
このブログにコメントするにはログインが必要です。
さんログアウト
この記事には許可ユーザしかコメントができません。