takeisa memo: [Ruby][Scheme] Micro Schemeの実装(14) Virtual machine方式に変更

いままで実装してきたインタプリタ方式で、末尾最適化や継続を実現するには、どのようにすれば良いのか、Webを検索したり、いろいろ考えていたが、これといった良い方法が思い付かなかった。
そこで、方針を変えて、Virtual Machine を使う方式に変更し、ごそごそやってできたのがこれ。

https://github.com/takeisa/uschemer2/tree/v0.00

Virtual machineとコンパイラを実装した。実装中にいろいろバグが出て、コンパイラのバグなのか、Virtual machineのバグなのか、分かり難かったりしたが、四苦八苦するのも、なかなか楽しい。ただ、適当に作ってしまったのでソースが非常に汚い。orz

Three Implementation Models for Scheme

Three Implementation Models for Scheme(3imp.pdfとして有名)というScheme処理系の実装方式の解説を読んだ結果、コンパイルしたSchemeコードをScheme用に最適化したVitrual machine上で実行する方式のほうが、インタプリタ方式よりも、末尾最適化や継続の実装が簡単そうだった。

VMを使う方式では、末尾最適化と継続は次のように実装できる。

末尾最適化: コンパイル時に、呼び出す関数が処理の末尾にあるか判定し、末尾の場合はコールフレームを生成せずに、関数を呼び出すコードを生成する。
継続: 継続時点のスタックフレームを保存しておき、継続手続の呼び出しで、スタックフレームを復元後、値を渡す。

Virtual machine

いまのところ 3imp.pdf とほぼ同じ仕様だ。
備忘録をかねて書いておこう。

レジスタ

5つのレジスタを持つ。

レジスタ	機能
a	アキュムレータ
x	次に実行する式
e	現在の環境
r	引数のリスト
s	現在のスタックフレーム

命令セット

Virtual machineでサポートしている命令は以下の通り。

命令の中には、次に実行する命令を引数に取るものもあるが、以下では省略している。

命令	説明
(halt)	Virtual machineを停止する。aレジスタの値が評価結果となる。
(refer var)	環境を参照し、変数varの値を取得し、aレジスタに設定する。
(constant obj)	オブジェクトをaレジスタに設定する。
(test then else)	aレジスタが非nilの場合はthenを実行し、nilの場合はelseを実行する。
(assign var)	環境を参照し、変数varの値にaレジスタの値を設定する。
(conti)	継続オブジェクトを生成する。
(nuate s var)	スタックフレームsをsレジスタに設定し、変数varをaレジスタに設定する。
(frame ret)	コールフレーム(戻り先retは次に実行する式として設定)を生成し、スタックフレームへ追加する。
(argument)	aレジスタの値を、rレジスタに追加する。
(apply)	クロージャまたはプリミティブ関数を評価する。
(return)	スタックフレームのコールフレームより、フレーム生成前の状態にレジスタを戻す。

コンパイラ

式に応じてVirutal machineの命令を生成する。

コンパイル例

いくつかコンパイル例を示す。

変数aの参照	(refer a)
数値100	(constant 100)
(if pred "true" "false")	(refer pred) (test (constant "true") (constant "false"))
(+ 1 2)	(frame) (constant 1) (argument) (constant 2) (argument) (refer +) (apply) (return)

実行例

今はまだreplは無いので、rspec実行時のデバッグログ出力結果のみ。

クロージャ

context do
it {
    op = compile('
(((lambda (a)
    (lambda (b) (+ a b))) 10) 20)
')
    res = @vm.eval(op)
    res.should eq 30
}
end

(((lambda (a)
    (lambda (b) (+ a b))) 10) 20)
-> (frame) ...
↓ここから下はVMが実行した命令
(frame)
(constant 20)
(argument)
(frame)
(constant 10)
(argument)
(close #<SCons:0x86e7d98> (close #<SCons:0x86e6754> (frame)))
(apply)
(close #<SCons:0x86e6754> (frame))
(return)
(apply)
(frame)
(refer a)
(argument)
(refer b)
(argument)
(refer +)
(apply)
(return)
(return)
(halt)

継続

context do
it {
    op = compile('(+ 1 (call/cc (lambda (k) (k 3))))')
    res = @vm.eval(op)
    res.should eq 4
}
end

(+ 1 (call/cc (lambda (k) (k 3)))) -> (frame) ...
↓ここから下はVMが実行した命令
(frame)
(constant 1)
(argument)
(frame)
(conti)
(argument)
(close #<SCons:0x9d1a96c> (frame))
(apply)
(frame)
(constant 3)
(argument)
(refer k)
(apply)
(nuate #<CallFrame:0x9d1a4d0> v)
(return)
(argument)
(refer +)
(apply)
(return)
(halt)

不足しているもの

末尾最適化: まだ実装していない。
define special form: VMの命令追加が必要だ。
REPL: REPLが無いと不便だ。

リファクタリング

メソッド内の最大インデントは一段まで、elseは使わない等の強い制約の元で実装することで、オブジェクト指向プログラミングがうまくなるらしい。
このルールに従ってリファクタリングしてみるのも、いろいろと得るものがありそうだ。

takeisa memo

2013年6月2日日曜日

[Ruby][Scheme] Micro Schemeの実装(14) Virtual machine方式に変更