Re: SOLVED! Decoupled Mutual Recursion Challenger

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

bobduff@dsd.camb.inmet.com (Bob Duff) writes:

>In article <1994Oct17.205244.17450@swlvx2.msd.ray.com>,
>John Volan <jgv@swl.msd.ray.com> wrote:
>>
>>I guess the question really hinges on the meaning of the word
>>"representation".  When you say that two access types may be "stored
>>differently", do you mean that the number of bits used to store an
>>access type can be different, or do you only mean that the *contents*
>>of those bits might be interpreted differently?

>I meant both.  The number of bits can be different, and the meaning of
>those bits can be different.

>>All I really need is the relatively weak guarantee that all access types
>>occupy the same number of bits, i.e.:
>>
>>    A1'Size = A2'Size, for any two access types A1 and A2

>Sorry.  Ada makes no such guarantee.  In practice, you might be able to
>write portable code across *many* (but not all) implementations,
>especially if you're willing to restrict the designated type of the
>access type.  After all, most implementations don't read the phase of
>the moon clock to decide how many bits to use for a give type.

Right, I was kind of figuring that.  In the original "contract" for my
Identity package, I was trying to be as general as possible:

      -- Identity.Translation
      generic
        type Object (<>) is limited private; -- matches any type
        type Pointer is access Object;
      package Translation is ...

But now it looks like this is just too general to be portable.
However, making it this general was just a gratuitous freebie.  I
threw it in because I couldn't see any reason not to -- but now I do
see the reason.  At any rate, there is some room to back off: The
original intent was to be able to "opaquely" store pointers
designating what would (eventually) be tagged record types -- most
likely class-wide types, and most likely only *definite* tagged record
types.  So it would not hurt things very much if wee restricted the
contract to only support pointers designating definite, class-wide
tagged record types:

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

    generic
    package Identity is

      -- Identity.Value
      type Value is private; 

      -- Identity.None    
      None : constant Identity.Value;

      -- Identity.Translation
      generic
               -- Only definite types (no discriminants)
               -- vv 
        type Object is abstract tagged limited private;
                    -- ^^^^^^^^^^^^^^^
                    -- Only tagged types (but any abstract or non-abstract)
        type Pointer is access Object'Class;
                            -- ^^^^^^^^^^^^
                            -- Only access to class-wide types.
      package Translation is

        -- Identity.Translation.To_Pointer
        function To_Pointer (The_Identity : in Identity.Value) return Pointer;
        pragma Inline (To_Pointer);

        -- Identity.Translation.To_Identity
        function To_Identity (The_Pointer : in Pointer) return Identity.Value;
        pragma Inline (To_Identity);

      end Translation;
    
    private -- Identity

      type Void is abstract tagged null record; -- "dummy" designated type
    
      -- Identity.Value
      type Value is access Void'Class;
                 -- ^^^^^^^^^^^^^^^^^
                 -- An access-to-classwide-definite-tagged-type,
                 -- so likely to be implemented the same as other
                 -- access-to-classwide-definite-tagged-types.

      -- Identity.None      
      None : constant Identity.Value := null;
	
    end Identity;

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

(Perhaps an alternate package, say, "Indefinite_Identity", could support
pointers designating classwide indefinite tagged record types.)

In the body of this version of package Identity, we might be able to
get away with doing Unchecked_Conversions.  But I guess even this
might be playing the odds:

>Another implementation I've heard about (from Rational, I think?),
>creates a separate storage pool for every access type, and uses various
>virtual memory tricks to make that efficient.  Access types end up being
>represented in various numbers of bits, I believe.

So, depending on what pools the clients store their tagged types in,
even the above scheme might not turn out to be portable.

[snip]

>I'm not real clear on what you're trying to do, so I don't have much
>useful advice here.  Perhaps Address_To_Access_Conversions would be of
>some help?

I did consider that as a possibility at first, but I was still working
under the assumption (obsolete, I guess) that X'Address = X'Access, or
at least X'Address'Size = X'Access'Size.  Now I would say that using
Address_To_Access_Conversions is a possibility ...  *except*: Looking
more closely at that package, I'm now noticing that the Object_Pointer
type isn't a generic *parameter*.  Rather, it's in the public part of
the package:

    generic
      type Object (<>) is limited private;
    package Address_To_Access_Conversion is
      type Object_Pointer is access all Object;
      ...

In other words, this package provides a *new* access type into which
address values can be converted.  It's *not* providing the capability
to convert some *arbitrary* access type into addresses.  (It's called
"Address_To_Access_Conversions" after all.)  So at this point, I'm not
sure how I could use this to implement the Identity package.  It seems
like the Identity package would have to provide not only the "opaque"
identity type but also the "transparent" Pointer type.  (In my
original formulation, it was the class packages themselves that
provided the Pointer types, along with the Object types.)  But I don't
see how the Identity package could supply the Pointer type as a
visible access type and still keep the opaque identity type private,
if the Pointer type now has to come from an instantiation of
Address_To_Access_Conversions.  This seems like a "chicken and egg"
problem -- which is ironic, since that's precisely the kind of problem
that the Identity package was supposed to solve in the first place!

However, there are other alternatives, as long as we're willing to
impose certain (relatively reasonable) restrictions on the use of the
Identity package.  For instance, the Identity package could assume
that all classes that want to participate in decoupled mutual
recursion have to inherit from some root Universal abstract class:

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

    package Universal is

      -- Universal.Object
      type Object is abstract tagged null record;
      -- or perhaps: abstract new Ada.Finalization.Limited_Controlled
      --               with null record;

      -- Universal.Pointer
      type Pointer is access all Universal.Object'Class;

      -- Universal.None
      None : constant Universal.Pointer := null;

    end Universal;

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

    with Universal;

    generic
    package Identity is

      -- Identity.Value
      type Value is private; 

      -- Identity.None    
      None : constant Identity.Value;

      -- Identity.Translation
      generic
        type Object is abstract new Universal.Object with private;
                    -- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    -- Actual must be some subclass of Universal.Object
                    -- (but may be abstract or non-abstract)
        type Pointer is access Object'Class;
      package Translation is

        -- Identity.Translation.To_Pointer
        function To_Pointer (The_Identity : in Identity.Value) return Pointer;
        pragma Inline (To_Pointer);

        -- Identity.Translation.To_Identity
        function To_Identity (The_Pointer : in Pointer) return Identity.Value;
        pragma Inline (To_Identity);

      end Translation;
    
    private -- Identity

      -- Identity.Value
      type Value is new Universal.Pointer;
                 -- ^^^^^^^^^^^^^^^^^^^^^

      -- Identity.None      
      None : constant Identity.Value := null;

    end Identity;

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

Then the we can implement the Identity.Translation package in terms of
safe "narrowing" and "widening" type conversions:

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

    package body Identity is

      -----------------------
      -- Identity.Translation
      -----------------------

      package body Translation is

        ----------------------------------
        -- Identity.Translation.To_Pointer
        ----------------------------------

        function To_Pointer (The_Identity : in Identity.Value) return Pointer is
        begin
          return Pointer (Universal.Pointer (The_Identity));
                       -- ^^^^^^^^^^^^^^^^^
                       -- Hmm... do I even need this?
        end To_Pointer;   

        -----------------------------------
        -- Identity.Translation.To_Identity
        -----------------------------------

        function To_Identity (The_Pointer : in Pointer) return Identity.Value is
        begin
          return Identity.Value (Universal.Pointer (The_Pointer));
                              -- ^^^^^^^^^^^^^^^^^
                              -- Hmm... do I even need this?
        end To_Identity;

      end Translation;
    
    end Identity;

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

I assume that such type-conversions are totally portable.  

(Are there any holes in this? Does deriving type Identity.Value from
Universal.Pointer get in the way of doing "narrowing" and "widening"?
If it does, we could get around that by implementing the Value type as
a record instead:

      -- Identity.Value
      type Value is
        record
          Its_Pointer : Universal.Pointer;
        end record;

      -- Identity.None
      None : constant Identity.Value := (Its_Pointer => Universal.None);

That way, we're always dealing cleanly with a Universal.Pointer.)

Of course, given this new contract for the Identity package, classes
participating in decoupled mutual recursion would have to inherit from
Universal:

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

    with Universal;
    with Office_Identity;
    with Employee_Identity;
    ...
    package Office is

      -- Office.Object
      type Object is new Universal.Object with private;
                  -- ^^^^^^^^^^^^^^^^^^^^

      -- Office.Pointer
      type Pointer is access all Office.Object'Class;

      -- Office.None
      None : constant Office.Pointer := null;

      -- Office.Translation
      package Translation is new
        Office_Identity.Translation
          (Object  => Office.Object,
           Pointer => Office.Pointer);

      ...

    end Office;

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

This is a bit of a restriction, but not too unreasonable.  In fact,
there may be other reasons for introducing a root Universal class
anyway.  Other object-oriented "infrastructures" often do something
similar.

For instance, consider Bill Beckwith's CORBA IDL-to-Ada9X translation.
That scheme included a "universal" Corba.Ref type and Corba.Object
type, from which all IDL Ref and Object types would be derived.
Unfortunately (IMHO), this scheme achieves decoupled mutual recursion
by exploiting inheritance as the mechanism for decoupling.  I would
argue that such a scheme falls into the trap of "inheritance
collision", where one usage of inheritance (providing alternate
programming-interface views for a single class of real-world entities)
gets in the way of the "customary" use of inheritance (supporting
generalization-specialization relationships between different classes
of real-world entities).

Luckily, I think that this problem can be solved quite neatly by
introducing something very similar to my Identity package.  In that
way, the IDL-to-Ada9X mapping could exploit generics, rather than
inheritance, as the way to achieve decoupled mutual recursion.
Meanwhile, inheritance would still be available for its customary
role in supporting generalization-specialization relationships:

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

    with Ada.Finalization;

    package Corba is

      -- Corba.Object
      type Object is tagged ...

      -- Corba.Ref
      type Ref is tagged ...

      -- Corba.Nothing
      Nothing : constant Ref;

      -- Corba.Identity
      generic
      package Identity is

        -- Corba.Identity.Value
        type Value is private;

        -- Corba.Identity.None
        None : constant Identity.Value;

        -- Corba.Identity.Translation
        generic
          type Ref is new Corba.Ref with private;
        package Translation is
          function To_Ref (The_Identity : in Identity.Value) return Ref;
          function To_Identity (The_Ref : in Ref) return Identity.Value;
        end Translation;

      private -- Corba.Identity

        -- Corba.Identity.Value
        type Value is new Corba.Ref with null record;

        -- Corba.Identity.None
        None : constant Identity.Value := Identity.Value (Corba.Nothing);

      end Identity;

    private -- Corba

      ...

    end Corba;

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

    with Corba;
    package Egg_Identity is new Corba.Identity;

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

    with Corba;
    package Chicken_Identity is new Corba.Identity;

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

    with Corba;
    package Rooster_Identity is new Corba.Identity;

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

    with Corba;
    with Egg_Identity;
    with Chicken_Identity;

    package Egg is

      -- Egg.Ref
      type Ref is new Corba.Ref with null record;

      -- Egg.None
      None : constant Egg.Ref := Egg.Ref (Corba.Nothing);

      package Translation is new 
        Egg_Identity.Translation (Ref => Egg.Ref);

      -- Egg.Hatch_Chicken
      function Hatch_Chicken (The_Egg : in Egg.Ref) 
        return Chicken_Identity.Value;

    end Egg;

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

    with Corba;
    with Chicken_Identity;
    with Egg_Identity;
    with Rooster_Identity; -- Rooster will (eventually) inherit from Chicken

    package Chicken is

      -- Chicken.Ref
      type Ref is new Corba.Ref with null record;

      -- Chicken.None
      None : constant Chicken.Ref := Chicken.Ref (Corba.Nothing);

      package Translation is new
        Chicken_Identity.Translation (Ref => Chicken.Ref);

      -- Chicken.Lay_Egg
      function Lay_Egg (The_Chicken : in Chicken.Ref) 
        return Egg_Identity.Value;

      -- Chicken.Mate_With_Rooster
      procedure Mate_With_Rooster
        (The_Chicken : in Chicken.Ref;
         The_Rooster : in Rooster_Identity.Value);

      -- *Ahem*.  Well, maybe these operations a more appropriate for 
      -- class *Hen* (which, like Rooster, would be a *subclass* of 
      -- Chicken ;-).  But bear with me -- I'm just trying to show an 
      -- example of the Decoupled Mutual Recursion Challenge that I 
      -- originally posed.

    end Chicken;

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

    with Chicken;  -- Rooster inherits from Chicken
    with Rooster_Identity;
    with Chicken_Identity;

    package Rooster is

      -- Rooster.Ref
      type Ref is new Chicken.Ref with null record;

      -- Rooster.None
      None : constant Rooster.Ref := Rooster.Ref (Chicken.None);

      -- Rooster.Translation
      package Translation is new
        Rooster_Identity.Translation (Ref => Rooster.Ref);

      -- Rooster.Mate_With_Chicken
      procedure Mate_With_Chicken
        (The_Rooster : in Rooster.Ref;
         The_Chicken : in Chicken_Identity.Value);

      -- *Ahem*.  Well, maybe this ought to be Mate_With_Hen, but you
      -- get the idea ... :-)

    end Rooster;

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

    with Corba;
    with Chicken;

    package Egg.Impl is

      -- Egg.Impl.Object
      type Object is new Corba.Object with ...

      -- Egg.Impl.Lay_Chicken
      function Hatch_Chicken (The_Egg : in out Egg.Impl.Object'Class)
        return Chicken.Ref'Class;

    end Egg.Impl;

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

    with Corba;
    with Egg;
    with Rooster;

    package Chicken.Impl is

      -- Chicken.Impl.Object
      type Object is new Corba.Object with ...

      -- Chicken.Impl.Lay_Egg
      function Lay_Egg (The_Chicken : in out Chicken.Impl.Object'Class)
        return Egg.Ref'Class;

      -- Chicken.Impl.Mate_With_Rooster
      procedure Mate_With_Rooster
        (The_Chicken : in out Chicken.Impl.Object'Class;
         The_Rooster : in     Rooster.Ref'Class);

    end Chicken.Impl;

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

    with Chicken.Impl; -- Rooster implementation inherits from Chicken impl.

    package Rooster.Impl is

      -- Rooster.Impl.Object
      type Object is new Chicken.Impl.Object with ...

      -- Rooster.Impl.Mate_With_Chicken
      procedure Mate_With_Chicken
        (The_Rooster : in out Rooster.Impl.Object'Class;
         The_Chicken : in     Chicken.Ref'Class);

    end Rooster.Impl;

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

Bill Beckwith, if you're listening, what do you think?

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