[m-dev.] Array modes

[Zoltan Somogyi]

On Sat, 25 Oct 2014 15:32:10 +1100, Mark Brown <mark at mercurylang.org> wrote:
> 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.

I have long thought that having insts that are not bound to a specific type
is a bad idea. I would even support a change in the language to require
each inst definition to say what type it is for.

> So can bogus constructors be made a formal part of the language?

I would need to see a more compelling use case than this.

> 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.

Arrays of unique terms and N-dimensional arrays for N>1 may look like
they have similar requirements, but they don't. For one thing, operations
on array slices apply only to the latter.

There are several languages out there that have only 1D arrays,
and implement 2D, 3D etc arrays as nested 1D arrays. Depending
on the language, these usually have problems such as

- dictating implementation choices (e.g. dope vectors), which often
turn out to be unsuited to high performance on modern hardware,

- posing semantic problems, such as an inability to ensure that
different rows have the same number of columns.

> 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:

We already have array2d.m in the library. If it is missing some
functionality you need, adding it to array2d.m to should be simpler
than using nested 1D arrays. Similarly, I wouldn't object to adding
array3d.m., if needed.
 
> 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.

You can control what goes into the manual, but you cannot control
how people speak. Even the same person will often use "unique"
to mean different things in different contexts.

In the original research on mode systems that inspired Mercury,
I talked about types representing AND-OR trees: types (the OR nodes)
representing choices between function symbols, and function symbols
(the AND nodes) having several arguments. Each mode says,
which each OR node: is it the caller or the callee that makes the
choice here?

Uniqueness can be thought of the same way: it is a choice that
can be made separately for each OR node. The choice is: is the memory
occupied by the arguments of the chosen function symbol referred to
through more than one pointer? Or, in the presence of alias tracking,
can the compiler can see all the pointers?

If the type tree you are talking about has only one OR node,
then the notions of "all OR nodes are unique" and "this OR node
is unique" coincide. If it is has two or more OR nodes, they don't.

Zoltan.