著者

皆川 宜久 鵜川 始陽 八杉 昌宏 湯淺 太一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.46, no.11, pp.71-71, 2005-08-15

---

継続とは,計算のある時点の残りの計算である.Scheme では,これをファーストクラスのオブジェクトとして扱え,コルーチンやマルチスレッドなどの機能を実現するのに有用である.ML 言語において一級継続の機能を搭載した処理系としては,Standard ML of New Jersey がある.この処理系はスタックを用いず関数フレームをすべてヒープ領域に割り付けているため,定数オーダの時間で継続の生成を実現している.しかし,一般に関数フレーム生成時にスタックを用いた方が,高速であり,メモリ効率も良い.本研究では,スタックを用いているML 処理系に対し,一級継続の実装を行った.この場合,継続の生成時にスタックの内容をヒープにコピーするスタック法が一般的である.実際,スタックを用いたScheme 処理系で多く採用されている.この方法は動作が単純で実装しやすいなどの利点がある.一方,継続生成のたびにスタックのコピーが行われるので,生成時間,メモリ効率の点などで効率が悪いことがある.そこで本研究では,その効率化手法である遅延スタックコピー法を採用した.この手法は,継続を使用したプログラムの効率を高める一方,オブジェクトの生成時や代入時にオーバヘッドが存在するという欠点がある.そこで,コンパイル時にML の型情報を利用して,そのオーバヘッドを軽減する手法を提案し,実装,評価を行った.A continuation is the remaining task at a point in a computation. In Scheme, a continuation can be captured as a first-class object. This is useful for implementing coroutines and multi-threading. Standard ML of New Jersey is an implemenation of ML with first-class continuations. This system allocates all activation records into the heap, and this feature allows capturing continuations in constant order time. In general, however, a stack is more efficent in terms of execution time and memory space to allocate activation records. We implemented first-class continuations in a stack-based ML system. In order to implement first-class continuations, we adapted the stack strategy which is used in many stack-based implementations of Scheme. With this strategy, the entire stack contents are copied into the heap whenever a continuation is captured. This strategy is simple and easy to implement, but capturing continuations requires a lot of time and memory space. Thus, we employed the lazy stack copying strategy, which is based on the stack strategy but more efficent. While this strategy is useful when creating continuations, there is an overhead when creating and modifying objects. We propose a technique to reduce this overhead by using the type information of ML at compile time, and we applied this techinique to the ML system and evaluated it.