- 著者
-
前田 敦司
曽和 将容
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)
- 巻号頁・発行日
- vol.41, no.4, pp.1-10, 2000-06-15
- 参考文献数
- 20
末尾再帰的な関数呼び出しをジャンプに変換する処理は,コンパイラの最適化として広く行なわれている.特に,Lispの一方言であるScheme言語においては末尾再帰呼び出しを空間計算量ο()で実行することが言語仕様で要求されている.このように,空間計算量ο()で実行することができる末尾再帰呼び出しを真の末尾再帰呼び出し(roper tail recursio)と呼ぶ.動的スコープを持つ変数が存在する場合,通常の実装では,スコープを規定する構文の実行が終るまで変数束縛を保持しておく必要があるため,構文の末尾で再帰的な関数呼び出しがあってもそれを真の末尾再帰呼び出しとすることができない.しかしながら,リスト構造を用いて変数束縛を保持する,いわゆる深い束縛を用いるLispインタプリタについては,事実上定数空間計算量で末尾再帰呼び出しを処理することができる手法が知られている.本論文では,動的スコープ変数の実装として現一般的な,浅い束縛を用いた場合について,真の末尾再帰呼び出しを実現するための手法について述べる.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.