Re: Mut. Recurs. in Ada9X w/o Breaking Encaps.? (LONG)

[jgv@swl.msd.ray.com (John Volan)]

Hmm.  I guess when I started this thread, I didn't really make it clear exactly
what I was asking for.  Let me see if I can explain it better, taking the
expression "a picture is worth a thousand words" to heart (but keeping the
thousand words, too :-)  (And there's a side-issue or two in this...)

THE IDENTITY/INTERFACE/IMPLEMENTATION TRICHOTOMY
------------------------------------------------

If I were to draw a Rumbaugh-oid Object Model depicting a requirements
analysis of the original problem I posed, it might look something like this
(highly, highly, schematized):

                        +----+  A1,2  +----+
                        | C1 |--------| C2 |
                        +----+        +----+

Two classes, related to each other by a single one-to-one association.

Additionally, I stated that the functional requirements of the problem demanded
that this association be traversable in both directions.  So, as one possible
design to satisfy these requirements, I proposed making both classes 
"responsible" for the association, by having them point to each other:

                        +----+        +----+
                        | C1 |        | C2 |
                        | o2--------->|    |
                        |    |<---------o1 |
                        +----+        +----+

Not the only possible solution, but a reasonable one.

This solution entails a cyclic dependency between the two classes.
I very much wanted to preserve the notion of 1 Package = 1 Class, but cyclic
dependency presents a dilemma in Ada.  You cannot, of course, have two packages
whose interfaces (specifications) both import ("with") each other.  You
can have their *implementations* (package bodies) import each other's 
interfaces, no problem, but the interfaces themselves can't be mutually 
dependent.

But I realized that, in terms of object-oriented classes, it wasn't really a
matter of having *interfaces* import each other.  To define the interface of one
class you don't *really* need to know the whole interface of the other class.  
All you really need to establish is that the other class *exists*, and that you
can express the *identities* (pointers, let's say) of objects of that other 
class.  In other words, you only need to "forward declare" the other class.  
Once that's done, you can get on with declaring the type and the subprogram
specs for your class.  It's only when you get around to the *implementation* 
(package body) of your class that you really need visibility to the interface 
of the other class.  I really see this as a three-tier system of dependencies
comprising class identity, class interface, and class implementation.  I call
this the "Identity/Interface/Implementation Trichotomy" (is there already
another term for this out there...?)

              +-------------------+           +-------------------+
              | C1 Class Identity |<--_   _-->| C2 Class Identity |
              +-------------------+    \ /    +-------------------+
                                        X
              +-------------------+    / \    +-------------------+
              |    C1 Class       |___/   \___|    C2 Class       |
              |    Interface      |<--_   _-->|    Interface      |
              +-------------------+    \ /    +-------------------+
                                        X
              +-------------------+    / \    +-------------------+
              |        C1         |___/   \___|        C2         |
              |      Class        |           |      Class        |
              |  Implementation   |           |  Implementation   |
              +-------------------+           +-------------------+

                       (Where -----> indicates dependency)

So my original question was:  How can you do this with Ada 9X packages and
tagged types?  Of course, Ada packaging directly supports only two tiers of 
this trichotomy: interface and implementation.  However, using abstract tagged 
types and safe downcasting, I was able to come up with a scheme to simulate 
this three-tier idea, which I outlined it a couple posts ago.  (It's not 
without its costs, mind you.  Maybe there's a better way to do this.  If anyone
can come up with one, I'd really appreciate it!)

(Interestingly enough, I think Eiffel implicitly supports this trichotomy.
At least, as far as I can tell (not actually having programmed in Eiffel) it
looks like you can have two class texts that mention each other in a way
that generates a cyclic dependency.  Anyone out there in Eiffel-land care to
comment?)

Now, I grant you, if it were only a matter of a couple of classes and a single 
association, it would be perfectly reasonable to argue that these classes are
so intimately related that they really form a single irreducible abstraction.
If this were all there were too it, then, yes, you might as well couple both
of these classes within a single package, and forget about decoupling them
from each other.  Other folks on this thread have proposed various schemes,
all very elegant and workable, that seem to me to share this common assumption.
Even where great pains are taken to reduce the coupling to an abstraction,
and hide it away in private parts, the coupling is still there.  Well, maybe
that's okay.

But what if two classes and one association wasn't all there was to it?  
What if, instead of this:

                        +----+  A1,2  +----+
                        | C1 |--------| C2 |
                        +----+        +----+

the requirements picture was really more like *this*:

                      `                 '
                       `               '
                         \            /
                        +----+     +----+
                  - - --| C7 |-----| C8 |             .     '
               +----+   +----+     +----+    '  `     .    '             '
        - - ---| C6 |__   |       /     \   '    `    .   '            '
               +----+  \  |  ____/      |  /       \  |  /            /
                        \ | /           | /         \ | /            /
          +----+  A5,1  +----+  A1,2  +----+  A2,3  +----+  A3,4  +----+
    - - --| C5 |--------| C1 |--------| C2 |--------| C3 |--------| C4 |-- - -
          +----+        +----+\       +----+        +----+        +----+
               \         /  \  \_____/__              |             |
                \       /    \      /   \             .             .
                 \+----+      \+----+    +----+       .             .
            - - --| C9 |-------| C10|----| C11|--- - - -
                  +----+       +----+    +----+       .
                     |          /  \       |
                     .         '    `      .
                     .        '      `     .

(Imagine this semantic network spreading out beyond the edges of your screen :-)
I gave up trying to label every association, but I think you get the picture.)

Let's assume that the nature of the application requires being able to traverse
*all* these binary associations in either direction.  What do we do now?  What
if there are dozens of classes in the model?  Hundreds?  Do we say: "Well, then,
if these classes are *all* so tightly related, then we must declare *all* of 
them in a single package."  And, based on the common software-management 
practice of 1 Package = 1 Engineer, do we also say, "Our requirements model
is bound to change continuously over the course of this project.  Therefore,
we shall have the maintainer of this very important package (upon which all
else depends) work very hard to keep it up-to-date.  Very, _very_ hard.
Moreover, let's also keep him busy making sure all the other packages in the
system recompile successfully every time he changes his package." :-)

(Note to Dave Weller:  Is it appropriate at this point for me to shudder
uncontrollably? ;-)

Okay, you might argue John's just being paranoid, real-world applications are
never all *that* complex.

But perhaps someday they will be.  Perhaps some already are, but they're just
not being done in Ada.

You might argue that even if the semantic network for a problem domain were
really that complex, you shouldn't have to worry that much about mutual 
dependency because real-world applications never demand all *that* much
bi-directional traversal.

But perhaps someday they will.  Perhaps some already do, but they're just not
being done in Ada.

Well, I for one want to be able to tackle them, without a lot of pain, in _Ada_!

(Gosh, I began to sound like GA there for them moment ... no offense, GA!  :-)

--------------------------------------------------------------------------------

IN THE "ON THE OTHER HAND" DEPARTMENT
-------------------------------------

Alright, as I already said, the design I proposed is not the only possible one.
Instead of making either or both of the two classes responsible for the
association:

                        +----+        +----+
                        | C1 |        | C2 |
                        | o2--------->|    |
                        |    |<---------o1 |
                        +----+        +----+

we could place the responsibility for the association entirely within a third
component:

                            +--------+
                            | A(1,2) |
                  +----+    |        |    +----+
                  | C1 |<-----o1  o2----->| C2 |
                  +----+    |        |    +----+
                            +--------+

This "association" package would probably contain some kind of dual hash table,
mapping C1-pointers to C2-pointers, and vice versa. With good modern hashing
techniques, lookups can be quite efficient.  Not as fast as a single pointer
dereference, but "good enough" (O(1) time complexity, amortized).  The nice
thing about this solution is that it totally decouples the classes from having
to know anything about the association.  Adding new associations to a model
has very little ripple effect, if any.  Moreover, this kind of thing is a prime
candidate for writing generically.  Given the nature of my premise (lots
of classes, lots of associations) such a generic would get a *lot* of reuse.

(Thanks to Matt Kennel for reminding me of this scheme.)

Ultimately, this seems to be an excellent way to go -- but does anybody
see any problems with this?  How about if an object instance (of any class)
needs to be deleted?  If the object itself has no knowledge of the associations
it participates in, who is going to make sure that all of these "association
tables" will be notified of that particular object's disappearance?  More
generally, consider any event, affecting an object's state, that also requires
traversing its associations, to propagate that event to other objects.  If the
object itself is not going to be responsible for doing that ... then who,
precisely, will?

Hmm ... maybe an object class *can* know about its associations after all:
What if the body of the class package imported the association package ...?
Hmmm ... got to give this more thought ...

-- John Volan

--------------------------------------------------------------------------------
--  Me : Person := (Name                => "John Volan",
--                  Company             => "Raytheon Missile Systems Division",
--                  E_Mail_Address      => "jgv@swl.msd.ray.com",
--                  Affiliation         => "Enthusiastic member of Team Ada!",
--                  Humorous_Disclaimer => "These opinions are undefined " &
--                                         "by my employer and therefore " &
--                                         "any use of them would be "     &
--                                         "totally erroneous.");
--------------------------------------------------------------------------------