Prolog：単純な事実のための推移性を確認してください

Question

私の意図は、Prologにおける推移性の簡単な例（自分のためだけ）を実装することでした。

これらは私の事実です：

trust_direct(p1, p2). 
trust_direct(p1, p3). 
trust_direct(p2, p4). 
trust_direct(p2, p5). 
trust_direct(p5, p6). 
trust_direct(p6, p7). 
trust_direct(p7, p8). 
trust_direct(p100, p200). 

私はCとA信託このB信頼Bがあるたびに真である、A信託Cかどうかを確認するために、この述語を書いた：

trusts(A, B) :- 
    trust_direct(A, B). 

trusts(A, C) :- 
    trusts(A, B), 
    trusts(B, C). 

は、

述語は、たとえばtrusts(p1, p2)またはtrusts(p1, p5)の場合はtrueを返しますが、trusts(p5, p6)は既にERROR: Out of local stackを返します。

Prologはこれをすばやくスタックにフラッディングしますか？

trusts私の考え/実装は悪い/無駄なシステムメモリですか？

Answer 1

はい、Prologはローカルスタックをすぐにフラッディングしています。これを確認するには

、それはに足りるだけ次のプログラムの断片を考えてみます。

 
trusts(A, C) :- 
     trusts(A, B), 
     false, 
     trusts(B, C). 

。これはfailure-sliceと呼ばれる：false/0後のすべてがを を無視することができるように、私は、false/0を挿入しました。私はストライクアウトテキストで無視できる部分を示します。これは、スニペットは、実際と同等であることを意味し

：今

 
trusts(A, C) :- 
     trusts(A, B), 
     false. 

、上記のスニペットのいずれかで、私たちはすぐに取得する：

 
?- trusts(p5, p6). 
ERROR: Out of local stack 

あなたは、この問題を取り除くために残りのフラグメントを変更する必要があります。このため、そのような断片は、の説明となる。

 
trusts(A, B) :- 
     trust_direct(A, B). 
trusts(A, C) :- 
     trust_direct(A, B), 
     trusts(B, C). 

サンプルクエリ：予想通りこれが機能するようになりました

 
?- trusts(p5, p6). 
true ; 
false. 

はたとえば、以下のバージョンを検討してください。それはあなたが投稿したバージョンと宣言相当し、より良い終端のプロパティがあります。

 
?- trusts(X, Y), false. 
false. 

これは、プログラムが今普遍を終了することを示しています。

代替ソリューションは、以下のとおりです。

• は
• transitive closure
• など