Zoltan Somogyi
2017-09-12 14:17:45 UTC
I have a question about what people think the compiler should do
when it is asked to generate warnings for mutually recursive calls
that are not TAIL recursive, but this fact is NOT a fault of the caller.
The require_tail_rec_N.m programs in tests/invalid each have
two mutually recursive predicates, odd and even. Even calls odd
in a non-tail position, while odd calls even in a tail position.
The expected output says the compiler should generate
a warning about the call to odd in even, but not the call to even
in odd. And that is what we generate in LLDS grades. In those
grades, the call to even in odd is optimized: the generated code
deallocates odd's stack frame and does a goto to even.
In MLDS grades, this doesn't work. The MLDS code generator
works on TSCCs: sets of procedures in which each procedure
is reachable from every other via TAIL calls. In this case,
since even does NOT call odd via a tail call (a fact that gets
a warning), the MLDS code generator generates code for them
separately, which means that the call from odd to even *must*
be an ordinary call, not a tail call. The MLDS code generator
therefore generates a warning about this non-tail recursive call.
But if the programmer looks at this call, he/she will see no reason
why this call is not a tail call. The actual reason is not *anywhere*
in odd; it is in even. The way I see it, this violates the law
of least astonishment.
Note that in this case, while the MLDS code won't be able to reuse
any of even's or odd's stack frames, the LLDS code won't be able
to reuse even's stack frames either, so BOTH backends use
stack space that is linear in the depth of recursion. The MLDS backend
will use twice as many stack frames, but there is no necessary
relationship between the *sizes* of the stack frames on the two backends,
so if the C compiler is much smarter than the Mercury compiler
about stack slot optimization, the MLDS version may in theory
be able to use *less* stack space than the LLDS version.
That is not very likely, but it is possible. It is much more likely
that the user cares about the constant vs linear stack space distinction
much more than about the linear constant factor. In both cases,
the extra warning in MLDS grades is not helpful, and (at least with
the current wording) is likely to be misleading.
Do people think that adding an explanation along the lines of
"the fault for the non-tail nature of this recursive call may lie
in another predicate" would be sufficient to reassure programmers
when they can't find the fault in the predicate (in this case, odd)
mentioned in the error message, or should we try to avoid generating
the misleading error message at all? The latter would require
changing the error message about the actual source of the problem
(the non-tail call in even) to explain that it may affect its whole SCC,
not just the predicate in which it appears.
Zoltan.
when it is asked to generate warnings for mutually recursive calls
that are not TAIL recursive, but this fact is NOT a fault of the caller.
The require_tail_rec_N.m programs in tests/invalid each have
two mutually recursive predicates, odd and even. Even calls odd
in a non-tail position, while odd calls even in a tail position.
The expected output says the compiler should generate
a warning about the call to odd in even, but not the call to even
in odd. And that is what we generate in LLDS grades. In those
grades, the call to even in odd is optimized: the generated code
deallocates odd's stack frame and does a goto to even.
In MLDS grades, this doesn't work. The MLDS code generator
works on TSCCs: sets of procedures in which each procedure
is reachable from every other via TAIL calls. In this case,
since even does NOT call odd via a tail call (a fact that gets
a warning), the MLDS code generator generates code for them
separately, which means that the call from odd to even *must*
be an ordinary call, not a tail call. The MLDS code generator
therefore generates a warning about this non-tail recursive call.
But if the programmer looks at this call, he/she will see no reason
why this call is not a tail call. The actual reason is not *anywhere*
in odd; it is in even. The way I see it, this violates the law
of least astonishment.
Note that in this case, while the MLDS code won't be able to reuse
any of even's or odd's stack frames, the LLDS code won't be able
to reuse even's stack frames either, so BOTH backends use
stack space that is linear in the depth of recursion. The MLDS backend
will use twice as many stack frames, but there is no necessary
relationship between the *sizes* of the stack frames on the two backends,
so if the C compiler is much smarter than the Mercury compiler
about stack slot optimization, the MLDS version may in theory
be able to use *less* stack space than the LLDS version.
That is not very likely, but it is possible. It is much more likely
that the user cares about the constant vs linear stack space distinction
much more than about the linear constant factor. In both cases,
the extra warning in MLDS grades is not helpful, and (at least with
the current wording) is likely to be misleading.
Do people think that adding an explanation along the lines of
"the fault for the non-tail nature of this recursive call may lie
in another predicate" would be sufficient to reassure programmers
when they can't find the fault in the predicate (in this case, odd)
mentioned in the error message, or should we try to avoid generating
the misleading error message at all? The latter would require
changing the error message about the actual source of the problem
(the non-tail call in even) to explain that it may affect its whole SCC,
not just the predicate in which it appears.
Zoltan.