I'm given the following program:
edge(a,b).
edge(b,c).
edge(a,d).
path(N,M):- path(N,New),edge(New,M).
path(N,M):- edge(N,M).
And asked if when applying a proof tree algorithm to the following query:
?- path(a,X).
the proof tree is an infinite success tree, or an infinite failure tree?
Now as I see it, during the building of the tree, you get stuck in applying rule 1 of path over and over again, creating an infinite tree and never getting to rule 2 of path..
thus creating an infinite failure tree. but the solution I have says it is an infinite success tree, my question is: am I right or is my professor right? :]
I would call that an infinite loop. Look at the trace:
?- trace, path(a,X).
Call: (7) path(a, _G394) ?
Call: (8) path(a, _G511) ?
Call: (9) path(a, _G511) ?
Call: (10) path(a, _G511) ?
...
Call: (147) path(a, _G511) ?
Call: (148) path(a, _G511) ?
...
ERROR: Out of local stack
I'm not familiar with these terms, but I might be able to wing it. No solutions are produced, so it would be hard for me to argue that this is an infinite success tree. Even given infinite time and space it would never produce a successful solution. At the same time, failure in the Prolog sense is immediate, and that isn't happening either. I'm not sure such a thing as an infinite failure tree could exist, unless you'd call that something that generates an infinite number of choice points, all of which fail. But there aren't any failures here. It would be more honest to just call this what it really is: an infinite loop. Such things exist outside the realm of success and failure. This is why in Haskell, ⊥ belongs to every type. Maybe in that sense you're both right.