Prolog - Tail recursion

Author

Tail recursion

Daniel Kraft

2007-09-04, 7:09 pm

Hi all,

I use GNU-Prolog and was wondering while I get stack overflows even if
my recursive calls (should) be tail-recursive and thus transformed into
iterations. My code looks as follows:

loop1(N, N) :- !.
loop1(I, N) :-
II is I+1,
loop1(II, N).
loop1(N) :-
loop1(0, N).

loop2(N) :-
\+ (for(I, 0, N), fail).

loop1/1 overflows with a large enough argument (and is significantly
slower), while loop2/1 does not overflow for the same magnitude and runs
faster. for/3 is a GNU-Prolog predicate which unifies I with the
integers from 0 to N on backtracking, thus doing "real" iteration,
probably similar to what repeat/0 does.

Of course, this might be something specific to GNU-Prolog; but I believe
it should be able to resolve proper tail recursion to iteration, and
therefore I suspect it might have something to do with my test-code. Is
this really a proper case of tail-recursion (but even placing a cut in
front of the recursive loop1/1 call does not change the behaviour)?

What would be the "best" way to, for instance, generate a sequence of
integers with standards-compliant Prolog, which does not (AFAIK) include
for/3? (Or better: Is there something which performs better than my code
given)?

Many thanks in advance,
Daniel

--
Got two Dear-Daniel-Instant Messages
by MSN, associate ICQ with stress--so
please use good, old E-MAIL!

Bart Demoen

2007-09-04, 7:09 pm

Daniel Kraft wrote:
> Hi all,
>
> I use GNU-Prolog and was wondering while I get stack overflows even if
> my recursive calls (should) be tail-recursive and thus transformed into
> iterations. My code looks as follows:
>
> loop1(N, N) :- !.
> loop1(I, N) :-
> II is I+1,
> loop1(II, N).
> loop1(N) :-
> loop1(0, N).
>
> loop2(N) :-
> \+ (for(I, 0, N), fail).
>
> loop1/1 overflows with a large enough argument (and is significantly
> slower), while loop2/1 does not overflow for the same magnitude and runs
> faster. for/3 is a GNU-Prolog predicate which unifies I with the
> integers from 0 to N on backtracking, thus doing "real" iteration,
> probably similar to what repeat/0 does.
>
> Of course, this might be something specific to GNU-Prolog; but I believe
> it should be able to resolve proper tail recursion to iteration, and
> therefore I suspect it might have something to do with my test-code. Is
> this really a proper case of tail-recursion (but even placing a cut in
> front of the recursive loop1/1 call does not change the behaviour)?
>
> What would be the "best" way to, for instance, generate a sequence of
> integers with standards-compliant Prolog, which does not (AFAIK) include
> for/3? (Or better: Is there something which performs better than my code
> given)?
>
> Many thanks in advance,
> Daniel
>

You probably consulted the code above, with consult(file) or [file].
If you gplc it, then you get the properly optimized tailrecursive
code and GNU-Prolog can do ?- loop1(1000000). in small stack.

Cheers

Bart Demoen

Carlo Capelli

2007-09-05, 4:20 am

"Daniel Kraft" <d@domob.eu> ha scritto nel messaggio
news:fbjtlm$2sr$1@newsreader2.utanet.at...
> Hi all,
>
> I use GNU-Prolog and was wondering while I get stack overflows even if my
> recursive calls (should) be tail-recursive and thus transformed into
> iterations. My code looks as follows:
>
> loop1(N, N) :- !.
> loop1(I, N) :-
> II is I+1,
> loop1(II, N).
> loop1(N) :-
> loop1(0, N).
>
> loop2(N) :-
> \+ (for(I, 0, N), fail).
>
> loop1/1 overflows with a large enough argument (and is significantly
> slower), while loop2/1 does not overflow for the same magnitude and runs
> faster. for/3 is a GNU-Prolog predicate which unifies I with the integers
> from 0 to N on backtracking, thus doing "real" iteration, probably similar
> to what repeat/0 does.
>
> Of course, this might be something specific to GNU-Prolog; but I believe
> it should be able to resolve proper tail recursion to iteration, and
> therefore I suspect it might have something to do with my test-code. Is
> this really a proper case of tail-recursion (but even placing a cut in
> front of the recursive loop1/1 call does not change the behaviour)?
>
> What would be the "best" way to, for instance, generate a sequence of
> integers with standards-compliant Prolog, which does not (AFAIK) include
> for/3? (Or better: Is there something which performs better than my code
> given)?
>
> Many thanks in advance,
> Daniel
>
> --
> Got two Dear-Daniel-Instant Messages
> by MSN, associate ICQ with stress--so
> please use good, old E-MAIL!

Maybe placing a cut before the tail recursive call could help the
interpreter.

loop1(N, N).
loop1(I, N) :-
II is I+1,
!, loop1(II, N).
loop1(N) :-
loop1(0, N),
!. % the last cut required to avoid infinite looping, for example in
?- loop1(4), fail.

Actually, that simple minded solution was what i adopted in my interpreter
some year ago to handle the simpler cases of tail-recursion.

Bye Carlo

Bart Demoen

2007-09-05, 4:20 am

Carlo Capelli wrote:

> Maybe placing a cut before the tail recursive call could help the
> interpreter.
>
> loop1(N, N).
> loop1(I, N) :-
> II is I+1,
> !, loop1(II, N).
> loop1(N) :-
> loop1(0, N),
> !. % the last cut required to avoid infinite looping, for example in
> ?- loop1(4), fail.

[The last cut is needed because you took out the first cut, right ?]

Anyway, placing the cut before the tailrecursive call doesn't help in this case
in GNU-Prolog: the same difference remains between compiled and consulted code.

Cheers

Bart Demoen

Chip Eastham

2007-09-05, 7:06 pm

On Sep 5, 3:30 am, "Carlo Capelli" <carlo.cape...@rdbos.it> wrote:
> "Daniel Kraft" <d...@domob.eu> ha scritto nel messaggionews:fbjtlm$2sr$1@newsreader2.utanet.at...
>
>
>
>
>
>
>
>
>
>
>
>
> Maybe placing a cut before the tail recursive call could help the
> interpreter.
>
> loop1(N, N).
> loop1(I, N) :-
> II is I+1,
> !, loop1(II, N).
> loop1(N) :-
> loop1(0, N),
> !. % the last cut required to avoid infinite looping, for example in
> ?- loop1(4), fail.
>
> Actually, that simple minded solution was what i adopted in my interpreter
> some year ago to handle the simpler cases of tail-recursion.
>
> Bye Carlo

Something like that was my first thought, but
in fact no alternative remains before Daniel's
recursive call to loop1/2:

loop1(N, N) :- !.
loop1(I, N) :-
II is I+1,
loop1(II, N).

The common predicate name for loop1/1 poses a
bit of a red herring.

The problem can be illustrated with loop1/2 by
itself, e.g.

?- N = 10000000, loop1(0,N).

regards, chip

Sponsored Links