[mercury-users] Self-referential data structures

[Fergus Henderson]

On Tue, Nov 25, Warwick HARVEY wrote:
> 
> What I'm trying to do is (basically) a circular list.  [...]
> The problem (for me) seems to be getting the first element inserted into the
> store.  My node data type includes fields for references to the previous and
> next elements, but for the first element, I cannot know what these are until
> I have inserted the element (since they are references to itself).
[...]
> I can think of several solutions; I'd welcome any additional input from
> others.

I have just thought of another solution.  We could provide a new
procedure in the `store' module to create a circular element. 
This procedure would take as an argument a function which when
given a reference (mutvar) to type T produces a value of type T.

	:- pred new_cyclic_mutvar(func(mutvar(T, S)) = T, mutvar(T, S),
							store(S), store(S).
	:- mode new_cyclic_mutvar(in, out, di, uo) is det.

Because we use a unique mode for the store, it is guaranteed that the
function won't have access to the store; thus it is safe to pass the
function a reference (mutvar) to uninitialized storage, because without
access to the store, the function can't dereference it.

This avoids the need for null references (and hence the need to
document for every procedure taking a reference what happens if
the reference is null).  It avoids the need to use a maybe(T) type.
And it avoids any possibility of dereferencing null or uninitialized
references (with potential inefficiencies due to runtime checking,
or potential for undefined behaviour if runtime checking is not mandatory).

The only disadvantage of this solution is that it may make things harder
for the garbage collector.  There's no problems for conservative GC,
but it would need some special handling for precise GC.

Still, I'm inclined to prefer this solution to the previously
described alternatives.  Comments?

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