[mercury-users] Managing a collection of unique objects

[Fergus Henderson]

Warwick HARVEY wrote:
> The problem is that I want to manage a collection of these (unique) circular
> lists.  Fine, I thought, just bung 'em in one of the many ADTs already
> provided (in this case a map seemed most appropriate).  The problem with
> sticking them in a map (or any of the other ADTs in the standard library)
> is, of course, that it doesn't preserve the uniqueness of inserted objects.

>From the LIMITATIONS file in the top-level directory of the Mercury
distribution:

 | The current implementation does not yet completely implement the
 | Mercury language.  The main limitations of the current implementation
 | are the following:
 | 
 | * We do not allow definite aliasing in the mode system.
 |   Without this, partially instantiated modes are unusable, 
 |   and so are nested unique modes :-(

This is the main reason that none of the ADTs in the standard library preserve
uniqueness.  Doing so would require nested unique modes, which currently
don't work.  Andrew Bromage is working on remedying this problem.

> The solution seems to be to create an ADT capable of managing unique
> objects properly.  Something along the lines of a store would probably be
> sufficient to fill most needs; one could then put the store references into
> a map or some other management structure.

Yes, that's a good idea.

> There seem to be two approaches
> possible for preserving uniqueness in such an ADT.  One is to force the
> object to be deleted from the ADT every time it is referenced.  If one
> wanted the object to be continued to be managed, the updated version would
> need to be re-inserted.

The current store doesn't provide any way of deleting an object.
(Instead, objects just get garbage collected when there are no more
references to them.)  To allow deletion, you would have to use
something like a store of maybe(T), so that doing attempting to
dereference a deleted reference could return `no'.

> The other option is to disallow direct access to
> managed objects, but to allow appropriate predicates to be applied to them,
> with the updated object replacing the original in the data structure.  Of
> course, these options aren't mutually exclusive, and both could be provided
> by an implementation.

Yep.  The first option is more primitive -- it would be straightforward
to implement the second one given the first, albeit perhaps not with
maximal efficiency.

> So...  Any comments on the problem or its solutions?

Well, just to flesh the solution out a little...
you need to add the following, either to the `store' module,
or in a new module.

%-----------------------------------------------------------------------------%
%
% uniq mutvars
%

	% uniq_mutvar(T, S):
	% a mutable variable holding either a unique value of type T,
	% or no value, in store S
:- type uniq_mutvar(T, S).

	% create a new unique mutable variable,
	% initially holding no value.
:- pred init_uniq_mutvar(mutvar(T, S), store(S), store(S)).
:- mode init_uniq_mutvar(out, di, uo) is det.

	% create a new unique mutable variable,
	% initialized with the specified value
:- pred new_uniq_mutvar(T, mutvar(T, S), store(S), store(S)).
:- mode new_uniq_mutvar(di, out, di, uo) is det.

	% retrieve the value stored in a given mutable variable,
	% if any, and (to ensure uniqueness) update the store
	% so that the variable no longer holds a value.
:- pred fetch_uniq_mutvar(mutvar(T, S), maybe(T), store(S), store(S)).
:- mode fetch_uniq_mutvar(in, uo, di, uo) is det.

	% set the value stored in a given unique mutable variable
:- pred set_uniq_mutvar(mutvar(T, S), T, store(S), store(S)).
:- mode set_uniq_mutvar(in, di, di, uo) is det.

%-----------------------------------------------------------------------------%

> Can somebody with a
> better understanding of unique modes and the state of the current Mercury
> implementation tell me whether it would be possible to write such an ADT in
> a "clean" fashion?

The above could be implemented in Mercury using the existing store
interface, in a "clean" fashion except for `fetch_uniq_mutvar'.
For `fetch_uniq_mutvar', you would need a way to promise that a value
is unique.  An `unsafe_promise_unique_value' predicate can be done in
a fairly trivial but not clean way using the C interface.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   WWW: <http://www.cs.mu.oz.au/~fjh>  
Note: due to some buggy software and a (probably accidental)
denial-of-service attack, any mail sent to me between
	Tue Nov 25 20:00:00 UTC (6am Wed, local time)
and	Wed Nov 26 06:00:00 UTC (4pm, local time)
may have gone into the bit-bucket.  Please re-send it.