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