Symmetrical Reference

Ward -- I've looked around on the web, and I can't find a pattern that deals with maintaining symmetric object relationships. Like, if A contains B, and B knows its container, what's a pattern that ensures referential integrity, so that we don't get A contains B, but B thinks it's contained by C? -- SteveMetsker

Steve -- I know the pattern you're talking about, but I don't know if it has been written up. The patterns mailing list is a good way to poll a lot of people. Try sending your request there and then read the list for a week or two. I'm going to see if I can write the pattern off of the top of my head. Then I will put the correspondence on WikiWikiWeb to see what happens there. Good luck with your search. Tell me what you find. Regards. -- WardCunningham

Pattern: SymmetricalReference

Context: Two collaborating objects maintain a relationship for some period of time.

Problem: Both objects must be aware of any changes in their relationship so that assumptions made about symmetry remain true.

Solution: Adjust the public accessing methods of both objects so as to keep collaborators informed. Use private protocol between the collaborators to distribute updates. Such protocol is simplest when one object is known to be responsible and the other delegates to it.

Use: Smalltalk-80 Models and Controllers work in pairs.

Alternative: An AsymmetricalReference? can sometimes have accessing protocol that makes it appear symmetrical. A RelationshipObject can take all responsibility for modeling dynamic collaboration.

This solution looks similar to the HalfObjectPlusProtocol (HOPP) pattern's solution, although I think the context/forces are different. -- DavidHooker

i'm beginning to believe that HalfObjectPlusProtocol is a pattern language, HoppPatternLanguage, of which this pattern is a part. --JimCoplien

My take on this is that maintaining the integrity of object links lies outside, and in a sense above, either object. For example, if containers contain items, making sure that containers and items match lies outside the encapsulated interests of either containers or items. In this case, we want to make sure that when Container c contains Item i, that i isContainedBy c. The integrity of these links seems to lie outside of either Container or Item. I'm inclined to introduce a Judge pattern, whose job it is to ensure the consistency of such links. In a system, there is one Judge singleton needed for each relation pair that is maintained. Only a Judge can 'marry' a Container and an Item.

- SteveMetsker

Come on, guys! This isn't hard! You do it every day, and it doesn't require extra objects or complicated code. I usually teach it when I teach Composite, though I always try to point out that it is much more generic than Composite.

I'm going to explain what Ward said. It is obvious that people did not understand it. In my opinion, Ward's mistake was that he was too abstract. A single example would have explained his point better.

Suppose a Component knows the Composite it is in. Composites always know their Components, but sometimes Components know their Composites, too. Then the Component will have a "container" instance variable, and Composite will have a "components" instance variable.

The problem is that an error might cause A to be a component of B, but B is *not* the container of A. In other words, the back pointer is messed up. How can you make sure this never happens?

The standard solution is to make sure that there is only one operation for changing the pointers. Actually, there needs to be two, one for adding a component and one for removing the component. This operation is usually on the Composite, i.e. you send addComponent: to the Composite to add a component and removeComponent: to remove it. The Composite must inform the Component that it has a new container. The code looks like this:

Container>>addComponent: aComponent

components add: aComponent. aComponent container: self

Container>>removeComponent: aComponent

components remove: aComponent. aComponent container: nil

Component>>container: aComposite

container isNil | aComposite isNil
ifFalse: [self error: 'circular reference'].
container := aComposite

The only problem with this solution is that the container: message should be private, and there is no way to make it private. Of course, this is not a problem in C++. In fact, if you make the container variable protected, you don't even have to add an accessing function for it, because the Composite can access it directly.

There *are* times when you want to make an object to represent a relationship, but the simple way is the right way 95% of the time.

-RalphJohnson

I think there's an important pattern here, because as Ralph points out:

- We do it every day. - Good teachers teach it.

However, I think I see two problems.

Problem 1, Multithreading Requires a Single Mutex Semaphore.

In a multithreaded environment, it may be critical that the lines of code Ralph's example execute without interruption:

components add: aComponent. aComponent container: self

One way to ensure that these lines execute in critical section is to make a singleton (which I call a Judge) responsible for these lines. Initialize the judge with a mutex semaphore, and have the judge execute the above instructions as a critical block. This is an effective way to ensure that all container/component marriages pass through one mutex semaphore. We don't want every container to have its own semaphore, we only need one, held by a singleton who stands outside and above all the containers -- the judge.

Problem 2, True Symmetric Relations.

Ralph's example illustrates the case Ward mentions, where 'one object is known to be responsible and the other delegates to it.' Not all relation pairs allow this.

The relations we're talking about, such as 'contains' and 'isContainedBy' are normally inverses. For integrity, we want to ensure that whenever aRb, then b(R inverse)a. For example, whenever a contains b, b isContainedBy a.

In some relations, R and (R inverse) are the same. This is called a 'symmetric' relation. Marriage is an example, where the relation isMarriedTo is the same as its inverse. If a isMarriedTo b, then b isMarriedTo a, if our links are correct. A Person class might have a spouse attribute, and the following setting method:

Person>>spouse: aPerson

        spouse := aPerson.

We can't add the line:

aPerson spouse: self

or we'll get an infinite loop. We can solve this problem, but we need a different approach than the one used for nonsymmetric relations, such as in Composite. An advantage of a Judge pattern is that it works for both symmetric and nonsymmetric relations, in pretty much the same way.

If we always use Judge singletons to marry the links of objects related by relation R and its inverse,

We shed light on an everyday pattern.

We help developers to avoid problems with messed up back pointers.

We can use the same pattern for both symmetric and nonsymmetric relations.

We allow related links to be connected in critical section.

-- SteveMetsker

I wrote up a version of this pattern (along RelationshipObject and a couple others) for TOOLS Pacific last year. A revised version was reviewed at EuroPlop as part of the BasicRelationshipPatterns? [1].

I may be confused, but I don't think you need a singleton for this --- won't the implicit DoubleDispatch and associated change in the message name break any symmetry? If a semaphore is shared, what can a Judge do that a Person can't?

Or have I missed something?

JamesNoble

There are several assumptions and issues showing up here.

1 - it's easy, as Ralph said; 2 - there is no 'it' in this discussion, there are several 'it's being discussed under the same heading; 3 - there is no 'pattern' to ask for, because there are different patterns for different situations, Steve and Ralph are talking about different situations, hence different patterns; 4 - you should adopt a simplifying naming convention in all but the simplest case.

I have seen at least two papers written on, roughly, "Modeling Relationships". One was an IBM Tech Report, if you have an excellent research library you can search for it and find it. James' paper may be easier to find.

What is making this simple discussion not converge is that how you implement a relationship differs greatly depending on the requirements of your situation, i.e., the forces acting on you.

In case I, the simplest case, you make one-way knowledge. Object A knows Object B but not vice versa. I have met people who simply refuse to put a two-way relationship in their system because they believe it is impossible to maintain its integrity over the life of the system.

In case II, you decide you must have two way links, and to guarantee consistency, you make only one published access point. You tell object A to add object B, then A tells B that its new partner is A in an unpublished (you can't make it private) method. Ward wrote this case, and Ralph commented on it. I have adopted the convention, to make my code easier to understand, that I always prefix the unpublished method with 'note'. So I would write

components add: aComponent. aComponent noteContainer: self

to remind strongly that that noteContainer is not a recommended public method. The 'note' prefix becomes especially useful in case III.

In case III, you decide you want to be able to change the relationship from either end - examples being parent/child, hubby/wife or employer/employee. Maybe you don't like having a programming rule that says one always has to tell the employer first. That may not be natural, or whatever grounds you choose for needing two-way access. Then life gets very complicated if you don't have a convention like the 'note' prefix (see 'spouse' example above). In the hubby/wife relation, you get 4 methods:

  Man>>wife: w  --does-> self noteWife: w.  w noteHubby: m.
  Woman>>hubby: m --does-> self noteHubby: m.  m noteWife: w.

  Man>>noteWife: w  --does-> wife := w.
  Woman>>noteHubby: m --does-> hubby := m.

Note that this also fixes the recursion problem in the spouse example

  Person>>spouse: p --does-> self noteSpouse: p. p noteSpouse: self.
  Person>>noteSpouse: p --does-> spouse := p.

Case IV is the one Steve is interested in, in which you decide you don't want to play those games, so you introduce a relationship object, some call it an associative object, Steve calls it a judge object. Neither A nor B know about the other, only the judge knows about both.

And now you start over again, asking whether A and B should know the judge as well. There are another 3 cases.

All in all, there are 4**3 combinations of who knows whom, at least 10 of which are potentially interesting, and of which 4 designs are commonly implemented (one-way, two-way, judge knows both but niether knows judge, judge knows both and both know judge). Which you use depends on what your particular requirements and philosophy are. There is, therefore, no "pattern" to ask for, or there are 4 or 10 or 64 patterns to ask for. or there is one pattern with the table of 64 solutions to ask for. Steve is right, Ralph and Ward are right, James is right - and you are all talking about different things, so the conversation won't converge.

The teaser for me out of this is, what does this situation say about patterns? I regularly find myself in such a situation, where there is one entry point to a pattern and many possible solutions, depending on the particular strengths of the various forces. I personally feel uncomfortable about using the word 'pattern' in such a case, because I somehow want to use that word for more stable, universal patterns, not just an entry into a table of solutions.

cheers,

--- AlistairCockburn

What it says to me is approximately what Christopher Alexander says in that quote from him Jim supplied in FormalMethodsAndPatterns. --- AlistairCockburn

ThankYou! I'm not a big fan of patterns, and this was the first time I've found some useful ideas for programming by examining them. This pattern has shown up many times when I've designed initialisation of large object systems (I use a lot of production pipelines, where every object knows its immediate neighbours, and the components from the pipeline should be possible to change at will).

I used to make the relationships artificially hierarchic and form the pipeline in initialisers: for example, a protocol_handler's initialiser just gets a connection_handler as an argument and not vice versa, and calls connection_handler's notification method about the new protocol_handler. But then I reverted these to use a function that is not member of either, i.e. connect_protocol_connection, which calls the notification method of both. Much cleaner, IMO. I wouldn't use an object as this "neutral" part, though.

Nowadays that I mostly do functional programming I tend to use CoRoutines for the same stuff. But reading this has been very enlightening in any case.

By the way, in the elaboration above it was implicitly assumed that in the Judge case, A and B don't know each other directly. But this need not be the case; they can very well know each other directly, and use the Judge only to update their relationship. It might even be worthwhile to use a global Judge for all maintained relationships.

-- PanuKalliokoski

---

That quotation reminds me of this. -- MartineDevos

"... the greatest power and depth, comes about under circumstances where the uniqueness of design is allowed to rule -- and where the slight uniqueness that every design starts with, gives way to progressively greater and greater levels of uniqueness, as the centers and symmetries take on more and more meaning, and the configuration develops in character. Of course, this happens under conditions of considerable freedom. It will tend not to happen, when we are copying, too closely some known pattern, or some previously worked out design. It happens, more often, where the uniqueness of a particular fragment of a design takes off, develops and leads into unknown and unexpected directions." -- ChristopherAlexander in his RugBook

What it says to me is that SymmetricalReference is comprised of several (64?) more specific patterns, and provides some guidance about how to select among them. -- TomStambaugh

matain referential integrity in the single address address is simple, like RalphJohnson's solution.

But what if it involves serialization issues?

---Tao

[side discussion moved to PatternsOfPatterns]