[m-dev.] Tail recursion warning proposal

[Paul Bone]

I have proposed and partly implemented a pragma that can enable and disable
the tail recursion warning. In some ways it offers more control than
Zoltan's recent scope goal, and in other ways it offers less.

% Disable warnings
:- pragma require_tail_recursion(foo/3, [none]).

% Enable warnings
:- pragma require_tail_recursion(foo/3, [warn]).

% Make the warning an error
:- pragma require_tail_recursion(foo/3, [error]).

% Allow any type of recursion
:- pragma require_tail_recursion(foo/3, [self_or_mutual_recursion]).

% Direct recursion only
:- pragma require_tail_recursion(foo/3, [self_recursion_only]).

% Mutual recursion, but with a specific SCC (not implemented yet).
:- pragma require_tail_recursion(foo/3, [scc([bar/3, baz/2])]).

And so on, some of the options can be combined. The original discussion is
here:
http://www.mercurylang.org/list-archives/developers/2015-November/016482.html

I think that it makes sense to add an option that will make the option
conditional on whether the implementation was able to optimize the tailcall.
Since MLDS cannot currently optimize recursive calls.

:- pragma require_tail_recursion(foo/3, [optimized_tailcalls]).

This would generate a warning for recursive calls, including those in tail
position, that are not optimized to something that uses a constant stack
size (LCO, a loop, etc).

Is this okay?

Cheers.

[Paul Bone]

Post by Paul Bone
I have proposed and partly implemented a pragma that can enable and disable
the tail recursion warning. In some ways it offers more control than
Zoltan's recent scope goal, and in other ways it offers less.
% Disable warnings
:- pragma require_tail_recursion(foo/3, [none]).
% Enable warnings
:- pragma require_tail_recursion(foo/3, [warn]).
% Make the warning an error
:- pragma require_tail_recursion(foo/3, [error]).
% Allow any type of recursion
:- pragma require_tail_recursion(foo/3, [self_or_mutual_recursion]).
% Direct recursion only
:- pragma require_tail_recursion(foo/3, [self_recursion_only]).
% Mutual recursion, but with a specific SCC (not implemented yet).
:- pragma require_tail_recursion(foo/3, [scc([bar/3, baz/2])]).
And so on, some of the options can be combined. The original discussion is
http://www.mercurylang.org/list-archives/developers/2015-November/016482.html
I think that it makes sense to add an option that will make the option
conditional on whether the implementation was able to optimize the tailcall.
Since MLDS cannot currently optimize recursive calls.
:- pragma require_tail_recursion(foo/3, [optimized_tailcalls]).
This would generate a warning for recursive calls, including those in tail
position, that are not optimized to something that uses a constant stack
size (LCO, a loop, etc).

That's weird though.

What should this do?

:- pragma require_tail_recursion(map/3,
[self_recursion_only, optimized_tailcalls]).

map(P, [X | Xs], [Y | Ys]) :-
P(X, Y),
map(P, Xs, Ys).

Should it generate a warning without LCMC? Likewise.

:- pragma require_tail_recursion(foo/3,
[self_or_mutual_recursion, optimized_tailcalls]).

In MLDS:
Generates a warning for a mutually recursive call in tail position
(because it can't be optimized).

In LLDS:
No warning.

That means that without optimized_tailcalls, the first example (map)
shouldn't generate a warning, even without LCMC, even though it uses linear
stack space. And the second example wouldn't generate a warning either.
That kind-of defeats the purpose.

So instead we have the earlier proposal where the warnings are only
generated when we attempt tail recursion. So you would get a warning even
if you said mutual recursion is okay in a grade that doesn't support mutual
recursion, that could be a little confusing. Maybe the flag should be
"allow_unoptimized_tailcalls", the reverse of the above proposal.
Adding it to mutually recursive code would suppress the warning in MLDS
grades for calls that would normally be optimized in LLDS grades. What
should it do with regard to LCMC? Doing anything sensible for LCMC or
accumulator introduction may be difficult.

[Michael Day]

Hi Paul,

Post by Paul Bone
I have proposed and partly implemented a pragma that can enable and disable
the tail recursion warning. In some ways it offers more control than
Zoltan's recent scope goal, and in other ways it offers less.

I'm struggling to understand the ramifications of these new warning
controls and how they might play out in different situations.

Do these scenarios sound reasonable:

1. Tail recursion warnings are disabled, the default.

2. Tail recursion warnings are enabled for all predicates by
command-line option.

3. Tail recursion warnings are enabled for specific predicates by pragma.

4. Tail recursion warnings are enabled for all predicates by
command-line option, then disabled for specific predicates by pragma.

I'm not really sure of the more subtle scenarios like distinguishing
between self / mutual recursion, when would they be used?

Michael

[Paul Bone]

Post by Michael Day
Hi Paul,

Post by Paul Bone
I have proposed and partly implemented a pragma that can enable and disable
the tail recursion warning. In some ways it offers more control than
Zoltan's recent scope goal, and in other ways it offers less.

I'm struggling to understand the ramifications of these new warning controls
and how they might play out in different situations.
1. Tail recursion warnings are disabled, the default.
2. Tail recursion warnings are enabled for all predicates by command-line
option.
3. Tail recursion warnings are enabled for specific predicates by pragma.
4. Tail recursion warnings are enabled for all predicates by command-line
option, then disabled for specific predicates by pragma.
I'm not really sure of the more subtle scenarios like distinguishing between
self / mutual recursion, when would they be used?

If you did a fair amount of your development in a low-level C grade, but
also knew that you needed to support other grades. By using the
self_recursion_only option you would get more immediate feedback when you
introduced mutual recursion that the MLDS cannot handle.

self_and_mutual recursion is the default, it's what happens when you don't
specify one of these three options.

scc(...) is good if you want to limit the size of the SCC. This can be
useful for other reasons, such as helping to limit the computational
complexity of code. It doesn't affect it directly but it might help prevent
it getting out of hand.