Brainf.ck considered too complicated

小さな言語の代表としては、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であれば以下で全てです。

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(''));
};

ただしナイーブな実装ゆえ、複雑なものだと簡単に call stack を食いつぶしてしまいはしますし、遅延評価の問題などもありますが。きちんとした実装は後ほど紹介するとして、ここでは基本演算をSKIで実装していくことにしましょう。

Prelude

/* bool */
T    = unlambda('k');
F    = unlambda('`ki');
IF   = unlambda('i');
NOT  = unlambda('``s``si`k`ki`kk');
AND  = unlambda('``ss`k`k`ki');
OR   = unlambda('``si`kk');
/* list */
CONS = unlambda('``s``s`ks``s`kk``s`ks``s`k`sik`kk');
CAR  = unlambda('``si`kk')
CDR  = unlambda('``si`k`ki');
NIL  = unlambda('`kk');
NILP = unlambda('``si`k`k`k`ki');
NTH  = unlambda('``s`k`s`k``si`kk``si`k``si`k`ki')
/* num */
ZERO = unlambda('`ki');
SUCC = unlambda('`s``s`ksk')
ADD  = unlambda('``si`k`s``s`ksk');
MUL  = unlambda('``s`ksk');
POW  = unlambda('``s`k`sik');
PRED = unlambda('``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k'
            +   '``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`ki');
SUB  = unlambda('``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s'
            +   '`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik');
/* Y combinator and others */

Y CombinatorももちろんSKIで実装できるはずなのですが、上記の問題を回避するため以下はJS側で実装しておくことにします。

Y = unlambda('```ss`s``s`ksk`k``sii'); /* needs a lazy evaluator */
Y = unlambda('``s``s``s`ksk`k``sii``s``s`ksk`k``sii'); /* eagar eval OK, but */
Y    = function(f){ /* to save call stack, Y and others are hand-crafted */
    return (function(g){return function(m){return f(g(g))(m)}})
            (function(g){return function(m){return f(g(g))(m)}})
};
IFR  = function(p){return function(x){return function(y){
    return IF(p)(x)(y)(I) /* wrap x and y with function(){} -- see cnfact */
}}};
LSOF   = function(a){return Y(CONS(a))}; /* (infinite) list with elem. a */
CNEQ   = function(m){return function(n){ /* n == m for church num. */
    return NTH(n)(m(CONS(F))(CONS(T)(LSOF(F))))
}};
CNNE   = function(m){return function(n){ /* n != m for church num. */
    return NTH(n)(m(CONS(T))(CONS(F)(LSOF(T))))
}};

js utilities

これだけでは動いているところが見づらいので、さらに「ふつうのJS」とやりとりするためのユーティリティも用意しておくことにしましょう。

cb2bool = function(p){return p(true)(false) };
cn2num  = function(n){return n(function(i){return i+1})(0)};
ary2cl  = function(a){
    if (a.length === 0) return NIL;
    var c = a.shift();
    return CONS(c)(arguments.callee(a));
};
cl2ary  = function(l){
    var a = [];
    for (;!cb2bool(NILP(l)) ; l = CDR(l)) a.push(CAR(l));
    return a;
};
/* special numbers */
cn1   = SUCC(ZERO);
cn2   = ADD(cn1)(cn1);
cn4   = MUL(cn2)(cn2);
cn16  = POW(cn2)(cn4);
cn256 = POW(cn4)(cn4);

/* numerals up to 255 */
cn  = (function(a){
    var i, j, n, m; 
    for (j = 0, n = ZERO; j < 16; j++, n = SUCC(n)) {
        for (i = 0, m = ZERO; i < 16; i++, m = SUCC(m)){
            a[j*16+i] = ADD(MUL(cn16)(n))(m);
        }
    };
    return a;
})([]);

/* for lazy-k evaluator */
str2cl = function(s){
    var a = [], i, l;
    for (i = 0, l = s.length; i < l; i++) a.push(cn[s.charCodeAt(i)]);
    return ary2cl(a);
};
cl2str = function(l){
    var a = cl2ary(l), i, l, cs = [];
    for (i = 0, l = a.length; i < l; i++){
        cs.push(String.fromCharCode(cn2num(a[i])));
    };
    return cs.join('');
};
/* unlambda to js in string */
ul2jsstr = 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(''));
};

Demo

ここまで準備しておけば、もう十二分に遊べます。

iota & jot

[`ski]でも驚きですが、さらにシンボルを減らすことは可能でしょうか?

もちろん。

たとえばiは``skkと等価です。

みんなー、SKKしあってるくぁーい?

さらにιx.xSKというコンビネーターを定義してしまえば、ιでSもKも再現可能となります。

残ったのは、ιコンビネーターとその適用だけ。

それが、Iotaです。

iotaではιを表記するのにiを、そしてそれを適用するのに*を使っています。

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はすでに究極、Turing Tarpitの底に到達していますが、その父 Chris Baker は、それに飽き足らず、iotaにJotという妹まで与えています。

B = function(x){return function(y){return function(z){ return x(y(z))}}};

jot = function(str){
    return (function(a, v){
        return !a.length ? v 
            : a.shift() === '0' ? arguments.callee(a, U(v))
                                : arguments.callee(a, B(v))
    })(str.replace(/[^01]/g, '').split(''), I);
};

iotaとの最大の違いは、iotaには syntax erorrがありえるのに対し(たとえば*はiよりも必ず一つ少ない)、jotではそれがないこと。何をする関数となるかはさておき、全てのビット列は正しいjot文であるという意味においても究極です。

• Iota and Jot: the simplest languages?

Lazy K

これらの集大成ともいえるのが、Lazy Kです。

• The Lazy K Programming Language
  • Index of /essie2/download/lazy-k

正確には新言語ではなく、unlambda-- + iota + jot という構成になっています。Unlambdaから[`ski]以外を取り去り、iotaとjotを加え、実行時のI/Oストリームを、文字をチャーチ数表記し、それらをさらにチャーチリストでまとめたものに置き換えたというわけです。

なので、catコマンドはLazy Kではi一文字。これはすごい。

C++の実装が上のlinkにあるのですが、そのままではコンパイルできませんでした。以下のpatchをlazy.cppあててからg++ lazy.cpp -o lazykとすればいけます。

Lazy-K Patch

--- lazy-k.orig/lazy.cpp	2002-03-13 20:34:12.000000000 +0900
+++ lazy-k/lazy.cpp	2010-09-26 04:26:51.000000000 +0900
@@ -32,7 +32,6 @@
 
 
 #include <stdio.h>
-#include <io.h>
 #include <fcntl.h>
 #include <stdlib.h>
 #include <ctype.h>
@@ -56,7 +55,7 @@
 public:
 	enum Type { A, K, K1, S, S1, S2, I1, LazyRead, Inc, Num, Free } type;
 
-	static void* operator new(unsigned) {
+	static void* operator new(size_t) {
 		Expr* result = free_list;
 		if (result) {
 			free_list = result->arg1;
@@ -562,10 +561,12 @@
 			case 0:
 				e = append_program(e, &File(stdin, "(standard input)"));
 				break;
-			case 'b':
-				setmode(fileno(stdin), O_BINARY);
-				setmode(fileno(stdout), O_BINARY);
-				break;
+ 			case 'b':
+#ifdef O_BINARY
+ 				setmode(fileno(stdin), O_BINARY);
+ 				setmode(fileno(stdout), O_BINARY);
+#endif
+ 				break;
 			case 'e':
 				++i;
 				if (i == argc) {

このLazy K "SDK"、むしろうれしいのは付属のschemeファイルかも知れません。これを使うとschemeをunlambda/iota/jotのマクロとして使うことができます。さらに bf2lazy.cなんてファイルもあって、これを使うとBFプログラムをunlambdaに翻訳することができたりといたれりつくせりです。

Enjoy!

Dan the Lazy Blogger with SKK