[m-users.] Ambiguous tail recursion?

[Julien Fischer]

Hi,

On Tue, 16 Jul 2019, Julian Fondren wrote:

> Consider this module:
>
>   :- module tailornot.
>   :- interface.
>   :- import_module io.
>   :- pred main(io::di, io::uo) is det.
>   :- implementation.
>   :- import_module list, bool, int.
>
>   main(!IO) :-
>       X = (test([1, 2, 3]) -> yes; no),
>       io.print(X, !IO), io.nl(!IO).
>
>   :- pred test(list(int)::in) is semidet.
>   test([]).
>   test([X | Xs]) :-
>       X < 5,
>       test(Xs).
>
> Is it defined that test/1 is tail recursive?

It depends how you are compiling it.  If you're using a hlc grade
and invoke the compiler with --no-optimize-tailcalls, then definitely
not!

Assuming you're not doing something like that then yes, the above
will be compiled into tail recursive code; if you want to make sure
then ask the compiler, e.g. invoke it with --warn-non-tail-recursion=self.

(We also have pragma versions of that warning, although they are
currently undocumented.  If you put

     :- pragma require_tail_recursion(test/1, [error]).

in your program, then the compiler will emit an error if test/1
is not going to compiled in a way that is tail recursive.)

> It seems to be just as valid for it to walk to the end of the list,
> hit the [], and then walk backwards to test 3 < 5, 2 < 5, 1 < 5.

It would be valid, but there's no reason for the compiler to re-arrange
the code that way.

Julien.