なんでひげぽんが反復がすぐにわからなかったかを憶測すると、「変数とは代入すべきもの」、という手続き型言語の呪縛が思い立つ。ひげぽんは別にがっかりする必要はない。hyukiさんさえそれに引っかかっていたんだから。

その証拠を、以下にお見せする。

[結]2005年8月 - www.textfile.org
sub fix { my $G = shift; return $G->( sub { my $x = shift; return fix($G)->($x); } ); }

これはPerlで実装した不動点関数で、全く問題なく動く。しかし、hyukiさんも知らぬ間に一つ「反則」を犯していることに気がつかれたかたはいらっしゃるだろうか?それがどうして反則なのかは、読み進めるうちに判明するだろう。

そのためには、まずはChurch Calculusを紹介しなければならない。Lambda Calculusを一言で説明すると、全てを--数字ですら--関数で表現する、ということになる。これは、実はTuring Machineの概念、すなわち全てを--関数ですら--データで表現するの対極の概念になる。

それでは、実際に数字を関数で表してみよう。こうすればいい。

0 := λ f x . x
1 := λ f x . f x
2 := λ f x . f f x

え?何の事かわからない?それではもう少し実例に近づけよう。schemeならこう。

(define zero (lambda (f) (lambda (x) x)))
(define one  (lambda (f) (lambda (x) (f x))))
(define two  (lambda (f) (lambda (x) (f (f x)))))

perlならこう。

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

要は、ある数は、ある関数fを何回xに適用するか、という定義にしてしまうのである。ひげぽんがやっている練習問題のdoubleを参照してほしい。one, two, threeをonce, twice, thrice (thriceはもうほとんど使いわない言葉だけど)....に置き換えたという感じだ。

これを普通の数値に戻すには、以下のようにすればいい。

scheme
((two (lambda(x)(+ x 1))) 0)
perl
$two->(sub{ $_[0] + 1 })(0)

しかし、ここでの特徴は、「普通の数値に戻す」ことではなくて、「関数をそのまま数として扱う」ということにある。これで、数そのものの「作り方」はわかったが、そこから任意の数を作るための「演算」はどうしたらよいのだろう?

例えば、自然数は、次の数を求める一般的手法が一つあれば、あとはドミノ倒し式に作れる。「1は0の次、2は1の次....」といった具合である。次の数を求める関数をSUCCと名付けると、SUCCの定義はこんな風になる。

SUCC := λ n f x . f(n f x)

本当にそうだろうか?実際に上の数を入れて確かめてみよう。

 
2 := (λ n f x . f(n f x)) 1
  => λ f x . f (1 f x)
  => λ f x . f (f x)
  => λ f x . f f x

うまく行きそうである。こんな具合にλ演算だけで全ての演算が出来るかどうか?

ここで手続き型言語の知見が生きてくる。要は繰り返しと条件分岐さえあれば、全てのプログラムは書けるのだ。要はifとgotoが書ければいい。

そのためにはブール演算が必要なので、先にtrueとfalseを定義しておく。

TRUE  := λ x y . x
FALSE := λ x y . y

なんか狐につつまされたような感じがするが、ifの定義を見ればなぜこうなのかがわかる。

IF    := λ p x y . p x y

やってみればわかるが、pにtrueを入れれば確かにxが出て来て、falseを入れれれば確かにyが出てくる。

Polymorphic Existential Recursive Lambda

これで条件分岐が手に入った。後は繰り返しさえ定義できればいい。関数しかない正解で繰り返し?そう。そこで再帰が登場する。ある関数を与えるとそれを再帰する関数を出すという関数さえ手に入れれば、それで繰り返しが出来るではないか。そんな関数は存在するのだろうか?

それを見つけたのがプログラミング言語Haskellの名前の由来ともなった、Haskell Curry。万能再帰関数生成関数は、こんな形をしている。

Y := λ f . (λ x . f (x x)) (λ x . f (x x))

これのfに再帰したい関数を与えれば、それが再帰関数になって出てくる。別名Y-combinator。これと上記のifを組み合わせて行けば、任意のプログラムが書けるというわけだ。

これがいかに重要な発見であるか。MITのSchemeのロゴを見ればわかる。そしてPerl 6のAudreyの定義、"Polymorphic Existential Recursive Lambda"のロゴの"Recursive"が"Y"になっているのもそれが理由だ。

ここでhyukiさんのプログラムに戻る。見ての通り、λ演算においては、引数しか出て来ておらず、その引数の適用の順番を適宜変えているだけだ。別の言い方をすると、束縛変数しか使っていない。ひげぽんがすぐに繰り返しがわからなかったのはそのためだ。繰り返しに必要なはずの、引数でない普通の変数--自由変数がなかったのだから。

さらに見ての通り、全ての関数は「名無し化」されている。ところが、hyukiさんのfixは、fix自身を再帰している。名無しであるというのは、自分の名前を呼ぶことも反則のうちに入ってしまうのだ。

sub fix { my $G = shift; return $G->( sub { my $x = shift; return fix($G)->($x); # 反則! } ); }

それでは、上記のY combinatorをそのままschemeやperlに書き直して動くのだろうか?perlならこんな感じになる。

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

しかし、これは残念ながら動かない。schemeでも駄目だ。perlもschemeもapplicative orderだからだ。applicative orderというのは、先に括弧の中身を評価してしまうということ。例えば前述のifでは、

$if->($cond)($then)($else);

とあった場合、$condだけではなく、$thenも$elseも評価してしまう。結果として、上のY combinatorでは停止条件をifで与えても無限loopしてしまうのだ。何とか実際に値が必要となるまで遅延させることは出来ないだろうか。

実は、方法はある。関数で遅延させたい関数をくるんでしまうのである。$xを後で欲しかったら、$xを返すのではなく、

sub { my $x = shift; sub { my $dummy = shift; $x } };

を返して、あとでそれに任意の値を引数で入れて、$xを取り出せばよいのだ。ここではλ演算をしているので、最もシンプルなλ関数、λ x . x を入れれてやればいい。Perlなら

our $FORCE = sub { my $a = shift; $a };

とでもすればよい。この遅延評価を組み込んだY-combinatorの変種は、Z-combinatorという名前のようである。以下のようにして使う。ここでは簡潔のため、fact自体はLambda定義はしていないが、見ての通りLambda記法でない関数を再帰化することも可能であり、その意味で万能である。

our $Z = sub { my $f = shift;
               sub { my $x = shift; 
                     sub { my $y = shift;
                           $f->($x->($x))
                     }
                 }->(sub { my $x = shift; 
                           sub { my $y = shift; 
                                 $f->($x->($x)) 
                           }
                     })
         };
my $_fact = sub { my $f = shift;
                  sub { my $n = shift;
                        $n < 2 
                           ? 1 
                           : $n * $f->($FORCE)($n - 1) }};

our $fact = $Z->($_fact)($FORCE);

このように、関数とデータの等価性は、データから関数を作り出すTuringのアプローチからも、関数からデータを作り出すChurchのアプローチからも保証されている。

なぜ関数型言語を注目すべきか、これで感じ取れるだろう。関数型を知っていれば、トンネルをもう片方の側からも掘る事ができるのだ。

実はTuringのアプローチとChurchのアプローチを、両方載せた本というのは以外と少ない。どちらか一方に偏っているのが通常だ。イントロダクションとして私が知っている最良の本は、以外にも冒頭に上げたRoger PenroseのThe Emperor's New Mindだ。天才と聞いて真っ先にこの人を思い浮かべる人も多いのではないか。本書には、Universal Turing Machineの実定義と、Lambda Calculusで自然数を作る方法の双方が乗っている。ただし、同書においてはこれらは副題の一つに過ぎないので、より詳細に解説した本も欲しいところだ。

それにしても、見ての通り、churchの方法はシンプルだが頭が痛くなる。turingの方法は直感的でわかりやすいが、今度は手が痛くなる。通常の電脳言語は、双方へのショートカットを用意している。もっと言い切ってしまえば、これらへの構文糖衣に過ぎないのが電脳言語とも言える。口に苦すぎる良薬をいかに飲みやすくするか。しかし、糖衣のありがたさは生の薬にふれてこそ実感できる。

また、味わい慣れれば苦い薬すらおいしく感じるようにもなってくる。養命酒の味にハマった事がある人は、Lambda Calculusにもハマる....かも知れない。

Dan the Recursive Lambdacamel