[m-dev.] New pragmas for tail recursion warnings

Paul Bone paul at bone.id.au
Wed Dec 16 23:15:16 AEDT 2015


I thought of a useful addition to this proposal.

Currently both the pragma and --warn-non-tail-recursion will emit a warning
for the second recursive call in quicksortapp but not the first.

    qsortapp([], []).
    qsortapp([Pivot | T], List) :-
        partition(Pivot, T, [], Left0, [], Right0),
        qsortapp(Left0, Left),
        qsortapp(Right0, Right),
        append(Left, [Pivot | Right], List).

This is intentional to prevent the output from being too noisy.  It's also
pretty obvious, that the first call isn't a tail call.  Even when it's not
always obvious that the second call isn't a tail call.  Here it looks as if
the last call is qsortapp, but it's not because of the call to ++ in the
clause head.  Construction and changing argument orders can also cause
confusion, which is part of the motivation for the pragma and command line
option.

    qsortapp([], []).
    qsortapp([Pivot | T], Left ++ [Pivot | Right]) :-
        partition(Pivot, T, [], Left0, [], Right0),
        qsortapp(Left0, Left),
        qsortapp(Right0, Right).

Anyway, I'm trying to show that omitting the warning for the first recursive
call is good.

However when we make the second call tail recursive by using an
accumulator, in qsortacc, this feature can be a problem:

    qsortacc([], Acc, Acc).
    qsortacc([Pivot | T], Acc0, Acc) :-
        partition(Pivot, T, [], Left0, [], Right0),
        qsortacc(Right0, Acc0, Right),
        qsortacc(Left0, [Pivot | Right], Acc).

The second recursive call is a tail call, so it gets no warning.  However
the first recursive call is not a tail call, which should be obvious.
However when the compiler doesn't generate a warning, and the developer
doesn't look at the predicate body at all, they might conclude that this
predicate uses constant stack space.

Depending on what the developer is thinking it may either be useful or a
hindrance to create a warning for a recursive call on the same execution
path as a recursive call, whether or not that second call is a tail call.

Rather than enumerate all the possible behaviors I could implement.  I will
list just those that I'm considering (but feel free to suggest others that I
may have dismissed or not considered):

    1. Suppress the warning only when a later call on that execution path has
       already had a warning generated for it.  Therefore suppressing the
       warning for qsortapp but generating it for qsortacc.

    2. Adding another option to the require_tail_recursion pragma to control
       this. The option allows the developer to choose between the current
       behaviour (always suppressing these warnings) and option 1
       (suppressing the warnings when another call later in that path had a
       warning generated for it) and always generating such warnings.  If so
       what shooed the default setting be and what should it be called?
       Keeping in mind that if the user wants to guarantee constant stack
       space (not a real guarantee because of higher order / module calls)
       then they need this always turned on.

Thanks.


-- 
Paul Bone



More information about the developers mailing list