まずは遅延評価から、らしい
Y-combinator云々の前に、まず遅延評価らしい。
404 Blog Not Found:λ Calculus - まずは遅延評価から

ということで、弾さんのエントリを見ながらお勉強。


my $ELSE = 0;
sub {
my ( $a, $b, $c ) = @_;
return $a ? $b : $c;
}->( 1, 1, $ELSE = 1 + 1 );
print $ELSE; #=> 2

確かに、上のコードだと $ELSE が 2 になる。
(ただ書き写すだけじゃ面白くないので、元のコードを Perl で書き直した)。


var myif = function(_cond, _then, _else){
return _cond ? _then : _else;
};
こういう定義だと、一応

myif(true, 1, 1+1);
のようなものは動くけど、

function fact(n){
return myif(n <= 1, 1, n * fact(n-1));
};
のようなものは動かない。なぜなら、n * fact(n-1)は問答無用で実行されてしまうので、無限ループになってしまうからだ。

同じ話が SICPの問題1.6 にもあったなぁ。こういう動きのイメージは分かる。

先行評価する言語でも、クロージャーが使えるなら、それを利用して評価は後回しにできる。

なるほど、クロージャにしちゃえばいいのか。ということで、最後のコードも Perl で書き換え。

my $myif = sub {
my ( $_cond, $_then, $_else ) = @_;
return $_cond->() ? $_then->() : $_else->();
};

sub fact {
my $n = shift;
$myif->( sub { $n <= 1 },
sub { 1 },
sub { $n * fact( $n - 1 ) } );
}
print fact(10); #=> 3628800

ちゃんと動いた。

こうやって、順を追って説明されると理解できるなぁ。特に難しい話じゃない気がする。

となると、SICP の 問題1.6 も、new-if と sqrt-iter を書き直せばちゃんと動くはず。


(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))

(define (square x)
(* x x))

(define (improve guess x)
(average guess (/ x guess)))

(define (average x y)
(/ (+ x y) 2))

(define (new-if predicate then-clause else-clause)
(cond (predicate (then-clause))
(else (else-clause))))

(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
(lambda () guess)
(lambda () (sqrt-iter (improve guess x) x))))

(define (sqrt x)
(sqrt-iter 1.0 x))

(sqrt 9) ;=> 3.00009155413138
(sqrt 100) ;=> 10.000000000139897
(sqrt (* 12 3)) ;=> 6.000000005333189

おぉ、動いた。わーい ヽ(´▽`)ノ
[PR]
by fkmn | 2008-02-05 23:55 | IT
<< HUNTER×HUNTERの念... やっと SICP の第3章に突入 >>


とあるWebアプリケーションエンジニアの日記
S M T W T F S
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
カテゴリ
以前の記事
ブログパーツ
リンク
検索
タグ
最新のトラックバック
プログラミングが「出来る..
from とりあえず9JP?
Genographic ..
from ナンジャモンジャ
ジュセリーノ
from ありの出来事
くちこみブログ集(ライフ..
from くちこみブログ集(ライフ)(..
以降、丁寧語で行こう!
from エッセイ的な何か
人気ジャンル
ファン
記事ランキング
ブログジャンル
画像一覧

fkmnの最近読んだ本 フィードメーター - フッ君の日常 あわせて読みたい AX