Prolog - VERY short program enclosed - why is it not tail-recursive?

Author

VERY short program enclosed - why is it not tail-recursive?

Joey Dewille

2004-05-20, 8:31 pm

Hello group,

I making my first steps toward learning Prolog and wrote the following
program using various sources from the web and a bit of exploration.
Why is the stack overflown very, very quickly when I run the program in gnu prolog?
I thought that this program is tail-recursive and has no choicepoints?!
Thanks.
--Joey

Usage: at the prompt type genprime(3,3000000).
It blows up near 41000 (8MB stack).
If "N*N > P -> true" is replaced with "N*N =< P ->true" then it blows up near 465000.
How come results are correct in either case?

==== program ===================
not_divide(P, N) :- ( N * N > P -> true;
P mod N > 0,
N1 is N + 2, not_divide(P, N1)
).

prime(2) :- !.
prime(P) :- P mod 2 =:= 1, not_divide(P, 3).

genprime(L,U) :- L <= U,
(prime(L) -> write(L), nl, true; true ),
L1 is L + 2, genprime(L1, U).
=============================

Bart Demoen

2004-05-21, 4:31 am

Joey Dewille wrote:
> Hello group,
>
> I making my first steps toward learning Prolog and wrote the following
> program using various sources from the web and a bit of exploration.
> Why is the stack overflown very, very quickly when I run the program in gnu prolog?
> I thought that this program is tail-recursive and has no choicepoints?!

Tail-recursive is a property of a program; "has no choicepoints" depends on the
Prolog implementation - usually, at most the implementor of the Prolog system has enough
insight to know :-)

But one would indeed expect no overflows.

> Thanks.
> --Joey
>
> Usage: at the prompt type genprime(3,3000000).
> It blows up near 41000 (8MB stack).

Look at the message you got - it says:

Fatal Error: global stack overflow (size: 8193 Kb, environment variable used: GLOBALSZ)

That has nothing to do with tail-recursion or choice points.

Here is a non-tail-recursive predicate:

x :- x, p.

The query ?- x.

results in

Fatal Error: local stack overflow (size: 4096 Kb, environment variable used: LOCALSZ)

That's the message related to (the absence of) tail-recursion.

So why do you get the global stack overflow ...
You have consulted the file with your program. Consulting leads to code (internally in gprolog)
that is less optimized - it produces garbage and gprolog does not have a garbage collector.

If you compile the program first (gplc file.pl) and then execute the executable file,
it will run much longer (I dodn't get overflow for gen_prime(3,3000000).)

> If "N*N > P -> true" is replaced with "N*N =< P ->true" then it blows up near 465000.
> How come results are correct in either case?

???
In one case you get prime numbers, in the other case you get all odd numbers.

Cheers

Bart Demoen

Joey Dewille

2004-05-21, 11:31 pm

Bart,

thanks for the competent answer. Indeed your diagnosis was very accurate.
When I compiled that program with gplc under Linux, memory consumption was
mostly constant no matter how big the upper bound was.
I was disappointed, though, that Amzi! Prolog (ver7.0.20) blew up when I set the upper bound
quite high (300 million) - again I ran the code as compiled project and watched
garbage collection take place from time to time, ultimately though it blew up and
I had no choice but to terminate the whole IDE inside which the project ran.
Efficiency is very important in my evaluation of Prolog tools, and there is no excuse
to grow stacks too large or overflow them if it is avoidable.
--Joey

"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message news:1085123478.41404@seven.kulnet.kuleuven.ac.be...
> Joey Dewille wrote:
>
> Tail-recursive is a property of a program; "has no choicepoints" depends on the
> Prolog implementation - usually, at most the implementor of the Prolog system has enough
> insight to know :-)
>
> But one would indeed expect no overflows.
>
>
>
>
> Look at the message you got - it says:
>
> Fatal Error: global stack overflow (size: 8193 Kb, environment variable used: GLOBALSZ)
>
> That has nothing to do with tail-recursion or choice points.
>
> Here is a non-tail-recursive predicate:
>
> x :- x, p.
>
> The query ?- x.
>
> results in
>
> Fatal Error: local stack overflow (size: 4096 Kb, environment variable used: LOCALSZ)
>
> That's the message related to (the absence of) tail-recursion.
>
>
> So why do you get the global stack overflow ...
> You have consulted the file with your program. Consulting leads to code (internally in gprolog)
> that is less optimized - it produces garbage and gprolog does not have a garbage collector.
>
> If you compile the program first (gplc file.pl) and then execute the executable file,
> it will run much longer (I dodn't get overflow for gen_prime(3,3000000).)
>
>
>
>
> ???
> In one case you get prime numbers, in the other case you get all odd numbers.
>
> Cheers
>
> Bart Demoen

Sponsored Links