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

[Zoltan Somogyi]

On Fri, 13 Nov 2015 18:06:58 +1100, Paul Bone <paul at bone.id.au> wrote:
> > 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.

They may be more than most people require, but they are optional;
people don't have to specify more than they want to specify.

> I'd prefer to call "clique" "scc". 

Fine.

> 
> > 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 typically insist on an options list (empty or not) when either there is
something following it, or we expect that we may later add an extra parameter
to the pragma that would follow the options list. I don't think it would
make sense to add an extra parameter to this pragma, so I see no reason
why we shouldn't allow the options list to be deleted if it is empty. On the
other hand, requiring people to type an addition ", []" is not a big burden
either, so I would not object to requiring the options list either.

The default behavior I listed above is what I propose if the options list
is silent on a matter, either because it does not have an option on e.g.
what kinds of recursions it applies to, or because there is no options list.

The idea is that (a) the compiler has a default behaviour about
e.g. whether to warn about the absence of tail recursion, (b) the
user can override that behaviour for a module with a compiler option,
and (c) the user can override both (a) and (b) for a specific procedure's scc 
with this pragma.

This would mean, for example, that specifying :- pragma require_tail_recursion(
PROC_SPEC, [none]) would override a compiler option asking for such warnings.

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

Can you imagine that ever being useful?

A programmer typically cares about the answer to the question:
"can this code work in constant stack space?". If the "code" in question
is mutually recursive, having a backend that guarantees tail recursion
for self recursive calls only is not much help. Even if half the tailcalls
are self-tail-calls and the other half are tail calls to other procedures
in the scc, optimizing only the former will still cause you to blow the
stack with large enough inputs. The only thing that changes is that
"large enough" is now (on average) twice as large. Is that a useful
amount of help? Probably only in pretty rare circumstances.

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

Exactly. The ancestor may not even be in the current module,
which is why I don't think the compiler can do anything useful about it.

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

Agreed; that is why I mentioned it.

Zoltan.