Subject: Re: [SWIPL] Memoization

From: "Richard A. O'Keefe" <[email-masked]>
Date: Tue, 8 May 2001 13:19:41 +1200 (NZST)

"Douglas R. Miles" <[email-masked]> wrote:
	I would like to see how to impliment a meta interpretor in SWI
	that can [handle a left-recursive rule].
	
See "The Craft of Prolog" where I describe how to do iterative deepening.

The example

	|?- path(1,5,X).
	
	path(X,Y) :- path(X,Z), edge(Z,Y).
	path(X,Y) :- edge(X,Y).
	
can't work even then because there is no path/3 predicate.

id(Goal) :-
    length(Bound, _),
    id(Goal, Bound, _).

id(Goal, Bound, Bound) :-
    fact(Goal).
id(Goal, [_|Bound0], Bound) :-
    rule(Goal, Body),
    id_body(Body, Bound0, Bound).

id_body([], Bound, Bound).
id_body([Goal|Goals], Bound0, Bound) :-
    id(Goal, Bound0, Bound1),
    id_body(Goals, Bound1, Bound).

fact(edge(1,2)).
fact(edge(2,2)).
fact(edge(2,4)).
fact(edge(2,3)).
fact(edge(3,5)).

rule(path(X,Y), [path(X,Z),edge(Z,Y)]).
rule(path(X,Y), [edge(X,Y)]).

With this code, the query id(path(1,5)) succeeds (at depth 3) in
SWI Prolog and Quintus Prolog.