[m-users.] Ambiguous tail recursion?

[Julien Fischer]

On Tue, 16 Jul 2019, Julian Fondren wrote:

> On 2019-07-16 21:14, Julien Fischer wrote:

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

The order of conjunctions doesn't matter to the declarative semantics of
the code; it definitely matters to the operational ones.   And with the
above example, what's going to happen is again dependent on what
optimization are enabled.  Enabling --constraint-propagation, which
moves semidet goals to as early as possible, will cause the compiler to
re-order the conjunction in the above predicate (and as a result of that
it will be become tail recursive.)

Note that how much the compiler is allowed to reorder your code is
controlled by which semantics are selected -- see the ``Semantics''
chapter of the reference manual.  By default, the compiler is allowed to
reorder both conjunctions and disjunctions for optimization purposes
(beyond whatever reordering is required for mode correctness).

> At least I should have a style rule like "put tail calls at the end".

As a rule of thumb, sure.  The rationale for the addition of the tail
recursion warnings and pragmas was to give programmers a mechansim for
stating that tail recursion *must* occur.

Julien.