[GOODIE] BinaryRelation

Richard A. O'Keefe ok at cs.otago.ac.nz
Mon Mar 31 22:13:39 UTC 2003


"Jason Rogers" <jacaetevha at fast-mail.org> asked:
	Pardon my ignorance, since most of this is out of my league.
	Doesn't this make garbage collection essentially ineffective?

In fact this is one of the reasons why a BinaryRelation object as a
separate object *not* "owned" by the things it relates is a good idea.

Suppose you have a binary relation R and two objects (x,y) related by R.
Suppose this is implemented by data structures inside x and y,
so that x owns a set which has y as an element, and y owns a set which
has x as an element.  Then you have a cycle linking x and y, which is
bad news for a reference counting garbage collector.  For other kinds
of garbage collector, it need not be a problem.  However, it does mean
that as long as x remains interesting, y will be retained, even if the
relationship itself ceases to be of interest.  To work around that,
Squeak has WeakSet, but we don't for some reason have WeakIdentitySet
and WeakPluggableSet.

Note that BinaryRelation is a class.  *A* binary relation is just an
object, and there isn't the slightest necessity for it to be held in
a global variable or class variable.  When the relation R is held in
a BinaryRelation object, there are no cycles:  R points to x and y,
but x does not point to R or to y, and y does not point to R or to x.
This means that using BinaryRelation objects is *better* from a
garbage collection point of view.  x and y remain interesting as long
as either they would have been interesting anyway, plus as long as the
relation R remains interesting, just like they would hang around if they
were in a Set or Array.

	There's also some flag about coupling being raised in the back
	of my mind, but I am not yet able to articulate it.

Here again, the point is that a BinaryRelation *reduces* coupling.
Suppose we are interested in the relationship
    (dog is-registered-in city)
Without a binary relation object, the Dog class is coupled to the City
class and vice versa.  With a binary relation object, we can relate objects
of any two classes *without* coupling them.

Obviously *some* object has to accept the resposibility of registering
and unregistering dogs, but it doesn't have to be a Dog object or a City
object; it can be an AnimalRegistry object which either has or isa
BinaryRelation.  (Probably 'has'; it would also need to keep track of
(dog has-registration-number n), and we certainly don't want numbers to
have to know about dogs.)

Everything I have said about the merits of binary relations applies to
n-ary relations as well.  However, Smalltalk already has one kind of
set-of-pairs (Dictionary) so adding another kind of set-of-pairs
(BinaryRelation) which loosens the restrictions of Dictionary is the
smallest extension which lets you do relations at all.



More information about the Squeak-dev mailing list