Arantium Maestum

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

LispKit Lisp処理系の実装 6:SECD抽象機械の状態遷移〜条件分岐、関数関連など

前回に続いてstep関数内の命令コードに対するパターンマッチを見ていく。

今回見ていくのは以下の命令コード:

  • 条件分岐のSEL、JOIN
  • スタックに値を乗せるLD、LDC、LDF
  • 関数適用のAP、RTN
  • 再帰関数のためのDUM、RAP
  • プログラム停止のSTOP

条件分岐のSEL、JOIN

SELコードはスタックの先頭要素に応じて分岐する:

("T".s) e (SEL n m.c) d -> s e n (c.d)
("F".s) e (SEL n m.c) d -> s e m (c.d)

このnmは数値だが、実際にはメモリ番地を表している。

スタックの先頭要素が”T"(つまり真)であればコントロールレジスタnから始まる命令コードのリスト、”F"(つまり偽)であればmから始まる命令コードのリストを指すように変更。ただし分岐部分が終わった時に合流できるよう、現在のコントロールレジスタの値はダンプレジスタに退避させておく。

分岐部分のコードは最後にJOIN命令コードが乗っている。JOINの状態遷移は以下のとおり:

s e (JOIN.c') d -> s e c d

現在のコントロールが指す命令コードのリストは破棄して、ダンプの先頭に退避させておいた元のコントロールレジスタの値を復元する。

Python実装:

        case Op.SEL:
            d = cons(cdr(cdr(cdr(c))), d)
            if svalue(car(s)) == "T":
                c = car(cdr(c))
            else:
                c = car(cdr(cdr(c)))
            s = cdr(s)

        case Op.JOIN:
            c = car(d)
            d = cdr(d)

SELではサボって”F"かどうかは明確にチェックしていないので、”T"以外ならすべて偽として扱うようになっている。

スタックに値を乗せるLD、LDC、LDF

LD、LDC、LDFはそれぞれ変数、定数、関数をスタックの先頭に乗せる命令コード。

LD - 変数の参照

LD命令は環境に含まれている変数の値を参照してスタックに乗せる:

s e (LD (n.m).c) d -> (x.s) e c d 
where x is the mth element of the nth list in e

コントロールリストにLDに続いて数値2つnmのConsセルがあり、環境リストの先頭からn番目のサブリストのm番目の要素をスタックに乗せる。

Python実装:

        case Op.LD:
            w = e
            for _ in range(ivalue(car(car(cdr(c))))):
                w = cdr(w)
            w = car(w)
            for _ in range(ivalue(cdr(car(cdr(c))))):
                w = cdr(w)
            w = car(w)
            s = cons(w, s)
            c = cdr(cdr(c))

LDC - 定数

コントロールリストにLDCコードのすぐあとに乗っている定数をスタックに乗せる:

s e (LDC x.c) d -> (x.s) e c d 

Python実装:

        case Op.LDC:
            s = cons(car(cdr(c)), s)
            c = cdr(cdr(c))

LDF - 関数

LDFは現在の環境を含んだ関数のクロージャを作成してスタックに乗せる:

s e (LDF x.c) d -> ((x.e).s) e c d 

コントロールリストに乗っている「関数本体の式」と現在の環境をConsセルにしてスタックの先頭に乗せている。このConsセルが値としての関数(別の言い方をすれば「クロージャ」)である。

Python実装:

        case Op.LDF:
            s = cons(cons(car(cdr(c)), e), s)
            c = cdr(cdr(c))

関数適用のAP、RTN

AP

AP命令コードはLDFで作成されたクロージャに実引数を適用して実行する:

((c'.e') v.s) e (AP.c) d -> NIL (v.e') c' (s e c.d)

スタックの先頭要素がクロージャ、第二要素が実引数のリストである。元のs e cレジスタを「関数適用の呼び出し元」の状態としてダンプに退避させた上で、クロージャの第一要素はコントロールリストとして、第二要素は(実引数を追加した上で)環境として使う。

Python実装:

        case Op.AP:
            d = cons(cdr(cdr(s)), cons(e, cons(cdr(c), d)))
            e = cons(car(cdr(s)), cdr(car(s)))
            c = car(car(s))
            s = nil

RTN

RTN命令コードで「関数の呼び出し元に戻る」。SECDマシンの場合、ダンプレジスタに退避させておいたスタック、環境、コントロールの値を復元することになる(ただし現時点でのスタックの先頭要素を「戻り値」として、以前のスタックリストの先頭に追加する):

(x.s) e (RTN.c) (s' e' c'.d) -> (x.s') e' c' d

Python実装もそのまま:

        case Op.RTN:
            s = cons(car(s), car(d))
            e = car(cdr(d))
            c = car(cdr(cdr(d)))
            d = cdr(cdr(cdr(d)))

再帰関数のためのDUM、RAP

再帰関数の場合、インタプリタと同様「一旦作ったConsセルの中身を破壊的に書き換える」という処理で再帰性を実現している。

DUM

破壊的に書き換えるダミー値を環境に追加する命令コード:

s e (DUM.c) d -> s (NIL.e) c d

実はこれはHenderson本の実装と少し変えていて、あちらでは環境の前にNILではなくΩというシンボルを置くようになっている。どうせ破壊する(&めんどくさいのでその値が正しくΩかチェックしない)のでNILで代用。

Python実装:

        case Op.DUM:
            e = cons(nil, e)
            c = cdr(c)

RAP

「Recursive AP」の意であろうRAP命令コードの状態遷移は、APコードと非常に近い:

((c'.e') v.s) (NIL.e) (RAP.c) d -> NIL rplaca(e', v) c' (s e c.d)  ただしe' = (NIL.e)

((c'.e') v.s) e (AP.c) d -> NIL (v.e') c' (s e c.d)

違いは三点。

まず第一に、環境の先頭にNILが来ている。つまりDUMが

次にクロージャの中の環境e'は現時点の環境(NIL.e)を指している。この場合「同じ値」であるだけではなく、まったく同じメモリ位置を指しているのがポイント。

最後に、関数適用後の環境が(v.e')ではなくrplaca(e', v)になっている。このrplacaという関数は「新たなConsセルを作ってvをe'に追加するのではなく、既存のConsセルの先頭データを書き換えて(NIL.e')が(v.e')になるようにする」というもの。この処理に関しては少しわかりにくいので、LispKit Lisp再帰関数をコンパイルする話題の時にもっと詳細に見ていく予定。

        case Op.RAP:
            d = cons(cdr(cdr(s)), cons(cdr(e), cons(cdr(c), d)))
            c = car(car(s))
            e = cdr(car(s))
            memory[e].car = car(cdr(s))
            s = nil

memory[e].car = car(cdr(s))で「すでに作られたConsセルのcar部分を破壊的に書き換える」という処理になっているのがわかる。これがrplacaに相当する。

ちなみに再帰関数から呼び出し元に戻る場合は普通の関数と同じくRTNでダンプから呼び出し元の状態を取ってきて復元する。

プログラム停止のSTOP

STOP命令コードに到達するとSECDマシンの状態遷移は終了する。逆にいうと、それ以外の命令コードの場合、そのコードに応じて状態が変更した後ループして次の命令コードを読んで状態遷移する、という処理になっている。

Python実装を見ると:

        case Op.STOP:
            return False
        case e:
            raise ValueError(f"Incorrect Opcode {e}")
    return True

STOPの場合はreturn False、該当する命令コードがなければ例外を投げる、そしてSTOP以外の正当な命令コードの場合はすべてreturn Trueするようになっている。

SECDマシンにプログラムを実行させる場合、step関数をループさせてFalseが返ってきた時点で停止、スタックの先頭の要素を戻り値として返す、という処理の流れになる:

def exec():
    while step():
        pass
    return memory[car(s)]

これでstep関数の定義と使用法についての紹介は終了。そしてこれで前回、前々回と合わせてSECD抽象機械の実装が終了。

SECD抽象機械のコード

Implementation of the SECD Abstract Machine (based on Henderson's "Functional Programming Application & Implementation") · GitHub

次回

LispKit LispのコードをSECD抽象機械の命令コードのConsリストへとコンパイルすることで、SECDマシン上で実際のプログラムを実行できるようにする。