純粋関数型言語の処理系を作ってみることにした (その4 : Mark-2 G-machine)

puref

純粋関数型言語の処理系を作ってみることにした (その3 : Mark-1 G-machine)の続き。

教科書P94-P97まで。
http://github.com/nineties/puref/commit/4cd5d92a5f02468929bc2dd2ddafbd363251c86c

Mark-2 G-machineでは遅延評価を行う為の準備として、Update/Popというインストラクションで前回のSlideインストラクションを置き換えます。
また、実行中のVMのインストラクション列・スタック・ヒープの状態を自動的に可視化する機能を実装しました。
ビルド

% git clone git://github.com/nineties/puref.git
% cd puref
% make

テストコードとしてExcercise 3.11を用意しています。

% cat test.pf
twice f x = f (f x);
id x = x;
main = twice twice id 3

-mark1,-mark2オプションで使用するG-machineを切り替えます。また-vis hogeでVMの状態を可視化したhoge.pdfが生成されます。

% ./puref -mark1 -vis test_mark1 test.pf
output: 3
% ./puref -mark2 -vis test_mark2 test.pf
output: 3

また-dinsnでコンパイル結果を出力します。

% ./puref -dinsn test.pf
=== twice [2] ===
   1: Push 1
   2: Push 1
   3: Mkapp
   4: Push 1
   5: Mkapp
   6: Update 2
   7: Pop 2
   8: Unwind
=== id [1] ===
   1: Push 0
   2: Update 1
   3: Pop 1
   4: Unwind
=== main [0] ===
   1: Num 3
   2: SC id
   3: SC twice
   4: SC twice
   5: Mkapp
   6: Mkapp
   7: Mkapp
   8: Update 0
   9: Pop 0
  10: Unwind
output: 3

以下のpdfを読む際の参考になるかと思います。

生成されたpdfがこちら。全ステップを可視化しているので、枚数＝ステップ数となります。
test_mark1.pdf
test_mark2.pdf

  • sc "hoge" はスーパーコンビネータ
  • appは関数適用ノード。赤いエッジが関数ノード。青いエッジが引数ノード。
  • *はただの間接ノード

Graphvizを使ったのですが、ノードの位置関係が入れ替わったりしてあまり見やすくないです。ごめんなさい。
で、mark1とmark2で何がどう変わったか説明しなければならないのですがそれはまた今度にします。