2010年09月28日 00:00 [Edit]

Math - 新言語、(), [] and {}

()[]{}の三姉妹を紹介します。


You gotta love ()!

その名は()、読み方は"parens"です。複数形。ペアでないとsyntax errorなので。()は名前であると同時に、Iコンビネータでもあり、そのチャーチ数は1にしてブール演算のif。名は体をあらわす()、もとい格好の例でもあります。

()が1であることは、以下でご確認いただけます。



実はiotaの娘

()はiotaの娘であり、∴チューリング完全です。

まずは

より、iotaの実装をおさらいすることにしましょう。

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

これは、以下のように定義しなおすこともできます。

iota2jsstr = 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 = function(str){ return eval(iota2jsstr(str)) };


はい。*iiは、JSだとU(U)と同じだということです。

でもコンビネータがιしかないのに、いちいちそれを書くのって冗長ですよね?

∴実装はこうなります。

iota2parens = function(str){
    return iota2jsstr(str).replace(/[^\(\)]/g, '');
};

parens2jsstr = function(str){
    return str.replace(/\(/g, 'U(')
                .replace(/U\(\)/g, 'U(U)')
                    .replace(/\)U\(/g, ')(');
};

parens = function(str){ return eval(parens2jsstr(str)) };


実装そのものが、()がiotaの正嫡であることとチューリング完全であることを同時に証明しています。

興味深いことに、括弧しかないにも関わらず、いやそれ故に正しい()プログラムは同等のiotaプログラムより1ワード短くなります。iotaではiは*より必ず一つ多くなりますが、()では括弧のペアが*に相当し、その代わりiが暗黙されるのでこうなるわけです。

妹言語、[]と{}

iotaにjotという妹がいるように、()にも妹がいます。[]は"brackets"、{}は"braces"とそれぞれ発音します。ここでは[]の実装のみ示します。

parens2brackets = function(str){ 
    return str.replace(/[\(\)]/g, function(m){ return m === '(' ? '[' : ']' });
};

brackets2parens = function(str){
    return str.replace(/[\[\]]/g, function(m){ return m === '[' ? '(' : ')' });
};

brackets = function(str){ return parens(brackets2parens(str)) };


[]の方には、他の姉妹にはない面白い特長が一つあります。何とJSONを装うこともできるのです。

brackets2json = function(str){ 
    return '['
        + str.replace(/\]\[/g, '],[')
        +  ']';
};

json2brackets = function(str){
    return str.substr(1, str.length-2).replace(/[^\[\]]/g, '');
};


さいごに

括弧を蛇蝎のごとく嫌う人たちもいます。Cでさえこんな風にしてしまうほど。

しかし忘れないでください。()はIであり、1であり、IFであるということを。

Remember what they said?

All you need is (). (()こそすべて)

Dan the Esoteric Linguist


この記事へのトラックバックURL

この記事へのトラックバック
404 Blog Not Found:Math - 新言語、(), [] and {} これはLispで実装しとかないとなーという事で書いてみた。Gauche用。 gist: 609899 - parens language (in scheme)- GitHub Schemeのマクロ良く知らんのですけどこんなんで良いのかしら。あと名前の付け方分からん
[esolang][scheme] Parens Language in Lisp【* *scrap*】at 2010年10月05日 02:06
これは恥ずかしい。 10代で読んでいないと恥ずかしい必読書 - その1 - PictorialConnect 何が恥ずかしいって、なんといってもその分量。 必読っていうなら、なるべく短くなくちゃ。
Math - 01者で読んでいないと恥ずかしい必読論文【404 Blog Not Found】at 2010年09月30日 03:34