継続計算のための仮想機械の導出
木谷有沙

1(指導教官: 浅井健一)
かつ J Operator を実装しないのであれば、「スタッはじめにク」「環境」「コード」の三つ組の状態遷移により仮想プログラム変換によって単純λ計算のインタープリ機械を構成することができる。よって本研究では、ほタから抽象機械を機械的に導出する手法 [2] と、抽象ぼ SECD マシンに近い挙動をするがダンプを持たない機械をコンパイラと仮想機械に分割する手法 [1] は、と仮想機械を導出する。その上で、shift/reset での継続もに先行研究によって示されている。本研究では、まの切り取りをコードのコピーとして明示するために、ず単純λ計算のインタープリタを継続渡し形式に変換

コードのリストを評価器に受け渡すようにする。関数して shift/reset をサポートするインタープリタを導出

呼び出しの際にスタックとコードは退避されず、環境し、それに対してプログラム変換を行うことで、継続はスタックに保存される。コードリストへのコードの計算のための抽象機械を導出する。そして、その抽象退避は reset 命令が行われたときにのみ行われる。こ機械を分割することによって継続計算のためのコンパの仮想機械は「スタック」「環境」「コード」「コードイラと仮想機械を得られることを示す。

2リスト」の四つ組の状態遷移操作の繰り返しとして定インタープリタの CPS 変換義されるので、SECC マシンと呼ぶことにする。

継続（計算が終わった後にする処理, continuation）

5を引数として渡すことで、全ての関数を末尾呼び出しに抽象機械の導出
以下に示す手順で抽象機械を導出する。

する形式のことを、継続渡し形式（CPS : Continuation(1) CPS 変換

Passing Style）と呼ぶ。単純λ計算のインタープリタを CPS にするには、評価器が評価する項（term）や評価器を CPS 変換し、末尾再帰にする。この変換

環境（environment）に加えて、継続を受け取るようにより、項の評価順序が実装言語の評価戦略に依存しにする。ここでの継続は、「値（value）を受け取ったなくなる。ただし本研究では shift/reset の実装のため

ら、次にすべき評価をする」という関数となる。そし既に一度 CPS 変換されたインタープリタを扱うため、て、評価器のうち値を返していた節において、値をそ

ここでの CPS 変換は行わない。のまま返すのではなく継続に値を渡すようにする。

(2) 値と環境をスタックで受け渡しするよう変更

3

shift / reset

この変換により、それまではシステム上で各関数のshift/reset は、プログラム中の限定された区間の継スコープに保存されていた値や環境が評価器内で明示続を操作するオペレータである。今回の実装では、プ的に受け渡しされるようになる。ここで、関数呼び出

ログラム中で shift(...) と書く（... の部分には関数がし後の継続において環境が自由変数になるのを防ぐた入る）とユーザプログラムの中から現在の継続を切りめ、関数呼び出しの際に環境をコピーし、スタックに取ってきて、括弧内の関数に継続を引数として渡し、保存している。

その後関数のボディ部分を実行する。プログラム中で(3) 非関数化

reset(...) と書くと、括弧内の shift 命令で取って来られる継続を、括弧内の項で行われる評価のみに限定する。

CPS 変換により評価器内でクロージャを生成するようになっているのを、クロージャを使わずに同等の処理4を行うプログラムに変換する。この変換により、評価

SECD マシンと SECC マシン器が高階関数でなくなる。継続が関数ではなく項のリSECD マシンとはλ計算式を評価する仮想機械で、ストになるため、評価器の引数として新たに「項のリ「値を貯めるスタック (stack)」「環境」「コード (code)」ストのリスト」を受け渡すように変更することによっ「ダンプ (dump)」の四つ組の状態遷移操作の繰り返して、reset 命令での継続の限定範囲を判別するようにしとして定義されている。ダンプとは他の三つ組を一時た。また関数呼び出し後の環境の復帰のために、環境的に保存するための領域で、関数呼び出しの際にダンをスタックから出し入れするための項を新たに定義し、プにその時のスタック、環境、コードが保存され、関評価中に必要な箇所でコードへ追加するようにした。

数のボディの処理後にダンプから戻される。また、J(4) 関数をまとめる

Operator という継続計算のオペレータではダンプのそれぞれ一変数について再帰的な処理を行っていた中身をそのまま継続として取ってくる。これら以外で四つの関数を、ひとつの関数にまとめる。

ダンプが使われることはない。よって、関数呼び出し得られる抽象機械の状態は四つ組 hs, e, c, cli であり、後にスタック、環境、コードを適切な状態に復元でき、

15

c

⇒

h[], [], Term(c) :: [], []ihs, e, Term(x) :: c, cli
hs, e, Term(λx.t) :: c, cli⇒⇒

he(x) :: s, e, c, cli
hVFun(x, t, e) :: s, e, c, cli

hs, e, Term(t0 t1 ) :: c, cli⇒hs, e, Term(t1 ) :: Term(t0 ) :: Apply :: c, cli

hs, e, Term(shif t(t)) :: c, cli
hs, e, Term(reset(t)) :: c, cli⇒⇒hVCont(s, e, c) :: [], e, Term(t) :: Apply :: [], clih[], e, Term(t) :: [], (CSetEnv(s, e) :: c) :: cli

hVFun(x, t, e0 ) :: v :: s, e, Apply :: c, cli⇒hVEnv(e):: s, (x, v) :: e0 , Term(t) :: CPopEnv :: c, cli

hVCont(s0 , e0 , c0 ) :: v :: s, e, Apply :: c, cli⇒hv :: s0 , e0 , c0 , (CSetEnv(s, e) :: c) :: cli

hs, e, CSetEnv(s0 , e0 ) :: c, cli
hv :: VEnv(e0 ) :: s, e, CPopEnv :: c, cli⇒⇒hs @ s0 , e0 , c, cli
hv :: s, e0 , c, cli

hs, e, [], c :: cli⇒hs, e, c, cli

hv :: s, e, [], []i⇒v

図 1: 抽象機械の状態遷移規則c⇒h[], [], c, []ihs, e, access(x); c, cli
hs, e, close(x, c0 ); c, cli
hs, e, shift(c0 ); c, cli⇒⇒⇒he(x) :: s, e, c, cli
hVFun(x, c0 , e) :: s, e, c, cli
hVCont(s, e, c) :: [], e, c0 , cli

hs, e, reset(c0 ); c, cli⇒h[], e, c0 , (setEnv(s, e) :: c) :: cli

hVFun(x, c , e ) :: v :: s, e, apply; c, cli
hVCont(s0 , e0 , c0 ) :: v :: s, e, apply; c, cli⇒⇒hs, (x, v) :: e0 , c0 @ c, cli
hv :: s0 , e0 , c0 , (setEnv(s, e) :: c) :: cli

hs, e, setEnv(s0 , e0 ); c, cli
hv :: VEnv(e0 ) :: s, e, popEnv ; c, cli
hv1 :: v0 :: s, e, pushEnv; c, cli⇒⇒⇒

hs @ s0 , e0 , c, cli
hv :: s, e0 , c, cli
hv1 :: v0 :: VEnv(e) :: s, e, c, cli

hs, e, nil, c :: cli⇒hs, e, c, cli

hv :: s, e, nil, []i⇒v00

図 2: 仮想機械の状態遷移規則
こうして得られる仮想機械の状態は四つ組 hs, e, c, cli

その状態遷移規則は図 1 のように定義される。

6であり、その状態遷移規則は図 2 のように定義される。

仮想機械の導出7

前節で得た抽象機械を、Ager [1] らの手法を用いてまとめと今後の課題コンパイラと仮想機械へと分割する。前節で得た評価

本研究では shift/reset をサポートしたインタープリ

器は「項を引数とし、（再帰的に処理を行い、）コータについて、機械的なプログラム変換によってコンパドを返す」関数と、「スタック、環境、コード、コードイラ及び仮想機械を得られることを示した。今後は本列を引数とし、値を返す」関数に分割でき、前者をコ研究で得られた仮想機械の命令列からアセンブラへ変ンパイラ、後者を仮想機械と見なすことができる。実換する手法について検討し、最終的には機械語のレベ際には以下の手順でコンパイラ及び仮想機械の導出をルで限定継続の処理がどのように扱われるのかを明ら行った。

かにすることを目指す。そしてそれに伴い、継続計算のための処理系の系統的な導出法を示したい。

(1) 評価器を、上述の考えに基づきカリー化する。

参考文献(2) 中間言語（仮想機械にとっての機械語）を定義し、(1) をもとに、項を受け取ったらそれをコードに変換するコンパイラを定義する。また、スタック、[1] M. S. Ager, D. Biernacki, O. Danvy, and J. Midtgaard: “From Interpreter to Compiler and VirtualMachine : A Functional Derivation,” Technical Report RS-03-14, BRICS, Aarhus, Denmark (March2003).

環境、コードを受け取ったら値を返す仮想機械を構成する。このとき、環境を出し入れするための[2] O. Danvy and K. Millikin: “A Rational Deconstruction of Landin’s J Operator,” Technical Report RS06-17, BRICS, Aarhus, Denmark (December 2006).

命令はコンパイラ側で追加するように変更し、仮想機械でコードを処理する際の、コードへの干渉を減らした。

16