Mutually Recursive Data-Structures in ADA

Mutually Recursive Data-Structures in ADA

[Geoffrey Clemm]

I posted this on csnet a couple of times a while back and received no
significant response.  It was suggested that I send it directly to
info-ada@eclb.  If there is a better alternative solution to the one
I am using, I would be very interested in hearing about it.

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

From postnews Sun Jul  7 17:19:36 1985
Subject: Implementing mutually dependent access types in separate packages
Newsgroups: net.lang.ada
Distribution: net

*

Problem :
   I have a large program with data structures whose implementations
   are all mutually dependent.  For example, a "FileHeader" is a structure
   containing a field that is a pointer to a "Parameter", a "Parameter" is a
   structure containing a field that is a pointer to an "Item", and an "Item"
   is a structure containing a field that is a pointer back to a "FileHeader".
   (For a simple example, see section 3.8.1 of the ADA standard).
   
   The desireable implementation would consist of one package for each data
   structure, where a package performs the usual data abstraction principle
   of providing accessing functions while hiding the physical implementation
   of the data structure.

   In the above example, the package for "FileHeader" must provide (amoung
   other things) the type "FileHeaderPtr" (ACCESS FileHeader) and an accessing
   function "FileHeader_Parameter" that takes a FileHeaderPtr as an input
   argument and returns a ParameterPtr.  Similarly for each of the other
   packages.

   Unfortunately, I can find no way of doing this in ADA.  The obvious
   implementation generates a "USE" cycle that is illegal according to
   the language standard (not to mention being rejected by our compiler).

   The only method I can discover for doing this in ADA is to take all
   of the data structure definitions out of their respective packages
   and then clump them together into a single "implementation package".
   All the individual packages then "USE" this implementation package.

   This is very unfortunate for a variety of reasons.  Not the least of
   these is that unless the ADA compiler is very smart (which ours isn't),
   changing the implementation of any data structure causes the re-compilation
   of all the data structures that USE the implementation package.

Question :
   Can anyone come up with a way of leaving the implementation of each
   data structure in its own package, while providing the desired accessing
   functions and not violating the ADA standard ?

Note:
   If one was not required to provide accessing functions of the form
   "FileHeader_Parameter(FileHeaderPtr) RETURN ParameterPtr", there of
   course would be no problem, but these accessing functions are critical.

Geoffrey Clemm

Re: Mutually Recursive Data-Structures in ADA

[Frank Adams]

[Not food]

One possibility would be to remove the access functions from the packages
for the types, and put them in a separate package of their own.  I know this
isn't ideal, but it may be better than the alternatives.

Sorry to send this on the news, but mail didn't make it.

Frank Adams                           ihpn4!philabs!pwa-b!mmintl!franka
Multimate International    52 Oakland Ave North    E. Hartford, CT 06108

Re: Mutually Recursive Data-Structures in ADA

[Doug Bryan]

Geoffrey,

Submitted for your consideration:

  ---------------------
  generic
    type File is limited private;
  package Item_Pac is
    type Item is limited private;

    function Get_File (Of_Item : Item) return File;
    -- other operations...
  private
    type Item is
      record
        F : File;
        -- other data
      end record;
  end Item_Pac;

  package body Item_Pac is
    ...
  end Item_Pac;
  ---------------------
  generic
    type Item is limited private;
  package Parameter_Pac is
    type Parameter is limited private;

    function Get_Item (Of_Parameter : Parameter) return Item;
    -- other operations...
  private
    type Parameter is 
      record
        I : Item;
        -- other data
      end record;
  end Parameter_Pac;

  package body Parameter_Pac is
    ...
  end Parameter_Pac;
  ---------------------
  with Item_Pac, Parameter_Pac;
  package File_Pac is
    type File is limited private;
    type Access_File is access File;

    package Items is new Item_Pac (File => Access_File);
    package Parameters is new Parameter_Pac (Item => Items.Item);

    function Get_Parameter (Of_File : File) return Parameters.Parameter;
    function Get_Parameter (Of_File : Access_File) return Parameters.Parameter;
    -- other operations...
  private
    type File is
      record
        P : Parameters.Parameter;
        -- other data
      end record;
  end File_Pac;

  package body File_Pac is
    ...
  end File_Pac;
  ------------------

Now the users need simply "with" File_Pac to get the operations on all
three abstract data types.  The types need not be limited.  We used
limited types to show that this method should work for any actual
implementations of the types.

what think you?

Doug Bryan            Geoff Mendal
bryan@su-sierra       Mendal%UMich-MTS.Mailnet@MIT-Multics.ARPA
Stanford U.           Lockheed Missiles & Space Company, Inc.

-------

Re: Mutually Recursive Data-Structures in ADA

[Geoffrey M. Clemm]

In article <8509191758.AA23499@UCB-VAX.ARPA> BRYAN@SU-SIERRA.ARPA (Doug Bryan)
suggests to use generic packages to separate the parts of a mutually recursive
data type into separate packages.

I agree that generics allow one to "un-nest" packages, but one of the main
reasons I wanted to separate the mutually recursive data type into separate
packages was to provide for re-compilation efficiency.  In our compiler,
generics are just treated as fancy macros (as far as I can tell), which
means that a generic solution, i.e.

   GENERIC PACKAGE a ... END a;
   GENERIC PACKAGE b ... END b;
   PACKAGE all IS
      PACKAGE my_a IS NEW a;
      PACKAGE my_b IS NEW b;
      ...
      END all;

is no better than

   PACKAGE all IS
      PACKAGE my_a IS ... END my_a;
      PACKAGE my_b IS ... END my_b;
      ...
      END all;

The only way that I can get re-compilation efficiency (i.e. if I modify
one part of the mutually recursive data structure, I only have to recompile
the accessing functions for that part), would be to place them in separate
non-generic packages, i.e.

   PACKAGE my_a IS ... END my_a;
   PACKAGE my_b IS ... END my_b;

And that's what I don't think I can do in ADA.

Geoffrey Clemm

P.S. The reason I am concerned with recompilation efficiency is that
I am doing exploratory programming with a large system, half of which
is accessing functions to data structures that all end up being mutually
recursive.  If I had an efficient validated ADA interpreter I wouldn't care ...