[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Iteratively calling Prolog from C

From: Lindsey Spratt
Subject: Re: Iteratively calling Prolog from C
Date: Wed, 16 Jul 2003 10:02:57 -0500

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]