変数条件に基づく原始帰納関数の再帰融合について
スポンサーリンク
概要
- 論文の詳細を見る
本発表では原始再帰的な関数に関するプログラム変換の一手法について述べる.Pを原始再帰関数としQを再帰子としたとき, 合成関数Q^*PにおいてPの生成する中間データ構造を除去してQをPに取り込むことは「再帰計算の融合」として知られている.例えば自然数の加乗算における結合法則や指数法則はこの典型例としてとらえることができる.再帰計算の融合は展開・畳み込み法によって実現可能であるが, 本講演ではこれと同値でかつより洗練された形式を持つプログラム変換を提示する.素朴な展開・畳み込み法では, プログラムP(融合される側)中の再帰部分をまず展開し, その結果得られたプログラムに畳み込み可能な構造が現れている場合に畳み込みを実行する.しかし, そうでない場合には既に行なった展開を遡ってキャンセルするという手順上の冗長性がある.また変換手続きの記述も複雑で理論的な分析の対象としては不都合である.一方本講演で与える手法では, 変換を適用するに先立ってプログラム中の変数の現れ方を調べ, 確実に畳み込みが成功する再帰部分を特定する.続く変換ではその箇所のみ展開を実行すればよい.畳み込み可能性の判定には「強自由変数」とよぶ新概念を利用するが, その定義はプログラムの構成に関する単純な帰納法で記述することができ, 理論的な解析にも有用である.
- 一般社団法人情報処理学会の論文
- 1999-08-15
著者
関連論文
- 変数の出現条件を用いた融合変換とその反復適用について (プログラム変換と記号・数式処理)
- 変数条件に基づく原始帰納関数の再帰融合について
- 一般部分計算における形式的推論体系の利用について(一般発表)
- 証明論的手法による一般部分計算の記述
- Shrinkability of Unbounded Sets in the Cohen Extention(Metamathematics and it's applications)