Re: Iteratively calling Prolog from C

[Lindsey Spratt]

On Wednesday, July 2, 2003, at 03:30  AM, Daniele Peri wrote:
> I made some tests about iteratively calling prolog from a foreign C
> function. The idea is to improve either performance or memory footprint
> of very deep recursion calls. This is also needed as gprolog doesn't
> seem to optimize tail recursion. I didn't delve into gprolog source but
> I have not find any reference to such optimization in the 
> documentation.

gprolog *does* "optimize tail recursion". It uses the Last Call 
Optimization (LCO). I looked at the generated WAM code, and gprolog 
appears to follow the LCO as described by Hassan Aït-Kaci in "Warren's 
Abstract Machine: A Tutorial Reconstruction" (MIT Press, 1991). 
Specifically, the "call;deallocate" at the end of the body is replaced 
by "deallocate;execute". This can work well for a tail recursive 
predicate, leading to constant stack size. Unfortunately, there is 
nothing to optimize the use of heap storage, so a simple recursive 
predicate may exhaust the heap. For instance, consider the following 
predicate to calculate the sum of the series of integers from 1 to N 
(the hard way):

sum(N, S) :-
        sum(N, 1.0, S).


sum(0.0, N, N) :- !.

sum(N, J, S) :-
        N > 0,
        K is N - 1,
        L is N + J,
        sum(K, L, S).


The two structures, 'N - 1' and 'N + J', are allocated on the heap on 
every recursive invocation and never freed (until the query processing 
finishes). I think this is an opportunity for garbage collection. 
Daniel Diaz has mentioned a desire to implement garbage collection: 
perhaps this is the sort of thing he has in mind.

Lindsey Spratt
http://homepage.mac.com/lspratt