tail recursion optimization in SWI Prolog

Hi,

I have a question about tail recursion.

I have some predicates that use tail recursion and I expect them to
iterate for many thousands of iterations.
I am getting stack overlfow errors, which I can mitigate to some extent
by increasing the available stack size.
However isnt it right that tail recursive procedures should use a fixed
amount of the stack?
Is there anyway to make SWI Prolog perform some optimization on tail
recursion. I dont mind if the optimized form is a compiled program.


Any ideas, pointers would be really helpful.
Thank you!


bow
-----

bow wrote:

> However isnt it right that tail recursive procedures should use a fixed
> amount of the stack?

If there is no non-determinism (or undetected determinism).

Simple tail recursive predicates like

a :- a.

for query ?- a.

or

a(0).
a(X) :- Y is X + 1, a(Y).

for ?- a(1).

seem not to run out of stack in SWI-Prolog, so perhaps you should show
us your program (and query) ...

Cheers

Bart Demoen

Well here is a program that I ran in SWI prolog.
The output is shown at the bottom.
It can be seen that the Stack usage values increase over time.
I took that to mean that the stack is consumed, even though the program
uses tail iteration.
Does that make the question clearer?



out(N) :-
write('-----------------------------------------------------'),nl,
statistics,
write('-----------------------------------------------------'),nl,
rec(N),
statistics,
write('-----------------------------------------------------'),nl.


rec(0).
rec(N) :-
NewN is N-1,
rec(NewN).



Output from the program
-------------------------------------
5 ?- out(1000000).
-----------------------------------------------------
0.16 seconds cpu time for 228,966 inferences
2,024 atoms, 1,223 functors, 1,466 predicates, 23 modules, 29,800
VM-codes

Limit    Allocated       In use
Heap         :                                 416,220 Bytes
Local  stack :     2,097,152       12,288          764 Bytes
Global stack :     4,096,000       20,480        1,156 Bytes
Trail  stack :     4,194,304       12,288          412 Bytes

5 garbage collections gained 1,392,100 bytes in 0.00 seconds.
1 threads, 0 finished threads used 0.00 seconds.
-----------------------------------------------------
0.59 seconds cpu time for 2,229,012 inferences
2,024 atoms, 1,223 functors, 1,466 predicates, 23 modules, 29,800
VM-codes

Limit    Allocated       In use
Heap         :                                 416,220 Bytes
Local  stack :     2,097,152       12,288          828 Bytes
Global stack :     4,096,000      102,400       99,200 Bytes
Trail  stack :     4,194,304       36,864       33,088 Bytes

62 garbage collections gained 17,261,800 bytes in 0.05 seconds.
1 threads, 0 finished threads used 0.00 seconds.
-----------------------------------------------------

bow a écrit :
> Well here is a program that I ran in SWI prolog.
> The output is shown at the bottom.
> It can be seen that the Stack usage values increase over time.
> I took that to mean that the stack is consumed, even though the program
> uses tail iteration.
> Does that make the question clearer?
>
>
Are you refering to some kind of memory leak ?
here's the output in my swi home version ( 5.2.13, ouch an old one :) )


?- out(1000000).
-----------------------------------------------------
0.00 seconds cpu time for 2,462 inferences
1,768 atoms, 1,080 functors, 1,290 predicates, 20 modules, 26,220 VM-codes

Limit    Allocated       In use
Heap         :                                 379,248 Bytes
Local  stack :     2,048,000       16,384          832 Bytes
Global stack :     4,096,000       16,384          756 Bytes
Trail  stack :     4,096,000       16,384          292 Bytes

1 threads, 0 finished threads used 0.00 seconds.
-----------------------------------------------------
1.96 seconds cpu time for 2,002,505 inferences
1,768 atoms, 1,080 functors, 1,290 predicates, 20 modules, 26,220 VM-codes

Limit    Allocated       In use
Heap         :                                 379,248 Bytes
Local  stack :     2,048,000       16,384          896 Bytes
Global stack :     4,096,000       73,728       70,468 Bytes
Trail  stack :     4,096,000       24,576       23,516 Bytes



?- out(10000000).
-----------------------------------------------------
1.98 seconds cpu time for 2,002,736 inferences
1,770 atoms, 1,080 functors, 1,290 predicates, 20 modules, 26,220 VM-codes

Limit    Allocated       In use
Heap         :                                 379,368 Bytes
Local  stack :     2,048,000       16,384          832 Bytes
Global stack :     4,096,000       40,960          744 Bytes
Trail  stack :     4,096,000       24,576          276 Bytes

54 garbage collections gained 15,907,420 bytes in 0.26 seconds.
1 threads, 0 finished threads used 0.00 seconds.
-----------------------------------------------------
21.42 seconds cpu time for 22,002,782 inferences
1,770 atoms, 1,080 functors, 1,290 predicates, 20 modules, 26,220 VM-codes

Limit    Allocated       In use
Heap         :                                 379,368 Bytes
Local  stack :     2,048,000       16,384          896 Bytes
Global stack :     4,096,000      172,032      171,364 Bytes
Trail  stack :     4,096,000       57,344       57,148 Bytes

596 garbage collections gained 175,680,348 bytes in 2.63 seconds.
1 threads, 0 finished threads used 0.00 seconds.

and for out(10000000).

but once I ran statistics after the goal execution, I got :

statistics.
21.45 seconds cpu time for 22,011,294 inferences
2,356 atoms, 1,531 functors, 1,294 predicates, 20 modules, 30,460 VM-codes

Limit    Allocated       In use
Heap         :                                 469,764 Bytes
Local  stack :     2,048,000       16,384          796 Bytes
Global stack :     4,096,000       40,960          740 Bytes
Trail  stack :     4,096,000       24,576          264 Bytes

596 garbage collections gained 175,680,348 bytes in 2.63 seconds.
1 threads, 0 finished threads used 0.00 seconds.

a pretty normal situation no ?


I'm not sur to understand the problem : isn't it normal to swi to keep
all the choice points in the stack if a predicate is not over ?

you can see from your runs that the Global stack usage increases, the
bigger the value of N in the call "out(N)".

What I know is that when you program in other languages and use a tail
recursive definition, the compiler can change it into an iterative
form.
The amount of memory used in that case is constant and does not depend
on how many iterations.
So my question is, does SWI prolog do this optimization? or am I
missing something?


bow
------

On 2005-02-25, bow <bharat_purohit@yahoo.com> wrote:
> you can see from your runs that the Global stack usage increases, the
> bigger the value of N in the call "out(N)".
>
> What I know is that when you program in other languages and use a tail
> recursive definition, the compiler can change it into an iterative
> form.
> The amount of memory used in that case is constant and does not depend
> on how many iterations.
> So my question is, does SWI prolog do this optimization? or am I
> missing something?

Yes, but last-call optimization only affects the local (environment-)
stack.  The trouble is that A is B + 1 is by default executed totally
naive: create a term B+1 and evaluate it.  This creates global stack,
but GC will nicely deal with it.  If you enable optimisation using
"pl -O" or :- set_prolog_flag(optimise, true). arithmetic will be
translated to a stack engine and this goes away.  The downsite is
that you cannot trace it.

Please note that if you enable debugging (?- debug. or ?- trace.),
last call optimiation is disabled and the system will indeed run out
of stack.

Cheers --- Jan