名づけのない再帰 fixed-point combinator
p.65 Types and Programming Languages より。
afact は、引数に階乗関数を渡されたとき階乗関数になる関数。
つまり、階乗関数に適用すると階乗関数が帰ってくる関数。
#! /usr/bin/env perl use strict; use warnings; use integer; my $afact = sub { my $f = shift; sub { my $n = shift; print "*$n\n"; $n == 0 ? 1 : $n * $f->($n - 1); } }; # afact = L[f]. L[n]. n==0 ? 1 : n * f (n-1) my $fix = sub { my $f = shift; my $f1 = sub { my $x = shift; $f->( sub { my $y = shift; $x->( $x )->( $y ); } ) }; $f1->($f1); }; # fix = L[f]. f1 f1 where f1 = L[x]. f ( L[y]. x x y ) my $fact = $fix->($afact); # fact = fix afact # -> f1 f1 where f1 = L[x]. afact( L[y]. x x y ) # -> afact( L[y]. f1 f1 y ) where f1 = L[x]. afact( L[y]. x x y ) # <-*- afact( L[y]. fact y ) = afact( fact ) print $fact->(4), "\n";
上記のコードでも名前を使ってはいるが、
どの名前も、実体と置き換えて消去できるので、
再帰に使ってるわけではない。
# 再帰に使う名前は、置き換えを無限に続けられる
消去すると、こうなる。
print sub { my $f = shift; my $f1 = sub { my $x = shift; $f->( sub { my $y = shift; $x->( $x )->( $y ); } ) }; $f1->($f1); } -> ( sub { my $f = shift; sub { my $n = shift; print "*$n\n"; $n == 0 ? 1 : $n * $f->($n - 1); } } )->(4), "\n";
再帰を含む処理を1文で書けました。
$f1 も消せるけど、あまりに可読性が低くなるので、消さずにおいた。
sub { my $x = shift;
は、lambda x のこと。
これは名前にカウントしないことにする。