Beginner Prolog Stack Overflow

Question

I am working on my very first Prolog assignment, and on recursive problems, I cannot seem to stop overflowing the stack. It's like an addiction; I don't know how to stop.

Let me give you an example. I want to create a function that determines if an object, Y, is a part of another object, X. Here is the database I am working with:

% Parts Database
has(bicycle,wheel,2).
has(bicycle,handlebar,1).
has(bicycle,brake,2).
has(wheel,hub,1).
has(wheel,spoke,32).
has(bicycle,frame,1).

has(car,steering_wheel,1).
has(car,stereo,1).
has(car,tires,4).

From here, I want to write a function partof(X,Y) that returns true if Y is a part of X. This is what I currently have:

% Determines if Y is a part of X
partof(X,Y) :-
    has(X,Y,_).
partof(X,Y) :-
    partof(X,Z),
    partof(Z,Y).

This works for all true queries, but overflows the stack instead of returning false. For example:

?- partof(wheel, spoke).
true ;
ERROR: Out of local stack

?- partof(bicycle, spoke).
true ;
ERROR: Out of local stack

?- partof(wheel, X).
X = hub ;
X = spoke ;
ERROR: Out of local stack

I know you are all thinking to yourselves, "This dumb idiot, doesn't know what a base case is. Doesn't know how to pull out of recursion." Well, I don't blame you. I feel dumb. Some patient guidance would be very helpful, though. Thanks in advance!

To elaborate on @CapelliC's comment, `partof(X,Y) :- partof(X,Z)` is going to lead to unbounded recursion, because whenever Prolog goes to figure out `partof/2`, it has to first figure out `partof/2`. It's a classic infinite loop. Why would it ever stop? Chris's improvement forces Prolog to do something before it loops, so it has the opportunity to fail and stop. — Daniel Lyons, Nov 15 '17 at 18:31

false · Answer 1 · 2022-08-11T17:20:53.447

Recursion in Prolog kind-of works as in other programming languages, but it is much more complex in Prolog since there are two independent control flows intertwined within the same run. In traditional imperative languages, either recursion works (and yields a result) or doesn't and thus loops thereby maybe overflowing some stack.

But in Prolog, we may get many interesting answers first, and only after a while we are stuck in an infinite loop. You had quite some luck with your query, you found loops immediately after the first solution/answer. Imagine you would have taken the following query:

?- partof(X, Y).
   X = bicycle, Y = wheel
;  X = bicycle, Y = handlebar
;  X = bicycle, Y = brake
;  X = wheel, Y = hub
;  X = wheel, Y = spoke
;  X = bicycle, Y = frame
;  X = car, Y = steering_wheel
;  X = car, Y = stereo
;  X = car, Y = tires
;  X = bicycle, Y = hub
;  X = bicycle, Y = spoke
;  loops. % ERROR: Out of local stack

Note that the solutions are not really interesting to us. We were only after this last message. How many times shall we hit space until we say that a query terminates? Fortunately, there is a cheaper way out. We simply add false (a condition that is never true) as an additional goal. Clearly, the query must never have a solution. The only interesting thing that remains is whether or not the query terminates:

?- partof(X, Y), false.
   loops. % ERROR: Out of local stack

This trick can be extended to your whole program¹. Simply add false where you like. The remaining program called a failure slice shares still a lot with your original one: It needs less (or equal) many inferences to execute. Thus, if the failure slice loops, also the original program loops. Here is the minimal looping failure slice for your program:

partof(X,Y) :- false,
    has(X,Y,_).
partof(X,Y) :-
    partof(X,Z), false,
    partof(Z,Y).

Note that has/3 has been completely eliminated. In other words, modifying has/3 no matter how will not stop this loop! Never! You need to modify something in the visible part first. There is not much left!

Experienced Prolog programmers see such problems immediately. With the help of a failure-slice you can learn to identify these parts for yourself. And, trust me, for very complex programs, it is very useful to always have the option to check if your intuition is right or not.

And here is another way to define transitive closure using closure/3 and library(lambda):

partof(X, Y) :-
   closure(\A^B^has(A, B,_), X, Y).

^{1 actually, this only works for pure monotonic programs}

Beginner Prolog Stack Overflow

1 Answers1