言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella
トップ > アリゲーター・エッグでラムダ計算

アリゲーター・エッグでラムダ計算

計算の本質は何でしょうか？計算には、足し算引き算掛け算と色々あります。さらに因数分解や微分積分など、計算の種類を挙げればきりがありません。しかし、いくら沢山のルールを沢山覚えても、それで計算の本質を分かった事はなりません。ここで視点を逆転して、より難しい計算ではなく、より単純な計算について考えてみる事にします。

面白いことに、どんな複雑な計算も単純な計算の組み合わせで出来ています。掛け算は足し算の組み合わせですし、引き算は足し算を逆にしたものです。さらに、足し算よりもさらに単純な計算を考える事は出来るでしょうか？昔から沢山の数学者がこのパズルに挑戦し、沢山のモデルが生まれました。今日ご紹介するラムダ計算もその一種です。ラムダ計算は非常に単純な計算モデルですが、単純すぎて計算過程を追うのが難しいです。そこで、アニメーションを使うと仕組みがわかりやすいのでは無いかと考えました(Firefox, Chrome, Safari で動作確認しました)。

まず一番簡単なラムダ式 x です。一つの変数をこのように一つの卵で表します。

この例ではワニが卵を抱いています。このワニは家族です。ラムダ式では λx.x と書きます。まだ何も面白い事は起こりません。

緑のワニ家族の右に青のワニ家族がいます。ラムダ式では (λx.x) (λy.y) です。このようにワニの色は変数名によって変わります。さて、ここで残酷な事が起こります。図をクリックしてみてください。ワニはいつでもお腹が空いているので、左のワニは右のワニを食べてしまいます。しかし食事の済んだワニはお腹が膨れすぎてそのまま死んでしまいます。代わりに卵から新たな生命が誕生します。しかし生まれた子供は不思議なことに、お母さんではなく、食べられた家族にそっくりなのです！という事でこのラムダ式の計算結果は (λy.y) になります。

もう少し複雑な例を見てみましょう。左に親ワニ x と y が縦に二匹と卵 x があって、その右に a と b 二つの卵が二つ並んでいます。この場合、まず上のワニ x が卵 a を食べ、次に下のワニ　y が b を食べます。残った卵 x からは最初のワニが食べた卵 a が生まれます。ということで、計算過程は次のようになります。

(λx.λy.x) a b
(λy.a) b
a

もう一つ特別な白ワニをご紹介します。白ワニはいつでも満腹で、特に他のワニを食べたりしません。ただ、何らかの理由で白ワニが守っている家族が一つになると死んでしまいます。白ワニは、括弧の役割を果たします。

今度は少々難しいルールです。世の中には色や名前は同じだけど、全然家族では無いワニがいます。この例では、y の青いワニが左右二匹いますが、このワニは縦に並んでいないので家族関係ではありません。上の x　ワニが y ワニを食べた後で y ワニは x の卵から生まれ変わるのですが、本当は独立した家族関係が混ざらないように色が変わります。この例では、(λy.y) は色が変わってオレンジの (λy1.y1) になります。

と、まあだいたい必要なルールはここまでで、残りは私の好きなワニ家族たちをご紹介します。

クリックする前に何が起こるか予想できますでしょうか？左のワニが右のワニ家族を食べると、食べられたワニ家族は卵から復活します。卵は二つあるので、二組のワニ家族がうまれ、また永遠に食べ続けます。アニメーションを止めるにはもう一度クリックして下さい。たまに止まります。

もう一つ美しい物を紹介します。これは Y コンビネーターと呼ばれるもので、放って置くと次々増殖する大変危険なワニです。気を付けないと増えすぎてブラウザがクラッシュするので注意して下さい。

さて、最初により単純な計算について考えてみると書いてしまいましたが、正直書くのが疲れたので説明無しで足し算の例だけ上げます。これは 3 + 4 を表します。なぜこれが足し算なのかは Wikipedia に書いてあります。ざっくり言って、一番左の家族が足し算を表し、のこりは緑の卵(s) の数で数字を表します。真ん中の家族は s が三つあるので 3、右の家族は s が四つあるので 4 です。計算が終わると s が七つ残ります。

さて、このアリゲーター・エッグというのはブレット・ビクターさんが Haskell の発明者の一人であるフィリップ・ワドラーに触発されて考案した物です。ブレットさんのアイデアはただのイラストだったのですが、私はこのワニたちが Y コンビネーターのダンスをしている所をどうしても見たくて自分でアニメにしてみました。まだまだ面白いラムダ計算がありますので、自分で実験したい人は http://metatoys.org/alligator/ のページで色々実験してみて下さい。

参考