LispKit Lisp処理系の実装 ５：SECD抽象機械の状態遷移〜リスト操作と比較・算術演算
前回の記事ではSECD抽象機械のメモリとレジスタを定義していった。今回（と次回）はSECD抽象機械が実際にどうやってプログラムを実行するかを見ていく。
SECDマシン上でプログラムを実行するということは、Controlレジスタcが指し示すコンパイルされたプログラムを「消費」しながら他のレジスタの状態を変更させていき、STOPという命令コードに到達した時点で終了、プログラムの計算結果がスタックレジスタsの指すConsリストの先頭要素となっている、というものだ。
「プログラムを消費する」とはcレジスタの先頭要素を命令コードとし、その命令コードによってはいくつかそれ以降の要素も使い、cレジスタの値をその後のConsセルのメモリアドレスに変更することである。
状態遷移の一例
スタックの状態が(1 2)、コントロールが(ADD STOP)という非常に簡単な状態からの終了への遷移を考えてみる。
初期設定ではメモリとSECDレジスタの状態は以下のとおり：
メモリ： [0:"NIL" | 1:"T" | 2:"F" | 3:(4, 5) | 4:1 | 5:(6, 0) | 6:2 | 7:(8, 9) | 8:ADD | 9:(10, 0) | 10:STOP | ... ] レジスタ： s = 3 e = 0 c = 7 d = 0
メモリの部分は今勝手に作った記法。[ ... | ... | ... | ... ]とセルに区切られていて、個々のセルの内容は...の部分。
内容の読み方は：
0:"NIL"は「アドレスは0、値はシンボル"NIL"」3:(4, 5)は「アドレスは3、値はCAR=4, CDR=5のConsセル」4:1は「アドレスは0、値は数値１」8:ADDは「アドレスは0、値は命令コードADD」（実際には数値で表されるのだが）
スタックレジスタはメモリ番地3を指していて、3で始まるConsリストは[ ... 3:(4, 5) | 4:1 | 5:(6, 0) | 6:2 ...]なので(1 2 . NIL)となる。
同じようにコントロールレジスタが指す番地は７で[ ... 7:(8, 9) | 8:ADD | 9:(10, 0) | 10:STOP ...]というメモリが(ADD STOP . NIL)となる。
この状態からSECDマシンが停止するまで走らせた場合、終了時の状態は以下のとおり（ガベージコレクションはないものとする）：
メモリ： [0:"NIL" | 1:"T" | 2:"F" | 3:(4, 5) | 4:1 | 5:(6, 0) | 6:2 | 7:(8, 9) | 8:ADD | 9:(10, 0) | 10:STOP | 11:(12, 0) | 12:3 | ... ] レジスタ： s = 11 e = 0 c = 9 d = 0
終了時のスタックは(3)、コントロールは(STOP)。スタックの先頭２要素を足した結果がスタックの先頭に残っている。
今回（と次回）の記事では命令コードに応じてどのように遷移させていくのか、抽象機械の仕様とPythonでの実装の両方を見ていく。分量が多かったので今回はリスト操作（CONS、CAR、CDR）や比較・算術演算などについて。条件分岐や関数関連は次回。
step関数
状態遷移は命令コード一つに対してパターンマッチして実行するstep関数で定義されている：
def step(): global s, e, c, d, w match ivalue(car(c)): ...
global宣言でわかるとおり、レジスタはすべてモジュールレベルのグローバル変数になっている。オブジェクト化しても良かったのだが、そうすると至るところでself.sなどと書く必要が出てくるのがいやだったのでこの形に。
「次に実行するべき命令コード」はコントロールレジスタcが指すメモリ位置から始まるConsリストの先頭位置にある。ivalue(car(c))でその命令コードを数値として取得した上でmatch構文でパターンマッチしている。
car（と対応するcdr）ヘルパ関数の定義：
def car(i): return memory[i].car def cdr(i): return memory[i].cdr
（メモリアドレスの内容がConsでない場合はPythonの例外が投げられる）
数値の中身を取り出すivalueとそのシンボル版であるsvalue関数：
def ivalue(i): match memory[i]: case Int(n): return n case _: raise ValueError(f"Cannot get int value of {memory[i]}") def svalue(i): match memory[i]: case Symbol(s): return s case _: raise ValueError(f"Cannot get symbol value of {memory[i]}")
ここからstep関数のパターンマッチ詳細をケースごとに見ていく。（各ケースの順番は解説の都合で実際のコードとは違っている）
CONS, CAR, CDR
リスト操作関連の命令コードであるCONS、CAR、CDRがControlレジスタの先頭にあった場合、SECDレジスタの状態遷移は以下の通り：
CONS: (x y.s) e (CONS.c) d -> ((x.y).s) e c d CAR ((x.y).s) e (CAR.c) d -> (x.s) e c d CDR ((x.y).s) e (CDR.c) d -> (y.s) e c d
CONSはスタックの先頭２要素をPopし、一つのConsセルに格納してそのConsセルをスタックの先頭要素として追加する。
CAR、CDRはスタック先頭要素であるConsセルをPopし、そのcar/cdr部分をスタックの先頭に追加する。
パターンマッチ内のケース実装は以下のとおり：
case Op.CONS:
s = cons(cons(car(s), car(cdr(s))), cdr(cdr(s)))
c = cdr(c)
case Op.CAR:
s = cons(car(car(s)), cdr(s))
c = cdr(c)
case Op.CDR:
s = cons(cdr(car(s)), cdr(s))
c = cdr(c)
ややこしいことにCONS, CAR, CDR命令コードの処理の実装に、ヘルパ関数cons, car, cdrが多用されている。大文字のCONS、CAR、CDRはSECDマシンのスタック上の値を操るための命令コードで、小文字のcons, car, cdrはSECDマシンのメモリセルを操るためのPythonのヘルパ関数である。
このうちcarとcdrの実装は前述のとおり。
consはメモリをアロケートしてConsセルを作成する：
def cons(a=0, b=0): return store(Cons(a, b))
同じように数値、シンボルを作成するヘルパ関数も存在する：
def int_(n=0): return store(Int(n)) def symbol(s=''): return store(Symbol(s))
これらに使われているstoreは値を新しくアロケートしたメモリアドレスに保存する関数：
def store(val): global w, ff w = ff ff = memory[ff].cdr memory[w] = val return w
wレジスタを一時変数的に「アロケートされるアドレス」として使い、ffはcdrをたどって「次の使われていないセル」に変更。wのアドレスのメモリに値を代入してからアドレスを返している。
ATOM
ATOMはスタックの先頭要素がアトミックである（つまりConsセルでない）ことを調べるための命令コード。
状態遷移は：
(x.s) e (ATOM.c) d -> (t.s) e c d if (isnumber(x) or issymbol(x)) else (f.s) e c d
Python実装：
case Op.ATOM:
if (isnumber(car(s)) or issymbol(car(s))):
s = cons(t, cdr(s))
else:
s = cons(f, cdr(s))
c = cdr(c)
isnumberとissymbolはメモリアドレスの内容が数値かシンボルかを確認するヘルパ関数：
def isnumber(i): match memory[i]: case Int(_): return True case _: return False def issymbol(i): match memory[i]: case Symbol(_): return True case _: return False
EQ, LEQ
スタックの先頭要素二つを比較する関数。
EQは「先頭要素二つがどちらもアトミックであり、かつ同じ値である」かどうかを判定して結果をスタックにプッシュする。
EQ: (x y.s) e (EQ.c) d -> (t.s) e c d if (isatomic(x) and isatomic(y) and x==y) else (f.s) e c d
真偽値がsymbol("T")、symbol("F")と新しいメモリ上の値で表されるのではなく、tとfという専用のレジスタを使って表現されている。
Python実装：
case Op.EQ:
if ((issymbol(car(cdr(s))) and issymbol(car(s)) and svalue(car(cdr(s)))==svalue(car(s)))
or (isnumber(car(cdr(s))) and isnumber(car(s)) and ivalue(car(cdr(s)))==ivalue(car(s)))):
s = cons(t, cdr(cdr(s)))
else:
s = cons(f, cdr(cdr(s)))
c = cdr(c)
LEQは「先頭要素二つXとYがどちらも数値であり、かつY<=X」かどうかを判定して結果をスタックにプッシュする。
LEQ: (x y.s) e (LEQ.c) d -> (t.s) e c d if (isnumber(x) and isnumber(y) and y<=x) else (f.s) e c d
順番に注意。(LEQ 1 2)のような式がコンパイルされた上で実行される場合、まず1がスタックにプッシュされその後2がスタックにプッシュされる。その結果こういう形での比較になる。
Python実装：
case Op.LEQ:
if ivalue(car(cdr(s))) <= ivalue(car(s)):
s = cons(t, cdr(cdr(s)))
else:
s = cons(f, cdr(cdr(s)))
c = cdr(c)
ADD, SUB, MUL, DIV, REM
算術演算の命令コードは、スタックの先頭２要素を取って計算結果をスタックにプッシュする：
ADD: (x y.s) e (ADD.c) d -> ((y + x).s) e c d SUB: (x y.s) e (SUB.c) d -> ((y - x).s) e c d MUL: (x y.s) e (MUL.c) d -> ((y * x).s) e c d DIV: (x y.s) e (DIV.c) d -> ((y / x).s) e c d REM: (x y.s) e (REM.c) d -> ((y mod x).s) e c d
LEQと同じようにスタックに乗っている順番と計算で登場する順番が逆になっている点に注意。
Python実装：
case Op.ADD:
s = cons(int_(ivalue(car(cdr(s)))+ivalue(car(s))), cdr(cdr(s)))
c = cdr(c)
case Op.SUB:
s = cons(int_(ivalue(car(cdr(s)))-ivalue(car(s))), cdr(cdr(s)))
c = cdr(c)
case Op.MUL:
s = cons(int_(ivalue(car(cdr(s)))*ivalue(car(s))), cdr(cdr(s)))
c = cdr(c)
case Op.DIV:
s = cons(int_(ivalue(car(cdr(s)))//ivalue(car(s))), cdr(cdr(s)))
c = cdr(c)
case Op.REM:
s = cons(int_(ivalue(car(cdr(s)))%ivalue(car(s))), cdr(cdr(s)))
c = cdr(c)
次回
次回では残りの命令コードSEL, JOIN, LD, LDC, LDF, AP, RTN, DUM, RAP, STOPについての詳細とstep関数が実際にどのように使われるかを見てSECD抽象機械の実装解説を終える。
