Re: SOLVED! Decoupled Mutual Recursion Challenger

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

jmartin@oahu.cs.ucla.edu (Jay Martin) writes:

>>But this would still require the compliation of both spec and "representation"
>>parts before you could compile anything that depended on the package.
>>Totally revamping the package scheme just to increase the eligence of 
>>a boundary case (especially when there are reasonable workarounds) is
>>unproductive.

>>Mark Biggar
>>mab@wdl.loral.com

>I don't think that removing implementation details from the spec
>is a boundary case.  Note that I wrote that I thought a 
>representation part was too excessive an extension. I was just
>putting it out as an interesting idea taking separation of packages
>to an extreme.

Here, I agree with Mark Biggar.  The workaround (introducing another
level of indirection and hiding the actual object-structure type in
the package body) is a perfectly reasonable solution that gives you
exactly what you need, and it is preferable to a major change in the
language definition.  (It also happens to be similar to the way this
would be solved in C++.)  You could even combine this with a strategic
use of private child units to give you something similar to your
"package representation" construct.

>But I don't feel that package "forwards" are excessive (should be
>minimally easy to implement) and it allows the programmer to directly
>express what he wants to do.

Don't underestimate the complexities involved here.  Your "package
forward" idea is essentially identical to the "package abstract"
concept I suggested a while back (although my proposal didn't require
any new Ada reserved-words :-).  When I presented the idea of "package
abstracts", I at least considered some of the issues they raise:

1. Is a package abstract an optional feature, or are you compelled to
   precede every package spec with a package abstract?  If optional,
   how do you distinguish a package spec that has a preceding abstract
   from one that does not?  Or are we creating a situation analogous to
   the Ada83 problem of an "optional body for a bodiless package spec"?

2. How do you distinguish a "with"-clause that only imports a package
   abstract from one that imports the whole package spec?

3. Can a package-with-abstract be generic?  If so, where does the generic
   clause go?  How do you instantiate such a beast?  What impact does this
   have on the whole generic contract scheme?

4. This is much too late for 9X, and has to be left for 0X, if it goes
   anywhere at all.  Even if all the difficulties can be ironed out, is
   this feature worth the added compiler complexity, when there are
   reusable workarounds that already effectively extend the language?

>One point that I am making is that the
>Ada compilation scheme of compiling into a library in dependency
>order in a complete fail-safe way is not inherently incompatable with
>direct support for mutual recursion of objects.  This scheme is 
>inherently better than the brain-dead method of simple source code 
>insertion with every include file's code surrounded by "ifdefs" using
>preprocessor variables to prevent multiple inclusions. 

Violent agreement here! :-)

>  Mutual recursion is common from my experiences with Ada and other
>object oriented languages.  An example is: 

[snip description of a class X and a manager class which points to
class X, but class X also needs a pointer back to the manager class
because an X needs to notify its manager about certain events]

I agree, this is a common situation.

Back to Mark Biggar:

>>This is going back to a "One True Way" of OOP again.  What's so ugly about:

>>package Forward_X is
>>    type X_Parent is abstract tagged null record;
>>    type X_Ptr_Type is access all X_parent;
>>end Forward_X;

>>Especially when supported bu generics like John is proposing.

>I found the complexity of John's method alittle overwhelming and was
>turned off by the use of unchecked_conversion and generics.  

Hmmm ... in reality, I don't think my "decoupling-via-generics"
technique is any more complex than the "decoupling-via-inheritance"
technique.  Perhaps I was a bit too thorough in spelling out how my
technique worked and how you could use it, and that might have given
the impression of greater complexity.  But I think, if you actually
work out a complete example using either technique, you will see a
similar degree of complexity.  (In fact, you [Jay Martin] did flesh
out an example of decoupling-via-inheritance later in your post, and
you make the point that it seems pretty complex.)

In fact, in actual usage, I believe my decoupling-via-generics scheme
turns out to be *less* complex than the decoupling-via-inheritance
scheme.  There's less code that an end-user has to write to introduce
the "forwarding" declaration for a class, because it's just an
instantiation of a reusable generic package.  More to the point, my
technique avoids the "inheritance collision" problem (competing usages
of inheritance interfering with each other), because it divorces the
decoupling issue from inheritance.  Thus, my technique reserves
inheritance for its most "customary" use: supporting
generalization/specialization relationships from the problem domain.
No intervening levels of abstract types intrude to clutter this up, so
the resulting code is easier to understand.

Jay, why were you turned off by the use of generics?  Personally, 
I think generics are very elegant and powerful tools for solving a
lot of programming problems (especially thorny ones like this).
I tend to think a lot of people overlook the power of generics
when they program, and this is unfortunate.

As for the use of Unchecked_Conversion, realize that that was just one
of several possible ways of *implementing* my technique.  My generic
Identity package attempts to support the notion of "opaque identity"
in a completely abstract way: From an end-user's perspective, the
Identity.Value type is just a "black box".  It's just this private
type that can somehow be translated "magically" into some pointer type
which the user can define at a later time.  How the Identity.Value
type is actually implemented is completely immaterial, as long as it
works.

I could have waved my hands here, leaving everybody twisting in the
wind as to exactly how to implement this private type.  But I felt
obligated to provide at least one possible implementation.  True, I
started off with Unchecked_Conversion, and that wasn't very "pretty",
but at least it was hidden away as an implementation detail.  It's
"under the hood," so to speak, so whether it's pretty or not doesn't
matter to the clients of the abstraction.  (Look under the hood of
your own car.  Is what you find there "pretty"?  Even if it isn't,
does it matter to you when you're behind the wheel?)

But there are many other possible implementations, each involving
different degrees of portability, balanced against different
fine-tunings of the generalness of the generic contract.  In fact, one
of those possible implementations exploits *inheritance* to implement
the decoupling!  The Identity.Value type could be derived from a
class-wide "Universal.Pointer" type that designates objects of a
"Universal.Object" type.  All participating object types have to be
derived, directly or indirectly, from that Universal.Object type, but
this is not an unreasonable restriction.  That way, the translations
between "opaque" Identities and "transparent" Pointers can exploit
type-casting operations (including "narrowing" and "widening") that
are totally type-safe and portable.  But remember that this use of
inheritance is completely encapsulated as an implementation detail
inside the Identity package.  So, in particular, it does *not* result
in "inheritance collision."

>I posted
>a global variable solution as sort of a joke.  

Well, we'll leave it at that ... :-)

>And I am not persuaded
>by the idea of putting everything in the same package. 

Nor am I.  Thus my twisting of Robb Nebbe's "door-through-a-wall"
analogy: If you have only two buildings that people need to go
between, it might seem practical at first to simply break down the
intervening walls and merge the two buildings, rather than go to the
trouble of installing doors.  But carry that strategy out to an entire
city and what do you have?  One huge building with no walls anywhere?
(Note: Even shopping malls and skyscrapers have walls inside them.
More to the point, try to imagine a skyscraper without *floors*! :-)

>Using tagged types looks like the best way. 

I disagree, I think generics are the best way to achieve decoupling.

>But I have qualms about using
>abstract types for this purpose because abstract type doesn't really
>represent an dynamic abstract type but it represents a workaround
>trick. Its a type we can put in the spec so we can pass it in and
>then type convert it to the proper type.

I agree entirely here.  Moreover, I object to
decoupling-via-inheritance because of its "collision" with the more
"customary" use of inheritance.  But if a solution must use some
"workaround" that requires a "trick", isn't it a nicer to distill the
workaround to its essential abstraction, and then hide the
"trickiness" of it as an implementation detail, as I do with my
Identity generic?

>Every new Ada9x programmer
>will have to butt his head up against this problem and then learn this
>ugly trick (or idiom (nicer)).  This makes the language harder to learn
>and less elegant. 

Hmm... beauty (and ugliness) is in the eye of the beholder.  I kind of
agree with you that decoupling-via-inheritance is rather "ugly", but
I'd shy away from using that as an argument against it as a technique.
Other folks may reasonably complain that such an argument is based on
subjective taste and not on sound engineering reasoning.  But I've
already objected to decoupling-via-inheritance along other lines that
are not purely subjective: The use of inheritance to do decoupling can
"collide" with the use of inheritance for problem-domain
generalization/specialization.  This can be seen most clearly in any
situation that constitutes my "Challenge": wherever a class and *one
of its own subclasses* has a mutually-recursive relationship.

Personally, I think my solution of decoupling-via-generics is quite
elegant ... but of course, I'm bound to think that! :-)

>Lets look at the example:

[snip example showing use of decoupling-via-inheritance technique]

>All in all this method seems to have alot of programming and conceptual
>overhead.  Also there will probably have to be a section in every
>decent Ada9x programming book explaining this method.
>                                                     w
>Jay

Yes, this "learning-curve" is a drawback of the
decoupling-via-inheritance technique.  For that matter, it's also a
drawback of my decoupling-via-generics technique.  Even a concept such
as "package forwards" or "package abstracts" would present a certain
amount of complexity that would need to be learned and understood.  In
fact, even if you give up on decoupling entirely, and just put your
mutually-recursive types in the same package, you still have to deal
with using incomplete type declarations to forward declare at least
one of the types.

So how much of this learning-curve is due to the nature of these
various solutions, and how much to the nature of the problem itself?
Isn't the whole idea of mutual recursion itself a tricky one to grasp,
regardless of how it's rendered in a programming language?  The only
way to "simplify" it as a programming issue would be to *obscure* the
issue, the way Eiffel or Smalltalk do: Instead of explicitly stating
dependencies, you just mention other classes anywhere in your class's
interface or implementation, and the programming environment takes
care of any nasty mutual recursions for you, whether you realize that
they're there or not. 

Is it better for a programmer to be *unaware* of these situations?  Or,
supposing the original programmer is fully aware of the mutual recursions,
wouldn't it be a good idea to make those mutual recursions very obvious
to other folks who have to read the code (such as future maintainers)?
At least, with my decoupling-via-generics technique, you have a clear
signpost indicating that decoupled mutual recursion may be present.
Whenever you see a context clause that says

    with Identity;

or later, wherever you see something like:

    with Employee_Identity;
    with Office_Identity;
    ...

you know that mutual recursion lies ahead.

-- 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.");
--------------------------------------------------------------------------------