[mercury-users] Non-backtrackable references and di modes.

[Fergus Henderson]

On 29-Sep-1999, Ralph Becket <rbeck at microsoft.com> wrote:
> How far away are nested unique modes?

Good question.

> Which brings me to wonder how nested unique modes will work in practice.

Another good question ;-)

> Say I have a hash table implemented using open addressing with double
> hashing (that is, each entry has a unique id which is used to detect
> hashing collisions and when a collision is detected a secondary hashing
> scheme is used to place the new entry).  It's going to look something like
> this:
> 
> :- type hash_id == array(id).
> :- type hash_entry == array(entry).
> :- type hash_table
> 	  ---> ht(hash_id, hash_entry, int /* Number of occupants. */).
> 
> Now, hash_ids and hash_entrys are going to be unique objects.  Therefore,
> it seems, a hash_table must also be a unique object.  Now, if I have some
> hash_table in X and do
> 
> 	  X = ht(HashId, _, _)
> 
> to get at the hash_id field, surely I've destroyed the uniqueness of that
> field?

The idea is that the compiler will keep track of "definite aliases".
For the code above, the compiler will know that `HashId' is aliased
with the first field of `X'.  If you then call e.g.

	array__set(HashId, 0, some_id, NewHashId)

then this will be allowed.  The mode of the first argument of
array__set is `di' (i.e. `unique -> dead'), which requires that the
argument be unique on input, but that's OK, since you only HashId to
array__set.  If you had passed both `X' and `HashId' to array__set,
then neither would be treated as unique for that call.  But so long as
you only pass one of them, it's OK.  The compiler will update the insts
of both of the aliases variables to reflect the results of the call.

Similarly, if you instead call

	array__lookup(HashId, 0, SomeId)

that will be allowed, and the inst of the first argument for array__lookup
on entry will be `unique', so mode analysis will select the `ui'
(i.e. `unique -> unique') mode rather than the `in' (i.e. `ground -> ground')
mode, and thus on exit from that call `HashId' will still be `unique'
(with aliases) rather than `ground'.  The compiler will remember that `HashId'
and the first field of `X' are aliases, but as soon as `HashId' goes
out of scope, `X' will be truly `unique' again.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------