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

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

Austin Z. Henley

私は人々のためのツールを構築しています

---

---

2026年9月6日

［画像: GolfされたC言語コードの1024バイトのスクリーンショット。］

この記事の議論はHacker News、r/programming、およびLobste.rsでご覧ください。

人間らしく感じるために、週末には手書きでコードを書いています。

私の最新の挑戦は？ 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()

1024バイトのコードでPython言語のすべてを収めることはおそらくできません。では、Pythonらしく見えるものを何なら収めることができるでしょうか？

このfizzbuzzプログラムは、明らかにPython風に見えます。def、コロン、インデントがあり、if文に括弧がありません。私にはPythonに見えます！もちろん、構文のサブセット以外にもいくつかの制限を追加する必要があります。

私の最初の試みはひどいものでした。

最初のアプローチ: 512バイトでは足りない！

私は多くの再帰下降パーサーを書いてきたので、これはどれほど違うのでしょうか？ Pythonのサブセットは、私が実装した他の言語（例えば私のTeeny Tinyコンパイラ）と似ているはずです。

最も基本的なコードから始めました： 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') {
        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"をスキップ。    */

トークンの境界が正しいと仮定し、ほとんどの空白を削除します。文字列リテラルのインデントとスペースは保持します。

変数名は単一の小文字に限定されており、シンボルテーブルのルックアップを直接行うことができます。

    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ループの両方が、条件式の位置を追跡します。本体が実行された後、その位置にジャンプしてパースを続行します。

関数も同様に機能します。定義をパースするとき、シンボルテーブルはソースコード内の関数の位置を記憶します。次に、関数呼び出しをパースするとき、呼び出し元 location が保存され、パーサーは関数本体にジャンプし、本体を実行し、終了時に呼び出し元 location を復元します。

中間表現がなくても、これほど美しいことができるとは！ インタプリタは状態も非常に少なく維持しています。

ミニファイ！

私はあまりコードゴルフをしたことがありません。変数名や空白をトリミングするのは明白ですが、大きなバイトをどうやって節約するのでしょうか？

Stack Overflowという、昔のコードマジシャンたちが知識を共有していた、古くて忘れられたウェブサイトが存在します。私はC言語でのゴルフのヒントから多くのアイデアを学びました。

［画像: Stack Overflowのコードゴルフスレッドのスクリーンショット。］

ルールは自分の想像の中にしか存在しないので、創造的にならざるを得ませんでした。それらのヒントのいくつかは、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値を使用しています。

別の例は、行末までスキップするヘルパー関数です。

void skip_to_eol(void) {
  if (ch != 0 && ch != '\n') {
    next();
    skip_to_eol();
  }
}

これをY(){c&&c-10&&Y(G());}に短縮しました。0をテストし、10を引いて改行をチェックし、&&をifの代わりに使っています。そして、G();Y();の代わりにY(G());とすることで1バイト節約しています。賢い！このStack Overflowの投稿に改めて感謝します。

すべてが終わった後、ゴルフされたバージョンは1024バイトになりました！

最終的な読みやすいバージョンは4800バイトを超えています。当初はさらに多くの機能を盛り込んでいましたが、収めるためにカットし続けました。比較式は次の削減対象でした。なぜなら、それらは多くのバイトを消費し、真偽値はそれらなしでも機能するからです：if n%15:。

もしfizzbuzzを機能させることだけを気にかけていたなら、800バイト以下にできると思います！ 他にもゴルフのトリックがあるかもしれません。

［画像: ゴルフされたコードのバイト長をチェックし、コンパイルして、それを使ってfizzbuzzを実行しているターミナルのスクリーンショット。］

ここに、栄光のゴルフされたソースコードがあります。

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つのみ）
• 整数としての真偽値
• if および else
• while ループ（elseブロックを含む）
• for x in range(y) ループ（elseブロックを含む）
• 引数なしの関数定義
• 関数呼び出し（再帰呼び出しも含む）
• インデントベースのブロック（スコープなし）
• 単一の文字列リテラルまたは整数式を使用したprint
• コメント

もうしばらくコードゴルフのチャレンジはしないと思います。プロセスは非常に退屈で、ゴルフ中のバージョンと元のバージョンを行き来して、2分前に変更したことを理解しようとしました。両方のバージョンはGitHubにあります。

さあ、あなたの番です。あなたの1024バイトのPythonはどのようなものですか？