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

[Zoltan Somogyi]

On Mon, 16 Nov 2015 10:53:43 +1100, Paul Bone <paul at bone.id.au> wrote:
> > >     :- 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.

You haven't answered my question: WHY would they want that? Why
would they think that such a warning would be useful to them? (See below.)

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

My point is: a predicate is either self-recursive only or is part of a mutually
recursive scc; it does not change from one to the other just because gets
recompiled on a different backend. And the user either wants to be told
when the backend cannot guarantee that the predicate can be executed
in constant stack space, or they don't want to be told. I don't see users
ever saying to themselves "This predicate is mutually recursive, so it will
blow the stack unless the backend supports both self and mutual tail
recursion. Nevertheless, I don't want to be warned about this fact if I am
compiling this on a platform that supports self-tail-recursion but not
mutual-tail-recursion." Likewise, I don't think any user will say "this predicate
is only self recursive, but I want to be warned about it on platforms
that support self tail recursion but don't support mutual-tail-recursion."

A compiler option applies to all predicates in a module, some of which
may be self-recursive and others mutually recursive, so this consideration
does not apply to them.

If you are worried about a predicate changing e.g. from self-recursive
to mutually recursive when the programmer updates its code but
forgets to update the pragma, that is a legitimate concern, but I don't
think your proposed design helps to address it. That would be better
handled by extending the none/tail_only/etc spectrum to include
an option that would allow the programmer to say "please warn me
if the compiler can't make all the recursive calls in this predicate tail
calls, and I leave it up to the compiler to work out whether those
recursive calls are self or mutual recursive."

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

Agreed.

Maybe we should introduce new scopes in the compiler that would record
that the goal inside came from the inlining of a given call, recording the
call's details (location of the call, the callee's name, and the actual argument list),
or that the goal inside came from higher order specialization of a call,
again recording similar details. They would have no effect on code generation,
but they would allow you to generate better error messages.

An issue I can see with that is that we would have to decide in advance
exactly what invariants such analyses would be allowed to assume about
the scopes, so that code in the compiler that moved code across the boundaries
of the scope could ensure that it did not invalidate the invariant. I say in advance
because changing the invariant later would be almost impossible; since the
invariant would not be about the HLDS itself but about its history, you couldn't
just look at the HLDS and test whether the invariant was satisfied. Therefore
if you changed the invariant to make it tougher, there would no way to
automatically test whether compiler optimizations broke the updated invariant.

Zoltan.