U-in-BLC

これは恥ずかしい。

何が恥ずかしいって、なんといってもその分量。

必読っていうなら、なるべく短くなくちゃ。

Binary Lambda Calculus and Combinatory Logic

読むべきなのは、こちら。

わずか20ページのこの論文は、著者が見いだした Binary lambda calculus (以下BLC)と Binary combinatory logic (以下BCL)の簡潔な説明であると同時に、Binary抜きの Lambda calculusCombinatory logic の必要充分な紹介ともなっています。

しかしこの論文はあくまでも紹介文。正確には、「読むべきもの」を読むための解説文であり、本当に読むべきものは、すでにあなたは目にしているのです。

そう。本entry右肩の、あのアイコン。

これ、実は Universal Turing Machine (UTM)(正確にはその本体を成す Self Interpreter、E)なのです。210ビットの。

Haskellで実装された処理系uni.lam を「コンパイル」すると、(そのEにΩ = (λx.x x)(λx.x x) を適用し、E⟨Ω⟩とした後の姿である)、236ビットの UTM が得られます。あえて(10|16)進数表記するのであれば、little endian とみなすと

38108887391445187577007730460967697268155469879012070470378073912018314 or 0x58589859dece1fe1fe86c3f34b97a1fe1fe76d0f03f9d0fe7a18180858a

big endian では

35211385256152452183701324955184827616705999399455063746889114210343450 or 0x51a1018185e7f0b9fc0f0b6e7f87f85e9d2cfc3617f87f8737b9a191a1a

となります。

なお、この処理系をGHCでコンパイルするとき、

% make
ghc -O2 -Wall --make Main.lhs -o blc

Main.lhs:2:9:
    Could not find module `Data.List.Split':
      There are files missing in the `split-0.1.2.1' package,
      try running 'ghc-pkg check'.
      Use -v to see a list of the files searched for.
make: *** [blc] Error 1

となるかも知れませんが、その場合は

cabal install split

としてからmakeしなおして下さい。

Why BLC and BCL Matter?

しかしなんでこんなものが必読なのでしょう?

これの読み方を知っている者がこのビット列を読むと、その読み方で書かれたどんな文章でも読めるようになるからです。こういうビット列=文字列は、これの読み方=言語(Language)における Universal Program と呼ばれています。「Cで書かれたC」、「Pythonで書かれたPython」というのはその一例ですが、そうした言語で最初に発見された Turing Machine にちなんで、 Universal Turing Macine (UTM)とも呼ばれます。

こうした UTM の大きさは、その言語の種類に左右されます。複雑な語彙を持つ言語で何かを言う場合、その言葉そのものは短くなりますが、その言語を処理する系 = system は逆に大きくなる傾向にあります。これはまだ語彙が少ない子供の文章と大人の文章を比べても実感できますし、CやJavaとLL言語を比べても実感できます。

ということは、「ある言葉」の複雑さを吟味するときに、その言葉の長さだけ量っても駄目だということです。「バルス」の三語で足りるのは、ラビュタがそれに対応する語彙とそれを解釈するシステムをもっていたからであって、そのシステムがなければバルスはただの音素の集まりにすぎないのです。

それであれば、その言語そのものをその言語で紡いで、その長さを量れば、言語系そのものの複雑さを推し量ることが出来るのではないか?

著者がBLCとBCLにたどり着いたのはそんな動機からのようです。

BCLを実装してみよう

結論から言うと、BLCの方がBCLよりも小さな Universal Machine が作れると論文は主張しているのですが、BLCの方はちょっと説明が大変なので、より簡潔な(代わりに文章が長くなる)BCLの方を実装してみます。

まず 404 Blog Not Found:Math - 言語はどこまで小さくなれるか - (unlambda|iota|jot) のすすめ をもう一度おさらいすることにしましょう。unlambdaの処理系はこうでした。

S = function(x){return function(y){return function(z){return x(z)(y(z))}}};
K = function(x){return function(y){return x}};
I = function(x){return x};

unlambda = function(str){
    return (function(a){
        if (!a.length) throw 'syntax error';
        return { s:S, k:K, i:I }[a.shift()] 
            || arguments.callee(a)(arguments.callee(a))
    })(str.replace(/[^`ski]/g, '').split(''));
};

S、K、Iという「単語」を ιx = xSK にまとめて、S、K、Iは ι の「熟語」で表現することにすると、それは iota になりますが、BLCではSとKをそのまま残す代わりに、このようにしています。

  • [ 00 ] == K
  • [ 01 ] == S
  • [ 1 <term1> <term2> ] == ( [<term1>] [<term2>] )

一種の接頭符号であるわけですが、おかげでunlabmda--とBCLの相互翻訳は実に簡単です。

ul2bcl = function(str){
    return (function(a){
        if (!a.length) throw 'syntax error';
        return { k:'00', s:'01' }[a.shift()] 
            || '1' + arguments.callee(a) + arguments.callee(a)
    })(str.replace(/[^`ski]/g, '').replace(/i/g, '``skk').split(''));
};

bcl2ul = function(str){
    return (function(a){
        if (!a.length) throw 'syntax error';
        return a.shift() === '0' 
            ?  a.shift() === '0' ? 'k' : 's'                     
            :  '`' + arguments.callee(a) + arguments.callee(a)
    })(str.replace(/[^01]/g, '').split(''));
};

bcl = function(str){ return unlambda(bcl2ul(str)) };

それでは、同様に unlambda-- → iota 翻訳機を作った上で、どちらの表現がコンパクトになるかを確認してみましょう。

ul2iota = function(str){
    return str.replace(/[^`ski]/g, '').replace(/[`ski]/g, function(m){
        return { '`':'*', s:'*i*i*i*ii', k:'*i*i*ii', i:'*ii' }[m];
    });
};

U = function(x){return x(S)(K)};

iota = function(str){
    return (function(a){
        if (!a.length) throw 'syntax error';
        return a.shift() === 'i' ? U : arguments.callee(a)(arguments.callee(a));
    })(str.replace(/[^\*i]/g, '').split(''));
};


iotaよりずっとコンパクトです。(一ワードを2ビットで表現できる)unlambda--の二倍よりも少しかさばっていますが、これはBCLがIをSKKで代用してることを反映しているとみなせます。その点、すなわち「チャーチのNOTを表現する」ことに関しては unlambda-- の及ばないことにはなりますが、 self interpreter を実装することまで視野に入れれば、BCLの簡潔さは unlambda-- を上回りそうだという見通しも得られます。

さいごに

この驚くべき Tromp 論文には、 "August 7, 2010" とあります。かなり最近ですね。 Church の Lambda Calculus が完成したのが 1940年、Lispが1958年、Unlambdaが1999年、IotaとJotが2001年。おそらく人類の歴史と大差ないほど長い論理学の歴史から見れば、ごく最近のことですが、天才達が知恵をふりしぼってたどり着いた成果を、今や我々は「たかだかblogの1 entry」でこうして手に取って確認することが出来ます。

そこに至る歴史を知るのも悪いことではありませんが、「10代で知らないと恥ずかしい」のは、10代ではなくそれを10代に対して言う人のことです。物理学を学ぶのにプリンキピアを読めというほど。歴史を学ぶ愉しみは大人になってからでいい。むしろ10代が読むべきは、Tromp論文のように短くて簡潔で現代的で、そして読むにとどまらず手に取って確認できるものではないでしょうか?

Dan the Bloated Man with Redundancy