A=call(A), call(A). % can I get tail recursion?

[Frank_Schwidom]

Hi,

swipl 8.4.1 :

(ins)?- A=call(A), call(A).
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.7Gb, global: 0.2Gb, trail: 0Kb
ERROR:   Stack depth: 10,735,430, last-call: 0%, Choice points: 3
ERROR:   Probable infinite recursion (cycle):
ERROR:     [10,735,430] system:call(<compound (:)/2>)
ERROR:     [10,735,429] system:call(<compound (:)/2>)

comparison with yap:

+   ?- A=call(A), call(A).
^C+Action (h for help): a

Yap loops forever. What can I do to have this kind of recursion in Swi Prolog?

Regards,
Frank.

[brebs]

What do you want that would actually be useful?

An infinite loop is not useful, in itself, e.g. 10 goto 10 in BASIC.

[Frank_Schwidom]

@brebs

What do you want that would actually be useful?

I could write “hello world” in a loop:

(ins)?- A = ( write('hello '), call(B)), B = ( writeln( 'world'), call(A)), call(A).
hello world
hello world
hello world
...

And I could decide how the loop begins:

(ins)?- A = ( write('hello '), call(B)), B = ( writeln( 'world'), call(A)), call(B).
world
hello world
hello world
...

This is like programming with ‘goto’ but in an very structured way. Even lisp has the ‘tagbody’ where you can use ‘goto’.

Regards,
Frank.

[Boris]

But why are you using call/1 for this? It works as expected (???) if it is a normal predicate, like:

a :- a.

and then:

?- a. % loops forever

You can have it with mutual recursion, too:

a :- b.
b :- a.

or as in your example:

hello :- write(hello), world.
world :- write(world), hello.

I hope someone else looks deeper in it but I suspect it is the unnecessary (?) use of call/1 that causes trouble.

EDIT: I am getting curious and hope someone actually says what happens. One thing is for sure: while this:

a :- a.

is infinite recursion when evaluated, the term itself is not cyclic; however, A = call(A) creates a cyclic term. I don’t really know what should happen when a cyclic term is evaluated. At least logically it is not immediately obvious what should happen.

[Frank_Schwidom]

@Boris

a :- a.

@Boris

a :- b.
b :- a.

Both don’t interrupt, so swipl uses tail recursion this time.

But my usecase is the call of the cyclic term.

Regards.

[Boris]

@Frank_Schwidom

But my usecase is the call of the cyclic term.

My comment might come across as argumentative, but to me this looks like a mechanic, not a use case. I mean that “calling a cyclic term” is a mechanic but to what end? Surely you must have some use case for it and it might be that there is a different mechanic to achieve the same? For one very specific use case, “endless recursion”, I showed one other mechanic, “recursive predicate” instead of “calling a cyclic term”.

[brebs]

Seems relevant: Compiler support for cyclic terms? - #3 by jan

[Frank_Schwidom]

@Boris

My comment might come across as argumentative, but to me this looks like a mechanic, not a use case. I mean that “calling a cyclic term” is a mechanic but to what end? Surely you must have some use case for it and it might be that there is a different mechanic to achieve the same? For one very specific use case, “endless recursion”, I showed one other mechanic, “recursive predicate” instead of “calling a cyclic term”.

A module of predicates is not the same than a term. A term can provide backtracking on its own which a module cannot.

The only possibility which I see is to provide the predicate approach in a tree structure (like assoc) which is then interpreted by a meta interpreter as if it were a module. The predicates then are kept inside of the structure. And then the question is: does the meta interpreter provide tail recursion?

Regards.

[Boris]

OK, I really don’t understand. Maybe I should stay out of it.

[peter.ludemann]

Are you trying to make a meta-interpreter, using a cyclic term that’s derived from the clauses? That is, the cyclic term is the fix-point of the recursive term that represents the clause? If so, it might be useful to show how you create that cyclic term.

(I tried something like this a long long time ago, when cyclic terms first became available on some Prologs; I eventually abandoned it but I can’t recall what problems I ran into …)

[j4n_bur53]

The diagnosis of this here, is not so easy:

@Frank_Schwidom

?- A=call(A), call(A).

You can also use this call:

?- A=(write('.'), flush_output, call(A)), call(A).

Its a test of at least two things, depending on circumstances, not
mentioning the choice point optimization that the Prolog system must
master for write/1 and flush_output/0:

• When it runs indefinitely, i.e. goes on and on outputting …,
  its a sign that your Prolog interpreter has tail recursive meta calls.

• When it runs indefinitely, i.e. goes on and on outputting …,
  and it could be a sign that your Prolog interpreter has shallow meta calls

Tail-recursive meta calls are meta calls that do not build up some stack.
This is quite tricky, since meta calls sometimes involve multiple hops
of some internal calls, but it can be done by making these internal calls

all heavily last call optimized. Shallow meta calls are meta calls
where the Prolog term arguments of the predicates in the meta call are
not compiled, only the control structure. On the other hand if you deep

compile the meta call, you would need to deep compile a cyclic structure.

Edit 23.04.2022:
Judging from this output here, since it outputs something:

?- A=(write('.'), flush_output, call(A)), call(A).
........................^C

And this behaviour here:

 ?- A=(1=1, call(A)), call(A).
ERROR: Stack limit (1.0Gb) exceeded

I would say SWI-Prolog has shallow meta calls, but not tail recursive
meta calls. Right, correct? Here are a few Prolog systems that have or do
not have tail recursive meta calls, running the same last test case:

SICStus Prolog: Pass ✓
Formerly Jekejeke Prolog: Fail ✗
Dogelog Player: Pass ✓
Scryer Prolog: Fail ✗

Maybe I can bring the same to formerly Jekejeke Prolog as well? To see
the Scryer Prolog Fail, you need to watch the memory growing and growing.
The other Prolog systems that do Pass have constant memory.

[jan]

As is, call(X) does not do last call optimization. It could of course. There are some scenarios where this is probably fairly easy to do. The same code is also used by many other meta-calling primitives where last call optimization should not be done. Also, if the argument to call/1 is a control structure it is compiled into a temporary clause on the environment (local) stack and this this will overflow anyway. This has advantages (good performance on complex goals that perform a lot of backtracking) and disadvantages (resource usage and the risc to compile parts that are never executed). It alsi prevents the other way to create a loop:

 ?- A = (a,A), call(A).

There has never been much incentive to make call/1 do last call optimization. So, the real question is whether this is more a theoretical exercise or a real problem for which there is no obvious alternative. And, if so, whether it is covered by the subset of cases where this is fairly easy to optimize.

[j4n_bur53]

@jan

So, the real question is whether this is more a theoretical exercise
or a real problem for which there is no obvious alternative.

There are many libraries that use meta calls. For example
Bart Demoen et al. “Tor” and Ulrich Neumerkels “indexing dif”:

Tor: Extensible Search with Hookable Disjunction
https://www.swi-prolog.org/pack/list?p=tor

Many Prolog programs are unnecessarily impure
https://arxiv.org/abs/1607.01590

But the issue needs of course be also examined for call/n
and not only call/1. Currently Dogelog Player doesn’t have call/n,
only call/1, so I don’t know. I also don’t know why it doesn’t

work in formerly Jekejeke Prolog or in SWI-Prolog. In SWI-Prolog
if you create a temporary clause, last call optimization could skip
it, but you need also a mechanism to garbage collect it.

In formerly Jekejeke Prolog I create a temporary half clause,
only the body of a clause. I thought I made it so that it gets skip
and garbage collected, maybe there is a bug somewhere.

Edit 24.04.2022:
One view of last call optimization is that it shrinks the call stack,
either by reusing a clause instance frame, B-Prolog and its TOAM
architecture wrote about this, or by creating a new one, and

deleting an old one, the alternative to TOAM. You need then compaction
so that it gets permanently “skipped” in the calls stack. It could be that
SWI-Prolog is closer to TOAM, and the reuse, the check for reuse,

that all compiled code has in SWI-Prolog, doesn’t work for a meta calls.
B-Prolog the precursor of Picat, describes the approach of TOAM
as follows, in the paper here:

Unlike the call instruction which always allocates a new frame
for the callee, the last call instruction reuses the current frame if
it is a determinate frame or a choice point frame whose
alternatives have been cut off.

Dogelog Player doesn’t do that, instead it is completely stackless
trampoline. And then the host language garbage collector can also
collect frames resulting from meta call compilation.

As a drawback currently Dogelog Player cannot show a stack trace
when an error is thrown. Although maybe there is a way to extract a
stack trace from the choice points that are around,

but I havent figured this out yet.

[j4n_bur53]

Practically the example can be made run on most Prolog
systems by replacing call/1 by Vanilla Interpreter solve/1.
When I use this here:

solve(X=X).
solve(solve(A)) :- solve(A).
solve((A,B)) :- solve(A), solve(B).

I can run this query:

?- A=(1=1, solve(A)), solve(A).

Indefinitely. The test results are now:

SWI Prolog: Pass ✓
SICStus Prolog: Pass ✓
Formerly Jekejeke Prolog: Pass ✓
Dogelog Player: Pass ✓
Scryer Prolog: Pass ✓

Edit 27.04.2022:
The solution is of course not the most speedy. Especially if backtracking
would be involved. See what Jan W. wrote about the advantage of
call/1 that does a kind of preprocessing and storage in a differnet

format of the goal argument. Also there is much more than what
meets they eye. Prolog systems that do not manage their own continuous
variable space might need special algorithms to reuse Variable sernos.