Re: AIs for Ada extensions

["Robert I. Eachus" <rieachus@attbi.com>]

Alexander Kopilovitch wrote:
> Robert I. Eachus wrote:
> 
> 
>>>It seems to be an unfortunate collision that multiple new packages should be
>>>proposed when Abstract Interfaces still aren't established firmly.
>>>It is highly likely that some packages (for example, Data structures
>>>components) may look significantly better if they can use Abstract Interfaces.
>>
>>I personally don't see any conflict.  The interface AI will allow easier 
>>bindings to C++ and Java.  But in Ada, mix-ins are a better abstraction 
>>IMHO for containers.  The advantage is that you can easily put objects 
>>in a container even if the original declarer of the type/class had no 
>>idea that they would be put in a container.  For example:
>>...

> Yes, but what about similar containers, such as various flavors of List?
> And it is not an easy task to align properly the above your words with another
> your opinion (with which I fully agree), posted here about 3 weeks ago -
> I mean the following:

>>...  In Ada you tend not to have one sort
>>package in your toolbox, or one list type implementation, you have
>>several.  Now the programmer solving some problem sees a part of his
>>decomposition that can be solved by a list package or a sort package,
>>and does a generic instantiation.  The problem is that there is no easy
>>way, in Ada, to express a binding to a member of the class of sort
>>generics, but to delay the choice of the actual mapping.
>>
>>This is why one of the features I expect interfaces to add to Ada is a
>>better way of organizing collections of sort algorithms and the like.

Real subtle point.  Interfaces as currently planned will ALLOW multiple 
interface inheritance.  They can also be used as I described in the 
first paragraph to provide multiple instances of a single abstract 
interface.  I expect the multiple (interface) inheritance use to be 
common when interfacing to code written in other OO languages.  The 
usage I described is almost not a programming convention but a way to 
describe the relationship between a number of otherwise unrelated 
abstractions.  They all implement the same interface, so they can be 
passed to generics as instances of that interface, but otherwise there 
is no necessary relation between the abstractions.

Can you use multiple interface inheritance to describe abstractions that 
match more than one interface?  Sure, and it will happen.  For example 
imagine an AVL_Tree package which clearly allows random (indexed) 
access, and also has an ability to do an inorder walk.  It can also 
implement the list interface.  The question is whether it will be 
common.  The problem becomes a programming in the large issue.  It is 
going to be much easier to create a list 'view' of the AVL_Tree package 
and keep it consistant with the list interface, than to maintain a 
package that directly implements multiple interfaces.

This is probably a very good example, so let me follow it through a bit.

    generic
      type Element is private;
    package Lists is
      type List is abstract interface;
      function Head(L: in List) return Element;
      function Is_Empty(L: in List) return Boolean;
      procedure Append(L: in out List; E: in Element);

      type Iterator is private with null;

      function Create(L: in List) return Iterator;
      function Next(I: in Iterator) return Element;
      function At_End(I: in Iterator) return Boolean;

    private
      ...
    end Lists;

I did the iterator this way because it brings up an interesting question 
about interface types.  Obviously an instance of the Lists package also 
creates a new Iterator type, and that type is closely related to type 
List.  But are functions like Next and At_End part of the List 
interface?  I think it is an issue AI-251 needs to address.

Now I want to create a binding between this interface and a tree type. 
The package spec is easy:

    with Lists;
    generic
      with package Trees is new AVL_Trees;
      -- Could make the element type explicit, but no reason to, it is
      -- already specifed by the element type in the AVL_Trees instance.
    package List_View is

      type List is private with null;

      function Head(L: in List) return Element;
      function Is_Empty(L: in List) return Boolean;
      procedure Append(L: in out List; E: in Element);

      type Iterator is private with null;

      function Create(L: in List) return Iterator;
      function Next(I: in Iterator) return Element;
      function At_End(I: in Iterator) return Boolean;

    private
      type List is Trees.AVL_Tree;
      type Iterator is Trees.Inorder_Walk with null;
    end List_View;

Now it gets tough.  Not because it is hard to write, but their is one 
tough decision.  Head is fairly easy to write, start at the root of the 
tree and follow left links until you find one that is null.  The 
contents of that node are what you want to return.  Is_Empty and the 
Iterator operations shouldn't be too hard, since I specified that 
AVL_Trees provides an inorder walk interator.  But what to do about 
Append?  I see three options:

1) Always raise Program_Error.  In other words, this is just a view, and 
not a full list implementation.

2) Raise an error if the new Element does go at the end of the list. 
Err, tree.  This allows the Append operation to be used to insert a 
sorted set of Elements one at a time.

3) Insert the Element at the proper position in the tree, and invalidate 
any existing Iterators, that are past the position the new Element will 
be inserted in, either in the implementation or by fiat.  (In other 
words, document it as an error to insert with an open Iterator.)

Whichever solution you choose, all done.  Notice that we have created a 
binding between one abstraction Lists, and another, AVL_Trees, that 
never explicitly uses the new interface feature to implement multiple 
inheritance.  We could have done it, but some of the List operations 
only loosely make sense for an AVL_Tree viewed as a tree (the Head 
operation) while others will be hidden by the interface entirely.  It 
may be that some of the operations for the List view may perfectly match 
the available operations for the AVL_Tree (Is_Empty?), but many will 
have different names.  So what?  The "overhead" of making the list view 
explicit makes maintenance much easier.