Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wasatch!cs.utexas.edu!uunet!mcvax!ukc!icdoc!cdsm
From: cdsm@doc.ic.ac.uk (Chris Moss)
Newsgroups: comp.lang.prolog
Subject: Re: Higher Order Extensions
Message-ID: <799@gould.doc.ic.ac.uk>
Date: 9 May 89 13:25:15 GMT
References: <11500013@hpldola.HP.COM> <783@gould.doc.ic.ac.uk> <10145@burdvax.PRC.Unisys.COM>
Reply-To: cdsm@doc.ic.ac.uk (Chris Moss)
Organization: Dept. of Computing, Imperial College, London, UK.
Lines: 27

In article <10145@burdvax.PRC.Unisys.COM> lang@macbeth.PRC.Unisys.COM (Francois-Michel Lang) writes:
>I know how to find the set of all solutions in O(N^2) time
>without using assert/retract (a la findall),
>but unless we have somewhat different notions of "pure Prolog",
>I can't do it completely purely.
>
>How is the pure version of such a predicate written?

There are 2 problems. 
1. "how do I write a version of 'call' in pure Prolog?"
Answer: for all predicates in your program supply a clause of the form:
   call(foo(A,B)) :- foo(A,B).

This could easily be done by a preprocessor. 
Call does not, by itself, add any metalevel power to Prolog. Only convenience.

2. How do I recursively call a goal with uninstantiated variables?
Answer: Make a copy of the term each time with new variables.
This can be done with freeze and melt (as in Sterling and Shapiro).
It requires something akin to "univ" (or alternatively functor and arg) 
which requires a clause (similar to "call") for each function symbol 
in the program.

These are clearly inconvenient, but they CAN be done in pure Prolog.
They are more "structural" than "metalevel" facilities.

Chris Moss.