[m-users.] Using one out parameter to compute another

[Zoltan Somogyi]

On Fri, 23 Aug 2019 15:24:23 -0400, Philip White <philipwhite at cedarville.edu> wrote:

> Below is my code:
> 
> :- pred parse_statement(src::in,
>                         ast_statement::out,
>                         ps::in, ps::out) is semidet.
> parse_statement(Src, Statement, InitialPS, OutPS) :-
>   current_offset(Src, Start, InitialPS, _),
>   current_offset(Src, End, OutPS, _), <--- error is right here.
>   Range = range(Start, End),
>   (
>     if
>       parse_identifier(Src, Identifier, InitialPS, IdentPS),
>       punct("=", Src, _, IdentPS, PunctPS),
>       parse_term(Src, Term, PunctPS, TermPS)
>     then
>       OutPS = TermPS,
>       Statement = definition(Identifier, Term, Range)
>     else
>       parse_term(Src, Term, InitialPS, OutPS),
>       Statement = term(Term, Range)
>   ).
>
> Am I missing some logical error in my code, or is it just a limitation
> of the compiler?

It is a limitation of the compiler.

The compiler *can* delay the code that computes End until OutPS is
bound, but ONLY when this can be done by reordering the conjunction
that contains that goal. In this case, that is not possible, because

- the conjunct in that conjunction that binds OutPS is the if-then-else, and
- that conjunct needs the value of Range, and therefore the value of End,
  as an input.

So from the compiler's point of view, there *is* a circular data dependency
among the conjuncts.

This circularity could be broken if the compiler could delay the computation of End
(and Range) *separately* in each branch of the if-then-else, by putting the two goals
that compute End and Range just before the two goals that construct Statement.
Note that this takes two goals completely OUT of the conjunction that originally
contained them, and puts them into TWO OTHER conjunctions.

The compiler was not written to look for such solutions, for two reasons.

One reason for that is that that worst case big-O complexity of mode analysis is
already pretty bad (though the average case is much, much better), and making it
examine a much larger class of possible code rearrangements would make this
even worse.

The other, more important reason is that the mode checker is already very complex
in the software engineering sense, because it tracks a whole bunch of things
at the same time:

- whether a certain point in the code is reachable,
- how instantiated each variable is at each reachable code point,
- what function symbols each instantiated part of each variable can be bound to
  at each reachable code point,
- whether each instantiated part of each variable represents an unique reference
  to a memory cell at each code point,
- for each instantiated part of a variable that represents a higher order value,
  what the modes of the arguments of that predicate or function are.

(And all that complexity was there before the addition of solver types
to the language, which required mode analysis to consider yet more things.)

This is why getting the mode checker to work was probably the hardest part
of building the compiler. Making it look for this wider class of rearrangements
would have made the task of building it much harder still.

Now that you know this, the fix for you is simple: make by hand the code
transformation that the compiler cannot do automatically.

Zoltan.