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

Help!
1

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.

2

What do you want that would actually be useful? :slightly_smiling_face:

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

3

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.

4

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.

5

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

But my usecase is the call of the cyclic term.

Regards.

6

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”.

7

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

8

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.

9

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

10

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 …)

12

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.

2 Likes