Perl で Church数をいじってみた
Church数をちゃんと理解できているかいまいち不安だったので、Perl でちょっといじってみた。

まず、SICP の問題2.6の、zero と add-1(ついでに one)を Perl に移植。

my $zero = sub {
my $f = shift;
sub { my $x = shift; $x }
};

my $one = sub {
my $f = shift;
sub { my $x = shift; $f->($x) };
};

sub add_1 {
my $n = shift;
return sub {
my $f = shift;
return sub {
my $x = shift;
$f->( $n->($f) ($x) )
};
};
}

my $two = add_1($one);

# 数値に戻してみる
print $zero->( sub { $_[0] + 1 } ) (0); #=> 0
print $one->( sub { $_[0] + 1 } ) (0); #=> 1
print $two->( sub { $_[0] + 1 } ) (0); #=> 2


add_1 をもとに、任意の2つの数の加算ができるように変形。
$m->($f) で m の数をつくって、その回数分 $n->($f) ($x) を繰り返してやる。

sub add {
my ( $n, $m ) = @_;
return sub {
my $f = shift;
return sub {
my $x = shift;
$m->($f) ( $n->($f) ($x) );
};
};
}

my $three = add( $one, $two );
my $five = add( $two, $three);

# 数値へ
print $three->( sub { $_[0] + 1 } ) (0); #=> 3
print $five->( sub { $_[0] + 1 } ) (0); #=> 5


加算が出来ると、乗算も割と楽。
$m の回数分 $n->($f) を繰り返してやって、それを $x に適用させる。
# 上の add と比べて、変わってるのは * の部分だけ。

sub multi {
my ( $n, $m ) = @_;
return sub {
my $f = shift;
return sub {
my $x = shift;
$m->( $n->($f) ) ($x); # *
};
};
}

my $six = multi( $two, $three );

# 数値へ
print $six->( sub { $_[0] + 1 } ) (0); #=> 6


この調子で Y-combinator にまで進もうと思ったけど、Perl だと遅延評価が必要とか、Z-combinator とか言われて、正直よく分からんかった。。。

とりあえず、lambda だけで無限ループ(再帰)するのは簡単だよね、というところまで。

# 無限ループ(再帰)
my $omega = sub {
my $f = shift;
$f->($f);
};
$omega->($omega);



一応、Y-combinator がちゃんと理解できるまで続く予定。


参考サイト:
404 Blog Not Found:TuringとChurchの狭間で
The Mellow Musings of Dr. T : Recursive lambda expressions
[PR]
by fkmn | 2008-01-30 23:55 | IT
<< 資格よりも優先して勉強すべき事 gauche.night のチ... >>


とある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
カテゴリ
以前の記事
ブログパーツ
リンク
検索
タグ
最新のトラックバック
プログラミングが「出来る..
from とりあえず9JP?
Genographic ..
from ナンジャモンジャ
ジュセリーノ
from ありの出来事
くちこみブログ集(ライフ..
from くちこみブログ集(ライフ)(..
以降、丁寧語で行こう!
from エッセイ的な何か
その他のジャンル
ファン
記事ランキング
ブログジャンル
画像一覧

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