Show HN: ケント・ダイブビッグのスキームマシンを400行のCで実装（ヒープメモリモデル）

231日前原文(gist.github.com)

概要

このCコードは、 Schemeのヒープベース仮想マシン を実装したもの。入力文字列を 字句解析・構文解析 し、S式を内部表現に変換。 コンパイル して命令列を生成し、 仮想マシン で評価。 REPL環境で Lisp式の入力・評価・出力 が可能。 Dybvig論文 のセクション3.4に基づく設計。

ヒープベース仮想マシンの全体像

Schemeインタプリタ の簡易実装
字句解析（lexer） でトークン分割
構文解析（read, read_exp, read_list） でS式の再帰的構造構築
内部表現（Pair, Text構造体） によるリスト表現
print関数群 によるS式の再現的出力
compile関数 でS式から命令列への変換
virtmach関数 で命令列の逐次実行・評価
REPLループ で入力→評価→出力を繰り返し

字句解析と構文解析

lexer関数
- 文字列を トークン配列 に変換
- 括弧・アポストロフィ・シンボルの切り分け
read_exp / read_list関数
- トークンを 再帰的にS式へ変換
- クォート・リスト・ドットペア対応
cons, istext関数
- リスト構造 の生成と判定

S式の内部表現

Pair構造体
- car, cdrでリストやペアを表現
Text構造体
- 文字列リストのための構造
text配列とtextptr
- ヒープ領域 として利用

コンパイルと命令列

compile関数
- S式を 命令列（Pairのリスト） に変換
- quote, lambda, if, set!, call/cc, apply等の対応
- クロージャ・継続 のサポート
命令の種類
- refer, constant, close, test, assign, conti, nuate, frame, argument, apply, return

仮想マシン（virtmach）

命令ごとに分岐処理
- refer: 環境から変数参照
- constant: 定数値の設定
- close: クロージャ生成
- test: 条件分岐
- assign: 変数代入
- conti/nuate: 継続の処理
- frame: コールフレームの積み上げ
- argument: 引数リストへの追加
- apply: 関数適用（環境拡張）
- return: フレーム復元
accum, next, env, rib, stack の5つのレジスタで状態管理

REPL（Read-Eval-Print Loop）

main関数
- 入力受付→字句解析→構文解析→コンパイル→仮想マシン実行→出力
- Lisp式を1行ずつ評価・表示

注意点・制約

環境管理やset!の実装は簡易的
数値・真偽値以外は全てシンボル扱い
組み込み関数やガーベジコレクションは未実装
栄養的なSchemeサブセットのみ対応

参考：Dybvig論文との対応

Three Implementation Models for Scheme
- セクション3.4の「ヒープベース仮想マシン」モデル
- S式→命令列→仮想マシン評価の流れを忠実に再現

このコードは Scheme処理系の学習や実験 に最適な最小実装例。 Dybvig論文 の理解や、 Schemeインタプリタ設計 の参考資料として活用可能。

Hackerたちの意見

すごいね！これが数千行のアセンブリコードに翻訳されて、ほぼ素の状態からSchemeをブートストラップできるって想像できるよ。初期のIBM 709 LISPみたいにね。ちょっと考えたんだけど、LLMがこれをアセンブリコードに書くのに向いてるかどうか、気になるな。

└

これからアセンブリコードを書くなら、Cコンパイラを使えばいいよ。そっちの方がバグも少ないしね。LLMが登場する前には、約65年の間、プログラムを書くプログラムがあって、労力を節約してたんだよ。

└

LLMがこれをアセンブリコードに書くのに向いてるかどうか、気になるな。コンパイラがそれをやるのは見えるね。

└

もし速度が目的なら、もっと分析（つまりコード）が必要だよ。V8を見てみて。

└

Cコンパイラは最適化をオフにすれば、かなり読みやすいコードを出力できるし、現代のアセンブリでこれをするのに何千行もかかることはないよ。aarch64でやるなら、ぎりぎり1000行くらいで済むかもしれないし、LLMも多分できると思う。LLMがやってるのを見た限りでは、何を聞くかを知っていれば、これらのプログラムを確実に強化できるし、コードの各部分がどう機能するかも説明できるよ。ルートレジスタが明示的だから、評価器にガーベジコレクションを追加できるかもしれないし、評価器は静的メモリにしか作用しないからね。

└

これはGNU MesとGuixの人たちが進んでいる道だね：https://guix.gnu.org/en/blog/2023/the-full-source-bootstrap-... （LLMなしでね。彼らは357バイトのブートローダーからコンパイルできるScheme（GNU Mes）を持っていて、そのSchemeはtinyccをコンパイルできるCコンパイラを動かせるみたい。tinyccからgccをコンパイルする道もあると思うけど、その後どこまで行けるかは分からない。このブログ記事[1]によると、Gashを動かすにはまだguileのバイナリが必要みたいで、GashはSchemeで書かれたPOSIXシェルなんだ。おそらく、Gashを簡素化するか、Mesを複雑にしてGuileを依存関係から外す計画なんじゃないかな。[1] https://guix.gnu.org/en/blog/2023/the-full-source-bootstrap-...

└

これからアセンブリコードを書くのにLLMが役立つか気になるな。なぜ、過去30年のどのCPUでもできることをGPUのクラスターにやらせるの？

MIT Schemeは、スイッチ文とgotoを混ぜて、直接Cにコンパイルしていたと思う。コールスタックをエミュレートするためにね。でも、プログラムが大きくなると、コンパイル時間が線形じゃなくなるのが問題だった。昔やってみたことがあるけど、ちょっとスピリチュアルな体験だったよ。: https://github.com/glouw/switch

└

ありがとう！MIT SchemeのCバックエンドのことを言ってるの？MIT Schemeは長い間使ったり使わなかったりしてるけど、Cバックエンドには触れたことがなくて、どう動くのか全然分からないから、これは興味深いね。（MIT SchemeにはIntel CPU用のネイティブコードコンパイラもあって、実際にMIT Schemeを使ってる人たち（正直小さなコミュニティだけど）が大体それを使ってるみたい。）

└

SICPの本には、非常に基本的な実装（理解しやすいもの）が載ってると思うよ。

└

マニュアルにはMITスキームがCにコンパイルするって書いてないな。自分のネイティブコードオブジェクトファイルと、いくつかのポータブルバイトコードについては書いてあるけど… https://www.gnu.org/software/mit-scheme/documentation/stable...

原子を文字列リテラルで表す代わりに、グローバル変数として表現できるよ。例えば、const char conti[] = "conti"; みたいにね。そうすれば、strcmp()の代わりにポインタの比較が使えるよ。

└

ポインタが同じでない限り、strcmpはまだ必要だと思うよ。それをチェックして同じにしないといけないからね。eq?（参照の等価性）がSchemeでどう機能するか考えてるかもしれないけど、それは通常、識別子の文字列をハッシュ化することで行われるんだ。これがこの等価性問題に対するより一般的な解決策だね。

ケント・ダイブビッグは、Chez Schemeも書いていて、ほとんどのベンチマークで圧倒的に速いSchemeの実装なんだ。最近、RacketがChezを基に書き直されたって聞いたけど、Racketのメンテナーからも、効果があったって言われたよ。パフォーマンスが向上して、コードベースも小さくてメンテナンスしやすくなったみたい。

└

Chez Schemeのコードベースを読むのはいつも楽しいし、すごく刺激的だよ。特に、もっとメインストリームなコンパイラやコードジェネレーターと比べるとね。ケント・ダイブビッグだけじゃなくて、アンディ・キープの貢献（nanopass）も超印象的だよ。全体がすごくきれいにデザインされていて、美しく表現されてる。

これが他のScheme実装を紹介する機会になってるみたいだね… 90年代初頭にLinux PCで大学の課題をやるのに、マティアス・ブルームのVSCMを使ってたのがすごく楽しかったな。

20年以上前にIUブルーミントンで私たちのCS入門コースを教えてくれたダイブビッグ先生に感謝！それが私の再帰の初めての入門だったし（もちろんクラスは全部Schemeベースだった）、独学から来た私にとってソフトウェア開発に対する自信がすごくついたんだ。

└

2000年代後半にIUでダイブビッグと一緒にコンパイラ、そして最適化コンパイラを学べたのは本当に楽しかった。彼は素晴らしい教授で、知識が豊富なのはもちろんだけど、それを教えるのがめちゃくちゃ上手かった。

400行のコンパイラと比べて、どれくらい速いのか遅いのか知りたいな。 https://news.ycombinator.com/item?id=26191243

今こそForthのブートストラップをやろうぜ。

この特定のコードの関連性について、もっと詳しく教えてくれる人いる？

└

これは彼の論文からのインタプリタの実装だよ。 https://www.cs.unc.edu/xcms/wpfiles/dissertations/dybvig.pdf

注意！replはトップレベルがあることを示唆してるけど、実際にはないんだよね…ちょっと混乱してる。どうしてトップレベル環境がないの？関数適用によって古い環境に変数とその値のリストを追加する環境があるんだ。void* extend(void* env, void* vars, void* vals) { return cons(cons(vars, vals), env); } これはcdrがnilのルート環境を示唆してる。

ハクソク