Implicitな定義からの変換によるPrologプログラムの導出
スポンサーリンク
概要
- 論文の詳細を見る
効率は考えずに判り易さを最優先に書いた宣言的プログラムから出発して(判りにくいかも知れないが)効率的なプログラムを作り出すというアプローチの基本的手法としてunfold/fold技法が知られている。この変換のヒューリスティクスの重要なものの1つに、ゴールの挿入がある。導き出されたclauseを最初に与えたclauseでたたみ込めるよう故意にあるゴールを挿入するというもので文献[1][2]ではこれを"forced folding"として紹介している。また[3]では,"(folding driven) goal insertion"と呼び図1のようなsortプログラムを扱っている。ゴールの挿入が行われる直前のclauseについて見てみよう。この本体中のinsert-randomly(X,N,M),ordered(M)が成り立つとき常にordered(N)も成り立つ。もし、本体中にperm(L,N),ordered(N)が出そろっているとこれらはsortの最初のclauseでたたみ込めて再帰的なclauseが出来上がる。このたたみ込みを行うために"ordered(N)"を挿入している。しかしながら一般には"ゴールの挿入"をunfold/foldルールと合わせると、最小Herbrandモデルの意味での"同値性"が失われるかも知れない。またそれを保証するには少し面倒な余分な処理が必要になる[3]。本稿では、この操作を自然に行う為のImplicitな定義によって一般化されたPrologプログラムの変換合成について述べる。
- 一般社団法人情報処理学会の論文
- 1986-10-01