[mercury-users] Self-referential data structures

[Fergus Henderson]

On Tue, Nov 25, 1997 at 06:12:37PM +1100, Warwick HARVEY wrote:
> 
> 	% Stores may be used to implement cyclic data structures such as
> 	% circular linked lists, etc.
> 
> 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).
[...]
> Solution 3:
> Modify the implementation of stores to allow you to obtain/reserve a
> reference for a node before you actually insert it.

The problem with this solution is this: what happens if you attempt to
dereference a reference before you have specified a value for it?

> Solution 2:
> Modify the implementation of stores to provide a dummy reference*.

This has a similar problem: what happens if you attempt to dereference
the dummy reference?

These solutions also have another problem: now you have to document for
every routine that takes a reference as a parameter what happens if the
argument reference does not yet have a value or is the dummy reference.

Both of these solutions are easy enough to implement.
For example, I have appended an implementation of solution 2.

I suppose that despite its disdavantages, solution 2 is the least worst...
unless anyone has any better ideas, I guess we'll include this in the
next release.

Index: store.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/store.m,v
retrieving revision 1.8
diff -u -u -r1.8 store.m
--- store.m	1997/11/20 05:59:20	1.8
+++ store.m	1997/11/25 14:45:17
@@ -75,6 +75,12 @@
 :- pred store__set_mutvar(mutvar(T, S), T, store(S), store(S)).
 :- mode store__set_mutvar(in, in, di, uo) is det.
 
+	% return a `null' mutvar.
+	% Note: any attempt to get or set the value stored in a null mutval
+	% will result in undefined behaviour (typically a segmentation fault).
+:- pred store__null_mutvar(mutvar(T, S), store(S), store(S)).
+:- mode store__null_mutvar(out, di, uo) is det.
+
 /* 
 The syntax might be nicer if we used some new operators
 
@@ -111,6 +117,12 @@
 :- pred store__new_ref(T, ref(T, S), store(S), store(S)).
 :- mode store__new_ref(di, out, di, uo) is det.
 
+	% null_ref(Ref): return a `null' reference.
+	% Note: any attempt to dereference such a null reference
+	% will result in undefined behaviour (typically a segmentation fault).
+:- pred store__null_ref(ref(T, S), store(S), store(S)).
+:- mode store__null_ref(out, di, uo) is det.
+
 	% ref_functor(Ref, Functor, Arity):
 	% Given a reference to a term, return the functor and arity
 	% of that term.
@@ -211,6 +223,13 @@
 
 :- pragma c_code(init(_S0::uo), will_not_call_mercury, "").
 
+:- pragma c_code(null_mutvar(Mutvar::out, S0::di, S::uo),
+		will_not_call_mercury,
+"
+	Mutvar = 0;
+	S = S0;
+").
+
 :- pragma c_code(new_mutvar(Val::in, Mutvar::out, S0::di, S::uo),
 		will_not_call_mercury,
 "
@@ -234,6 +253,13 @@
 ").
 
 %-----------------------------------------------------------------------------%
+
+:- pragma c_code(null_ref(Ref::out, S0::di, S::uo),
+		will_not_call_mercury,
+"
+	Ref = 0;
+	S = S0;
+").
 
 :- pragma c_code(new_ref(Val::di, Ref::out, S0::di, S::uo),
 		will_not_call_mercury,


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