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

[Paul Bone]

On Fri, Nov 13, 2015 at 05:46:36PM +1100, Zoltan Somogyi wrote:
> 
> 
> On Fri, 13 Nov 2015 17:20:46 +1100, Paul Bone <paul at bone.id.au> wrote:
> > > What I'd like to have reviewed at this stage are the names and syntax of the
> > > pragmas.
> > > 
> > >     % This pragma works on all procedures of a given predicate/function.
> > >     :- pragma no_warn_tail_recursion(NAME/ARITY).
> > > 
> > >     % This pragma works on a single procedure.
> > >     :- pragma no_warn_tail_recursion(NAME(ARG_MODES*)).
> > > 
> > >     :- pragma warn_tail_recursion(NAME/ARITY).
> > >     :- pragma warn_tail_recursion(NAME(ARG_MODES*)).
> > 
> > Argh,  I meant to say no_warn_non_tail_recursion and
> > warn_non_tail_recursion, these match the option name
> > --warn-non-tail-recursion.
> 
> The predicate parse_arity_or_modes in prog_io_pragma.m
> should parse either the NAME/ARITY or the NAME(ARG_MODES) syntax
> for specifying a procedure or set of procedures. In the following,
> I use PROC_SPEC as a shorthand for either.

I just found that predicate myself.  I'm on the right track.

> I don't like the double negative in the name no_warn_non_tail_recursion.
> I think it is very likely to confuse people, and even the ones who aren't
> confused will not like having to take time to resolve the negatives.
> 
> I propose something like this:
> 
> :- pragma require_tail_recursion(PROC_SPEC, [OPTION_1, ... OPTION_N]).
> 
> where an option may be "warn" or "error" to govern what happens if
> the requirement isn't met, or it may be "none", "self_recursion_only",
> "mutual_recursion_only", or "self_and_mutual_recursion" to say what
> kinds of recursion are required to be tail recursion, and maybe
> "clique([OTHER_PROC_SPEC_1, ... OTHER_PROC_SPEC_N])" if the
> user wants to specify what procedures the clique should have, so they
> get a warning or an error if the clique accidentally becomes bigger
> than what they expected.

Some of these seem like more than (most) users require.  But I could easily
be wrong about that, and by the time I implement some of them, implementing
the others isn't very much extra work.  So it seems okay to me.

I'd prefer to call "clique" "scc".  The definition of clique is a group of
nodes where each node has an edge to every other node.  But that's not
necessarily true for mutually recursive code.  To compare, a strongly
connected component (SCC) is a group of nodes where each node is reachable
from every other node (it assumes a directed graph).

> That leaves the question of what the defaults should be; I propose
> "warn", "self_and_mutual_recursion", and no of course no explicitly
> specified clique.

Is that the default behaviour if the pragma has an empty options list or no
options list?  What if there is no pragma?  (Currently this warning is not
enabled by default).  I'm pretty sure I know the answers, I just want to
clarify.

> We could also add an option that lists the backends on which
> the requirement is valid.

We might want a way to say that some requirements hold in some backends, but
not others.

    :- pragma require_tail_recursion(foo/3,
        [warn,
         llc_backend(self_and_mutual_recursion),
         hlc_backend(self_recursion_only)]).

Or even.
    
    :- pragma require_tail_recursion(foo/3,
        [warn, self_recursion_only,
         llc_backend(self_and_mutual_recursion)]).


> Both your proposal and mine has to decide what happens if the
> specified predicate has no recursive calls at all, and what happens
> if it contains a higher order call (which may end up being a recursive
> call, if the procedure's address is taken). I am pretty sure we would
> have to ignore the latter, but the former is a different question.

Of course the latter case might only be directly recursive if it has the
same type or a curried type.  It may however be mutually recursive.  It may
also happen if an ancestor's address has been taken.  This is related to the
problem Tom/you identified in the deep profiling paper regarding seeing
unintended SCCs through higher order code such as exception handling code.
In these cases the programmer usually didn't intend to create mutual
recursion and probably doesn't mind it and won't want to be bothered about
it.

Maybe for the former we should always have a warning if the pragma is
present at all, because it isn't sensible.

Thanks.


-- 
Paul Bone