[m-rev.] Fwd: Re: for review: Add new require_tail_recursion pragma.

[Paul Bone]

On Sat, Nov 28, 2015 at 10:22:40AM +1100, Zoltan Somogyi wrote:
> I accidentally sent this only to Paul, not the list.
> 
> ----- Start Forwarded Message -----
> Sent: Sat, 28 Nov 2015 10:18:58 +1100 (AEDT)
> From: "Zoltan Somogyi" <zoltan.somogyi at runbox.com>
> To: "Paul Bone" <paul at bone.id.au>
> Subject: Re: [m-rev.] for review: Add new require_tail_recursion pragma.
> 
> > Attached.
> 
> And from me, the review of the first part. I will do the second
> part later, but this should be enough to work on today :-(
> 


> > +add_pragma_require_tail_recursion(Pragma, Context, !ModuleInfo, !Specs) :-
> > +    Pragma ^ rtr_proc_id =
> > +        pred_name_arity_mpf_mmode(Name, Arity, _MaybePF, MaybeMode),
> > +    get_matching_pred_ids(!.ModuleInfo, Name, Arity, PredIds),
> > +    ( PredIds = [],
> > +        Pieces = [pragma_decl("require_tail_recursion"), words("declration")],
> > +        undefined_pred_or_func_error(Name, Arity, Context, Pieces, !Specs)
> > +    ; PredIds = [PredId],
> 
> The compiler doesn't use this indentation style for switches.

Ah, This is the MCit style, it had become a habit (plus I like it).  I'll
keep Mercury stuff consistent though and fight the habit.

> > +            % Choose the matching proc.
> > +            ( if
> > +                % XXX We should probably also check that each pair in
> > +                % the renaming has the same name.  See the comment in
> > +                % add_foreign_proc
> 
> I don't understand that comment; the inst var names shouldn't matter
> for this pragma.

I went looking for other code that looked up the proc of a predicate from
its arguments' modes, to use this code as an example of how to do the same.
Especially code at the same stage of the compiler, in case that was
relevant.  I found add_pragma_foreign_proc in add_foreign_proc.m and saw the
comment there.  My understanding is that if the proc is declared with:

    :- pred foo(arg1::in(I)) is det.

But that this pragma was used with a different inst variable.
    
    :- pragma require_tail_recursion(foo(in(Inst)), [warn]).

That I and Inst do not match, even though they may be unified.  And that I
had to use a predicate like get_procedure_matching_declmodes_with_renaming
to find the matching procedure, while taking issues like this into account.

In add_foreign_proc.m there was an XXX saying "We should probably also check
that each pair in  the renaming has the same name."  I don't have enough
information to understand the issue that it's referring to, and I'm not sure
the original author does either, since they left an XXX comment.  I copied
the comment (admittedly a cargo-cult thing to do).  I forgot to revise it
before posting it for review.

I still don't know, and don't know what to read, to determine if this is a
genuine concern and needs fixing, or if the XXX can be deleted.  For now I
will add more information including referring to the correct place in
add_foreign_proc.m.

> 
> Just in case the comment IS relevant:
> 
> It is not clear that add_foreign_proc refers not to a predicate
> but to add_foreign_proc.m, and in any case, directing people to a whole module
> is not *that* useful.
> 

add_pragma_foreign_proc in add_foreign_proc.m, line 342.

> > +        % Put them together.
> > +        (
> > +            MaybeProc = ok1(Proc),
> > +            (
> > +                MaybeOptions = ok1({WarnOrError, Option}),
> > +                PragmaType = pragma_require_tail_recursion(
> > +                    pragma_info_require_tail_recursion(Proc, WarnOrError,
> > +                        Option)),
> 
> This does not handle the suppress_tailrec_warnings case.

That's a constructor for a different type, require_tailrec_info from
hlds_pred.m  This type is pragma_info_require_tail_recursion from
prog_item.m

This feels a bit awkward to me, with two types tracking the same
information.  One for the pragma in the parse tree and one for the
information from the pragma in the HLDS.  Is there a better way to do this?
has something similar been done before?

Likewise the follow up patch tracks the same information, using the
require_tailrec_info type, in the MLDS.


> > +                MaybeIOM = ok1(iom_item(item_pragma(
> > +                    item_pragma_info(PragmaType, item_origin_user, Context,
> > +                    SeqNum))))
> > +            ;
> > +                MaybeOptions = error1(Errors),
> > +                MaybeIOM = error1(Errors)
> > +            )
> > +        ;
> > +            MaybeProc = error1(ProcErrors),
> > +            (
> > +                MaybeOptions = ok1(_),
> > +                MaybeIOM = error1(ProcErrors)
> > +            ;
> > +                MaybeOptions = error1(OptionsErrors),
> > +                MaybeIOM = error1(ProcErrors ++ OptionsErrors)
> > +            )
> > +        )
> > +    else
> > +        Pieces = [words("Error: wrong number of arguments in"),
> > +            pragma_decl(PragmaName), words("declaration."), nl],
> > +        Spec = error_spec(severity_error, phase_term_to_parse_tree,
> > +            [simple_msg(Context, [always(Pieces)])]),
> > +        MaybeIOM = error1([Spec])
> > +    ).
> > +
> > +:- pred parse_pragma_require_tail_recursion_options(list(term)::in,
> > +    maybe(warning_or_error)::in,
> > +    maybe(require_tailrec_option)::in,
> > +    maybe1({warning_or_error, require_tailrec_option})::out) is det.
> 
> This signature cannot handle the "none" option.
> 
> I think you need a separate "have we seen 'none'?" argument.

It's in require_tailrec_option.  This is misleading and it'd be nice to fix
it.  I can fix it pending feedback on whether the two types from the pragma
above can be reconciled.

One problem with the current code, is that if the user gives [warn, none] it
is not reported as an error.

>
>

You had a fair amount of feedback on the documentation of the
self_or_mutual_recursion and self_recursion_only options.  I've re-written
that part.  I re-ordered the description of these options so that
self_recursion_only is described after self_or_mutual_recursion which allows
me to explain how it is more restrictive.  I've also moved a remark to
outside the list.  So it's easier to review it if I paste it a-new.

@c @item self_or_mutual_recursion                  
@c Allow the recursive calls to be self or mutually recursive.
@c The compiler will generate warnings or errors for recursive calls that are
@c not tail calls (and not later followed by a recursive call that @emph{is} a
@c tail call).         
@c This is the default.                            
@c This option is incompatible with @samp{self_recursion_only} and @samp{none}.
@c                          
@c @item self_recursion_only                       
@c Require that all recursive calls are self-recursive.
@c In addition to @code{self_or_mutual_recursion},
@c this option causes the compiler to generate a warning or error
@c when a mutually recursive call is a @emph{tail} call, even if it can
@c optimize the tail call.
@c Some backends can optimize self recursion but not mutual recursion,
@c or mutual recursion is less efficient.
@c This option can be used to alert the programmer of code that isn't tail
@c recursive on these backends.
@c This option is incompatible with @samp{self_or_mutual_recursion} and
@c @samp{none}.
@c 
@c @end table
@c
@c Note that the compiler cannot analyse recursion across module boundaries
@c or through higher order calls.
@c Therefore inter-module and higher order calls are considered to be
@c non-recursive.

This makes me wonder should there be an option such as optimized_recursion_only
So that the errors are raised when the call cannot be optimised, regardless of
mutual/self recursion.  We would probably want to keep the
self_recursion_only option, as it allows the compiler to reject mutual
recursion which it has optimised but that optimisation is still not as fast
as self-recursion (like my proposed hlc change).

> > + at c This option is incompatible with @samp{self_or_mutual_recursion}.
> > + at c 
> > + at c @item self_or_mutual_recursion
> > + at c Allow the recursive calls to be self or mutually recursive.
> > + at c The calls must not be mutually recursive over module boundaries or through
> > + at c higher order calls.
> > + at c This option is incompatible with @samp{self_recursion_only}.
> > + at c 
> > + at c @end table
> > + at c 
> > + at c This pragma has no effect when @samp{--optimize-tailcalls} is disabled
> > + at c or on the Erlang backend.
> > + at c Erlang provides last call optimisation itself.
> 
> Instead of "1, 2a. 2b.", make the sentence structure "1. 2a, 2b.", like this:
> 
> This pragma has no effect with @samp{--no-optimize-tailcalls}.
> It also has no effect when generating Erlang code,
> because the Erlang implementation itself implements last call optimisation.

> This is course begs the question: what happens to recursive calls that
> aren't tail calls? Isn't the option supposed to warn about them?

It does warn about those. but only when (MLDS specific so far) the
--optimize-tailcalls option is given, otherwise the relevant compiler pass
won't be executed.  When I realized this I didn't change it, I reasoned that
the point of disabling an optimisation, especially one that's always on, is
because you want to make the compilation faster at the expense of the
program's runtime, and that if the compiler spent time checking for
tailcalls, it might as well perform tail call optimisation.

Alternatively when --no-optimize-tailcalls is given we could run the
analysis only if --warn-tail-recursion or a pragma is given, respectively for
the whole module or single procedures.  This seems like overcomplicating
things.

> 
> > + at c Issuing the pragma more than once for the same predicate or function, or a
> > + at c mode off that predicate or function, will cause undefined behaviour.
> 
> Why not guarantee to catch that?
> 

Only that I wrote the documentation after the code, and just described what
it did.  I will fix the implementation.

Thanks.


-- 
Paul Bone