Prolog : Recursion problem with a calculated end condition

Question

I'm trying to model a set of cog wheels in Prolog. And to query to find if two wheels are connected by a chain of others.

I have a simple recursion :

connected(X,Y) :-   
    engages(X,Y).

connected(X,Y) :-
    engages(X,Z),
    connected(Z,Y).

If I define engages in terms of a hard-wired predicate :

engages(X,Y) :- touches(X,Y).

and

touches(z1,z2).
touches(z2,z3).
touches(z3,z4).

Then this works.

A test of

connected(z1,z4).

produces true and

connected(z1,z5).

produces false.

However, if I replace my touches predicate with a calculation (that the sum of the two radii is roughly the distance between the two centres), then this search goes into what looks like an infinite recursion (stack overflow) when the answer should be false.

Why should this be, given that my "touches" calculation doesn't itself call the "connected" functor? Is it because a touches functor is going to try to match more atoms than the explicit predicates?

This, roughly, is my calculated touches (A and B are the wheels, ARAD and BRAD are their radii, D is distance and approx is an "approximately equals" function.

touches(A,B) :- 
    wheel(A,_,_,ARAD),
    wheel(B,_,_,BRAD),
    distance(A,B,D),
    approx(D,(ARAD+BRAD),2),
    A \== B.

Fred Foo Fred Foo · Accepted Answer · 2011-04-11T19:21:25

The infinite recursion occurs because the program doesn't check for cycles. Here's what might happen:

The program finds wheels A and B, that touch.
Given B, it looks for a wheel that touches. It finds A.
Goto 1.

You can prevent this from maintaining a "closed set" of wheels already considered in an extra argument to connected:

connected(X,Y) :-
    connected(X,Y,[]).
connected(X,Y,Closed) :-
    touches(X,Y),
    \+ memberchk(Y,Closed).
connected(X,Z,Closed) :-
    touches(X,Y),
    \+ memberchk(Y,Closed),
    connected(Y,Z,[Y|Closed]).

(Exercise for the reader: shorten this.)

Prolog : Recursion problem with a calculated end condition

1 Answers