prologにおける解の探索方法

Question

言語

prolog

知りたいこと

解の探索方法

内容

X+Y=1+(2+3)+4としたときに、
X=1+(2+3), Y=4
のみが解として帰ってくるのはなぜでしょうか？調べてみると、最初に見つかった答えのみを返すかららしいですが、ではなぜX=1, Y=(2+3)+4などではなく、X=1+(2+3), Y=4が最初の解として見つかるのでしょうか？

また、X+Y=((1+2)+3)+4+(5+6)とした場合は、
X = 1+2+3+4,
Y = 5+6 ? ;
となりました。先ほどの問題と比べても、括弧が省略される基準が分かりません...

Comments

[ikedas]

実際に実行したPrologのプログラムを、実行した通りにすべて書いてください。
また、プログラムは下記の説明の「コードを入力」のやりかたで書いてください。
https://teratail.com/help#about-markdown

[xebme]

わたしの乏しい知識で答えると中置記法は前置記法に置き換えられます。
+(X,Y) = +(+(1,+(2,3)),4).

Answer 1

中置記法を前置記法に置き換える

prologの中置記法を前置記法に置き換えると次と同じです。なぜそうなるのか。+は左結合だから。scryer-prologで実行しましたがswi-prologでも同じ結果になります。

?- =(+(X,Y),+(+(1,+(2,3)),4)).
   X = 1+(2+3), Y = 4.
?- =(+(X,Y),+(+(+(+(1,2),3),4),+(5,6))).
   X = 1+2+3+4, Y = 5+6.

y+xの優先度と括弧

Predicate op/3に記載されていました。

op(500,yfx,[+, -, /\, \/, xor])

• 500は優先度。数字が小さいほうが優先度が高いと読めます。
• タイプyfxのfは演算子の位置です。+の右側のxの優先度は+より低い。+の左側の優先度は+と同じか低い。右側の優先度が低いので括弧をつけているのだと思います。
• 演算子のリスト

演算子はモジュールにローカル。変えることができると記述があります。

Comments

[xebme]

質問は解の探索法ですが、前置形に変形するとユニフィケーション自体は単純です。
むしろ、式の解釈や演算子の優先順位によって質問の現象が起きていると考えられます。

[xebme]

+を演算子ではなくただの文字と見なせば次のような結果を予測できるでしょう。
?- append(X,Y,[1,2,3,4,5]).
X = [], Y = [1,2,3,4,5]
; X = [1], Y = [2,3,4,5]
; X = [1,2], Y = [3,4,5]
; X = [1,2,3], Y = [4,5]
; X = [1,2,3,4], Y = [5]
; X = [1,2,3,4,5], Y = [].

しかしprologは+演算子を解析して木構造を作るので、X,Yのマッチングは１度だけになると考えられます。
『Prologへの入門』 I.Bratko 近代科学社 3.3. オペレータ記法　に日本語の解説があります。

Answer 2

Prologに知識は大昔止まりですが、最初の解だけを表示するか、全部の解を求めて表示するかは処理系依存な気がします（ちょっと自信ないですが）。

一般的な二項演算子は左結合（a+b+cは(a+b)+cと同じ）なので、1+(2+3)+4は(1+(2+3))+4であり、この括弧を補うことでX+Yの形とマッチングして、XとYがそれぞれの値になります。

また、X+Y=((1+2)+3)+4+(5+6)とした場合は、

上に書いたとおり、((1+2)+3)+4+(5+6)は(((1+2)+3)+4)+(5+6)で、同じくXが(((1+2)+3)+4)で、Yが(5+6)ですが、内部表現の木構造は1+2+3+4と(((1+2)+3)+4)は同じなので、内部表現を表示するときに括弧が表示されなかったのでしょう。

1つ目の解のX=1+(2+3)については、式を表す木構造が1+2+3と1+(2+3)は異なるので括弧が明記されたのだと思います。

数学の足し算だと順不同(※注)ですが、パターンマッチングや表示の際に、演算子の持つ数学的な意味まで解釈してマッチングしているわけじゃ無いので、任意の左結合の二項演算子について同じ処理になるかと思います。
Prologで右結合の二項演算子（a★b★cがa★(b★c)と解釈されるもの）がどう扱えるのかはちょっとわかりません。

※注：有限桁の浮動小数点演算だと足し算の順番で誤差の発生が異なりますが、今回の本筋では無いので省略。