Translate this into Ada ...

Translate this into Ada ...

[Richard Irvine]

Can anyone help with what I imagine is a frequently ocurring problem?

We would like all lists in an application to be read using an iterator
with operations like:

  function  theCurrentItem( theIterator :        Iterator ) return
ItemType;
  function  atTheEnd      ( theIterator :        Iterator ) return
Boolean;
  procedure goToTheNext   ( theIterator : in out Iterator );

Furthermore, since an iterator has to be created for a particular list
and since the implementation of an iterator is dependent on that of the
list 
we would like all list types to have a (constructor) operation like

  function  aNewIteratorFor( theList : List ) return Iterator;

This design decision should apply to all types of list, regardless of
the ItemType and regardless of the implementation of the lists.

How using generics, abstract types (e.g. AbstractList and
AbstractIterator), 
abstract subprograms or any other Ada features can this decision be
expressed? 

I have struggled with this for quite some time without finding a
satisfactory
solution. Any suggestions gratefully received.

Re: Translate this into Ada ...

[Norman H. Cohen]

In article <3219E6E2.2F5@eurocontrol.fr>, Richard Irvine
<Richard.Irvine@eurocontrol.fr> writes:

|> We would like all lists in an application to be read using an iterator
|> with operations like:
|>
|>   function  theCurrentItem( theIterator :        Iterator ) return
|> ItemType;
|>   function  atTheEnd      ( theIterator :        Iterator ) return
|> Boolean;
|>   procedure goToTheNext   ( theIterator : in out Iterator );
|>
|> Furthermore, since an iterator has to be created for a particular list
|> and since the implementation of an iterator is dependent on that of the
|> list
|> we would like all list types to have a (constructor) operation like
|>
|>   function  aNewIteratorFor( theList : List ) return Iterator;
|>
|> This design decision should apply to all types of list, regardless of
|> the ItemType and regardless of the implementation of the lists.

One approach is a generic, each instance of which declares a root
abstract type for collections and a root abstract type for iterators.
The instance declares all of the above operations as abstract
subprograms.

The package in which you declare your list type derives both a new list
type from the root abstract collection type and a new iterator type from
the root abstract iterator type.  It provides concrete subprograms to
override each of the inherited abstract operations.  Since the concrete
collection type and the concrete iterator type are declared in the same
package, the bodies for these operations have access to the
implementations for both concrete types.

Here is a generic template like that I have described:

   generic

      type Item_Type (<>) is limited private;

   package Generic_Abstract_Collections is

      type Collection_Type is abstract tagged private;
      type Iterator_Type is abstract tagged private;

      function New_Iterator_For
         (Collection: Collection_Type) return Iterator_Type'Class
         is abstract;

      function Current_Item (Iterator: Iterator_Type) return Item_Type
         is abstract;

      function At_The_End (Iterator: Iterator_Type) return Boolean
         is abstract;

      procedure Advance (Iterator: in out Iterator_Type) is abstract;

      Iterator_Error: exception;
         -- Raised by Current_Item or Advance invoked with an iterator that is
         --    not currently positioned at an item.
   private

      type Collection_Type is abstract tagged null record;
      type Iterator_Type is abstract tagged null record;

   end Generic_Abstract_Collections;


(New_Iterator_For has a classwide result because it is not permitted to
be a primitive operation of more than one tagged type.)  Here is a sample
application, to a collection of integers implemented as a linked list:


   with Generic_Abstract_Collections;

   package Integer_Lists is

      package Abstract_Integer_Collections is
         new Generic_Abstract_Collections (Item_Type => Integer);

      type Integer_List_Type is
         new Abstract_Integer_Collections.Collection_Type with private;

      type Integer_List_Iterator_Type is
         new Abstract_Integer_Collections.Iterator_Type with private;

      Iterator_Error: exception renames
                         Abstract_Integer_Collections.Iterator_Error;

      -- Concrete subprograms to override inherited abstract subprograms:

      function New_Iterator_For
         (Collection: Integer_List_Type)
         return Abstract_Integer_Collections.Iterator_Type'Class;

      function Current_Item
         (Iterator: Integer_List_Iterator_Type) return Integer;

      function At_The_End
         (Iterator: Integer_List_Iterator_Type) return Boolean;

      procedure Advance (Iterator: in out Integer_List_Iterator_Type);

      -- Other Integer_List_Type operations could be declared here.

   private

      type Cell_Type;
      type Cell_Pointer_Type is access Cell_Type;
      type Cell_Type is
         record
            Value : Integer;
            Link  : Cell_Pointer_Type;
         end record;

      type Integer_List_Type is
         new Abstract_Integer_Collections.Collection_Type with
            record
               First_Cell: Cell_Pointer_Type;
            end record;

      type Integer_List_Iterator_Type is
         new Abstract_Integer_Collections.Iterator_Type with
            record
               Next_Cell: Cell_Pointer_Type := null;
            end record;

   end Integer_Lists;


   package body Integer_Lists is

      function New_Iterator_For
         (Collection: Integer_List_Type)
         return Abstract_Integer_Collections.Iterator_Type'Class is
      begin
         return Integer_List_Iterator_Type'
            (Abstract_Integer_Collections.Iterator_Type with
             Next_Cell => Collection.First_Cell);
      end New_Iterator_For;

      function Current_Item
         (Iterator: Integer_List_Iterator_Type) return Integer is
      begin
         if Iterator.Next_Cell = null then
            raise Iterator_Error;
         else
            return Iterator.Next_Cell.Value;
         end if;
      end Current_Item;

      function At_The_End (Iterator: Integer_List_Iterator_Type) return Boolean is
      begin
         return Iterator.Next_Cell = null;
      end At_The_End;

      procedure Advance (Iterator: in out Integer_List_Iterator_Type) is
      begin
         if Iterator.Next_Cell = null then
            raise Iterator_Error;
         else
            Iterator.Next_Cell := Iterator.Next_Cell.Link;
         end if;
      end Advance;

      -- [Bodies of other Integer_List_Type operations.]

   end Integer_Lists;

Note that the return type of New_Iterator_For is the classwide type for
the root Iterator_Type declared in the generic instance (i.e., the return
type for the version of New_Iterator_For inherited by Integer_List_Type),
not for the derived type Integer_List_Iterator_Type.  However, the
function body returns an Integer_List_Iterator_Type object.

It might be more appropriate to make Iterator_Type limited (since it
represents the state of an in-progress loop iteration, something that it
does not make sense to copy).  In this case, the New_Iterator_For
function should be replaced by a procedure Start_Iteration with an out
parameter of Iterator_Type.  Also, if operations are provided to insert
items in or delete items from a collection, a decision must be made about
the semantics of iterating over a list while it is being updated, and the
implementation of iterators must account for insertions and deletions
during iteration.

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Translate this into Ada ...

[Richard Irvine]

Many thanks to Norman Cohen for his comprehensive 
reply. I certainly learnt something about Ada 95,
namely that the body of the function

> function New_Iterator_For
>   (Collection: Integer_List_Type)
>    return Abstract_Integer_Collections.Iterator_Type'Class;
> 

can return a member of the class rather than something which
is of type Iterator_Type'Class, i.e.

>  type Integer_List_Iterator_Type is
>     new Abstract_Integer_Collections.Iterator_Type with private;

> function New_Iterator_For
>    (Collection: Integer_List_Type)
>    return Abstract_Integer_Collections.Iterator_Type'Class is
> begin
>    return Integer_List_Iterator_Type'
>       (Abstract_Integer_Collections.Iterator_Type with
>        Next_Cell => Collection.First_Cell);
> end New_Iterator_For;
> 

In general one might like to have more than one
iterator for the same collection type, each 
iterator implementing a different traversal
policy but all having the same protocol.

So for example, in the package Integer_Lists
one might want to derive a second concrete
type from Abstract_Integer_Collections.Iterator_Type .
However, the problem arises that the function
New_Iterator_For is a classwide function rooted
at Abstract_Integer_Collections.Iterator_Type 
and as it stands will always return the first
type of iterator, namely Integer_List_Iterator_Type.

A possible solution is the following.
Define a (generic) abstract collection which 
has those operations which do not mention 
iterators.
Define a (generic) abstract iterator.
Define a (generic) concrete collection which
conforms to the abstract collection.
Then, for each iterator type, define a
(generic) package which is a child of
the (generic) concrete collection. 
Each child package can instantiate its
own abstract iterator and provide its
own implementation of New_Iterator_For,
which in fact returns the appropriate
concrete iterator. Within each child
package the implementation of the concrete
collection is visible.

For example, (with some naming and
naming convention differences) 


generic

   type ItemType (<>) is private;

package AbstractAppendableCollection_P is

   type AbstractAppendableCollection is abstract tagged null record;
   
   function  isNotEmpty
           ( theCollection   :        AbstractAppendableCollection )
   return                             Boolean
   is abstract;

   procedure append
           ( theItem         : in     ItemType; 
	    toTheCollection : in out AbstractAppendableCollection)
   is abstract;
   
   procedure removeTheLastItemFrom
           ( theCollection   : in out AbstractAppendableCollection)
   is abstract;
-- precondition: isNotEmpty( theCollection );
   
end;


generic

   type CollectionType (<>) is private;
   type ItemType       (<>) is private;

package AbstractIterator_P is

   type AbstractIterator is abstract tagged null record;
   	   
   function  aNewIteratorFor
           ( theCollection :      CollectionType )
   return                         AbstractIterator'Class
   is abstract;
-- precondition: isNotEmpty( theCollection )
-- after creation the iterator points to the first item in the
collection

   function  theCurrentItem
           ( theIterator :        AbstractIterator )
   return                         ItemType
   is abstract;

   function  atTheEnd
           ( theIterator :        AbstractIterator )
   return                         Boolean
   is abstract;

   procedure advance  
           ( theIterator : in out AbstractIterator )
   is abstract;
-- precondition : not(atTheEnd())

   procedure reset  
           ( theIterator : in out AbstractIterator )
   is abstract;
-- reset the state of the iterator to be that after creation
   
end;


with AbstractAppendableCollection_P;

generic

   type ItemType (<>) is private;  
   
package AppendableCollection_P is

   package ItemTypeAbstractAppendableCollection_P
      is new AbstractAppendableCollection_P(ItemType => ItemType);      
   use ItemTypeAbstractAppendableCollection_P;
   
   type AppendableCollection 
      is new AbstractAppendableCollection with private;

   function  isNotEmpty
           ( theCollection      :       AppendableCollection )
   return                               Boolean;
	   
   procedure append
           ( theItem            : in     ItemType; 
	    toTheCollection    : in out AppendableCollection);
   
   procedure removeTheLastItemFrom
           ( theCollection      : in out AppendableCollection);	   
-- precondition: isNotEmpty( theCollection );

private

   type AppendableCollection 
      is new AbstractAppendableCollection with null record;

-- (with null record until I get round to implementing it!)
      
end;


with AbstractIterator_P;

generic
   
package AppendableCollection_P.ForwardsIterator_P is

   package ItemTypeAbstractIterator_P
      is new AbstractIterator_P
         (CollectionType => AppendableCollection, 
	 ItemType       => ItemType );      
   use ItemTypeAbstractIterator_P;
      
   type ForwardsIterator is new AbstractIterator with private;
   
   function  aNewIteratorFor
           ( theCollection      : AppendableCollection )
   return                         AbstractIterator'Class;
   
   function  theCurrentItem
           ( theIterator :        ForwardsIterator )
   return                         ItemType;

   function  atTheEnd
           ( theIterator :        ForwardsIterator )
   return                         Boolean;

   procedure advance  
           ( theIterator : in out ForwardsIterator );
-- precondition : not(atTheEnd())

   procedure reset  
           ( theIterator : in out ForwardsIterator );
-- reset the state of the iterator to be that after creation
	   
private

   type ForwardsIterator is new AbstractIterator with null record;
   
-- (with null record until I get round to implementing it!)

end;


-- similar child packages for BackwardsIterator etc.


The above specifications compile but I have yet to write
some bodies and check that this is really a workable scheme.

Re: Translate this into Ada ...

[Richard Irvine]

Richard Irvine wrote:

> 
> The above specifications compile but I have yet to write
> some bodies and check that this is really a workable scheme.

I wish I had done this first as I now think it is probably completely
unworkable. I think I'll quietly make do with a single iterator as
per Norman Cohen's example!

Re: Translate this into Ada ...

[Norman H. Cohen]

In article <321C5BB1.3B2F@eurocontrol.fr>, Richard Irvine
<Richard.Irvine@eurocontrol.fr> writes: 

|> In general one might like to have more than one
|> iterator for the same collection type, each
|> iterator implementing a different traversal
|> policy but all having the same protocol.

By "more than one iterator", Richard means "more than one iteration
algorithm", not "more than one iterator object".

The approach I described already supports more than one iteration
algorithm.  You simply derive a different concrete iterator type from the
abstract iterator type for each algorithm you wish to support, and
override the Current_Item, At_The_End, and Advance subprograms for each
type with versions appropriate for that type's algorithm.  You must
declare new functions with the same profile as New_Iterator_For,
returning iterators of each type.  (You still have to override
New_Iterator_For, so you might as well designate one of the iterator
types as the "standard" one and have New_Iterator_For be a renaming of
that type's constructor function.) For example: 

   with Generic_Abstract_Collections;

   generic

      type Element_Type is private;

   package Binary_Trees is

      package Abstract_Element_Collections is
         new Generic_Abstract_Collections (Element_Type);

      type Tree_Type is
         new Abstract_Element_Collections.Collection_Type with private;

      Iterator_Error: exception renames
                         Abstract_Element_Collections.Iterator_Error;

      --------------------------
      -- Preorder traversals: --
      --------------------------

      type Preorder_Traversal_Type is
         new Abstract_Element_Collections.Iterator_Type with private;

      function Current_Item
         (Iterator: Preorder_Traveral_Type) return Element_Type;

      function At_The_End (Iterator: Preorder_Traversal_Type) return Boolean;

      procedure Advance (Iterator: in out Preorder_Traversal_Type);

      function New_Preorder_Traversal
         (Tree: Tree_Type)
         return Abstract_Element_Collections.Iterator_Type'Class;

      -------------------------
      -- Inorder traversals: --
      -------------------------

      type Inorder_Traversal_Type is
         new Abstract_Element_Collections.Iterator_Type with private;

      function Current_Item
         (Iterator: Inorder_Traveral_Type) return Element_Type;

      function At_The_End (Iterator: Inorder_Traversal_Type) return Boolean;

      procedure Advance (Iterator: in out Inorder_Traversal_Type);

      function New_Inorder_Traversal
         (Tree: Tree_Type)
         return Abstract_Element_Collections.Iterator_Type'Class;

      --------------------------
      -- Endorder traversals: --
      --------------------------

      type Endorder_Traversal_Type is
         new Abstract_Element_Collections.Iterator_Type with private;

      function Current_Item
         (Iterator: Endorder_Traveral_Type) return Element_Type;

      function At_The_End (Iterator: Endorder_Traversal_Type) return Boolean;

      procedure Advance (Iterator: in out Endorder_Traversal_Type);

      function New_Endorder_Traversal
         (Tree: Tree_Type)
         return Abstract_Element_Collections.Iterator_Type'Class;

      ---------------------------
      -- "Standard" traversal: --
      ---------------------------

      -- Since the inherited version of New_Iterator_For is abstract,
      --    it must be overridden.

      function New_Iterator_For
         (Tree: Tree_Type)
         return Abstract_Element_Collections.Iterator_Type'Class
         renames New_Inorder_Traversal;

   private

      ...

   end Binary_Trees;

The purpose of declaring New_Iterator_For to be abstract in
Generic_Abstract_Collections was to create an obligation on the part of
the programmer declaring a concrete type to provide a concrete
constructor function.  Unfortunately, it creates one obligation per
collection type rather than one obligation per iterator type.  The fix is
to replace the declaration

   function New_Iterator_For
      (Collection: Collection_Type) return Iterator_Type'Class
      is abstract;

with

   function New_Iterator_For
      (Collection: Collection_Type'Class) return Iterator_Type
      is abstract;

(with the parameter made classwide so that New_Iterator_For does not
become a primitive operation of more than one tagged type, which is
illegal).

Then each iterator type in the example above inherits one version of
New_Iterator_For, which must be overridden: 

   function New_Iterator_For
      (Collection: Abstract_Element_Collections.Collection_Type'Class)
      return Preorder_Traversal_Type;

   function New_Iterator_For
      (Collection: Abstract_Element_Collections.Collection_Type'Class)
      return Inorder_Traversal_Type;

   function New_Iterator_For
      (Collection: Abstract_Element_Collections.Collection_Type'Class)
      return Endorder_Traversal_Type;

(In a typical call on New_Iterator_For, the usual overload resolution
rules determine which version is being called based on the result type
expected in the context of the call.)

Unfortunately, in the bodies of these functions, the parameter Collection
must be converted downward in the inheritance hierarchy to Tree_Type in
order to access the internal representation of Tree_Type, and this
involves a useless run-time check.

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Translate this into Ada ...

[Robert A Duff]

In article <4vfb15$ujr@watnews1.watson.ibm.com>,
Norman H. Cohen <ncohen@watson.ibm.com> wrote:
>It might be more appropriate to make Iterator_Type limited (since it
>represents the state of an in-progress loop iteration, something that it
>does not make sense to copy).  In this case, the New_Iterator_For
>function should be replaced by a procedure Start_Iteration with an out
>parameter of Iterator_Type. ...

How about making it limited, with an access discriminant used to point
at the data structure being iterated over, and make it controlled, with
an Initialize that does whatever initialization is necessary?  Then you
could say:

    It: Iterator_Type(The_Thing_Being_Iterated_Over'Access);
    ...

By the way, finalization can be expensive, but I see no reason why a
controlled type that just overrides Initialize needs to be expensive.
The compiler would have to recognize that special case, of course.

- Bob

Re: Translate this into Ada ...

[David Weller]

In article <3219E6E2.2F5@eurocontrol.fr>,
Richard Irvine  <Richard.Irvine@eurocontrol.fr> wrote:
>How using generics, abstract types (e.g. AbstractList and
>AbstractIterator), 
>abstract subprograms or any other Ada features can this decision be
>expressed? 
>
>I have struggled with this for quite some time without finding a
>satisfactory
>solution. Any suggestions gratefully received.

Take a look at the sources for the Ada 95 Booch Conponents at
http://www.ocsystems.com/booch.  I know the existing material there is
out of date, and there will be an update in about a month (promise!),
but it can give you an idea on how to approach the problem.

Your approach seems similar to the approach used for the C++ STL,
which is OK, but the Booch Components will give you a different feel
for the implementation of iterators.

-- 
    Visit the Ada 95 Booch Components Homepage: www.ocsystems.com/booch
           This is not your father's Ada -- lglwww.epfl.ch/Ada

Re: Translate this into Ada ...

[Spasmo]

Richard Irvine (Richard.Irvine@eurocontrol.fr) wrote:
: Can anyone help with what I imagine is a frequently ocurring problem?

: We would like all lists in an application to be read using an iterator
: with operations like:

[Snip]

Well I'm no expert in Ada, but I have successfully written 
generic linked list routines that pretty much do what you want.
Here's some info, but if you would like the actual source code
I'd be more than happy to provide it (I haven't done all that
much debugging but it seems to work and at the very least should
give you an idea of how to proceed).

I did a generic package that was instantiated with the data
type to be stored in the list.  This data type was imbedded
in a record similar to the following:

type List_Node;
type List_Node_Ptr is access List_Node;
type List_Node is 
	record
		Data : Generic_Data;
		Next : List_Node_Ptr;
	end record;

Where Data was what was generically instantiated.  Of course
access restrictions were applied so the user only saw what
I wanted him/her to see.  Anyway as for the list itself I
used a simple singly linked list with head and tail pointers
for simplicity of operations, so the data type that was
immediately visible to the user was something like the following:

type List is private;

private
	type List is
		record
			List_Body, Head, Tail : List_Node_Ptr;
		end record;

So for use the user would say instantiate the package like
the following:
	package My_List_Pkg is new Lists ( Rec );

Then declare lists by:
	My_List : My_List_Pkg.List;

So the package would provide the data type for the list and
also all the operations (iterators, etc...).  I was able to
do linked lists of linked lists like this and so forth.

For multiple linked lists of the same type one could just
use the same instantiation but of course different types
would mean different instantiations but this was very
flexible.  BTW, I really didn't consider my implementation
to be an "iterator", since it provided iterator operations
and the data type itself, so it was more of a linked list
package but the functionality again seems to be what you
are looking for.

One thing that's a problem is if you want a heterogenous list
of objects.  Something like the above would not accomodate 
your needs unfortunately so you'd have to have a linked list
of pointers to class wide types, which isn't hard to achieve
but it's something to keep in mind.  My list package didn't
do this so while it could handle any data type, heterogenous
lists of related classes are pretty much out of the question.
		
Damn I love Ada!

--
Spasmo
"Everyone has secrets, but sometimes you get caught,
 So if it's just between us, my silence can be bought"
	"Blackmail" by Sloppy Seconds

Re: Translate this into Ada ...

[Richard Irvine]

Spasmo wrote:
> 
> Richard Irvine (Richard.Irvine@eurocontrol.fr) wrote:
> : Can anyone help with what I imagine is a frequently ocurring problem?
> 
> : We would like all lists in an application to be read using an iterator
> : with operations like:
> 
> [Snip]
> 
> Well I'm no expert in Ada, but I have successfully written
> generic linked list routines that pretty much do what you want.
> Here's some info, but if you would like the actual source code
> I'd be more than happy to provide it (I haven't done all that
> much debugging but it seems to work and at the very least should
> give you an idea of how to proceed).
> 

Thanks for your reply which concerned a particular implementation of 
a generic list. What I was really trying to get at was how to produce
an abstract specification of a list which MANY implementations (e.g.
singly-linked lists, arrays etc. ) might conform to. In our case
we are tyring to develop a subsystem which may be embedded in many
client applications (none of which is written in Ada!). 
The client applications will provide us with lists (collections)
and we have no idea how they will be implemented.
Nonetheless, we would like to have some way of ensuring that the
different lists provided by the client (and by ourselves) are 
accessed in a consistent way. The problems come because the 
function which creates the iterator refers to two asbtract types.
(Doubly dispatching).

For a concrete implementation one might make use of David Weller's 
Booch components, for example.

Re: Translate this into Ada ...

[Robert A Duff]

In article <321AFC20.5586@eurocontrol.fr>,
Richard Irvine  <Richard.Irvine@eurocontrol.fr> wrote:
>...The problems come because the 
>function which creates the iterator refers to two asbtract types.
>(Doubly dispatching).

The standard way around that problem is to make one of the parameters
(or result) class-wide.

- Bob