Search code examples
prologfailure-slice

Prolog - why does the following code generate the solution X=root forever?

black(root). 
black(v1). 
black(v3). 
black(v4). 

edge(root,root).
edge(v1,root). 
edge(v2,v1). 
edge(v3,v1). 
edge(v4,v3). 
edge(v5,v2). 
edge(v5,v4). 
edge(v6,v5). 

foo(root). 
foo(X) :- edge(X,Y), black(Y), foo(Y).

Then I type foo(X) and only get X=root.

I really can't figure out why. We get the first root because of the first part of foo. Then we are supposed to go the the second part, we then proceed to find the edge (root,root). black(root) returns true and so does foo(root) so we get another root solution. Why don't we then go to the edge (v1,root)? What am I missing?

Solution

  • Because looking for the 3rd solution starts with retrying foo(Y) when Y=root, and you've already established there are at least 2 distinct ways to prove foo(root). (But, as @WillemVanOnsem points out, it is much worse than that.)