To Mock a Mockingbird

著者 : RaymondSmullyan

• Oxford University Press (2000年11月30日発売)

感想・レビュー・書評

[kohyamaさんの感想 · 2010年11月22日]

前書きの, 前作を読んだ女性からの手紙のくだりで引き込まれる.

前半は論理パズル. 後半はコンビネータ論理の話.

コンビネータ論理は, 一引数を取り関数を返すような関数しかない世界. もちろん返される関数は一引数を取り関数を返す関数. （なんとこの体系はチューリング完全である.）

この本の著者スマリヤンは, これを, 鳥の名を呼べば別の鳥の名を答える鳥達のいる世界として描いている.
コンビネータに鳥の名前を付けたのはスマリヤンが最初なのだろうか.

もちろん「ものまね鳥」はこの世界で重要な役割を果たす鳥である.

邦訳はこちら http://booklog.jp/asin/4627019092 で.

[隆一郎さんの感想 · 2010年9月27日]

小さな言語の代表としては、Brainf.ckがあげられます。人前でいいづらいその名はとにかく、設計は実にエレガントなもので、Shibuya Perl Mongersの現代表の竹迫良範氏をして、

最もタメになる「初心者用言語」は Brainf*ck！ - TAKESAKOのはてな出張所
といわしめるほどのものであり、実際言語処理系の演習などではこれはネタではなくベタと言っても過言ではなく、私自身404 Blog Not Found:brainfu.k - BF2JS opimizing compilerやLanguage::BF - search.cpan.orgなど、もうなんべんともなく実装しているのですが、命令8つとはいかんせん多すぎます。

実際これを減らすというのもまた esoteric linguists の愉しみの一つで、私自身404 Blog Not Found:brainfu.k って命令大杉ね?でチューリング完全を Linear bounded automaton にまで落とす代わりに命令を半減させるという提案をしていますし、BF instruction minimalization - Esolangを見るとさらにその先にまで進んでいるようですが、いずれの場合も元祖BFほど美しく見えないのは、「命令を無理してまとめている」ところにありそうです。

Unlambda (LAZY-K version)
それでは。他に手だてはないのでしょうか?

希望の光は、命令型ではなく関数型の方からさしているように見えます。

たとえば、SKI combinator calculus。これを使うと、ラムダ計算を、 S, K, I という三つの関数 - コンビネーターに集約することが出来ます。これに関数の適用 -- 命令型言語のほとんどではfunに対するfun()相当 --を加えた4つのシンボルがあれば、チューリング完全な言語を実装するのに充分ということになります。

これを実現したのがUnlambdaですが、元祖Unlambdaには余計な関数も数多く入っています。そこから不要なものを取り除き、純粋化したのがLazy Kなのですが、表記法は同じ。例えば(S(K))(I)であれば``skiと表記します。必要なシンボルは[`ski]の四つ。一挙に半減です。

コンパクトなのは仕様だけではなく実装もそうで、JavaScriptであれば以下で全てです。