Open3
SECDマシンについて
星にゃーんSECDマシンは、関数プログラミング言語のコンパイラの目的言語として考案された抽象機械。Stack、Environment、Control、Dumpの４つのレジスタを持つ。Environmentは連想配列、他の３つはスタックを指す。
- SECDマシン - Wikipedia https://ja.wikipedia.org/wiki/SECDマシン
星にゃーんStackには演算に用いる値が乗る。Environmentには変数束縛の表が保持される。Controlには実行される命令列が乗る。命令の順序は逆ポーランド記法に基づく。Dumpには関数呼び出しの戻り先情報が乗る。
星にゃーんSECDマシンが扱う命令と値の定義には、文献によって細かな揺れがある。ここでは、英語版Wikipedia[1]と書籍『コンパイラ 原理と構造』を元に、独自に定義を示す。
x::xsは、要素xをスタックxsの先頭に追加したスタックを表す。
| 命令 | 説明 | 動作 |
|---|---|---|
ldc <constant> |
定数をスタックにプッシュ | (S, E, push c::C, D) => (c::S, E, C, D) |
ld <variable> |
変数の値をスタックにプッシュ | (S, E{x:v}, ld x::C, D) => (v::S, E, C, D) |
sel <then> <else> |
スタックトップに従って分岐。joinと合わせて使用 |
(true::S, E, sel C1 C2::C, D) => (S, E, C1, C::D) (false::S, E, sel C1 C2::C, D) => (S, E, C2, C::D)
|
join |
条件分岐から復帰する | (S, E, join::C, C'::D) => (S, E, C', D) |
ldf <parameter> <body> |
クロージャをプッシュ | (S, E, ldf x C'::C, D) => (Fn(E, x, C')::S, E, C, D) |
ldr <name> <parameter> <body> |
再帰クロージャをプッシュ | (S, E, ldr f x C'::C, D) => (Rec(E, f, x, C')::S, E, C, D) |
ap |
クロージャを呼び出す |
(v::Fn(E', x, C')::S, E, C, D) => (S, E'{x:v}, C', (E, C)::D) (v::Rec(E', f, x, C')::S, E, C, D) => (S, E'{f:Rec(E', f, x, C'), x:v}, C', (E, C)::D)
|
-
SECD machine - Wikipedia https://en.wikipedia.org/wiki/SECD_machine ↩︎