LunarMLの今年の目標に「REPLとインタープリターを実装する」というのがある。これまではLunarMLをLuaやJavaScriptをターゲットとするコンパイラーとして実装してきたけど、
- REPLによるインタラクティブな実行
- 書いたSMLコードを直接実行（一旦LuaやJavaScriptコードを生成するのではなく）
できると嬉しいよね、という話だ。（REPLを備えたStandard ML処理系は色々あるが、LunarMLとコンパチブルなREPLが欲しければ自分で作るしかない。）
つまりインタープリターだが、構文木を走査するインタープリターは遅そうだ。効率的な実行のためには、バイトコードとVMを設計したい。
バイトコードへのコンパイラーはSMLで、VM（ランタイム）はSMLによる実装とC言語による実装の両方を用意することをイメージしている。
C言語による実装を用意することで、高速な実行が期待できるだけではなく、「コンパイル済みバイトコード+C言語で書かれたランタイムによるbootstrap問題の解決」もできる。つまり、現状の「LunarMLを動かすためにはSMLコンパイラーが必要」という状態から「CコンパイラーまたはSMLコンパイラーがあればLunarMLが動く」という状態にできる。
ではバイトコードと抽象機械はどうやって設計するか？
目次
抽象機械の調査
まず、関数型言語向けの各種抽象機械を調べた。メモはこれ：
調べていて思ったが、ラムダ項を入力とする抽象機械は今回の目的にそぐわない。効率を考えると、コンパイラーはフラットな命令列（バイトコード）を生成して、それをVMが実行するという形が望ましい。この観点からいくつかの候補が脱落する。
また、中にはコンパイラーのための中間言語を意図しているものがあり、インタープリターにどれだけ適しているかよくわからなかった。
ZINCはOCamlやMoscow MLなどのベースになっているし良いのかもしれないが、それだとMoscow MLで良くね？となりそう。
考えを変えて、もっと実装寄りの文献を探すことにした。
読み物
Three Implementation Models for Scheme
- R. Kent Dybvig, Three Implementation Models for Scheme, 1987
Scheme処理系自作界隈（？）では有名っぽい。3impと略されることがある。
著者の博士論文（dissertation）らしい。
クロージャーと第一級継続を持つ言語（Scheme）の実装方法を3通り解説している。重要なのは2番目に解説されるスタックマシンである。
スタックマシンの話はざっくり言うと
- クロージャーには必要な値だけコピーする
- 継続のキャプチャーの際にはスタックをコピーする（継続のキャプチャーは頻繁には起こらないと仮定する）
- 可変な変数（
set!される変数）はボックス化する
ということのようで、2022年に読むと「なんだそんなことか」と思ってしまいそうになるが、35年前は新しかったのだろう。
スタックマシンのやつは著者のChez Schemeの基礎となったらしい。
Crafting Interpreters
Loxという言語のインタープリターを実装する本。
コンパイラーの教科書は色々あるけど、インタープリターに関してここまで書かれた本はなかなかないのではないか。Webでも無料で読める。
第1部はイントロ、第2部ではtree-walkingによる評価器（Javaによる実装）、第3部ではC言語でバイトコードVMを実装している。
C言語によるVM、ワンパスでの処理、クロージャーでの自由変数の取り扱い（upvalue）など、Luaとの類似性を感じられる部分が随所にある。もちろんLuaはレジスターマシンで、この本での実装（clox）はスタックマシンという違いはあるが。
リアルワールドの仕様と実装
教材を読み込んでだいぶ理解が得られてきたが、細かいところで実際の実装を参考にしたいこともある。定数テーブルは関数ごとに作るのか、プログラム全体でまとめるのか、とか。
というわけで、その辺のVMの仕様を調査してみる。
Lua VM
命令セットの定義はこの辺：
レジスターマシンなので命令の中にオペランドの情報が含まれる。1命令は32ビット（なので文字通りの「バイトコード」ではない）で、opcodeは7ビット使える。
VMのメインループはこっち：
GCC互換なコンパイラーの場合はthreaded VM（命令実行後に break&continue する代わりに goto *next するやつ）を使うようになっている。
関数の外部表現はこの辺：
特に、定数テーブルは関数ごとに持っているようだ。
値の表現に関して、Lua 5.2の頃は（LuaJITに影響されたのか）NaN boxingを使えるようになっていたが、Lua 5.3では64ビット整数が導入されたので普通のタグ付きunionに戻った。
LuaJIT
命令セットの定義はこの辺：
一個の命令は本家Luaと同じく32ビットだが、opcodeは8ビットっぽい。
関数の外部表現はこの辺：
string.dump で得られる関数の外部表現（バイトコードや定数テーブルを含む）は同一バージョンのLuaJITであればプラットフォームに依存しない、とされている。
JVM
- The Java® Virtual Machine Specification (Java SE 19 Edition)
- Chapter 4. The class File Format
- Chapter 6. The Java Virtual Machine Instruction Set
JVMはスタックマシンで、命令は可変長、opcodeは1バイトである。
opcodeの空間は比較的余裕があるのか、「floatの定数1.0をスタックに積む命令」みたいなのがある。
定数テーブルはクラスファイルに属する。文字列はModified UTF-8という形式で格納される（NULには2バイト使うのと、UTF-16でサロゲートを使うやつは4バイトの形式ではなく3バイト+3バイト使う）。
今後の方針
この数ヶ月は結構調査に費やしてきたので、そろそろ手を動かしたい。
いきなりフルのSMLが動くVMを作るのは大変そうなので、まずは単純なサブセットが動くVMを作ろうと思う。
参考にした「読み物」は例外を扱っていなかったが、Standard MLには例外がある。例外は頑張って実装する必要がある。ついでに限定継続も実装したい。
いきなりGC等のランタイムを実装するのは大変なので、最初はSMLでVMを実装する。VMの設計が固まってきた段階で、C言語によるVMを作りたい。
という方針で実装を始めた：
しばらくLunarML用のコードは書いてこなかったが、気持ちを新たにやっていきたい。