[mercury-users] Mode checking if-then-else vs less readable switch

[Zoltan Somogyi]

On 25-Aug-2011, Andrew Ross <andrew at bubblehelicopter.com> wrote:
> plus(A, B) = Z :-
>     ( if
>         A = const(IntA),
>         B = const(IntB)
>     then
>         Z = const(IntA + IntB)
>     else
>         Z = var("A + B")
>     ).

> plus(A, B) = Z :-
>     (
>         A = const(IntA),
>         (
>             B = const(IntB),
>             Z = const(IntA + IntB)
>         ;
>             B = var(_),
>             Z = var("A + B")
>         )
>     ;
>         A = var(_),
>         Z = var("A + B")
>     ).

> Should the mode checker be able to infer that the if-then-else version
> of plus satisfies the declared modes?

Determinacy inference and checking are undecidable problems, as can be
trivially shown by an if-then-else whose condition is asked to test
whether a Turing machine halts. As such, questions like the above do not
and cannot have a technical answer; the line between determinism that the
compiler can prove and determinism that it cannot prove is effectively
arbitrary, chosen by the compiler implementors.

The pragmatic answer is that in the second of these definitions, the
compiler can see and keep track of the bindings of both variables A and B.
In the first, it cannot do so directly. If it tried to do indirectly,
it would have to record, in both directions, information such as "the failure
of the condition means that A = const(...) implies B != const(...), which
in turn implies B = var(...)". The second of these steps is not possible in
many cases, since many variables have types with more than two function
symbols, and the first step itself, recording linkages between the binding
states of different variables, would hugely complicate mode analysis, which
is already the most complicated part of the Mercury compiler.

Overall, the answer has to be "no", unless you have funding for someone
to work on this problem for about two years.

Zoltan.
--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------