[m-users.] Ambiguous tail recursion?

[Julian Fondren]

On 2019-07-16 21:14, Julien Fischer wrote:
> 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.)

OK, cool.

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

OK, but what if the code is instead

    test([X | Xs]) :-
        test(Xs),
        X < 5.

Normally I read Mercury code as if conjunction order doesn't matter at 
all, but
if it does matter to tail recursive code (without semantics flags to 
disable
reordering), then I still have to think about order to an extent. At 
least I
should have a style rule like "put tail calls at the end".

> Julien.