TCO frame/env resuse needs improvement

[zoydoid]

As demonstrated by ROK's between/3 in the DEC-10 Prolog library: https://www.j-paine.org/prolog/tools/files/between.pl

xbetween(L, U, N) :-
    nonvar(N),
    !,
    integer(L),
    integer(U),
    integer(N),
    L =< N,
    N =< U.

xbetween(L, U, N) :-
    integer(L),
    integer(U),
    L =< U,
    xbetween1(L, U, N).

xbetween1(L, _, L).

xbetween1(L, U, N) :-
    L < U,
    M is L+1,
    xbetween1(M, U, N).

?- ['xbetween.pl'].
?- xbetween(1,1000000000,_),fail.

SWI-Prolog & Eclipse run this in constant memory. Scryer has a slow leak. GNU Prolog soon stacks out, as does Trealla.

[UWN]

Scryer has a slow leak.

The query fails for me in Scryer, even with ulimit -v 200000. Are you using the latest version?

For GNU Prolog, you need to use gplc as in https://github.com/didoudiaz/gprolog/issues/57

| ?- xbetween(1,1000000000,_),fail.

(48008 ms) no

[zoydoid]

Right, I was using Scryer from the Arch stable release. Building from Git with the latest source it runs in constant memory.

[infradig]

I tried Ciao & XSB, they also run in constant memory. CxProlog doesn't.

[infradig]

It's not a race, (but for what it's worth) on my Linux PC:

Name	Time
B-Prolog v8.1	693s
Ciao v1.22	144s
Eclipse-clp v7.1b13	86s
GPLC v1.6.0	49s
Scryer-Prolog v81712f4	397s
SWI-Prolog v9.1.14	161s
Trealla v2.25.0	448s
XSB v5.0.0	102s

[UWN]

Even for GNU (gplc) there is still room for improvement when comparing it to its built-in between/3. (Here from 44s down to 30s). And then, by compiling the query itself, it's 23s and 9s.

[infradig]

FYI: adding this line after the predicate definition:

:- help(xbetween1(+integer,+integer,-integer), [tco(true)]).

forces Trealla to make the example at top TCO.

There is still work to automatically make this example TCO. Well the change is easy, but it messes some other examples.

See also issue #580