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

• Item type: Trans(1)
• 公開日: 2010-12-10
• タイトル: L-Closureを用いた真に末尾再帰的なSchemeインタプリタ
• タイトル / 言語: en
• タイトル: A Properly Tail-recursive Scheme Interpreter Using L-closures
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: レッドハット株式会社グローバルサービス本部
• 著者所属: 電気通信大学大学院情報システム学研究科
• 著者所属: 京都大学学術情報メディアセンター
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: 京都大学大学院情報学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Red Hat K.K., Global Services, Japan
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Systems, the University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Academic Center for Computing and Media Studies, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者名: 八杉, 昌宏; 小島, 啓史; 小宮, 常康; 平石, 拓; 馬谷, 誠二; 湯淺, 太一
• 著者名(英): Masahiro, Yasugi; Hirofumi, Kojima; Tsuneyasu, Komiya; Tasuku, Hiraishi; Seiji, Umatani; Taiichi, Yuasa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Scheme処理系は真に末尾再帰的であることが要求されており，アクティブな末尾呼び出しの数に制限がない場合もサポートしなくてはならない．Clingerは真の末尾再帰の形式的定義の1つを空間効率の点から与えており，その定義に従えば，末尾呼び出しの最適化（末尾呼び出しをトランポリンなどによりジャンプに置き換えて実装する方法）だけでなく，BakerのCPS（継続渡しスタイル）変換を用いたC言語におけるSchemeの実装手法も，真に末尾再帰的と分類できる．Bakerの実装手法は，CPS変換された末尾呼び出しにおいて新たな継続を生成せず，C言語の実行スタックに対してもごみ集めを行うため，空間効率が良い．本論文では拡張C言語による真に末尾再帰的なSchemeインタプリタの実装手法を提案する．本手法はCPS変換を用いず，Cの実行スタックがあふれそうになれば，残りの計算に必要な“Frame”オブジェクトのみを含むリストとして表現された空間効率の良い一級継続を生成し，すぐさまその継続を呼び出すというアイディアに基づく．ごみ集めや継続のキャプチャにおいては，実行スタックに合法的にアクセスできる，つまりデータ構造や変数の値としてアクセスできるL-closureという言語機構を用いている．ベースとなるSchemeインタプリタは，Javaアプリケーション組み込み用LispドライバであるJAKLDをもとにC言語で再実装されたものとした．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 3, 号 5, p. 1-17, 発行日 2010-12-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会