2006年04月16日 13:53 [Edit]

TuringとChurchの狭間で

なんでひげぽんが反復がすぐにわからなかったかを憶測すると、「変数とは代入すべきもの」、という手続き型言語の呪縛が思い立つ。ひげぽんは別にがっかりする必要はない。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


この記事へのトラックバックURL

この記事へのトラックバック
前回、 おとうさんにもわかるYコンビネータ!(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。 Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換
さあ、Yコンビネータ(不動点演算子)を使おう!【よくわかりません】at 2009年04月22日 20:46
私はむしろ気違いに見られることの方が多いぐらいなので、正義とかの信念をもっちゃう人にはついていけない一方.... 自分も - finalventの日記自分も気違いに見られることがあるし、そういう人に親近感を覚えてしまう部分も大きいけど、正義とかの信念をもっちゃう人にはつ....
「一億分の一」と「百兆分の百億」の違い【404 Blog Not Found】at 2008年11月29日 22:18
Scalar::Lazyというモジュールをこさえたのでお報せします。 /lang/perl/Scalar-Lazy/trunk - CodeRepos::Share - Trac Dan Kogai / Scalar::Lazy - search.cpan.org
perl - Scalar::Lazy released!【404 Blog Not Found】at 2008年06月02日 02:39
Lambda Calculas 無名関数のことと思っていい? λ...   λ...  λ... WikiPedia:ラムダ計算, アロンゾ・チャーチ &quot;The Calculi of Lambda Conversion&quot; α変換 (alpha conversion) β簡約 (beta reduction) η変換 (eta conversion) チューリングマシンと等価 T...
ラムダ計算【assari (PukiWiki/TrackBack 0.3)】at 2008年02月02日 13:38
このY Combinatorの話題も、実名匿名論争ほどではないにしろ時折ネットを駆け抜ける風になる話題ですね。 Y コンビネータって何? - IT戦記Y コンビネータいみふ><! で、私を含め、 Y Combinator が何なのか、何が凄いのかというのを解説する人はたくさんいるのだけど、...
Y談 - 自分って自明?【404 Blog Not Found】at 2008年02月02日 02:42
「リクナビNEXT 『エンジニア適職フェア』 - 梅田望夫(WEB進化論著者)×近藤淳也(はてな社長)特別対談」という対談をYouTubeでみました。 学生にも見せたいなと思いました。ネットの世界はいま2度目(?)のちょうど面白い時期ですので学生たちにはうまくこのタイ
[技術][大学] My Life Between Silicon Valley and Japan, はてな近藤との対談映像「変化する時代で自分を生かす人」【one of ( external ) mnemonics】at 2006年07月17日 04:05
しかし、ここでの特徴は、「普通の数値に戻す」ことではなくて、「関数をそのまま数として扱う」ということにある。これで、数そのものの「作り方」はわかったが、そこから任意の数を作るための「演算」はどうしたらよいのだろう? 例えば、自然数は、次の数を求める一般的...
[プログラミング][scheme]Church 数のメモ - つづき。【oto-oto-oto日記】at 2006年04月19日 00:27
いやあ、脱帽。 The Road to Reality Roger Penrose これはすごい本だ。まだ邦訳はないみたいだけど、オイラーの贈り物を気に入った人ならすぐ注文すべきだ。大丈夫。高校修了の数学力と英語力でちゃんと読み通せるから。騙されたと思って上をポチッとクリックする....
Paved by Roger Penrose【404 Blog Not Found】at 2006年04月18日 14:29
[http://blog.livedoor.jp/dankogai/archives/50458503.html:title] で少しすっきりしたので、分かったところまでメモ。 0 := λ f x . x 1 := λ f x . f x 2 := λ f x . f f x 自然数 [tex:¥huge n] の場合を自分用に噛み砕いて。 自然数 [tex:¥huge n] は、2 変数関...
[プログラミング][scheme]Church 数のメモ【oto-oto-oto日記】at 2006年04月18日 00:59
この記事へのコメント
こんにちはいろいろとお世話になっています。
正直、現段階では danさんの書いているこの記事の1/4も理解できていません。
分かるまでがんばります!
Posted by ひげぽん at 2006年04月16日 22:54