バイトコードVMのための調査

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

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用のコードは書いてこなかったが、気持ちを新たにやっていきたい。


コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です