CVS difference for ai05s/ai05-0139-1.txt

Differences between 1.3 and version 1.4
Log of other versions for file ai05s/ai05-0139-1.txt

--- ai05s/ai05-0139-1.txt	2009/03/15 03:51:06	1.3
+++ ai05s/ai05-0139-1.txt	2009/06/02 06:22:37	1.4
@@ -637,3 +637,312 @@
 
 ****************************************************************
 
+From: Randy Brukardt
+Sent: Wednesday, May 27, 2009  10:06 PM
+
+[The following is a partial message from another thread, see AI05-0135-1 for
+the entire thread. - Editor.]
+
+One example that I've been thinking about is the proposed generic to provide
+iterators. If we do decide to define that "magic" generic, we will need to
+rearrange the Ada.Containers packages a lot to use it. But that rearrangement
+would seem to be incompatible in a number of ways, and limiting on
+implementation strategies to boot.
+
+To refresh, assume that we have a magic iterator generic (this is simplified for
+this example, as are the following packages) and we have Steve's "integrated
+packages":
+
+   generic
+       type Cursor is private;
+       No_Element : in Cursor;
+   package Ada.Iterator_Interfaces is
+       type Basic_Iterator is limited interface;
+       function First (Object : Basic_Iterator) return Cursor;
+       function Next (Object : Basic_Iterator; Position : Cursor) return Cursor;
+   end Ada.Iterator_Interfaces;
+
+[Note that the exact form of this generic doesn't matter much in terms of what
+rearrangements need to be done to the Ada.Containers packages.]
+
+Now, we currently have:
+
+   generic
+      type Element_Type is private;
+   package Ada.Containers.Doubly_Linked_Lists is
+      type List is tagged private;
+      type Cursor is private;
+
+      Empty_List : constant List;
+      No_Element : constant Cursor;
+
+      function Is_Empty (Container : List) return Boolean;
+      procedure Clear (Container : in out List);
+      function Element (Position : Cursor)
+         return Element_Type;
+      ...
+   private
+      ... -- not specified by the language
+   end Ada.Containers.Doubly_Linked_Lists;
+
+In order to add Basic_Iterator visibly to type List, we'll have to rearrange
+this into using at least one nested package. The simplest I can come up with is:
+
+   with Ada.Iterator_Interfaces;
+   generic
+      type Element_Type is private;
+   package Ada.Containers.Doubly_Linked_Lists is
+      use package Cursors is
+         type Cursor is private;
+         No_Element : constant Cursor;
+      private
+         ... -- not specified by the language
+      end Cursors;
+
+      package Iterators is new
+          Ada.Iterator_Interfaces (Cursors, No_Element);
+
+      type List is new Iterators with private;
+
+      Empty_List : constant List;
+      function Is_Empty (Container : List) return Boolean;
+      procedure Clear (Container : in out List);
+      function Element (Position : Cursor)
+         return Element_Type;
+      ...
+   private
+      ... -- not specified by the language
+   end Ada.Containers.Doubly_Linked_Lists;
+
+Limited with incompatibilities don't matter in this case, as you can't get a
+limited view of a generic unit.
+
+Primitiveness incompatibilities are definitely in evidence, but I do have to
+wonder if it matters. In particular, if you derive from type Cursor currently,
+you will inherit function Element. But you will no longer inherit that routine
+with this rearrangement. I don't know how significant that is (I would suggest
+it is not very significant).
+
+Naming incompatibilities don't seem to be a problem with this example. They
+could be if we wanted to remove the "integrated" nested package (as someone
+could have named it explicitly in a use clause or in an expanded name). That's
+not likely to be an issue in this case.
+
+Since there is only two entities (plus the inherited "=") in the nested
+packages, we could just rename them and not need any special construct at all.
+But we'd still have the incompatibilities. (I did not expect this result when I
+started writing this message.)
+
+But there still is a significant issue. While we are not specifying what goes
+into the private parts, we do need to be able to write them. A cursor needs a
+reference to a node and to the full container (the List in this example). The
+node probably could be defined in the private part of package Cursors, but we
+can't define a reference to List in the private part -- it hasn't been declared
+yet! And it *can't* be declared yet, because it depends on the interface that we
+haven't yet created.
+
+One way to workaround this problem is to use a Taft-amendment type in the
+private part of Cursors. But we can't complete that with the type List itself;
+we'd have to use a derived type. And that is obnoxious, forcing many junk type
+conversions. Even using class-wide types won’t get rid of those conversions,
+because they would be toward the root of the tree.
+
+Another possible workaround would be to clutter the spec with an incomplete type
+List before the nested package. But that could not be completed with the private
+extension List, so we would still end up with the same problem.
+
+In conclusion, this rearrangement works, has some client incompatibility (but it
+probably isn't important), but forces a major amount of junk type conversions in
+the body of the package. Of course, this is only one example, and it would be
+nice to look at additional examples in the future.
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Thursday, May 28, 2009  2:12 PM
+
+> Another possible workaround would be to clutter the spec with an 
+> incomplete type List before the nested package. But that could not be 
+> completed with the private extension List, so we would still end up with the
+> same problem.
+
+This particular problem seems fixable.  The requirement that an incomplete type
+declaration be completed with a full_type_declaration seems arbitrary.  There
+seems no inherent reason that it couldn't be completed with a private type or
+private extension declaration.
+
+The incomplete types produced from a "limited with" allow that, so the mechanism
+will be needed in Ada 2005 to handle such a completion anyway.
+
+> In conclusion, this rearrangement works, has some client 
+> incompatibility (but it probably isn't important), but forces a major 
+> amount of junk type conversions in the body of the package. Of course, 
+> this is only one example, and it would be nice to look at additional examples
+> in the future.
+
+Normally I would have expected that almost the entire package would be included
+in an "integrated" package, and then this big nested package would be followed by
+various generic instantiations.  But you have illustrated a case where that doesn't
+work, because you want one of the types to be built on the result of a generic
+instantiation.  I wonder how common that is.
+
+How would you do it without this feature?  As you point out, the integrated package
+is mostly just a short-hand for a bunch of renames, and in this case, there aren't
+that many.  Hiding the nested package name automatically from use-visibility might
+be a helpful advantage of the proposed feature ;-).
+
+It does seem the ability to define an incomplete type that is completed by a partial
+view would be helpful, independent of this proposal.
+
+I wonder if your "magic iterator" generic has this problem in general, and perhaps
+it needs to be *defining* a cursor type, rather than taking it as a parameter.  Or
+is it the fact that we want the container to be usable as an iterator?  I think that
+is probably a bad idea in general, as it is inherently problematic to have the container
+carry some state about a particular iterator over the container.  I understand the
+desire for a *syntax* approximating:
+
+     for Element in Container loop
+        ...
+     end loop;
+
+But I see no requirement that this means we somehow have an iterator built into the
+Container itself.  Also, we would certainly want to allow multiple tasks to iterate
+over a Container in parallel, I would think, or to allow nested iterators such as:
+
+     for Left in Container loop
+        for Right in Container loop
+           Try_Pair(Left, Right);
+        end loop;
+     end loop;
+
+I think the above *syntax* should always presume there is an anonymous iterator object
+created, and that is what carries the state of the iteration.
+
+In any case, I wonder whether it is the strange nature of this generic that is creating
+the problem, or is there a common need to be able to define in a single package two
+recursively-dependent types one of which is based on a generic instantiation of the other.
+I suppose this is a very hard question to answer...
+
+Thanks for the example!
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, May 28, 2009  2:49 PM
+
+...
+> This particular problem seems fixable.  The requirement that an 
+> incomplete type declaration be completed with a full_type_declaration 
+> seems arbitrary.  There seems no inherent reason that it couldn't be 
+> completed with a private type or private extension declaration.
+> The incomplete types produced from a "limited with" allow that, so the 
+> mechanism will be needed in Ada 2005 to handle such a completion 
+> anyway.
+
+Yes, I in fact wrote this up originally assuming that such completions were
+allowed. But before making a fool out of myself, I looked up the actual rules
+and changed this part accordingly.
+
+It would still clutter the spec a bit with an extra type declaration that
+doesn't really have anything to do with anything other than the implementation,
+but not a major problem overall.
+
+> > In conclusion, this rearrangement works, has some client 
+> > incompatibility (but it probably isn't important), but forces a 
+> > major amount of junk type conversions in the body of the package. Of 
+> > course, this is only one example, and it would be nice to look at
+> additional examples in the future.
+> 
+> Normally I would have expected that almost the entire package would be 
+> included in an "integrated" package, and then this big nested package 
+> would be followed by various generic instantiations.  But you have 
+> illustrated a case where that doesn't work, because you want one of 
+> the types to be built on the result of a generic instantiation.  I 
+> wonder how common that is.
+
+No idea. It seems to need interfaces to make much sense, so it would mainly
+come up in new code.
+
+> How would you do it without this feature?  As you point out, the 
+> integrated package is mostly just a short-hand for a bunch of renames, 
+> and in this case, there aren't that many.
+> Hiding the nested package name automatically from use-visibility might 
+> be a helpful advantage of the proposed feature ;-).
+
+I was surprised to find out that it doesn't seem to matter much either way; the key
+is to use the nested package. Making it "integrated" is just icing.
+
+> It does seem the ability to define an incomplete type that is 
+> completed by a partial view would be helpful, independent of this 
+> proposal.
+
+Yes, I think so.
+
+> I wonder if your "magic iterator" generic has this problem in general, 
+> and perhaps it needs to be *defining* a cursor type, rather than 
+> taking it as a parameter.
+
+I don't know how that could work, given that container cursors include a reference
+to the container object. I suppose the entire thing could be created as a mix-in generic
+(adding to the container directly), but that seems annoying (isn't that exactly the sort
+of thing that interfaces were created to avoid?).
+
+> Or is it the fact that
+> we want the container to be usable as an iterator?  I think that is 
+> probably a bad idea in general, as it is inherently problematic to 
+> have the container carry some state about a particular iterator over 
+> the container.
+
+I strongly agree with this, but you need to convince Ed. :-) Maybe the rest of
+your message will help.
+
+> I understand the desire for a *syntax* approximating:
+> 
+>      for Element in Container loop
+>         ...
+>      end loop;
+
+I had proposed
+    for Element in Container.Iterator loop
+       ...
+    end loop;
+(where "Iterator" is a function returning an anonymous iterator object).
+Since we're using that same sort of model for accessors (there is an "extra"
+discriminant reference in those), I don't see the problem. But of course, I
+was always happy with this formulation, it is other people that were not.
+
+> But I see no requirement that this means we somehow have an iterator 
+> built into the Container itself.  Also, we would certainly want to 
+> allow multiple tasks to iterate over a Container in parallel, I would 
+> think, or to allow nested iterators such as:
+> 
+>      for Left in Container loop
+>         for Right in Container loop
+>            Try_Pair(Left, Right);
+>         end loop;
+>      end loop;
+> 
+> I think the above *syntax* should always presume there is an anonymous 
+> iterator object created, and that is what carries the state of the 
+> iteration.
+
+With the accessor proposal, you have to write a single extra selection; that
+seems fine to me for iterators, too. Since it would not be surprising to use
+both of them together, it would actually be kinda weird to have simpler syntax
+for the iterator and not the accessor:
+
+    for Cursor in Container.Iterator loop
+        Container.Accessor(Cursor).Element.Component := 10;
+    end loop;
+
+> In any case, I wonder whether it is the strange nature of this generic 
+> that is creating the problem, or is there a common need to be able to 
+> define in a single package two recursively-dependent types one of 
+> which is based on a generic instantiation of the other.  I suppose 
+> this is a very hard question to answer...
+
+I would expect a similar problem any time that you wanted to define an interface
+that needs customization with some properties. But it is hard to tell for sure, other
+than to say that designers are clever and come up with structures that no one expects.
+
+****************************************************************

Questions? Ask the ACAA Technical Agent