asin:0192801422
To Mock a Mockingbird
Raymond M. Smullyan
[邦訳:数学パズル ものまね鳥をまねる]

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

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









さいごに




asin:B003YY8K92

1967~1970

The Beatles



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


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


Remember what they said?


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


Dan the Esoteric Linguist