浅い束縛による動的スコープ変数が存在する時の末尾再帰呼び出し

• Item type: Trans(1)
• 公開日: 2000-06-15
• タイトル: 浅い束縛による動的スコープ変数が存在する時の末尾再帰呼び出し
• タイトル / 言語: en
• タイトル: Proper Tail Recursion with Shallow - bound Dynamically Scoped Variables
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 電気通信大学 大学院 情報システム学研究科
• 著者所属: 電気通信大学 大学院 情報システム学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, University of Electro - Communications
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, University of Electro - Communications
• 著者名: 前田, 敦司; 曽和, 将容
• 著者名(英): Atusi, Maeda; Masahiro, Sowa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 末尾再帰的な関数呼び出しをジャンプに変換する処理は，コンパイラの最適化として広く行なわれている．特に，Lispの一方言であるScheme言語においては末尾再帰呼び出しを空間計算量ο(）で実行することが言語仕様で要求されている．このように，空間計算量ο(）で実行することができる末尾再帰呼び出しを真の末尾再帰呼び出し(roper tail recursio)と呼ぶ．動的スコープを持つ変数が存在する場合，通常の実装では，スコープを規定する構文の実行が終るまで変数束縛を保持しておく必要があるため，構文の末尾で再帰的な関数呼び出しがあってもそれを真の末尾再帰呼び出しとすることができない．しかしながら，リスト構造を用いて変数束縛を保持する，いわゆる深い束縛を用いるLispインタプリタについては，事実上定数空間計算量で末尾再帰呼び出しを処理することができる手法が知られている．本論文では，動的スコープ変数の実装として現一般的な，浅い束縛を用いた場合について，真の末尾再帰呼び出しを実現するための手法について述べる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Conversion of tail recursive function call into simple jump is a technique widely used as optimization in compilers. Especially, Scheme, a dialect of Lisp, requires as part of language specification that tail recursion be performed in ο(1) space complexity. Tail recursion implemented in ο(1) space complexity is called "proper tail recursion". With existance of dynamically-scoped variables, ordinary implementation keeps variable bindings until binding construct exits. Thus, syntactic tail call cannot be implemented in a properly tail recursive fashion. For Lisp interpreters which keeps variable bindings in list structures (i.e. deep binding), there is a known way to achieve almost-proper tail recursion with dynamic scoping. In this paper, we argue about an implementation method of proper tail recursion with shallow binding, which is a common way of implementing dynamically-scoped variables in current Lisp implementations.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 41, 号 SIG04(PRO7), p. 1-10, 発行日 2000-06-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会