Path: utzoo!attcan!uunet!snorkelwacker!usc!wuarchive!cs.utexas.edu!yale!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: C's sins of commission
Message-ID: <65419@lanl.gov>
Date: 10 Oct 90 23:00:52 GMT
References: <chl.655461731@m1>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 63

From article <chl.655461731@m1>, by chl@cs.man.ac.uk (Charles Lindsey):
> [...stuff about graphs with aliased nodes and aliased references to them...]
> Now with pointers, this is easily implemented. But with recursive data types
> it is impossible (at least in any straightforward way - can anyone tell me how
> to do this in a functional language).

What?  Where in the definition of recursive data structures is aliasing
prohibited?  C.A.R. Hoare carefully discussed not allowing aliasing in
recursive structures in "Structured Programming".  The fact that he had
to go to so much extra trouble indicates that the usual definition of
recursive data _does_ allow aliasing.

Now, I don't agree with Hoare that aliasing should be illegal.  But then,
I'm not as zealous as he (nor as clever - he _may_ be right).  Still, I
don't think that aliasing should be a default capability either.  I think
that allowing aliasing should require extra and explicit declarations to
clearly state what variables are allowed to be aliased what what objects.
For example:

   Recursive type graph         !recursive type with a float value and
      float :: value            !two links in each node
      graph :: left, right
   end type graph

   aliased graph :: a, b        !two vars which can be aliased to each
				!other and to their descendents

   aliased graph :: c, d        !ditto, EXCEPT that these can't be aliased
				!to the others (or vice-versa).

   graph :: e                   !this is just a binary tree, it can't
				!be aliased to any other nodes of to
				!its own descendents.

...
   a = graph(1.0,graph(2.0,null,null),null)
				!this assigns a graph with two nodes to
				!variable 'a'.  The type constructor
				!also allocates space.

   b <- a                       !'<-' is the shallow copy assignment.
				!The two variables are now aliased.

   c = a                        !'=' is the deep copy assignment.  'c'
				!is now a disjoint copy of all of 'a'.
				!If 'a' had cycles or aliased elements,
				!the corresponding elements of 'c' would
				!also be aliased - but 'a' and 'c' would
				!still be disjoint

   d <- b                       !ILLEGAL.  'd' and 'b' were in separate alias
				!alias declarations so they can't alias each
				!other.

You might argue that this is so nearly identical to pointers that it
doesn't make any difference.  But, this yields much greater control over
the meaning of the program.  Aliasing is only present when aliasing is a
required part of the algorithm and only those elements which _need_ to
be aliased are allowed to be.  Try to get that amount of control from
pointers.  Finally, there are no 'dereference' and 'address-of'
operators to misuse, forget, or confuse.

J. Giles