非決定性と双方向性

ウィキペディア小見出し辞書

非決定性と双方向性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/12 02:49 UTC 版)

「Prolog」の記事における「非決定性と双方向性」の解説

関数型言語等、他のプログラミング言語と比較しての Prolog の特長は、上記、一階述語論理に基づくこと、単一化、データベース言語的性格の他に、非決定性と双方向性が挙げられる。 非決定性は、解が唯一とは限らない場合、処理系側から見てひとつの解に決定できない場合、外部からの選択の余地を与える。そういうことが当然可能なこととして述語は定義されていく。インタプリタトップではなく、導出を繰り返すプログラム内部にあっては、処理系側とした所を述語と置き換えて考えると、非決定性の述語の解を決定するのは、前方または後方に連接する質問（副目標）である。前方の副目標群から引数経由で与えられる情報によって副目標は一つの解を作り出すが、この解が真であるとするのは最終的に後方に連接する副目標である。この後方に連接した副目標が全て真となった場合に限り副目標は真となる。後方に連接する副目標のどれかが真にならなかった場合は、それが存在すればであるが別解を用意しなくてはならない。ここでも非決定性の述語、ここでは副目標から見ての解の決定権は、外部にあるということになる。 非決定性は導出の過程、取り分けバックトラックアルゴリズムと一体化しており、Prolog プログラムの制御の根幹のひとつである。ただ、非決定性述語実行時に見られる論理変数の 束縛→解放→再束縛という遷移、すなわち一度束縛されたものが別のものに再度束縛されるということを好ましくないとする見方もある。 双方向性は、述語が実行された場合の返り値は真または偽だけであり、その代わりとして引数内の変数で値の授受を終始するのだが、このとき、入力として使われた変数が出力に、出力として使われていた変数が入力として使うことのできる述語となることがある。この性質を双方向性という。多くの場合、双方向性を持つ述語はそれ自体多義性を持つ。例えば append という3引数の述語は第一引数と第二引数に具体的なリストが来て呼ばれた時は、リストを結合する意味でよいが、第三引数がリストで第一引数と第二引数が変数の状態で呼ばれた場合その意味は、リストを分解する、がふさわしい。既に存在するリストを、それが結合されて存在したものと考え、それではどのように結合されていったか、あるいは、どのような組み合わせで結合されていったのかを、示していると解釈できる。 このような、双方向性は Prolog の述語自らがリバースエンジニアリング的開示能力を持ち、それを示していると捉えることができる。この性質は、Prologを含む論理型プログラム言語の持つ際立った特徴であり、プログラム作成時はもちろん、テスト、デバッグなどの検証の各段階でプログラムコードに対する見通しを向上させる。