文献

J-GLOBAL ID：201102265939068841   整理番号：11A1900646

L-Closureを用いた真に末尾再帰的なSchemeインタプリタ

A Properly Tail-recursive Scheme Interpreter Using L-closures

著者 (6件)： 八杉昌宏 (京大 大学院情報学研究科) ,  小島啓史 (レッドハット) ,  小宮常康 (電通大 大学院情報システム学研究科) ,  平石拓 (京大 学術情報メディアセ) ,  馬谷誠二 (京大 大学院情報学研究科) ,  湯淺太一 (京大 大学院情報学研究科)
資料名： 情報処理学会論文誌トランザクション(CD-ROM)  (情報処理学会論文誌 Computer Vision and Applications(CD-ROM))
巻： 2010  号： 2  ページ： ROMBUNNO.PUROGURAMINGU,VOL.3,NO.5,1-17  発行年： 2011年04月15日 
JST資料番号： L7379A  ISSN： 1882-7772  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： Scheme処理系は真に末尾再帰的であることが要求されており,アクティブな末尾呼び出しの数に制限がない場合もサポートしなくてはならない。Clingerは真の末尾再帰の形式的定義の1つを空間効率の点から与えており,その定義に従えば,末尾呼び出しの最適化(末尾呼び出しをトランポリンなどによりジャンプに置き換えて実装する方法)だけでなく,BakerのCPS(継続渡しスタイル)変換を用いたC言語におけるSchemeの実装手法も,真に末尾再帰的と分類できる。Bakerの実装手法は,CPS変換された末尾呼び出しにおいて新たな継続を生成せず,C言語の実行スタックに対してもごみ集めを行うため,空間効率が良い。本論文では拡張C言語による真に末尾再帰的なSchemeインタプリタの実装手法を提案する。本手法はCPS変換を用いず,Cの実行スタックがあふれそうになれば,残りの計算に必要な“Frame”オブジェクトのみを含むリストとして表現された空間効率の良い一級継続を生成し,すぐさまその継続を呼び出すというアイディアに基づく。ごみ集めや継続のキャプチャにおいては,実行スタックに合法的にアクセスできる,つまりデータ構造や変数の値としてアクセスできるL-closureという言語機構を用いている。ベースとなるSchemeインタプリタは,Javaアプリケーション組み込み用LispドライバであるJAKLDをもとにC言語で再実装されたものとした。(著者抄録)

シソーラス用語： *インタプリタ ,  再帰性 ,  実装設計 ,  *C言語 ,  ガーベジコレクション ,  アクセシビリティ ,  データ構造 ,  変数 ,  閉包 ,  Java ,  システム ,  LISP ,  組込みシステム
準シソーラス用語： 末尾再帰性 ,  *拡張C言語

分類 (2件)： 言語プロセッサ  (JD03040F) ,  汎用プログラミング言語  (JD03051H)

引用文献 (25件)：

• 1) Appel, A.W.: Compiling with Continuations, Cambridge University Press (1992).
• 2) Baker, H.G.: CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A., ACM SIGPLAN Notices, Vol.30, pp.17-20 (1995).
• 3) Chicken-hackers: Chicken Scheme. http://www.call-with-current-continuation.org/
• 4) Clinger, W.D.: Proper Tail Recursion and Space Efficiency, Proc. ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation (PLDI'98), pp.174-185 (1998).
• 5) Clinger, W.D., Hartheimer, A.H. and Ost, E.M.: Implementation Strategies for First-Class Continuations, Higher-Order and Symbolic Computation, Vol.12, pp.7-45 (1999).

タイトルに関連する用語 (2件)： Scheme ,  インタプリタ