著者

八杉 昌宏 小島 啓史 小宮 常康 平石 拓 馬谷 誠二 湯淺 太一

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.3, no.5, pp.1-17, 2010-12-10

---

Scheme処理系は真に末尾再帰的であることが要求されており,アクティブな末尾呼び出しの数に制限がない場合もサポートしなくてはならない.Clingerは真の末尾再帰の形式的定義の1つを空間効率の点から与えており,その定義に従えば,末尾呼び出しの最適化(末尾呼び出しをトランポリンなどによりジャンプに置き換えて実装する方法)だけでなく,BakerのCPS(継続渡しスタイル)変換を用いたC言語におけるSchemeの実装手法も,真に末尾再帰的と分類できる.Bakerの実装手法は,CPS変換された末尾呼び出しにおいて新たな継続を生成せず,C言語の実行スタックに対してもごみ集めを行うため,空間効率が良い.本論文では拡張C言語による真に末尾再帰的なSchemeインタプリタの実装手法を提案する.本手法はCPS変換を用いず,Cの実行スタックがあふれそうになれば,残りの計算に必要な"Frame"オブジェクトのみを含むリストとして表現された空間効率の良い一級継続を生成し,すぐさまその継続を呼び出すというアイディアに基づく.ごみ集めや継続のキャプチャにおいては,実行スタックに合法的にアクセスできる,つまりデータ構造や変数の値としてアクセスできるL-closureという言語機構を用いている.ベースとなるSchemeインタプリタは,Javaアプリケーション組み込み用LispドライバであるJAKLDをもとにC言語で再実装されたものとした.Implementations of Scheme are required to be properly tail-recursive and to support an unbounded number of active tail calls. Clinger proposed a formal definition of proper tail recursion based on space efficiency. The definition covers systematic tail call optimization, where every tail call is converted to a jump (with an optional trampoline), as well as Baker's implementation of Scheme in the C language with CPS (continuation-passing style) conversion. Baker's implementation is space-efficient, since no new continuation is created on a CPS-converted tail call and garbage is collected even on C's execution stack. We propose techniques to implement a properly tail-recursive Scheme interpreter in an extended C language. Our approach does not convert a program into CPS. The key idea is to avoid stack overflow by creating a space-efficient first-class continuation represented as a list containing only the "Frame" objects necessary for the rest of computation and immediately invoking the continuation. We use a language mechanism called "L-closures" to access the contents of the execution stack as values of legal data structures and variables for implementing garbage collection and capturing continuations. This research is based on a Scheme interpreter which is developed in the C language by referring to an existing Lisp driver called JAKLD that is intended to be embedded in Java applications.