前回はLispKit Lispの挙動を確認するためもあってASTを直接実行するインタプリタを実装した。これからはLispKit LispのプログラムをSECD抽象機械上で実行するために必要なものを揃えていく。

今回と次回はSECDマシン自体の実装の話。

SECDマシン

SECD抽象機械については以前一度OCamlで実装している&このブログで記事を書いてる：

zehnpaard.hatenablog.com

SECD抽象機械の歴史的意義などは上記の記事参照。本記事ではPythonでの実装とその解説に集中する。

内容としては

SECDマシンのメモリ
SECDマシンのレジスタ
SECDマシンの命令実行

があり、今回はメモリ・レジスタの解説、次回で命令実行によってSECDマシンの状態がどう遷移していくかを見ていく。

SECDマシンのメモリ

SECDマシンのメモリは「セルに区切られ、番地の振られたテープ」だと見做せる。

個別のセルは

数値
シンボル
二つの番地を指すCons

の三種のデータのいずれかを含む。LispKit LispのASTと一対一で対応している。

Pythonでは以下のように表す：

@dataclass
class Int:
    n : int

@dataclass
class Symbol:
    s : str

@dataclass
class Cons:
    car : int
    cdr : int

プログラム自体もデータとしてメモリに載る必要があり、SECD抽象機械の命令は数値としてメモリ上で表現されている。

理解しやすくするために本記事ではPythonのIntEnumを使って表現している：

class Op(IntEnum):
    LD = auto()
    LDC = auto()
    LDF = auto()
    AP = auto()
    RTN = auto()
    DUM = auto()
    RAP = auto()
    SEL = auto()
    JOIN = auto()
    CAR = auto()
    CDR = auto()
    ATOM = auto()
    CONS = auto()
    EQ = auto()
    ADD = auto()
    SUB = auto()
    MUL = auto()
    DIV = auto()
    REM = auto()
    LEQ = auto()
    STOP = auto()

各命令の詳細は次回解説していく。

今回の実装ではメモリはPythonリストで表現している：

SIZE = 10000
memory = [Int(0) for _ in range(SIZE)]

とりあえずInt(0)で初期化。

SECDマシンのレジスタ

HendersonのFunctional Programming - Application and Implementationで紹介されているSECDマシンにはレジスタが９つある。

SECDマシンの名前の由来になっている四つ：

Stack
Environment
Control
Dump

そしてHenderson本の実装で使われる追加の５つ：

Nil
True
False
Working Space
Free List

これらレジスタはすべて整数の値をとり、その値の意味はメモリ上のセルへのポインタだ。

Stack

SECDマシンはいわゆるスタックマシンであり、中間結果などをスタックにプッシュ・ポップしながら演算を進めていく。そのスタックというのはメモリ上のConsリストであり、その先頭のConsセルに対するポインタがスタックレジスタsに入っている。

Environment

Environmentレジスタeはその名の通り変数環境へのポインタ。SECDマシンの変数環境は値のリストのリストになっていて、コンパイル済みのプログラムには変数名であるシンボルは現れずインデックス二つのペアで環境内の変数を表現する（ラムダ計算でいうところのde Bruijn Indexのようなもの）。スタックと同じく、この変数環境もConsリストになっており、先頭のConsセルの位置がeレジスタの中身となる。

Control

プログラムカウンタ的なもの。「SECDマシンで実行したいプログラム」もやはりコンパイルされるとメモリ上のConsリスト（内容は命令コードや定数など）となっており、Controlレジスタの内容はそのプログラムを表すConsリストにおける未実行の先頭セルに対するポインタとなる。

Dump

いわゆる「継続」。SECDマシン上で関数適用する場合、他の３つのレジスタの内容をその関数のものに入れ替え、関数の演算が終わった時点で再度それらのレジスタを元に戻す、という作業が必要になる。Dumpレジスタが指すConsリストは、「元の状態」の退避先で、関数呼び出しが終わったらこのConsリストの先頭から関数呼び出し元の状態を取ってきて復元する。

Nil, True, False

特殊な値としてNil、True、False専用のレジスタを用意しておく。ここはHenderson本に従っている。実際のところNilはまだわかるのだが、TrueやFalseがレジスタとして必要な理由はいまいちわからない・・・

Working Space

SECDマシン内部の処理中（命令実行時の状態遷移の途中）に出てくる途中結果を保持しておくためのレジスタ。最初に実装した時はありがたみがわからなかったのだが、マーク＆スイープ型のガベージコレクションを追加した時点で必要性がよくわかった。処理中にガベージコレクションが走ったときに何らかのレジスタから辿れないセルは回収されてしまうので、それを避けるためにこのwレジスタで途中結果のセルも辿れるようにしておく。

Free List

（Henderson本で実装される）SECDマシンのメモリアロケーション戦略は非常に単純で、未使用のメモリセルはすべて一つの長いConsリストにしておく。このConsリストをFree Listと呼び、新しくセルをアロケートする場合このFree Listの先頭のセルを取って使う。レジスタffはこのFree Listの先頭を指す（Henderson本での説明はないが、Front of Free listでffなのだろうか）。アロケーションが起きるたびにffレジスタをffが現在指しているConsセルのcdrに変更し、元のConsセルをアロケートしたメモリとして返す。

というわけで９つのレジスタの詳細を見てきた。

とりあえず全部のレジスタを0で初期化しておく：

nil = 0
s = e = c = d = w = t = f = ff = nil

プログラムを実行するたびに再度初期化：

def init():
    global memory, s, e, c, d, t, f, ff
    s = e = c = d = nil

    memory[nil] = Symbol("NIL")
    for i in range(1, SIZE):
        memory[i] = Cons(0, i-1)
    ff = i

    t = symbol("T")
    f = symbol("F")

secd各レジスタをnilにリセットし、メモリをすべてFree Listに戻した上でffレジスタをそのFree Listの先頭を指すように変更する。その上で新しくTとFのシンボルのメモリを作成し、tとfレジスタをそのアドレスにセットする。symbolはメモリのアロケーションとそのアドレスへの値代入の両方を行うヘルパ関数。symbolを含むヘルパ関数の解説は次回。

次回

次の記事ではSECD抽象機械の状態が各命令コードに応じてどのように遷移していくかを見ていく。

Arantium Maestum

プログラミング、囲碁、読書の話題

LispKit Lisp処理系の実装　４：SECD抽象機械のメモリとレジスタ