1024バイトのPythonインタプリタをC言語で実装
Austin Z. Henley氏が、1024バイトのC言語コードでPythonインタプリタを実装するコードゴルフチャレンジに成功した。元の可読版は4800バイト以上であったが、最終的なゴルフ版は正確に1024バイトまで圧縮された。
Austin Z. Henley氏がコードゴルフのチャレンジとして、C言語でPythonインタプリタを実装した。当初は512バイト制限でのチャレンジだったが、これが十分ではないことが判明し、1024バイト制限に拡大された。
インタプリタの機能
このインタプリタは、単一の小文字名を持つ整数変数をサポートしており、算術演算子（+、-、*、%）と比較演算子（<、>、<=、>=、==）を優先順位付きで実装している。制御フロー機能として、if・else文、while ループ（オプションのelse ブロック付き）、for x in range(y) ループ（オプションのelse ブロック付き）に対応している。また、引数なしの関数定義と関数呼び出し（再帰呼び出しを含む）もサポートしており、インデント ベースのブロック構造を使用している。print文は文字列リテラルまたは整数式に対応し、コメントも認識する。
実装の工夫
このインタプリタは再帰下降パーサを採用しており、式を解析と同時に実行する。状態管理はグローバル変数で行われ、プログラムコードは999文字の固定長配列に、変数は256個のシンボルテーブル配列に格納される。ループは逆方向へのジャンプとソースコード再解析により実装され、関数はシンボルテーブル内の位置を保存して、呼び出し時にその位置にジャンプする仕組みになっている。
元の可読版は4800バイト以上あったが、コードゴルフの手法を駆使して正確に1024バイトまで圧縮された。Henley氏は、もしfizzbuuzzのみの動作で良いのであれば、800バイト以下にできると予想している。また、他にも利用可能なゴルフテクニックがあると考えている。
筆者の見立て
- 1024バイトでの実装が可能かもしれないと予想していた
- fizzbuzzのみの実装であれば800バイト以下に削減できる可能性を示唆している
- 他にも活用できるゴルフテクニックが存在すると論じている
この記事は元記事の事実のみに基づいて自動生成されました。
出典
Austin Z. Henley's blog, "Making a Python interpreter in 1024 bytes", https://austinhenley.com/blog/python1024.html (Stack Overflow および GitHub の報道による)