shift/reset を含む部分評価器の実装
対馬かなえ

1(指導教官:浅井健一)

はじめに束縛時解析

5

本研究では [2, 3] を参考にして部分評価器を実装し、束縛時解析ではプログラム中の式を評価可能 (Static)

それを [1] のように shift/reset を含むように拡張するな部分と評価不可能 (Dynamic) な部分に分けていく。

ことを目的とする。それによって shift/reset を含むプ

評価可能とは計算して値にすることが出来るというこ

ログラムの部分評価が可能となり、実行時により速くとであり、評価不可能とは式として残す必要があると計算出来るようになることが期待される。

いうことである。Static な式は通常と同じ構文で書き、継続とは式の評価時にその後にする仕事のことであDynamic な式はその前に “_” を付けることで表す。
例えば (fun m → m + (1 + 2)) では、(1 + 2) は評価出来るが、m の値は分からないので m + (1 + 2)る。shift/reset とは継続を限定して扱うための命令でを評価することは出来ない。従って (1 + 2) は Static、ある。shift は限定された継続を切り取ってくる命令、m は Dynamic、式全体は Dynamic となる。

2

継続、shift/reset とは加算の部分を型規則で表すと以下のようになる。

reset は shift の切り取る継続を限定する命令である。

Γ ` E1 : i1 Γ ` E2 : i2
Γ ` E1 + E2 : i
i2 → i, i1 → i
i2 → i は i2 が Dynamic であるならば i も Dynamic

例えば 1 + reset (2 * (shift k → k 3)) という式を考えると、shift が切り取ってくる継続は resetの内側に限定された 2 を掛けるという部分のみであり、になることを表す。これは加算の左右の項の片方でもreset の外側の 1 を足すという部分は含まない。この
2 を掛けるという部分は (fun x → 2 * x) という関Dynamic になったら、加算全体が Dynamic になることを示している。

数に相当する。よって k 3 は (fun x → 2 * x) 3 とDynamic な式の中に Static な式が発生する時には、Static な式を Dynamic な式として扱うための lift となり、6 と評価される。次に 2 * の部分は shift によって切り取られてしまったため、計算されず、最後いう式を用いる。これを用いて上の例を束縛時解析すに 1 + を評価して最終結果は 7 となる。

3ると (fun m → m _+ lift(1 + 2)) となる。m に足すという式は評価出来ないが、1 + 2 は評価出来ると部分評価

束縛時解析されているのが分かる。この式の特化を行部分評価とは、主に計算時間の短縮を目的としてプうと (fun m → m + 3) となる。

ログラム中の評価出来る「部分」を「評価」したプロ

lift の式の中に入り得るのは数字かブール値に評価出来る Static な式のみであり、関数は入り得ない。

グラムを作る処理である。プログラムを見ながら部分評価していくオンライン部分評価と、プログラムを評

5.1

価可能な所と評価不可能な所に分け (束縛時解析) それから評価 (特化) していくオフライン部分評価がある

polyvariant な束縛時解析

ここで以下のプログラムを考える。

が、本研究ではオフライン部分評価を扱う。

let rec power x y =例として x の y 乗を求める関数

if y = 0 then 1 else x * (power x (y - 1))
in (fun m → (power m 2 + power 2 m))

let rec power x y =if y = 0 then 1 else x * (power x (y - 1))

この関数 power は、power m 2 では x が Dynamic とを (fun m → (power m 2)) と呼び出す場合を考えなり、 power 2 m では y が Dynamic となる。従って両る。m の値が不明であるが、評価 (関数展開) してい者で一つの関数を共有すると、引数全てが Dynamic とくと、(fun m → m * m * 1) という 2 乗に特化しなり、3 章で部分評価可能だった power m 2 も部分評価た元のプログラムと全く同じ計算をする関数が得られ不可能になってしまう。そこで引数の Static/Dynamicる。このように評価出来る所を出来るだけ評価していに応じて関数を新たに作り、それぞれを束縛時解析しくというのが部分評価である。ていくことにする。
上のプログラムは4構文

let rec power1 x y =if y = 0 then (lift 1)
else x _* (power1 x (y - 1)) in

今回扱う構文は OCaml を簡略化したもので、束縛時解析後は構文が Static/Dynamic の 2 レベルとなる。

15

たっても決定出来ず、無限に展開されてしまう。

let rec power2 x y =_if y _= (lift 0) then (lift 1)

関数展開可能か否かの判断は一般には決定不能なので、ユーザがプログラム入力時に関数の引数が再帰関数

else(lift x) _* (_power2 x (y _- (lift 1)))か否かを、引数の後にブール値で指定するものとする。

in (_fun m → (power1 m 2 _+ _power2 2 m))

6.2のように power1 は power の引数が Dynamic、Static

束縛時解析の結果が Dynamic なら評価不可能であな場合、power2 は Static、Dynamic な場合とそれぞる。しかし 3 章のプログラムの場合、一つ目の引数がれ束縛時解析される。

5.2

特化

2 であることが分かっているので x を 2 で置き換えて
let rec power2 y =if y = 0 then 1 else 2 * (power2 (y - 1))

shift/reset を含む束縛時解析

継続が含まれると、型は式の型に加えて答えの前後

in (fun m → power2 m)とすることが可能である。引数を減らしその場合に特の型が必要になる。前述の型規則は以下のようになる。

Γ, t2 ` E1 : i1 , t1 Γ, t3 ` E2 : i2 , t2
Γ, t3 ` E1 + E2 : i, t1
i2 → i, i1 → i

化した関数を作るのでこの処理は特化という。

6.3

これは t を無視して、i のみ見れば shift/reset を含ま

特化変数

しかしいつでも特化を行ってよい訳ではなく、特化ない型規則と同一である。加えて下の shift/reset の構文の型規則が追加される。shift の型規則は、を行うと無限に特化を行ってしまうような例もある。

Γ, x : Fun(t2 , t3 , [t6 ], t1 , t3 ), t4 ` E : t4 , t5
Γ, t1 ` shift x → E : t2 , t5

例えばアキュムレータを使った x の y 乗を求める関数
let rec power x:false y:true acc:false =t 6 → t 2 , t6 → t 3 , t6 → t 1となる。t6 とは Fun 全体の型であり、t6 が Static なら

if y = 0 then acc
else (power x (y - 1) (x * acc))
で (fun m → power 2 m 1) と呼び出された場合にばその Fun の型を持つ式が評価可能であることを示している。t6 が Dynamic になれば、引数も含めて Fun特化を行うと acc が 1 のバージョン、2、4、· · · と無全体が Dynamic になる。

限に作られ、特化が止まらなくなる。
特化をしたい引数であるかどうかも関数の引数の後

また、reset の型規則は以下のようになる。にユーザが指定することにする。上の関数では
let rec power x:false,true y:true,true

Γ, t1 ` E : t1 , t2
Γ, t3 ` reset E : t4 , t3
if t2 = Dynamic/Fun then t4 = t2
shift/reset は式の型を増やし、上の規則を加えるだけ

acc:false,false =if y = 0 then acc
else (power x (y - 1) (x * acc))と指定される。

で実装出来ている。

特化

67

特化とは評価可能な式を評価し、評価不可能とされ

本研究では polyvariant な再帰関数の束縛時解析を定た式も与えられた値専用のプログラムが作れるならば式化し、shift/reset を含むプログラムの部分評価器を作り、より評価を進めることである。それぞれ考察す実装した。これによって関数の引数の Static/Dynamic

べき状況とその例があるので、それを以下で示す。

6.1

まとめと今後の課題に応じて関数が複製され、polyvariant な特化が行える

再帰変数ようになった。
今後は shift/reset を含む様々なプログラムで特化が再帰を含む関数の場合、関数展開してよいかどうかどのように行われていくか見ていきたい。

は、再帰に関わる変数 (再帰変数) が分かっているかどうかに関係してくる。再帰変数が分かっていると、無限の関数展開が避けられるため関数展開が行え、よ参考文献

り特化が出来る。しかし、[1] Kenichi. Asai “Logical Relations for Call-by-value
Delimited Continuations”, In A chapter of Trends inFunctional Programming, Vol. 6, pp. 63–78, Intellect(2007).
[2] 阪上紗里 “MinCaml Compiler における関数展開の制御”, お茶の水女子大学 卒業論文 2006.
[3] 長崎玲 “オフライン部分評価器の実装”, お茶の水女子
大学 卒業論文 2004.

let rec power x y =if y = 0 then 1 else x * (power x (y - 1))
in (fun m → power 2 m)というプログラムを考えると、再帰変数となっているm の値が分からないので y = 0 かどうかはいつまで

16