1024バイトでPythonインタプリタを作成する

Austin Z. Henley 私は週末にコードを手書きすることで人間らしさを感じています。私の最新の挑戦は？ わずか512、いや1024バイトのCコードでPythonインタプリタを作ることです。しかも、マクロの悪ふざけやライブラリのくだらない使い方は一切なしです。 def buzz(): for n in range(101): if n % 15 == 0: print("FizzBuzz") else: if n % 3 == 0: print("Fizz") else: if n % 5 == 0: print("Buzz") else: print(n) buzz() おそらく、Python言語のすべてを、わずか1024バイトのコードでできたインタプリタに詰め込むことはできないでしょう。では、Pythonらしく見えるものを何なら詰め込めるでしょうか？ このfizzbuzzプログラムは、明らかにPythonらしいです。def、コロン、インデントがあり、if文に括弧がありません。私にはPythonに見えます！ もちろん、コードサイズ以外にもいくつかの制限を追加する必要があります。 私の最初の試みはひどいものでした。最初の試み：512バイトでは足りない！ 私は多くの再帰下降パーサーを書いてきましたが、これがどうしてそんなに違うのでしょうか？ Pythonのサブセットは、私が実装してきた他の言語と似ているはずです。私は考えられる最も基本的なコードから始めました： 1 + 2 次に、それをより複雑にしました： x = 1 + 2 * 3 そして、ステートメントさえ追加しました： if x > y: z = 3 これで電卓ができあがりました… このチャレンジでやりたかったこととは違います！ すでに制限を超えていました。そこで、私はズームアウトして、Pythonらしい要素のリストを作成し、同時に私のコードゴルフのスキルが512バイトに収まるほどではないことに気づきました。もしかしたら1024バイトならできるかもしれません？ まずは動くようにして、それから小さくします。 パーサー 実際には、CPython実装はPythonソースをトークン化し、抽象構文木に解析し、いくつかの分析と最適化を実行し、バイトコードを生成し、そしてそのバイトコードを解釈します。これは実際には何も行いません。状態はいくつかのグローバル変数に保持されます。これは固定長の配列（現在は999）を使用し、生のPythonコードを保持します。変数と関数名はすべて単一の配列に収まります。 char src[999]; /* ほとんどのスペースを除いたプログラム全体。 */ int vars[256]; /* シンボルテーブル。 */ int pos; /* srcの次の文字。 */ int ch; /* srcの現在の文字。 */ int line_start; /* 現在の行が始まる場所。 */ 式は、他の再帰下降パーサーと同様に扱われ、実行中に実行されます。たとえば、次のようになります。 int parse_sum(void) { int value = parse_term(); while (ch == '+' || ch == '-') { if (ch == '+') value = value + parse_term(); else value = value - parse_term(); } return value; } ここまでは順調です。エラー処理は一切ありません！ コードの正しさに基づいて多くの仮定をしています。たとえば、キーワードがすべて正しく入力されていると仮定しています。 if (ch == 'w' || ch == 'i' || ch == 'f') { /* ---- while / if / for ---- */ int keyword = ch; int loop_var = 0; if (keyword == 'f') { /* "for K in range(N):" */ pos += 2; /* "or" をスキップ */ loop_var = next(); /* ループ変数 */ pos += 8; /* "inrange(" をスキップ */ vars[loop_var] = 0; } else if (keyword == 'w') pos += 4; /* "hile" をスキップ */ else pos += 1; /* "if" の "f" をスキップ */ トークンの境界が正しいと仮定し、ほとんどの空白を削除します。文字列リテラルのインデントとスペースは保持します。変数名は1文字の小文字に制限されており、これによりシンボルテーブルのルックアップを直接行うことができます。 if (ch > 96) { value = vars[ch]; next(); } 制御フローの魔法 コードブロックを実行する関数は、インデントが減少するまで続きます。それが起こると、関数は戻り、次の行を処理するのは呼び出し元の責任です。したがって、Cプログラムのコールスタックを使用して再帰を処理しています。 void run_block(int min_indent) { for (;;) { int indent = read_indent(); if (ch == '\n') continue; if (indent < min_indent || ch == 0) { pos = line_start; return; } } } しかし、ループはどうでしょうか？！ 何もコンパイルされないため、ループは後方にジャンプして各イテレーションでソースを再解析することで機能します。whileループとforループの両方が、条件式の位置を追跡します。本体が実行された後、その位置に戻って解析を続行します。関数も同様に機能します。定義を解析するとき、シンボルテーブルはソースコード内の関数の位置を記憶します。次に、関数呼び出しを解析するとき、呼び出し元のアドレスが保存され、パーサーは関数本体にジャンプし、本体を実行し、終了時に呼び出し元のアドレスを復元します。中間表現がなくても、これほど美しいことができるとは！ インタプリタは状態もほとんど維持しません。 最小化！ 私はあまりコードゴルフをしませんでした。変数名と空白をトリミングするのは明白ですが、大きなバイトをどうやって節約するのでしょうか？ Stack Overflowという、昔のコード魔術師たちが知識を共有した、古くて忘れられたウェブサイトが存在します。私は「Tips for golfing in C」から多くのアイデアを学びました。 ルールはあなたの想像力の中にしか存在しないので、創造的になる必要がありました。それらのヒントのいくつかは、GNU C89に固有の「機能」に依存しています。これはくだらないことではありません！ これは慣習的なごまかしです。読みやすいバージョンからバイトを削るために行ったことは次のとおりです。 * 単一文字の変数名と関数名 * コンパイラがlibcをリンクすると仮定する * 一時変数のためにグローバル変数を使用する * グローバル変数はゼロ初期化される * C89では、変数の宣言は暗黙的にintであると許可され、関数はintを返すと仮定される * 関数パラメータを、コールスタック上で保持される一時変数として使用する * 文字リテラルの代わりにASCII値を使用する * 三項演算子とカンマ演算子 * 論理演算子の代わりにビット演算子を使用する たとえば、先ほど示したparse_sum(void)関数は、e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}にゴルフされました。数バイトを節約するためにASCII値を使用しています。すべてが終わった後、ゴルフされたバージョンは1024バイトになりました！ 最終的な読みやすいバージョンは4800バイトを超えています。 当初はさらに多くの機能がありましたが、収めるためにカットし続けました。比較式は次に削除されたもので、多くのバイトを消費し、それらがなくても真偽値は機能します：if n%15:。fizzbuzzを動作させることだけが目的であれば、800バイト未満にできると思います！ 他にもゴルフのトリックがあるかもしれません。ここに、ゴルフされたソースコードをすべて示します。 char s[999];v[256],p,c,x,y,z,w,u; G(){return c=s[p++];} I(){for(u=p;G()==32;);return p-u;} Y(){c&&c-10&&Y(G());} f(){x=0;if(G()>96)x=v[c],G();for(;c-48u<10;G())x=x*10+c-48;return x;} t(g,h){for(g=f();c==42|c==37;)h=c,g=h-42?g%f():g*f();return g;} e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;} E(a,q){a=e();if(c-60u>2)return a;w=c-61;q=G()==61;p-=!q;x=e();return w?(a-x)*w>-q:a==x;} S(i){for(;I()>i|c==10;)Y();p=u;} Q(){for(G();G()-34;)putchar(c);G();} B(i,q,j,k,a,m,n){for(;;){j=I();if(c==10)continue;if(j<i|!c){p=u;return;}if(c==119|c==105|c==102){k=c;k-102?p+=k/4-25:(p+=2,m=G(),p+=8,v[m]=0);q=p;for(;;){a=k-102?E():v[m]<E();p+=k==102;G();if(!a){S(j);break;}B(j+1);if(k==105)break;k-102||v[m]++;p=q;}I()-j|c-101?p=u:(p+=4,G(),a?S(j):B(j+1));}else if(c==100){p+=2;k=G();Y();v[k]=p;S(j);}else{if(c>96){k=c;while(G()>96);c==40?k-112?(G(),n=p,p=v[k],B(2),p=n,G()):(s[p]-34?printf("%d",E()):Q(),puts(""),G()):(v[k]=E());}Y();}}}main(q,m,h){for(h=m=q=0;~(c=getchar());){c=c-9?c:32;h^=c==34;s[q]=c;q+=c-32?1:!m|h;m=c>32|m&&c-10;}B(0);} 最終的に、以下の機能を実装できました。 * 整数変数（1文字）とリテラル * 変数代入 * + - * % を使用した算術演算（優先順位あり、単項 +/- は式の先頭でのみ機能） * < > <= >= == を使用した比較（1つの式につき1つのみ） * 整数の真偽値 * if および else ループ、else ブロックを含む * for x in range(y) ループ、else ブロックを含む * 引数なしの関数定義 * 関数呼び出し、再帰呼び出しを含む * インデントベースのブロック（スコープなし） * 単一の文字列リテラルまたは整数式でのprint * コメント 近いうちにコードゴルフチャレンジを行うことはないと思います。プロセスは非常に退屈でした。