ワンショットの限定継続に着目した代数的効果から非対称コルーチンへの変換
河原 悟 亀山 幸義 (筑波大学)
研究内容
代数的効果 (algebraic effects) と呼ばれる、近年関心を寄せている言語機能がある。代数的効果はエフェクトの発生以降のコンテキストを継続として持ち、 shift/reset をエミュレートすることができる。代数的効果を持つ
Multicore OCaml は、継続の実行を高々 1 回に制限した代数的効果を持つ。一方、継続を一度だけ実行できる
限定継続 oneshot shift/reset は非対称コルーチンに変換できることが知られている。
本研究では、ワンショットの代数的効果からワンショットの shift/reset へ変換し、そしてその shift/reset から非対称コルーチンに変換することを検討する。そしてワンショットの代数的効果から非対称なコルーチンへの直接の変換を考える。ワンショットの代数的効果から非対称なコルーチンへ変換をおこなうことにより、 Lua のようなコルーチンを持つ体系でワンショットの代数的効果を用いたプログラミングが期待できる。

oneshot shift/resetoneshotAlgebraic
Effects

非対称コルーチン
非対称コルーチンは de Moura と Ierusalimschy により提唱された、 “呼び出す”、 “呼び出される” 関係を持つコルーチンである [3]。対称コルーチンやワンショットの継続と同等の表現力があることが知られており、非対称コルーチンはLua や JavaScript などの言語へ組み込まれているだけでなく、 Unity などのゲームエンジンの機能としても採用されている。

代数的効果
Moggi らの computational effects を基に、 2001 年に Plotkin らにより提唱された [4]。コントロールの操作ができ、例外だけでなく、限定継続を扱うことで shift/reset をエミュレートすることができる。代数的効果のあるプログラム言語とその実装に、 Eff、 Koka や Links などがある。
Multicore OCaml は、代数的効果を持つ OCaml の方言である。並列プログラミングやパフォーマンスのために、ハンドラにより取り出される限定継続の実行は、明示的なクローンをおこなわない限りは高々 1 回に制限されている [1]。
module State ( S : sig type t end ) = structtype t = S . t
effect Put : t -> unit
effect Get : t::::::::::::::::::::::::::::::::::::::::::

let get () = perform Get:::::::::::::::::::::::::

let run init f =init |> match f () with| x -> ( fun s -> (s , x ))| effect ( Put s ') k ->( fun s -> continue k () s ')| effect Get k ->( fun s -> continue k s s )end:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

let log m = perform @@ Log m::::::::::::::::::::::::

chr = { hp = 0; mp = 0}

try beginlet module IS =State ( struct type t = int end )in
let incr () =IS .( perform @@ Put ( get () + 1))
in
IS . run 0 ( fun () ->incr ();
log @@ IS . get ();incr ();
log @@ IS . get ())
end
with effect ( Log msg ) k ->print_int msg ; continue k ()::::::::::

chr.ctrl =coroutine.create ( function ( hp , mp )chr.hp = hp
chr.mp = mp::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

effect Log : int -> unit

asymmetriccoroutine

while true do
local fld , v = coroutine.yield ()chr [ fld ] = chr [ fld ] + v
endend )::::::::::::::::::::::::::::::::::::::::::::::::::::

coroutine.resume ( chr.ctrl , 100 , 100)
coroutine.resume ( chr.ctrl , " hp " , -10)
coroutine.resume ( chr.ctrl , " mp " , -20)::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

ワンショット代数的効果からワンショット shift/reset への変換

Kiselyov らによる shift/reset ライブラリを用いた Eff を OCaml へ埋め込む方法 [2]に基づいて実装をおこなった。本研究は、これをワンショットに限定した変換にする。
module Translate ( D : DELIMCC ) sig
type ('a , 'b ) free
val newi : unit -> 'a D . prompt
val op : ('a , 'b ) free D . prompt -> 'a -> 'b
val handler : ('g , 'g ) free D . prompt ->( ' g -> 'o ) -> (' g * (' g -> 'o ) -> 'o ) -> 'g thunk -> 'oval handle : (' a thunk -> 'b ) -> 'a thunk -> 'b
end = struct ...... end
let ans =let module Eff = Translate ( DelimccOne ) in
let readerh inst = Eff . handler inst
( fun v -> ( fun _ -> v ))( fun (x , k ) -> ( fun s ->(* runtime error : cannot call `k ` more than once *)(* k 0 0; let z = x + s in k z s *)let z = x + s in k z s ))inlet readi = Eff . newi () inlet hr = Eff . handle ( readerh readi ) @@ fun () ->let x = Eff . op readi 1 inlet y = Eff . op readi x in yin hr 10::::::::::::::::::::::::::::::::::::::::::::::::::::::::

ワンショット代数的効果から非対称コルーチンへの変換
ワンショットの shift/reset は非対称コルーチンへ変換できることが知られている [5]。この変換を踏まえて、ワンショットの代数的効果から非対称コルーチンへの変換を考える。まず、ワンショットの代数的効果からワンショットの shift/reset へ変換する。そして得られた shift/reset を非対称コルーチンへ変換する。この結果を観察し、ワンショットの代数的効果から非対称コルーチンへの直接の変換を検討する。 shift/reset への変換を経由しないことで、シンプルな変換として表現することが期待できる。
Kiselyov らによる代数的効果から shift/reset への変換では、対象となる shift/reset はプロンプトのある体系である。一方で Usui らの変換では、プロンプトをもたないshift/reset が用いられている。 Usui らの変換に基づき、プロンプトを持つワンショットの shift/reset をターゲットとした非対称コルーチンへの変換を考える。
done
Algebraic Effects

shift/resetmaybe

oneshot Algebraic Effects???
asymmetric coroutine

oneshot shift/reset

done

参考文献

[1] Stephen Dolan, Leo White, K Sivaramakrishnan, Jeremy Yallop, and Anil Madhavapeddy. Effective concurrency through algebraic effects. In OCamlWorkshop, p. 13, 2015.
[2] Oleg Kiselyov and KC Sivaramakrishnan. Eff directly in ocaml. In ML Workshop, 2016.
[3] Ana Lúcia De Moura and Roberto Ierusalimschy. Revisiting coroutines. ACM Trans. Program. Lang. Syst., Vol. 31, No. 2, pp. 6:1–6:31, February 2009.
[4] Gordon Plotkin and John Power. Adequacy for algebraic effects. In International Conference on Foundations of Software Science and Computation
Structures, pp. 1–24. Springer, 2001.
[5] Chiharu Usui. One-shot delimited continuations as coroutines, 2017.