A 正規形 CEK マシン・ベースの仮想マシン

Scheme コンパイラ向けの A 正規形 CEK マシン・ベースの仮想マシンを考えます。この手のものでは、Peter Henderson が 1980 年に発表した Lispkit Lisp の SECD マシンをベースにしたスタック・マシンが有名です。基本方針は、Henderson の仮想マシンにならって、CEK マシン向けにアレンジすることにします。

どんな感じになるのかを C 言語で試験実装したものを Gist に置いておきます。これにリーダとライタを追加すると Henderson の仮想マシン相当になります。今は、様子見なので、リーダとライタは含めてません。階乗計算手続きを再帰とループの両方で記述し、ハンド・アセンブルしたものを埋め込んでいます。

svm.c - experimental virtual machine for A-Normalized CEK expressions.

今回のマシンは 8 つのレジスタを持ちます。継続の引数と引数用レジスタを CEK マシンに追加しています。引数用レジスタはプリミティブ用の r0 と r1、合成手続き用の arg の 3 本を使います。arg レジスタは、環境フレームを手続きの環境に追加した手続き適用に使うための環境を参照しています。当初、プリミティブも同じように環境フレームを利用するようにしてみたのですが、動かしてみると、プリミティブ適用ごとに環境フレームを次々とヒープに割り当てていくのが無駄なので、レジスタを別に設けることにしました。また、コード、手続きフレーム、環境フレーム、継続フレームはすべてベクタを利用することを想定しています。

ctl   コード・ベクタ
ip    コード・ベクタ中の現在実行中の次の命令のオフセット
val   継続の引数
r0    プリミティブの第一引数
r1    プリミティブの第二引数
arg   合成手続きのフレームを加えた環境
env   環境
kont  継続

命令は CEK 動作をするためのコアと、プリミティブ手続きの 2 種類に分かれます。

2014年8月7日修正: PROC 命令のオペランドをコード・ベクタとオフセットの組に変更しました。RET 命令を CONT 命令に名称変更しました。

コア

CONT    継続適用をします。r0 と r1 を nil でクリアします。

    {CONT} q R0 R1 A E' (kont {ST 0,x;C} E K) → {ST 0,x;C} q nil nil A E K

LIT q   リテラル q を val レジスタにセットします。

    {LIT q;C} V R0 R1 A E K → {C} q R0 R1 A E K

PROC seg,off   コード・ベクタ seg のオフセット off から始まる手続きを val レジスタにセットします。

    {PROC L;C;L:LIT n;C1} V R0 R1 A E K  →  {C} (proc n {LIT n;C1} E) R0 R1 A E K
    手続きは環境フレームの大きさ n を先頭のダミーの LIT 命令で持つことにする。

LOAD l,s  レベル l 番目の環境フレーム中の s 番目の値を val レジスタにセットします。

    {LOAD l,s;C} V R0 R1 A E[(l,s):q] K → {C} q R0 R1 A E K

STORE l,s  val レジスタの値をレベル l 番目の環境フレーム中の s 番目にセットします。

    {STORE l,s;C} q R0 R1 A E K → {C} q R0 R1 A E[(l,s):q] K

EXTEND l,s にセットしてある手続きの環境フレームを arg レジスタに作成します。

    {EXTEND l,s;C} V R0 R1 A E[(l,s):(proc n C' E')] K → {C} V R0 R1 (() x n E') E K

ARG s   val レジスタの値を arg 環境フレームの s 番目にセットします。

    {ARG s;C} q R0 R1 A E K → {C} q R0 R1 A[(0,s):q] E K

AR0     val レジスタの値を引数レジスタ r0 にセットします。

    {AR0;C} q R0 R1 A E K → {C} q q R1 A E K

AR1     val レジスタの値を引数レジスタ r1 にセットします。

    {AR0;C} q R0 R1 A E K → {C} q R0 q A E K

APPL l,s  手続き適用をします。r0、r1、arg を nil クリアします。

    {APPL l,s;C} V R0 R1 A E[(l,s):(proc n C' E')] K → {C'} V nil nil nil A K

CALL l,s  継続をセットして手続き適用をします。

    {CALL l,s;C} V R0 R1 A E[(l,s):(proc n C' E')] K → {C'} V nil nil nil A (kont {C} E K)

UNLESS d  val が偽のときip+dへジャンプします。

    {UNLESS L;C;L:C1} #f R0 R1 A E K → {C1} #f R0 R1 A E K

WHEN d  val が真のときip+dへジャンプします。

    {WHEN L;C;L:C1} T R0 R1 A E K → {C} T R0 R1 A E K

BRANCH d   常に ip+d へジャンプします。

    {BRANCH L;L:C1} V R0 R1 A E K → {C1} V R0 R1 A E K

プリミティブ

EQ      val に (eq? r0 r1) の評価結果をセットします。
NOT     val に (not r0) の評価結果をセットします。

PAIRQ   val に (pair? r0) の評価結果をセットします。
CONS    val に (cons r0 r1) の評価結果をセットします。
CAR     val に (car r0) の評価結果をセットします。
CDR     val に (cdr r0) の評価結果をセットします。
SETCAR  (set-car! r0 r1) を評価し val に r1 をセットします。
SETCAR  (set-cdr! r0 r1) を評価し val に r1 をセットします。

INTQ    val に (fixint? r0) の評価結果をセットします。
PLUSI   val に (fixint+ r0 r1) の評価結果をセットします。
MINUSI  val に (fixint- r0 r1) の評価結果をセットします。
TIMESI  val に (fixint* r0 r1) の評価結果をセットします。
DIVIDEI val に (fixint/ r0 r1) の評価結果をセットします。
LTI     val に (fixint<? r0 r1) の評価結果をセットします。
LEI     val に (fixint<=? r0 r1) の評価結果をセットします。
GTI     val に (fixint>? r0 r1) の評価結果をセットします。
GEI     val に (fixint>=? r0 r1) の評価結果をセットします。

これらを組合わせて、A 正規形 CEK マシンの式からコード生成することができます。

L E' (ar x C E K)  →  C E[x:L] K ここで L はリテラル

        LIT     q
        CONT

y E' (ar x C E K) →  C E[x:E'[y]] K

        LOAD    l,v
        CONT

(lambda (y) C') E (ar x C E K) →  C E[x:(proc (y) C' E)] (ar x C E K)

        PROC    cseg,offset
        CONT

(let ((x L)) C) E K → C E[x:L] K

        LIT     q
        STORE   l,x
        C

(let ((x y)) C) E[y:L] K → C E[x:L] K

        LOAD    l,y
        STORE   l',x
        C

(let ((x (lambda (y) C'))) C) E K → C E[x:(proc (y) C' E)] K

        PROC    cseg,offset
        STORE   l,x
        C

(if x C1 C2) E[x:#t] K → C1 E K
(if x C1 C2) E[x:#f] K → C2 E K

        LOAD    l,x
        UNLESS  A2-.
        C1
        CONT
A2:     C2
        CONT

もしくは

        LOAD    l,x
        UNLESS  A2-.
        C1
        BRANCH  A3-.
A2:     C2
A3:     CONT
     
(f L x1) E'[f:(proc (y0 y1) C E)] K → C E[y0:L,y1:E'[x1]] K

        EXTEND  l,f
        LIT     L
        ARG     y0
        LOAD    l,x1
        ARG     y1
        APPL    l,f

(let ((y (f L x1))) C') E'[f:(proc (y0 y1) C E)] K' → C E (kont y C' E' K')

        EXTEND  l,f
        LIT     L
        ARG     y0
        LOAD    l,x1
        ARG     y1
        CALL    l,f
        STORE   l,y
        C'

(o L x1) E'[x1:L1] (kont x C E K) → C E[x:o(L,L1)] K

        LIT     L
        AR0
        LOAD    l,x1
        AR1
        o
        CONT

(let ((y (o L x1))) C) E K → C E K

        LIT     L
        AR0
        LOAD    l,x1
        AR1
        o
        STORE   l,y
        C