Preventing cycles in Prolog

Help!
1

Hello,

In my program, it is often a case that reasoners call each other to establish a goal. The crude way I approach this is using guards to stop a goal or subgoal from calling itself. For example:

The following code:

% Cyclic code
reasoner_1(Goal):- reasoner_2(Goal).
reasoner_2(Goal):- reasoner_1(Goal).

is turned into this code:

% I use this as some sort of guard
:- dynamic pending/1.

reasoner_1(Goal):- 
	% make sure this goal is not being evaluated by reasoner_1/1 earlier in the search tree
	\+ pending(reasoner_1(Goal)), 
	% if not, it is now, so mark it as "pending proof"
	assert(pending(reasoner_1(Goal))),
	(
		% either prove using reasoner_2/1 and release the guard
		(
			reasoner_2(Goal), 
			retract(pending(reasoner_1(Goal)))
		);
		% or in case reasoner_2/1 failed, release the guard and fail
		(
			(pending(reasoner_1(Goal)) -> retract(pending(reasoner_1(Goal))); true),
			fail
		)
	).
	
reasoner_2(Goal):- 
	% make sure this goal is not being evaluated by reasoner_2/1 earlier in the search tree
	\+ pending(reasoner_2(Goal)), 
	% if not, it is now, so mark it as "pending proof"
	assert(pending(reasoner_2(Goal))),
	(
		% either prove using reasoner_1/1 and release the guard
		(
			reasoner_1(Goal), 
			retract(pending(reasoner_2(Goal)))
		);
		% or in case reasoner_1/1 failed, release the guard and fail
		(
			(pending(reasoner_2(Goal)) -> retract(pending(reasoner_2(Goal))); true),
			fail
		)	
	).

Is there a more elegant – perhaps built-in – way to stop cyclicity without using these guards?

Many thanks.

2

Tabling? Simple example:

:- table reasoner_1/1, reasoner_2/1.

reasoner_1(Goal):- reasoner_2(Goal).
reasoner_1(a).
	
reasoner_2(Goal):- reasoner_1(Goal).
reasoner_2(b).

Sample calls:

?- reasoner_1(X).
X = b ;
X = a.

?- reasoner_2(Goal).
Goal = b ;
Goal = a.
2 Likes
3

Wow, this is neater than I thought!
This is the second time tabling is suggested to me, and each time it seems to be able to solve one of my major pains :slight_smile:
Thanks a lot.

4

Thanks to Jan for his hard work implementing tabling :slightly_smiling_face:

5 Likes