CのサブセットをJSで実装した

f:id:fujidig:20170403225601p:plain

CのサブセットをJavaScriptで実装しました。

以下のページで動かせます。

https://fujidig.github.io/c-subset-in-js/

ソースコードは以下

https://github.com/fujidig/c-subset-in-js

実装している機能は以下の通り。

型は多倍長整数型のみ (それをintと書いている)
変数代入、参照
各種演算子
if, else, while
関数呼び出し, return

たとえば

int fib(n) {
    if (n <= 1) return 1;
    return fib(n - 2) + fib(n - 1);
}
int main() {
    int i = 0;
    while (i < 20) {
        print(fib(i));
        i = i + 1;
    }
}

を実行すると次を得ます。

整数型が多倍長であるため次のようなプログラムを動かすと簡単に2の1000乗を出力できます。

int main() {
    print(1 << 1000);
}

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

また、コードを自然数に符号化する機能を搭載しています。

さらにCのサブセット自身で実装したCのサブセットのインタプリタがついています。

これにより、Cのサブセット in 「Cのサブセット in JS」ができます。

やってみましょう。

int main() {
    int a = 233, b = 377, c;
    int n = 1;
    while (n <= 5) {
        c = a + b;
        a = b;
        b  = c;
        print(c);
        n = n + 1;
    }
}

再帰フィボナッチは遅いので変更しました。また、フィボナッチ数の途中から5項を表示するよう変更しました。

これを実行すると

が得られます。

実行する代わりにEncodeボタンを押すと

2151370312757585239013893921680792355662486752412569148118764178423124275394560545515699620618390679749954365463276712440703239868128831904427466606016571762297213794979160614374073563745430656004482516317773057589341025004447961146147390127286244343288796934705377531463089162718506253985211455134666431223509512551974414474343672462798521790265803007504943944452569884958093931851114825905529277320800919509394108815581895937704399123986982191200330618144264490236450820715210311575386269331510535250444367316207434769401257253036824832178335578381245463684416737106182236342817759700301368800684649996332165657549447346233743185772934210938808280331980784115355655494351600163821670576622405334837112429337898494085760016249953010029070098290452099149093585994645858969474021323699095659397804178564149616100171888900802875821501165465628689469074724933056047927805153388198042811328724820317873906070961308820216848154752868246705991047232511137406181737589847980927438034993293142569425322534863372670621084881997309475592027063848468052474819497979418075183190689400892317362249982654264328698779198933832859573184531758281526678767231853049237813637063306722059557355922220218076338507472883800169331749000288864555086756341752671027190130207526809765937180

が得られます。

これをc-subset.cのmain関数内のevalの第一引数に指定します。

int main() {
    return eval(2151370312757585239013893921680792355662486752412569148118764178423124275394560545515699620618390679749954365463276712440703239868128831904427466606016571762297213794979160614374073563745430656004482516317773057589341025004447961146147390127286244343288796934705377531463089162718506253985211455134666431223509512551974414474343672462798521790265803007504943944452569884958093931851114825905529277320800919509394108815581895937704399123986982191200330618144264490236450820715210311575386269331510535250444367316207434769401257253036824832178335578381245463684416737106182236342817759700301368800684649996332165657549447346233743185772934210938808280331980784115355655494351600163821670576622405334837112429337898494085760016249953010029070098290452099149093585994645858969474021323699095659397804178564149616100171888900802875821501165465628689469074724933056047927805153388198042811328724820317873906070961308820216848154752868246705991047232511137406181737589847980927438034993293142569425322534863372670621084881997309475592027063848468052474819497979418075183190689400892317362249982654264328698779198933832859573184531758281526678767231853049237813637063306722059557355922220218076338507472883800169331749000288864555086756341752671027190130207526809765937180
, 0, 0);
}

int eval(int code, int nodeid, int vars) {
    int type = node_type(code, nodeid);
....

これを実行すると

が得られます。Cのサブセット in 「Cのサブセット in JS」ができました！

さて、Cのサブセット in 「Cのサブセット in JS」ができたらCのサブセット in 「Cのサブセット in 「Cのサブセット in JS」」もできそうですね。

出来ます。

上のコードをエンコードすると

5980329765610774127525245562340339041698066219641944319743934783175611745424082081909469512081526404990329327307663133360222179842204167878590696763364369328310595163512492390306181732744829222117518824617582650725740141952748499132995210154143453650196442366092313540868501218530765785202077459350045124230485161555127015535579281731237549416807088489950668251201877691301786506164869080335350936836780724474957976693965274738312936528413281682587340098367064230914323095122080804227660640366503916932207643381263729480625878251063342344491321746310705742164611935632444361598814398154552165339705969745088135940227990524875871445306557373704956903790714486847060660398146659416808412916342257564327042373789893508885075423093377342769000461009027832643305332470849028124039319790277321370911576608973742123713974755184012440142143498846118718870205865840232155186970509391712672169731177405233(中略)510598683619980655730447704072561755011557496861802213363042657146272152051448253232537222993284478241218521508753627807397667295345210321588828661028882576723361390442917570826740418840091727961426165295412166642922565427783394382300102978854750486841360479884360285646613836830334791874344769258423639706904789757288203770209076874980661725022227457454699592036668175729583056522607392923069630915743528982026403631785420924844469140930747327055844004757819140600689335892552518129228445853661349397832112260734508951124297567328771727350631899147423428097500075927570655026017406849604335337201966560953461194685273199307383470572710728285812162887665935977834511174577930840561717165020285218028369094475113108152679840829208807917849465770186516199998023505234400192250998515347296598256278102675603598662702878579009777455897033506640154580988505799442586296556106438320022128549948147421815478517853957228970488937248269631079685300035177024830468421766270037213040053707234917678845100597776938552755275192861496

という37957桁の自然数が得られます。これをc-subset.cのmain関数内のeval呼び出し部分に入れて実行してみましょう。

時間がかかります。

f:id:fujidig:20170403232236p:plain

ブラウザがこのようなアラートを出すほど時間がかかりますが待ちましょう。

結果、次の出力が得られます。

Cのサブセット in 「Cのサブセット in 「Cのサブセット in JS」」が出来ました！私の環境だと実行を終えるのに61秒かかりました。たくさん時間がかかるとはいえ、間違いなく実現できています。よかったですね。