cute-lambda

Gauche Nightではしゃぎすぎたところにもってきて、昨日はEncodeをメンテしながらホームパーティーなんぞをしていたらどうやら風邪を引いてしまったみたい。

風邪で頭が痛いときには、λと戯れるに限る、ということでこの話題。

前回までのあらすじ

ここまでのあらすじでわかった事は、遅延評価(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の方でやってみた次第。