[m-dev.] Array modes

[Mark Brown]

Hi Peter,

On Fri, Oct 24, 2014 at 4:06 PM, Peter Wang <novalazy at gmail.com> wrote:
> Hi,
>
> What do you think about changing the modes in the array module along the
> lines shown in the attached file?  Note that we don't need to use
> constrained inst vars; they can be replaced by `ground' and `unique'.

The `unique' versions would be useful for arrays of arrays. For three
dimensions, `uniq_array(unique)' would be what you want, and so on. In
practice you could get away with a small number, but constrained inst
vars would be a neater and more general solution. They would also
allow arrays of predicates to be conveniently used. See further
comments below, though.

BTW, I noticed your recent changes to better support constrained inst
vars (I don't presently subscribe to the reviews list, but I scan the
archives from time to time). The changes looked the right idea to me
(good work!), but I can review it in more detail if anyone is still
interested.

>
> The first change is to bring back the bogus insts while (hopefully)
> avoiding the problem that caused them to be removed in commit 67bcaf3.
> See also
> http://www.mercurylang.org/list-archives/developers/2007-February/014642.html
>

I think these "bogus" constructors are really useful for foreign types
that act as containers for Mercury terms, of which arrays are one
example, so I don't agree with disallowing them entirely as is
suggested in that thread. But the objection, which is reasonable, is
that what the insts are saying isn't really true, and the compiler
quite rightfully draws its bad conclusions from the faulty premises it
is given.

So can bogus constructors be made a formal part of the language? The
meaning of them would be that they represent foreign constructors that
can contain zero or more Mercury terms matching each argument inst.
The compiler would need to avoid making assumptions about the
determinism of unifications involving these constructors, but nothing
special would need to be declared - just treat a inst's constructor as
a bogus constructor whenever it doesn't match a constructor from a
visible type. If any of an inst's constructors is a bogus constructor
then they all must be (that would catch typo errors).

If this is practical to implement I think it would be a better
solution to do this, and go back to the original array inst
definition. Also think of a better name than bogus.

>
> The [intended] modes in the existing array.m don't make sense to me,
> e.g.
>
>     :- pred lookup(array(T), int, T).
>     %:- mode lookup(array_ui, in, out) is det.
>
> At the end of the call, the array is not unique in its elements as the
> third argument shares a reference with one of its elements.

Excellent point. Although, as Zoltan explained, the mode is correct,
this interface is simply not suitable for arrays of arrays or other
unique terms, for the reasons you mention. Anybody using it like that
will have to rewrite their code if the array module is changed to use
the proposed modes.

I would suggest adding appropriate support for arrays of arrays as
soon as possible, even though it isn't needed in practice right away.
For example:

        % replace(I, NewT, OldT, !Array):
        %
        % Replace the (possibly unique) element OldT with NewT at index I.
        % This can be used to update a unique element without losing the
        % uniqueness of the other elements, by temporarily replacing it with
        % a dummy value.
        %
    :- pred replace(int, T, T, array(T), array(T)).
    :- mode replace(in, in, out, array_di, array_uo) is det.
    :- mode replace(in, di, uo,
        uniq_array(unique) >> dead, free >> uniq_array(unique)) is det.

        % lookup2(Array, I, J) = Elem:
        %
        % Lookup an element in a 2D ragged array.
        %
    :- func lookup2(array(array(T))::in(uniq_array(uniq_array)),
int::in, int::in)
        = (T::out) is det.

Similarly for lookup3, etc, if desired. A more general solution again
requires inst vars:

        % extract_array(I, Elem, !Array):
        %
        % Lookup an element which is itself an array. The element is replaced
        % with an empty array by the call, so it will generally need
to be set again
        % after it is finished with. This can be applied repeatedly to
look up arrays
        % of any dimension.
        %
    :- pred extract_array(int, array(T), array(array(T)), array(array(T))).
    :- mode extract_array(in, free >> uniq_array(I),
        uniq_array(uniq_array(I)) >> dead, free >>
uniq_array(uniq_array(I))) is det.

>
>     :- pred set(int, T, array(T), array(T)).
>     :- mode set(in, in, array_di, array_uo) is det.

This would need more modes but could otherwise stay the same.

Talking of inst 'unique', it seems to be confusing whether this refers
a term whose nodes are all unique, or a term whose top node is unique
and all other nodes are ground. The reference manual says:

    Mercury also provides “unique” insts ‘unique’ and ‘unique(…)’ which are like
    ‘ground’ and ‘bound(…)’ respectively, except that they carry the additional
    constraint that there can only be one reference to the corresponding value.

I read this as saying that only the top node is unique. But it used to
be commonly understood as meaning that all nodes are unique, and that
is what is implemented in compiler/inst_match.m. Which is the correct
meaning of 'unique'?

I think it ought to mean just that the top node is unique. The
implementation change could be something as simple as the diff below
(not fully tested). The only purpose I can think of for the other
meaning of `unique' is as the mode for unsafe_promise_unique, but
maybe that's another thing better done with inst vars anyway:

    :- pred unsafe_promise_inst(T::in, T::out(I)) is det.

Opinions?

Cheers,
Mark.

diff --git a/compiler/inst_match.m b/compiler/inst_match.m
index 8c551cc..075d464 100644
--- a/compiler/inst_match.m
+++ b/compiler/inst_match.m
@@ -700,9 +700,7 @@ inst_matches_initial_4(InstA, InstB, MaybeType, !Info) :-
         InstB = ground(UniqB, none),
         compare_uniqueness(!.Info ^ imi_uniqueness_comparison, UniqA, UniqB),
         inst_results_bound_inst_list_is_ground_mt(InstResultsA, BoundInstsA,
-            MaybeType, !.Info ^ imi_module_info),
-        compare_bound_inst_list_uniq(!.Info ^ imi_uniqueness_comparison,
-            BoundInstsA, UniqB, !.Info ^ imi_module_info)
+            MaybeType, !.Info ^ imi_module_info)
     ;
         InstA = bound(Uniq, InstResultsA, BoundInstsA),
         InstB = abstract_inst(_,_),
@@ -734,7 +732,7 @@ inst_matches_initial_4(InstA, InstB, MaybeType, !Info) :-
         compare_uniqueness(!.Info ^ imi_uniqueness_comparison, UniqA, UniqB),
         bound_inst_list_is_complete_for_type(set.init,
             !.Info ^ imi_module_info, BoundInstsB, Type),
-        ground_matches_initial_bound_inst_list(UniqA, BoundInstsB, yes(Type),
+        ground_matches_initial_bound_inst_list(shared, BoundInstsB, yes(Type),
             !Info)
     ;
         InstA = ground(UniqA, HOInstInfoA),
@@ -1168,9 +1166,7 @@ inst_matches_final_3(InstA, InstB, MaybeType, !Info) :-
         InstB = ground(UniqB, none),
         unique_matches_final(UniqA, UniqB),
         inst_results_bound_inst_list_is_ground_mt(InstResultsA, BoundInstsA,
-            MaybeType, !.Info ^ imi_module_info),
-        bound_inst_list_matches_uniq(BoundInstsA, UniqB,
-            !.Info ^ imi_module_info)
+            MaybeType, !.Info ^ imi_module_info)
     ;
         InstA = ground(UniqA, HOInstInfoA),
         InstB = any(UniqB, HOInstInfoB),
@@ -1184,7 +1180,7 @@ inst_matches_final_3(InstA, InstB, MaybeType, !Info) :-
         unique_matches_final(UniqA, UniqB),
         inst_results_bound_inst_list_is_ground_mt(InstResultsB, BoundInstsB,
             MaybeType, ModuleInfo),
-        uniq_matches_bound_inst_list(UniqA, BoundInstsB, ModuleInfo),
+        uniq_matches_bound_inst_list(shared, BoundInstsB, ModuleInfo),
         (
             MaybeType = yes(Type),
             % We can only do this check if the type is known.