WEKO3
アイテム
変数条件に基づく原始帰納関数の再帰融合について
https://ipsj.ixsq.nii.ac.jp/records/16996
https://ipsj.ixsq.nii.ac.jp/records/16996417395fc-5a6d-4a75-aae2-87c42ec1f75d
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1999 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | Trans(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1999-08-15 | |||||||
タイトル | ||||||||
タイトル | 変数条件に基づく原始帰納関数の再帰融合について | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | A Fusion Procedure for Primitive Recursive Functions Based on a Variable Condition | |||||||
言語 | ||||||||
言語 | jpn | |||||||
キーワード | ||||||||
主題Scheme | Other | |||||||
主題 | 発表概要 | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
資源タイプ | journal article | |||||||
著者所属 | ||||||||
早稲田大学理工学総合研究センター | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Advanced Research Institute for Science and Engineering, Waseda University | ||||||||
著者名 |
湯浅, 能史
× 湯浅, 能史
|
|||||||
著者名(英) |
Takafumi, Yuasa
× Takafumi, Yuasa
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 本発表では原始再帰的な関数に関するプログラムの変換の一手法について述べる.Pを原始再帰関数としQを再帰子したとき 合成関数Q*PにおいてPの生成する中間データ構造を除去してQをPに取り組むことは「再帰計算の融合」として知られている.例えば自然数の加乗算における結合法則や指数法則はこの典型例としてとらえることができる.再帰計算の融合は展開・畳み込み法によって実現可能であるが 本講演ではこれと同値でかつより洗練された形式を持つプログラム変換を提示する.素朴な展開・畳み込み法では プログラムP(融合される側)中の再帰部分をまず展開し その結果得られたプログラムに畳み込み可能な構造が現れている場合に畳み込みを実行する.しかし そうでない場合には既に行なった展開を遡ってキャンセルするという手順上の冗長性がある.また変換手続きの記述も複雑で理論的な分析の対象としては不都合である.一方本講演で与える手法では 変換を適用するに先立ってプログラム中の変数の現れ方を調べ 確実に畳み込みが成功する再帰部分を特定する.続く変換ではその箇所のみ展開を実行すればよい.畳み込み可能性の判定には「強自由変数」とよぶ新概念を利用するが その定義はプログラムの構成に関する単純な帰納法で記述することができ 理論的な解析にも有用である. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | We present a way of transforming a program which calculates a primitive recursive function. It enables us to fuse a recursor Q into a program P automatically, by eliminating an intermediate data structure generated by P then consumed by Q Our transformation is based on the unfolding-folding procedure, but it is not the aim of this work to describe the procedure itself in a naive way. With the unfolding-folding procedure, one may think it redundant that he has to try unfolding a recursion even if he will never fold it again. So, we will show instead a better way of the transformation, by which one can predict by analyzing variables in a program whether he will success of fail in folding a recursion, and then can unfold them only in the successful cases. Another advantage of our method is the refined formulation of it. The transformation is defined by a simple induction on the construction of a program, then is adequate to theoretical analysis, while a naive formulation of the unfolding-folding procedure is so complicated that we can hardly analyze it. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AA11464814 | |||||||
書誌情報 |
情報処理学会論文誌プログラミング(PRO) 巻 40, 号 SIG07(PRO4), p. 96-96, 発行日 1999-08-15 |
|||||||
ISSN | ||||||||
収録物識別子タイプ | ISSN | |||||||
収録物識別子 | 1882-7802 | |||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |