著者

鵜川 始陽 皆川 宜久 小宮 常康 八杉 昌宏 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.13, pp.72-83, 2003-10-15

---

実行にスタックを利用している処理系でファーストクラスの継続を生成する場合,スタックの内容をヒープにコピーするのが一般的である.スタックの内容をヒープにコピーする戦略には様々なものが提案されているが,実際の処理系の多くはスタック法を採用している.スタック法では継続の生成のたびに処理系のスタック全体の内容をヒープにコピーする.このように,スタック法は動作が単純なので簡単に実装でき,また他言語呼び出しをサポートした処理系でも利用できるという長所がある.しかし,継続の生成に時間がかかり,また,メモリ効率が悪いという欠点があり,利用の妨げとなる場合もある.本発表では,スタック法による継続の生成に対する効率化手法として,スタックのコピーの遅延を提案する.継続の生成によりコピーされるスタックの内容は,継続を生成した関数からリターンするまでスタック上にも残っている.したがって,スタックのコピーを継続を生成した関数からリターンするまで遅らせてもよい.もし,生成した継続が,スタックをコピーする前にごみになれば,スタックのコピーを省略できる.本発表では,さらに,スタックコピーの遅延により可能となる,継続オブジェクトの部分的共有も提案する.これらの効率化手法をScheme処理系に組み込んで性能を評価したところ,継続を使ったプログラムの実行効率が改善された.In order to capture first-class continuations, most stack-based implementations copy contents of the stack to the heap. While various implementation strategies for copying are proposed, most implementations employ the stack strategy. With this strategy, the entire stack contents are copied to the heap whenever a continuation is captured. This simple strategy is easy to implement and can be used for implementations with foreign language interface. However, continuations with this strategy spend a lot of time and memory for their creations and invocations, and this week point often discourages programmers from using first-class continuations. We propose a lazy stack copying technique. The contents of the stack to copy will be preserved on the stack until returning from the function that is capturing the continuation. So we delay stack copying for a continuation until the function returns. We can avoid stack copying if it is detected that the continuation became a garbage before the function returs. In addition, we propose another technique, partial sharing of the copied stack, which is realized by using the lazy stack copying technique. We applied these techniques to Scheme interpreters and found that the proposed techniques improve runtime and memory efficiency of programs that use continuations.