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

[Paul Bone]

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

If possible I'd prefer to introduce something that "fits" with existing
syntax / conventions / idioms.  So I'll allow users to omit the options list
and let that mean the same thing as an empty options list.

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

Agreed.

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

I imagined this because they always want a warning about self-recursion
that's not tail recursion, or on the low-level C backend where it's
supported, self and mutual recursion that's not tail recursive.  Effectively
suppressing the warning about mutual recursion on backends that don't
support mutual recursion.  That maybe something the user would prefer to
control wholesale using a compiler option.

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

It depends on why the programmer wants constant stack space.  This is the
main reason, to avoid blowing the stack.  However a user may simply want to
reduce the amount of memory touched and therefore memory bandwidth required.
But you're right, almost all of the time the programmer wants to avoid
blowing the stack.

I guess the question is, if they take some code that uses mutual and direct
tail recursion, and run it on a backend that supports only direct tail
recursion, do they want to suppress the warnings for the mutually recursive
calls that are no-longer tail recursive, even if it means that they may now
blow the stack for large inputs?

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

Yep, I would therefore not warn at all for higher order calls, including
method calls.

Hrm, if ho-specialisation is applied that may be different.  We could safely
warn about them then, however the user may be confused by the
specialisation.

Thanks.


-- 
Paul Bone