CVS difference for ai12s/ai12-0196-1.txt

Differences between 1.3 and version 1.4
Log of other versions for file ai12s/ai12-0196-1.txt

--- ai12s/ai12-0196-1.txt	2016/10/04 02:20:14	1.3
+++ ai12s/ai12-0196-1.txt	2016/10/04 04:47:30	1.4
@@ -1,4 +1,4 @@
-!standard A(3/4)                                 16-10-03   AI12-0196-1/03
+!standard A(3/4)                                 16-10-04   AI12-0196-1/04
 !standard A.18(5)
 !class Amendment 16-06-07
 !status work item 16-06-07
@@ -37,49 +37,60 @@
 
 !wording
 
-Apply the following modifiations
+Modify A 3(4):
 
-A 3(4) "The implementation shall ensure that each language-defined subprogram
-is reentrant in the sense that concurrent calls on any language-defined
-subprogram{s (possibly the same)} perform as specified, so long as all objects
-that are denoted by parameters that could be passed by reference or designated
-by parameters of an access type are nonoverlapping."
-
-A.18 (2/2) "A cursor referencing an element in a container is considered to be
- overlapping {only} with the {element}[container] object itself."
-
-A.18 (2.a/2) "Reason: The last sentence is intended to clarify that operations
- that just use a cursor are {reentrant if the cursor objects designate
- different elements of the container}[on the same footing as operations that
- use a container] in terms of the reentrancy rules of Annex A. "
-
-A.18 (2.b/4) Add "Ramification: A cursor is not considered to overlap with
- the associated container, thus parallel operations involving a set of cursors
- each operating on mutually exclusive sets of elements from the same container
- are expected to work."
-
-A.18 (5.o/2)
- "Thus, it is only necessary for a user to protect a container if a single
-  container needs to be used by multiple tasks {and concurrent calls to
-  the container are not reentrant}."
-
-A.18.2 (125) Append "To_Cursor is reentrant."
-
-Add
-A.18.2 (125.1) "Ramification: Without the preceding rule, To_Cursor would not
-be considered reentrant for concurrent calls on the same container object
-by the reentrancy rules in A.3, since the container object of the concurrent
-calls would overlap with itself. We want this to be
-reentrant to allow parallel processing of Vectors to allow the Vector elements
-to be split into separate "chunks" of processing.
-
-A.18.6 (147.1) Append "An object of a Constant_Reference_Type
-  is considered to be overlapping only with the object designated by Element."
-A.18.6 (147.1) Append "An object of a Reference_Type
-  is considered to be overlapping only with the object designated by Element."
+   The implementation shall ensure that each language-defined subprogram
+   is reentrant in the sense that concurrent calls on any language-defined
+   subprogram{s (possibly the same)} perform as specified, so long as all objects
+   that are denoted by parameters that could be passed by reference or designated
+   by parameters of an access type are nonoverlapping.
+
+Modify A.18(2/2):
+
+   A cursor referencing an element in a container is considered to be
+   overlapping {only} with the {element}[container] object itself.
+
+Modify AARM A.18(2.a/2)
+   Reason: The last sentence is intended to clarify that operations
+   that just use a cursor are {reentrant if the cursor objects designate
+   different elements of the container}[on the same footing as operations that
+   use a container] in terms of the reentrancy rules of Annex A.
+
+   {Ramification: A cursor is not considered to overlap with
+   the associated container, thus parallel operations involving a set of cursors
+   each operating on mutually exclusive sets of elements from the same container
+   are expected to work.}
+
+Modify AARM A.18(5.o/2):
+
+   Thus, it is only necessary for a user to protect a container if a single
+   container needs to be used by multiple tasks {and concurrent calls to
+   the container are not reentrant}.
+
+Append to A.18.2(125):
+
+   For the purposes of determining whether To_Cursor is required to be
+   reenterant, the Container parameter is considered to not overlap
+   with any other object Redundant[(even with itself)].
+
+   AARM Ramification: Without the preceding rule, To_Cursor would not
+   be considered reentrant for concurrent calls on the same container object
+   by the reentrancy rules in A.3, since the container object of the concurrent
+   calls would overlap with itself. We want this to be
+   reentrant to allow parallel processing of Vectors to allow the Vector
+   elements to be split into separate "chunks" of processing.
+
+Append to A.18.6(147.1):
+   An object of a Constant_Reference_Type is considered to be overlapping only
+   with the object designated by Element.
+
+Append to A.18.6(147.1):
+   An object of a Reference_Type is considered to be overlapping only with the
+   object designated by Element.
 
 Similarly apply the above cursor and reference modifications to the other
-containers.
+containers. [Editor's note: This will have to be replaced by a list of
+paragraph numbers in the final AI.]
 
 !discussion
 
@@ -122,14 +133,14 @@
 subprogram however has a parameter that is the container associated with the
 cursor to be generated, and thus still is considered to be an overlapping call
 that is not reentrant if concurrent calls are applied to the same container
-object.
+object. We solve that by simply declaring otherwise.
 
-To_Cursor however, is trivial to implement as a reentrant routine since it only
-needs to contruct an object that designates the container and contains an
-index to the vector. To_Cursor has no side effects, and is thus what we might
-call a pure function, if the language defined such a thing. We specify in the
-wording that this subprogram is reentrant to ensure that it can be safely
-called.
+Thus, To_Cursor can safely be called concurrently since its container
+parameter is said above to not overlap with any object including itself.
+Similarly, the Index parameter is not a problem for concurrent calls, since
+elementary types are passed by copy, according to 6.2(3/3). We do not believe
+that there is any implementation problem here, as To_Cursor should not need
+to write to the container or any other object.
 
 Containers that allow random access such as vectors are ideally suited for
 parallel processing, but other containers such as Doubly_Linked_Lists can
@@ -143,9 +154,17 @@
 parallel. These parallel threads then iterate through their respective chunks
 applying the processing in parallel.
 
-Since Next, Previous, and Element are all that is needed for this type of
-parallel processing, which are now all defined to be reentrant, no container
-specific wording is needed for these types of containers.
+The subprograms Next, Previous, and Element are all that are needed for this
+type of parallel processing. These subprograms (for all the
+containers) have only a cursor parameter. Since they do not have a container
+parameter, and since cursors are considered to only overlap with the element
+they designate, these calls can be made concurrently as long as each of the 
+concurrent calls designates a different element in the container. Overlapping
+might be considered a problem for the cursor object itself, but for parallel
+iteration through a container, separate cursor objects are expected to be used,
+as each cursor is an independent cursor that processes a mutually exclusive
+set of elements of the container concurrently, so overlapping of cursor objects
+does not need to be prevented for parallel iteration.
 
 This AI provides the bare minimum to allow parallel processing of the container
 libraries. All other rules involving tampering and parameter overlapping still
@@ -581,5 +600,189 @@
 Bob had two typos as well.
 
 I updated the AI fixing these typos after posting your original version.
+
+****************************************************************
+
+From: Brad Moore
+Sent: Monday, October 3, 2016  11:04 PM
+
+>> Here is my homework for ai12-0196-1.
+>
+> Question: Is "reentrant" sufficiently defined to use it in the way 
+> that it is used in A.18.2(125) here: "To_Cursor is reentrant."
+>
+> A 3(4) sort of defines it, but I don't see how that definition is 
+> sufficient to apply it as a subprogram requirement. After all, it says 
+> that all language-defined subprograms are reentrant, so that would 
+> make the above statement the null statement. I'm pretty sure that's not what
+> we want.
+
+Good point!
+
+> My presumption from the meeting is that we were going to define the 
+> term "reentrant subprogram" in some meaningful way and then we could 
+> apply that to To_Cursor and any other subprograms that need it.
+
+I had something like that before in the previous version of the AI, where I
+defined "concurrently callable" which was meant to be a label that could be
+applied to indicate the reentrant properties of a subprogram.
+
+> Perhaps an alternative would be to say that "for the purposes of 
+> determining whether To_Cursor is required to be reenterant, the 
+> Container parameter is considered to not overlap with any other object 
+> Redundant[even with itself]". Since this seems to be the only place 
+> where you need to override the default meaning of A 3(4).
+
+This sounds like a better alternative to me. Especially since so far, it seems
+this is the only place where this is needed. OTOH, if we want to identify many
+other such subprograms, it will get annoying very quickly to have to repeat
+this paragraph everywhere.
+
+> ---
+>
+> I have to wonder if it would be better to define that all 
+> language-defined functions with Global = null (what Brad mentions as a 
+> "pure function") are fully reenterant. Then apply Global = null to 
+> To_Cursor and the other functions in question. Maybe too radical.
+
+I think Global = null would not be enough, as you'd want to also be able to
+rely on "in" mode parameters not being modified using the Rosen technique.
+Otherwise even though the function may be pure, it would not be safe to supply
+the same object as a parameter in two concurrent calls.
+
+> ---
+>
+> OTOH, the decscription of To_Cursor is pretty simplistic.
+...
+> At the very least, the discussion of To_Cursor shouldn't refer to any 
+> particular implementation model, but rather discuss the abstract 
+> properties of a cursor.
+
+Agreed. With your proposed wording above, I think there is less of a need for
+an explanation here.
+
+How about replacing that paragraph with;
+
+"To_Cursor can safely be called concurrently since its container parameter is
+said above to not overlap with any object including itself. Similarly, the
+Index parameter is not a problem for concurrent calls, since elementary types
+are passed by copy, according to 6.2(3/3)"
+
+> ---
+>
+> Since Next, Previous, and Element are all that is needed for this type 
+> of parallel processing, which are now all defined to be reentrant, no 
+> container specific wording is needed for these types of containers.
+>
+> ???
+>
+> This statement seems like nonsense. You seem to have left out a bunch 
+> of steps!
+>
+> You ought to explain why Next, et. al. are "now defined to be 
+> reentrant", since there is no wording that does that and the logic 
+> needed to figure that out is not obvious. (That is, say something 
+> about cursors no longer being overlapping, so these functions are now 
+> required to be reenterant. The normative wording is all about 
+> overlapping, after all.)
+
+Ok, how about replacing that paragraph with;
+
+"The functions and procedures Next, Previous, and Element for all the
+containers have only a cursor parameter. Since they do not have a container
+parameter, and since cursors are considered to only overlap with the element
+they designate, these calls can be made concurrently as long as each of the
+concurrent calls designates a different element in the container. Overlapping
+might be considered a problem for the cursor object itself, but for parallel
+iteration through a container, separate cursor objects are expected to be
+used, as each cursor is an independent cursor that processes a mutually
+exclusive set of elements of the container concurrently, so overlapping of
+cursor objects does not need to be prevented for parallel iteration."
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Monday, October 3, 2016  9:12 PM
+
+Thanks for the quick turnaround.
+
+...
+> > Perhaps an alternative would be to say that "for the purposes of 
+> > determining whether To_Cursor is required to be reenterant, the 
+> > Container parameter is considered to not overlap with any other 
+> > object Redundant[even with itself]". Since this seems to be the only 
+> > place where you need to override the default meaning of A 3(4).
+> 
+> This sounds like a better alternative to me. Especially since so far, 
+> it seems this is the only place where this is needed.
+> OTOH, if we want to identify many other such subprograms, it will get 
+> annoying very quickly to have to repeat this paragraph everywhere.
+
+OK, I made this change.
+
+> ...
+> > At the very least, the discussion of To_Cursor shouldn't refer to 
+> > any particular implementation model, but rather discuss the abstract 
+> > properties of a cursor.
+> 
+> Agreed. With your proposed wording above, I think there is less of a 
+> need for an explanation here.
+> 
+> How about replacing that paragraph with;
+> 
+> "To_Cursor can safely be called concurrently since its container 
+> parameter is said above to not overlap with any object including 
+> itself.
+> Similarly, the Index parameter is not a problem for concurrent calls, 
+> since elementary types are passed by copy, according to 6.2(3/3)"
+
+I tried that, but it reads weirdly as the previous paragraph said the opposite.
+And it never said why this is OK (even in the abstract). So I made a couple of
+changes to this suggestion and the preceding paragraph:
+
+For Vector containers, this still leaves us with the problem of obtaining the
+multiple cursors in the first place, since one normally would want to directly
+obtain the initial cursor for each chunk of the vector. The To_Cursor
+subprogram however has a parameter that is the container associated with the
+cursor to be generated, and thus still is considered to be an overlapping call
+that is not reentrant if concurrent calls are applied to the same container
+object. We solve that by simply declaring otherwise.
+
+Thus, To_Cursor can safely be called concurrently since its container parameter
+is said above to not overlap with any object including itself.
+Similarly, the Index parameter is not a problem for concurrent calls, since
+elementary types are passed by copy, according to 6.2(3/3). We do not believe
+that there is any implementation problem here, as To_Cursor should not need to
+write to the container or any other object.
+
+
+Hope this works!
+
+...
+> Ok, how about replacing that paragraph with;
+> 
+> "The functions and procedures Next, Previous, and Element for all the 
+> containers have only a cursor parameter. Since they do not have a 
+> container parameter, and since cursors are considered to only overlap 
+> with the element they designate, these calls can be made concurrently 
+> as long as each of the concurrent calls designates a different element 
+> in the container. Overlapping might be considered a problem for the 
+> cursor object itself, but for parallel iteration through a container, 
+> separate cursor objects are expected to be used, as each cursor is an 
+> independent cursor that processes a mutually exclusive set of elements 
+> of the container concurrently, so overlapping of cursor objects does 
+> not need to be prevented for parallel iteration."
+
+Pretty good, but you lost the point about these routines being the only ones
+needed for parallel processing. (That seems like a pretty important point!)
+
+So I redid the first sentence of the paragraph:
+
+The subprograms Next, Previous, and Element are all that are needed for this
+type of parallel processing. These subprograms (for all the containers) have
+only a cursor parameter. Since they do not have a container parameter, ...
+
+I also put all of the wording into more standard format, which gets rid of
+all of those quote marks. [This is version /04 of the AI - Editor.]
 
 ****************************************************************

Questions? Ask the ACAA Technical Agent