Prolog : 간단한 사실에 대한 전 이성 검사

Question

내 의도는 Prolog에서 단순성 (transmitivity)에 대한 간단한 예제를 구현하는 것이 었습니다.

이

내 사실이다 : 나는 확인하려면이 조건을 서면으로 작성했습니다

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). 

여부 A 신탁 사실 C을 C 및 A 신탁이 B 트러스트하는 B이있을 때마다 :

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

예, 프롤로그가 로컬 스택을 빠르게 플러딩합니다.

 
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
• 등