セプキャン2011感想文

みんながバイナリ*1とかバイナリ*2とかUCAS*3とかで書いて読むのに苦労したから、僕はちゃんとASCIIで書きましたよ!

https://gist.github.com/1156669

言語仕様

1文字1トークンで、単純に並べるだけで関数呼び出しになる。たとえば「XYZ」というコードがあった場合、これはPythonでいうところの「X(Y)(Z)」に相当する。つまり「関数Xに引数Yを渡して呼び出し、その返り値の関数に引数Zを渡して呼び出す」という意味だ。

括弧()は特別な意味を持っていて、まあみんなの期待通り処理をまとめるのに使われる。評価は内側の括弧から順番。たとえば「X(YZ)」というコードがあった場合、これはPythonでいうところの「X(Y(Z))」に相当する。つまり「関数Yに引数Zを渡して呼び出し、その返り値を引数として関数Xを呼び出す」という意味だ。あと一番内側が複数個ある場合は一番出現が早いものが評価される。「( (01)(02)(03) )」だと01,02,03の順に実行されるってことね。(追記:「一番内側」という言葉が「一番カッコの深いところ」と誤解されうるのでもう一言書いておくと「( (01) (0(02)) (03) )」は01, 02, 0(02), 03の順に実行される。)

組み込み関数がU, 0, 1の3つ。あと名前付けのための特殊形式+がある。

一番独特なのは数値が全て関数でもある点で、整数オブジェクトはその数だけ増やす関数としても扱える。1は整数の1であると同時に関数でもある。たとえば「11」は「1という関数に引数1を渡したもの」になるので2になる。ただし、0だけは0増やす関数になっても面白く無いので引数を出力する関数にした。返り値は引数に0を足したものになる。先ほどの例にあった「( (01)(02)(03) )」は1,2,3の順に出力し、その後(123)を評価して6を返す。

あと特殊形式+は値を名前に束縛する。「+X(11)」とやると、(11)が整数の2になってからそれをXという名前に束縛する。だからそれ以降「XX」とかやれば関数2に数値2を入れたことになって4が返る。評価の順番に注意。意外に思うかも知れないが「X(+X(11))」は最初のXが評価されるのより+Xで束縛される方が先なのでエラーにならずに実行される。なお(+XY)の返り値はYである。

もう一度例を挙げると、「(0(1(01)))」はまず(01)が評価されて1が出力され、(0(11))の(11)が評価されて2になり、最後に(02)が実行されて2が出力される

組み込み関数Uの仕様は http://en.wikipedia.org/wiki/Iota_and_Jot を参照。

言語の名前はspcampでバージョン番号が2011.0.0。

他になにか言うことあったかなぁ。不明な点があれば気兼ねなくコメントしてください。

ソースコードにSとかKとかIが出てきているのはかなり親切に書いたつもり。全部Uで書いてもよかったんだけど本質的じゃない部分で読みづらいし。特殊形式の+とかもSKIをUから定義してコードをコンパクトにするために作ったわけだし。S,K,Iについて良い日本語の記事がどこにあるかわからなかったので SKI combinator: http://en.wikipedia.org/wiki/SKI_combinator_calculus を参照。(追記:Uの仕様も含めて404 Blog Not Found:Math - 言語はどこまで小さくなれるか - (unlambda|iota|jot) のすすめがよくまとまっている)

1文字1トークンだからレキサーいらないし、構文も括弧で木構造なだけだからパーサも簡単。処理系はPythonで書いてて、doctestでテストケースたくさん書いて300行程度だからテスト削ったら200行くらいかなぁ。dis.disでバイトコードにディスアセンブルして562行くらい。SimpleHTTPServerよりちょこっと小さい。

追記: 12:03時点でメールで1通の正解が送られて来ました。