CVS difference for ai05s/ai05-0001-1.txt
--- ai05s/ai05-0001-1.txt 2006/03/18 06:09:22 1.1
+++ ai05s/ai05-0001-1.txt 2006/03/23 03:30:57 1.2
@@ -923,3 +923,335 @@
****************************************************************
+From: Matthew Heaney
+Sent: Thursday, March 16, 2006 7:56 AM
+
+> (I'd hoped someone else would answer this, but since no one
+> has, I'll take a stab at it...)
+
+I sent him some email privately.
+
+> In any case, Move destroys all of the cursors; the language
+> defines them as "invalid", and any future use is erroneous.
+> (If the error was detected, you are lucky.)
+
+In the GNAT case (that's the compiler he's using), the cursor is implemented
+as a record with a pointer to list object and another pointer to the node
+containing the item. When he attempted to use the old cursor with the new
+list object, he probabably got Program_Error, since the first thing
+cursor-based operations do is compare the list pointer to the address of the
+list parameter.
+
+> In this sense,
+> Move is very similar to destroying the container itself (say,
+> by calling Unchecked_Deallocation on it).
+
+Well, it's not quite as extreme as that, since the nodes haven't been
+deallocated; they've just been moved onto another list. His algorithm would
+work fine if the cursor didn't have a list pointer too.
+
+There is often a tradeoff between flexibility and safety, and Move is an
+example where some flexibility was lost as a result of adding the checks.
+
+> But Move isn't intended for cases where you need to preserve
+> cursors. The four parameter Splice is designed for that, as
+> it returns the new cursor for where the element(s) are
+> inserted. If you want to preserve the original container,
+> just use ":=".
+
+You could use Splice (in fact that's what I told him), but it can get a
+little hairy since you must somehow keep track of all the extant cursors.
+As you're iterating over the old list, splicing nodes on the new list, you
+have to compare the cursor with old cursors, and then call splice with the
+old cursor.
+
+I also told him to just write a generic child procedure to rebind the cursor
+from the old list to the new, and he seemed to like that idea better.
+There's probably a more elegant way to solve his problem without extending
+container behavior, but I didn't really understand the small fragments of
+code he sent me.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Saturday, March 18, 2006 5:20 PM
+
+> Given the inherent insecurity with First()...Next(), is there a better
+> iterator, such as the 'natural' extension of the For Loop construct
+> to iterators ... eg:
+>
+> for C in L loop
+> ... do something using Element (C) or Update_Element(..)
+> end loop;
+
+For what it is worth, I would point out that Ada is really a somewhat
+lower level language than Python. I find iterating awkward in Ada (and
+in many other languages, to a lesser or greater degree), but I often
+find that, in Ada, an alternative such as:
+
+ declare
+ procedure Mogrify (C : in Widget_Lists.Cursor) is
+ begin
+ ...
+ end;
+ begin
+ Widget_Lists.Iterate (My_Widgets, Mogrify'Access);
+ end;
+
+alleviates the dangers of missing something vital out.
+
+****************************************************************
+
+From: Pascal Leroy
+Sent: Monday, March 20, 2006 8:00 AM
+
+> in Ada, an alternative such as:
+>
+> declare
+> procedure Mogrify (C : in Widget_Lists.Cursor) is
+> begin
+> ...
+> end;
+> begin
+> Widget_Lists.Iterate (My_Widgets, Mogrify'Access);
+> end;
+>
+> alleviates the dangers of missing something vital out.
+
+I fail to see what dangers it alleviates. I for one would much prefer to
+write something like:
+
+ for each C in My_Widgets loop
+ ...
+ end loop;
+
+Remember, Ada is about readability, too.
+
+However, last time this was discussed it appeared that grafting such a
+capability on the language was not easy.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Monday, March 20, 2006 8:28 PM
+
+I'm reposting this private mail (with permission) on this topic for the
+record.
+
+----
+From: Alwyn Barry
+
+Hi,
+
+Thanks for your response.
+
+I did, in the end, use iterators. However I am using a list
+(which is backed-up on each cycle of the algorithm to a
+back-up list), and three different index lists onto the list
+(which are also backed up). This means, in the worst case,
+up to five iterator functions, each of one line, for five
+lines of algorithm. Its ok, but hardly readable. For cases
+where there are large tasks to do, Iterate is great. For
+single statements it is overkill. What is particularly
+frustrating is that though iterate() is provided [effectively
+apply()], there is a lack of reduce() and map() functions
+which would remove the need for the iterator functions to
+access other variables outside the function in order to do
+their task. These functions can easily be provided, but
+could have been included.
+
+Anyway, that was one issue which I could work around, although
+frustrated that Ada is not adopting features which other
+languages have included exactly so that the "dropped next()"
+errors do not occur. In regard to the other problem...
+
+Splice() could be used, but there is no cursor update
+with it. As Matthew Heaney points out in his reply, trying
+to update the cursors too gets nasty (the cursor is invalid
+once the item has moved, yet the new list does not contain
+the item so you cannot update the cursor before the splice).
+This can be programmed around, but thats not helpful either.
+
+Anyway, I've got around it by the old trick of having two
+records, one the 'current' and one the 'backup' list and
+indexes, and simply switching pointers. I used to do this
+in C, which I guess says something about the elegance or
+otherwise of the solution. It does save copying, but where
+speed is not really an issue it is a pity there is not a
+better way. Mind you, I do like the safety constraints of
+the current implementation! ... it just needs a means of
+switching the cursors if the list is moved, or a further
+internal level of indirection so that the cursor to list
+pointer remains, but the actual list type is a level removed.
+
+Alwyn
+
+---
+
+From: Randy Brukardt
+
+The general answer is that you can't provide the solution to every possible
+need, and keep things efficient. Every solution has trade-offs, and with
+containers, *everybody* has a better idea. Undoubtedly there is something
+better that could have been done [if I had designed them, they would have
+worked quite differently!], but the real value here is that they're
+standard. There never was any intent that this version would be the final
+word in containers for Ada.
+
+The syntax for iterators *is* clunky. We never seriously considered doing
+anything about that; I suspect that the greater use of containers will make
+that more important as we go forward. But the "next" style is needed for
+maximum flexibility; the only way to avoid it is to give up that flexibility
+in some way. So, you need both (no matter how nice the syntax of iterators).
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Tuesday, March 21, 2006 8:52 PM
+
+Alwyn Barry wrote [forwarded by Randy Brukardt]:
+
+> ... What is particularly frustrating is that though iterate() is
+> provided [effectively apply()], there is a lack of reduce() and map()
+> functions which would remove the need for the iterator functions to
+> access other variables outside the function in order to do their
+> task. These functions can easily be provided, but could have been
+> included. ...
+
+These functions (reduce and map) could not be so easily provided in Ada
+as they are in Python (which has dynamic typing and comprehensions,
+which Ada essentially does not). I think both functions would have to be
+generic, the 'reduce' function taking the result type as its generic
+parameter, and the 'map' function taking another list or vector package
+as its generic parameter. In other words, they would be not be the
+elegant one-liners that they are in Python.
+
+> ... Anyway, I've got around it by the old trick of having two
+> records, one the 'current' and one the 'backup' list and indexes, and
+> simply switching pointers. I used to do this in C, which I guess
+> says something about the elegance or otherwise of the solution. It
+> does save copying, but where speed is not really an issue it is a
+> pity there is not a better way. ...
+
+This is the kind of solution that I would have adopted. I'm sure that it
+is generally safer using access values in Ada than using pointers in C,
+so I'm not sure it need be considered a particularly inelegant solution
+(perhaps not in C either).
+
+Randy Brukardt replied:
+
+> The general answer is that you can't provide the solution to every
+> possible need, and keep things efficient. ... [if I had designed
+> them, they would have worked quite differently!], but the real value
+> here is that they're standard. There never was any intent that this
+> version would be the final word in containers for Ada. ...
+
+If I had designed the containers, they would have worked quite
+differently as well! But I think Matthew Heaney (the principal designer)
+and the ARG have done a good job, in the end, of producing a design that
+combines efficiency, safety, and intelligibility, especially as they
+didn't have a great deal of time to refine it.
+
+I am currently using Matt's reference implementation of the new
+containers, grafted into GNAT 3.15p (which is Ada 95), in various 'real
+life' programs I am writing, so I'm getting to know them quite well, and
+they are very handy!
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Tuesday, March 21, 2006 9:17 AM
+
+> For cases
+> where there are large tasks to do, Iterate is great. For
+> single statements it is overkill.
+
+The library works by providing primitives that you can use to synthesize
+higher-level abstractions. Any "single statement" can be written as a
+generic and instantiated as necessary.
+
+ > What is particularly
+> frustrating is that though iterate() is provided [effectively
+> apply()], there is a lack of reduce() and map() functions
+> which would remove the need for the iterator functions to
+> access other variables outside the function in order to do
+> their task.
+
+Well this is just silly. Of *course* local functions "access variables
+outside the function" since otherwise there'd be little point in making
+them local. Ada has *always* worked this way; the container library
+simply conforms to already-established language idioms.
+
+> These functions can easily be provided, but
+> could have been included.
+
+Yes of course, and that is by design. Obviously we didn't include
+everything. If you want a map function, then it's trivial to write it
+once and then keep reusing it. Here's one for arrays (which of course
+could be generalized):
+
+generic
+ type Result_Type is private;
+ type Array_Type is array (Count_Type range <>) of Result_Type;
+ type Container_Type (<>) is limited private;
+ type Cursor_Type (<>) is limited private;
+ with procedure Process
+ (Posn : Cursor_Type;
+ Result : out Result_Type);
+ with function Length (C : Container_Type) return Count_Type;
+ with procedure Iterate
+ (C : Container_Type;
+ Process : not null access procedure (C : Cursor);
+function Generic_Map (C : Container_Type) return Array_Type;
+
+function Generic_Map (C : Container_Type) return Array_Type is
+ A : Array_Type (1 .. Length (C));
+ I : Count_Type := 0;
+
+ procedure Process (Posn : Cursor_Type) is
+ begin
+ I := I + 1;
+ Process (Posn, A (I));
+ end;
+begin
+ Iterate (C, Process'Access);
+ return A (1 .. I);
+end;
+
+This algorithm works for any container type, including arrays.
+
+> Anyway, that was one issue which I could work around, although
+> frustrated that Ada is not adopting features which other
+> languages have included exactly so that the "dropped next()"
+> errors do not occur. In regard to the other problem...
+
+What "other languages" are we speaking about? Ada is a low-level
+systems programming language. It is not a scripting language. In
+particular it is neither Perl nor Python.
+
+Ada's closest analog is C++. Anything you can do in the STL you can do
+in the Ada container library.
+
+We didn't even attempt to include a generic algorithms library too,
+since we were trying to keep the scope of the revision small. The
+simplest thing for you to do it write the generic algorithms you need
+and reuse them as necessary.
+
+> Splice() could be used, but there is no cursor update
+> with it.
+
+Of course there is cursor update with it. I don't know what you're
+talking about here. The Position parameter of the 4-parameter Splice is
+passed using inout mode, the purpose of which is to rebind the cursor
+from the old (source) list to the new (target) list.
+
+> As Matthew Heaney points out in his reply, trying
+> to update the cursors too gets nasty (the cursor is invalid
+> once the item has moved, yet the new list does not contain
+> the item so you cannot update the cursor before the splice).
+
+So you update the cursor *during* the call to Splice, by specifying the
+cursor you want to rebind as the Position parameter.
+
+****************************************************************
+
Questions? Ask the ACAA Technical Agent