1

A typical loop code in Prolog is something like:

loop_test :-
  format('loop...~n'),
  loop_test.

as discussed in another question: How Can I simulate a while loop in Prolog with unchangeable conditions?

Here's my question: Is this recursive form safe against overflow? Typically such a recursive code of C,C++,Python would overflow as in each function call a new stack is added. I executed above loop_test under trace. It was something like:

?- trace.
?- loop_test.
  Call: (6) loop_test2 ? creep
  Call: (7) format('loop...~n') ? creep
loop...
  Exit: (7) format('loop...~n') ? creep
  Call: (7) loop_test2 ? creep
  Call: (8) format('loop...~n') ? creep
...
loop...
  Exit: (158) format('loop...~n') ? creep
  Call: (158) loop_test2 ? creep
  Call: (159) format('loop...~n') ? creep
...

Clearly the number is increasing. With this simple code, I couldn't find the memory increase; I executed loop_test for more than 5 min and tracked VmPeak (peak size of virtual memory) written in /proc/xxx/status, but no change was observed.

I want to understand if the above code (loop_test) is really safe? and Why is it safe? (or safer way to implement loops in Prolog).

Many thanks.

Community
  • 1
  • 1
Akihiko
  • 362
  • 3
  • 14
  • 3
    Prolog optimizes [tail recursion](https://en.wikipedia.org/wiki/Tail_call). Since your recursive call is the last call of the clause, it will not overflow. – Fatalize Oct 24 '16 at 14:21
  • 1
    @Fatalize: ... provided that the goals in between did not create any CPs! – false Oct 24 '16 at 14:27
  • @false I guess this question requires a more thorough answer than just an inaccurate comment by me then. I indeed fail to find much documentation about tail recursion for e.g. SWI-Prolog. So having some details about cases like the one you are talking about would be valuable :) – Fatalize Oct 24 '16 at 14:29
  • @Akihiko, Fatalize's comment is the heart of the answer to your question. Indeed language implementations like the standard python interpreter do _not_ optimize tail recursion, and will quickly reach max recursion depth. Also, yes, like false mentioned, this is assuming that choice points are not created in the predicate call. – eazar001 Oct 24 '16 at 17:38
  • 2
    @Akihiko, choice points add an _additional_ layer of complexity to space complexity. In order to understand the impact that it has and how to control it, one should become familiarized with the concept of backtracking in prolog. Cuts are inevitably stumbled upon while learning this fundamental area of logic programming. – eazar001 Oct 24 '16 at 17:42
  • 2
    [Related](http://stackoverflow.com/q/14096656/772868). – false Oct 24 '16 at 21:26
  • 1
    @eazar001: Direct cuts can often be avoided with pure replacements like [if_/3](http://stackoverflow.com/search?q=if_+%5Bprolog%5D). – false Oct 24 '16 at 21:29
  • 1
    Is there a good reference that explains **conditions** when a tail recursion is optimized? Above `loop_test` is a clear case, but sometimes Prolog programmers write like: `loop_test :- xxx, (yyy -> zzz; qqq, loop_test).` Does Prolog implementation recognize this as a tail recursion? – Akihiko Oct 25 '16 at 08:39

0 Answers0