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

From: Joey Dewille (joey1968_at_fastmail.co.uk)
Date: 05/21/04

  • Next message: Bart Demoen: "Re: VERY short program enclosed - why is it not tail-recursive?" 
    Date: Thu, 20 May 2004 19:06:50 -0400

    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).
    =============================

  • Next message: Bart Demoen: "Re: VERY short program enclosed - why is it not tail-recursive?"