[m-dev.] Tail recursion warning proposal

Paul Bone paul at bone.id.au
Thu Jan 19 16:20:48 AEDT 2017

On Thu, Jan 19, 2017 at 03:30:05PM +1100, Paul Bone wrote:
> I have proposed and partly implemented a pragma that can enable and disable
> the tail recursion warning.  In some ways it offers more control than
> Zoltan's recent scope goal, and in other ways it offers less.
>     % Disable warnings
>     :- pragma require_tail_recursion(foo/3, [none]).
>     % Enable warnings
>     :- pragma require_tail_recursion(foo/3, [warn]).
>     % Make the warning an error 
>     :- pragma require_tail_recursion(foo/3, [error]).
>     % Allow any type of recursion
>     :- pragma require_tail_recursion(foo/3, [self_or_mutual_recursion]).
>     % Direct recursion only
>     :- pragma require_tail_recursion(foo/3, [self_recursion_only]).
>     % Mutual recursion, but with a specific SCC (not implemented yet).
>     :- pragma require_tail_recursion(foo/3, [scc([bar/3, baz/2])]).
> And so on, some of the options can be combined.  The original discussion is
> here:
> http://www.mercurylang.org/list-archives/developers/2015-November/016482.html
> I think that it makes sense to add an option that will make the option
> conditional on whether the implementation was able to optimize the tailcall.
> Since MLDS cannot currently optimize recursive calls.
>     :- pragma require_tail_recursion(foo/3, [optimized_tailcalls]).
> This would generate a warning for recursive calls, including those in tail
> position, that are not optimized to something that uses a constant stack
> size (LCO, a loop, etc).

That's weird though.

What should this do?

    :- pragma require_tail_recursion(map/3,
        [self_recursion_only, optimized_tailcalls]).

    map(P, [X | Xs], [Y | Ys]) :-
        P(X, Y),
        map(P, Xs, Ys).

Should it generate a warning without LCMC?  Likewise.

    :- pragma require_tail_recursion(foo/3,
        [self_or_mutual_recursion, optimized_tailcalls]).

    In MLDS:
        Generates a warning for a mutually recursive call in tail position
        (because it can't be optimized).

    In LLDS:
        No warning.

That means that without optimized_tailcalls, the first example (map)
shouldn't generate a warning, even without LCMC, even though it uses linear
stack space.  And the second example wouldn't generate a warning either.
That kind-of defeats the purpose.

So instead we have the earlier proposal where the warnings are only
generated when we attempt tail recursion.  So you would get a warning even
if you said mutual recursion is okay in a grade that doesn't support mutual
recursion, that could be a little confusing.  Maybe the flag should be
"allow_unoptimized_tailcalls", the reverse of the above proposal.
Adding it to mutually recursive code would suppress the warning in MLDS
grades for calls that would normally be optimized in LLDS grades.  What
should it do with regard to LCMC?  Doing anything sensible for LCMC or
accumulator introduction may be difficult.

Paul Bone

More information about the developers mailing list