スタックベースのML処理系における効率的な一級継続の実装

概要

論文の詳細を見る
継続とは, 計算のある時点の残りの計算である.Schemeでは, これをファーストクラスのオブジェクトとして扱え, コルーチンやマルチスレッドなどの機能を実現するのに有用である.ML言語において一級継続の機能を搭載した処理系としては, Standard ML of New Jerseyがある.この処理系はスタックを用いず関数フレームをすべてヒープ領域に割り付けているため, 定数オーダの時間で継続の生成を実現している.しかし, 一般に関数フレーム生成時にスタックを用いた方が, 高速であり, メモリ効率も良い.本研究では, スタックを用いているML処理系に対し, 一級継続の実装を行った.この場合, 継続の生成時にスタックの内容をヒープにコピーするスタック法が一般的である.実際, スタックを用いたScheme処理系で多く採用されている.この方法は動作が単純で実装しやすいなどの利点がある.一方, 継続生成のたびにスタックのコピーが行われるので, 生成時間, メモリ効率の点などで効率が悪いことがある.そこで本研究では, その効率化手法である遅延スタックコピー法を採用した.この手法は, 継続を使用したプログラムの効率を高める一方, オブジェクトの生成時や代入時にオーバヘッドが存在するという欠点がある.そこで, コンパイル時にMLの型情報を利用して, そのオーバヘッドを軽減する手法を提案し, 実装, 評価を行った.
一般社団法人情報処理学会の論文
2005-08-15

スタックベースのML処理系における効率的な一級継続の実装

スポンサーリンク

概要

著者

関連論文

スポンサーリンク