Hacker News Reader

Comment by sp332 | Hacker News Reader

Nope, in vanilla Prolog you'd have to type "X(A,C) :- X(A,B), X(B,C)." for every single X you want to be transitive.

In formal logic, "A if B" is just syntactic sugar for "(B && A) || (!B)" or in English: when B is true, A is true. (But when B is false, A could be either true or false.) So you could rewrite your expression as (edit: fixed):

  transitive(X, A, B, C) :- (X(A,B), X(B,C), X(A,C)); not(X(A,B), X(B,C)).

View on HN

Prolog also has syntax for if-then, so

    x(A, C), x(A, B), x(B, C); not(x(A, C)).

can essentially be re-written as

    x(A, C) -> x(A, B), x(B, C); true.

(This saves testing `x(A, C)` twice. Also, `->` implicitly cuts, presenting backtracking over `x(A, C)`; but that shouldn't matter here.) However, this set-up mistakenly has `x(A, C)` as the antecedent; I think you actually want it as the consequent.

though be careful how you do this -- it's easy to end up with a divergent program, as prolog tries to:

* prove X(A,B)

* realizes that it can prove this if it can prove transitive(X, A, B, C), and then prove X(B,A)

* realizes that it can prove this if it can prove transitive(X, B, A, C), and then prove X(A,B)

* ...

Such behavior is easily avoided with tabling.

There are a couple of ways around this -- all of which fall under "be careful". :-)

Reply on news.ycombinator.com