CVS difference for ais/ai-00254.txt

Differences between 1.2 and version 1.3
Log of other versions for file ais/ai-00254.txt

--- ais/ai-00254.txt	2001/09/08 01:42:48	1.2
+++ ais/ai-00254.txt	2002/01/24 04:54:12	1.3
@@ -1,4 +1,4 @@
-!standard 03.10   (11)                               01-08-29  AI95-00254/01
+!standard 03.10   (11)                               02-01-23  AI95-00254/02
 !class amendment 00-12-06
 !status work item 01-08-29
 !status received 00-12-06
@@ -8,53 +8,86 @@
 
 !summary
 
-Access-to-subprogram parameters are introduced with similar properties to
-access parameters regarding accessibility.
+Access-to-subprogram parameters are introduced which enable an access to a
+subprogram at any level to be passed as actual parameter.
 
 !problem
 
 Despite the improvements introduced in Ada 95, there is no still no
 convenient way to perform certain general operations such as integration,
-minimization, iteration etc where the operation has to be parameterized by a
-function. This functionality was provided in Algol 60 and Pascal and it is
-outrageous and disgraceful (insert own words of disgust) that it is not in
-Ada.
+minimization, iteration etc where the operation has to be parameterized by
+a subprogram. This functionality was provided in Algol 60 and Pascal and it
+is surprising that it is not in Ada.
 
 !proposal
 
 Access-to-subprogram parameters are introduced as a further form of
 subprogram parameter. The changes to the syntax are as follows
 
-   access_definition ::= access subtype_mark
-                       | access_to_subprogram_definition
+   parameter_specification ::=
+        defining_identifier_list: mode subtype_mark [:= default_expression]
+      | defining_identifier_list: access_definition [:= default_expression]
+      | defining_identifier_list: access_to_subprogram_definition
+                                                    [:= default_expression]
+
+The actual subprogram must be an access value designating a subprogram
+which is subtype conformant to the formal profile. The actual parameter
+must not be null.
+
+The only operations permitted on such a formal subprogram parameter are a)
+to call it, and b) to pass it as an actual parameter to another subprogram
+call. (This simple semantics avoids many implementation problems and
+parallels the functionality of the corresponding construction in languages
+such as Pascal.)
+
+Type conversions on such parameters are forbidden and since they are of
+anonymous type like access-to-object parameters this implies that
+assignment of them is forbidden. The accessibility level of such parameters
+is considered to be infinite and this prevents the writing of P.all'Access
+which could otherwise create a hidden type conversion. (These restrictions
+again avoid a number of potential implementation difficulties.)
+
+Accessibility checks are never required and so such parameters do not need
+to carry an accessibility level with them.
+
+Access-to-subprogram values may not be used as access discriminants.
+
+The option of being protected does not apply to access-to-subprogram
+parameters. An access to a protected operation may not be passed to such
+parameters.  (Are we happy with this?)
 
-The actual subprogram must be an access value designating a subprogram which
-is subtype conformant to the formal profile.
+Default parameters are permitted for access-to-subprogram parameters with
+the semantics of renaming. The default must not be null.
 
-Rules for assignment and accessibility (static and dynamic checks) follow
-those for access to object parameters.
-
-A corollary is that access-to-subprogram values may also be used as access
-discriminants. These enable a subprogram to be permanently bound to a record.
-
-Note that the option of being protected applies to both access-to-subprogram
-parameters and access-to-subprogram discriminants. Default parameters apply
-to access-to-subprogram parameters.
-
-
 !discussion
 
-LSN 1083, which is below, outlined the problem and identified two possible
-solutions, namely, the introduction of limited access to subprogram types or,
+There are two basic uses for what might loosely be called pointers to
+subprograms. One use is as parameters to other subprograms where the
+parameter defines the activity to be performed; examples are routines for
+integration, iteration and so on. The other use is where the subprogram is
+provided for return communication purposes (usually known as callback); the
+pointer is passed to some other program which later calls back to the
+client by calling the subprogram whose address was handed over.
+
+The first usage was familiar in older languages such as Algol and Pascal.
+The second usage was provided in newer languages such as C and Modula. Ada
+83 was unhelpful in both areas and workarounds had to be used. Ada 95
+solved the callback problem through the introduction of general access-to-
+object types. However, the functional parameterization problem in its
+general form still remains.
+
+LSN 1083, a condensed version of which is at the end of this discussion
+section, outlined the problem and identified two possible solutions,
+namely, the introduction of limited access to subprogram types or,
 alternatively, access to subprogram parameters. It concluded that it would
-have been inappropriate to include either at the time of the design of Ada 9X
-largely because of implementation difficulties for display-based
+have been inappropriate to include either at the time of the design of Ada
+9X largely because of implementation difficulties for display-based
 implementations and for those with shared generics. It should be noted that
 it was recognised that there were workarounds involving generics and/or the
 new tagged types.
 
 The example in LSN 1083 concerns iterators. An example from the field of
-numerical analysis is presented below.
+numerical analysis is presented after this discussion.
 
 The workarounds provided in Ada 95 essentially involve polymorphism of some
 form - either dynamic polymorphism using tagged types or static polymorphism
@@ -71,15 +104,14 @@
 been a lost cause because most users just use Float or Long_Float anyway.
 
 The other objection concerned implementation difficulty with display based
-models. It so happens that in terms of number of users, display based
-implementations are now very much in the minority. It would thus seem foolish
-to deprive the majority of users of an important and natural feature because
-of a minority difficulty.
-
-A historical point is that the ability to pass access to subprogram
-parameters with full scope environment intact was a standard feature of Algol
-60 and widely used by numerical applications some 40 years ago. The feature
-was also present in Algol 68 and Pascal. It was not part of Ada 83 because it
+models. However, it is now clear that, given appropriate restrictions on
+the details of the feature, the implementation difficulties are not so
+severe as once thought.
+
+As mentioned above, the ability to pass access to subprogram parameters
+with full scope environment intact was a standard feature of Algol 60 and
+widely used by numerical applications some 40 years ago. The feature was
+also present in Algol 68 and Pascal. It was not part of Ada 83 because it
 was claimed that it violated one of the Steelman requirements for
 predictability; the objection was that it allowed dynamic binding of
 procedure calls and thus it was not possible in general to predict which
@@ -92,11 +124,7 @@
 techniques that have evolved over the years.
 
 It is concluded (see the example) that the workarounds are not satisfactory
-and that, since the number of users of those implementations which would have
-difficulty with the feature is now small, it is further concluded that the
-time is now ripe to correct this manifest error in the design of Ada. Ada 05
-(or whatever) should include the feature and any implementation that cannot
-cope will just have to be excused on practical grounds.
+and that Ada 0y should include the feature.
 
 LSN 1083 suggested two mechanisms: limited access-to-subprogram types and
 access-to-subprogram-parameters. Of these, the second is preferred because
@@ -131,10 +159,216 @@
 of natural extensibility is unfortunate.
 
 Ada 83 had just one workaround. Ada 95 has at least three different
-workarounds, two use generics and one uses tagged types. It is time now to do
-the job properly.
+workarounds, two use generics and one uses tagged types - none is
+satisfactory.
+
+There now follows a somewhat condensed form of LSN 1083 which was written
+during the design of Ada 9X. It concluded by recommending that downward
+closures not be supported for three reasons: a) it is a burden for some
+implementations, b) workarounds exist, c) it is too big a change at this
+stage (Ada 9x time).
+
+Addressing these three reasons: a) the proposal given here disallows all
+assignment of access-to-subprogram parameters thereby greatly reducing the
+implementation burden, b) the workarounds are horrid and a continual
+embarrassment in a general purpose language , c) seemingly much bigger
+changes are being formulated for Ada 0y and it would not seem that much of
+a change to users but a relief.
+
+============== LSN 1083 (slightly condensed extracts)
 
+1  Background to Downward Closures:
 
+Ada's access-to-subprogram types represent assignable subprogram
+values.  They support the ability to create data structures
+containing the identities of subprograms.  They support callbacks,
+where one software component declares a subprogram and hands its
+identity to another software component, which can then "call back"
+the first software component at a later time.
+
+These types do not support downward closures, where the identity of a
+more nested subprogram can be passed to a less nested subprogram.
+Downward closures can be used, for example, to implement iterators,
+like this:
+
+    package P is
+        type Integer_Set is private;
+        ... -- various operations
+        type Integer_Action is access procedure(I: Integer);
+        procedure Iterate(S: Integer_Set; Action: Integer_Action);
+            -- Call Action on each member of S.
+    end P;
+
+    function Count(S: Integer_Set) return Natural is
+        Result: Natural := 0;
+        procedure Increment(I: Integer) is
+        begin
+            Result := Result + 1;
+        end Increment;
+    begin
+        Iterate(S, Increment'Access); -- Illegal!
+        return Result;
+    end Count;
+
+Increment'Access above is illegal, because Increment is more nested
+than type Integer_Action.  It would be bad to have to make Increment
+global, because that would require making the variable Result global.
+It is a bad idea to force the use of global variables in a language
+that has tasks -- in this example, Count would not be reentrant if
+Result were global.
+
+Note that this situation is typical of iterators and similar things
+-- in typical use, the action passed to an iterator will often need
+visibility upon a variable declared in the caller of the iterator, in
+order to accumulate some sort of result.
+
+The reason for the restriction is that access-to-subprogram types
+allow assignment.  At the point where Iterate is called, we don't
+know if the body of Iterate is going to save the access value in a
+global variable.  We disallow passing the nested Increment procedure
+because Iterate *might* save a pointer to it, and call it later,
+after Increment (and the variable Result) no longer exist.
+
+...
+
+2  Implementation Issues:
+
+In a language (like Ada) with nested subprograms, each subprogram
+needs some way to access its environment -- that is, the variables
+declared outside it.  There are two common methods for representing
+this environment: static links, and displays.  Most Ada compilers use
+static links, but some use displays.  One key difference between the
+two methods is that static links have a compile-time-known size (32
+bits, on a typical machine), whereas the size of a display depends on
+the maximum nesting depth throughout the partition.
+
+In an implementation with static links, an access-to-subprogram value
+is generally represented as a pair of addresses -- the address of the
+subprogram's code, and the static link.  However, given the current
+Ada 9X rules, an access-to-subprogram type that is declared at
+library level does not need the static link -- it can be represented
+as just a code address.  This is nice, because it is efficient, and
+it allows the representation to easily match C's typical
+representation of function pointers.  Access-to-subprogram types
+declared one level deeper than library level can also be represented
+as just a code address.  However, two or more levels deeper requires
+the static link.
+
+In an implementation with displays, given the current rules, an
+access-to-subprogram value can be represented as just a code address
+-- it is not necessary to attach a display to each access value.
+This also has the nice interoperability-with-C property.
+
+It has been suggested that downward closures be supported by allowing
+the Unchecked_Access attribute on subprograms.  This is rejected because it
+would be unsafe and it would be uncomfortable to introduce erroneousness to
+a high-level feature like downward closures. It would also require every
+access-to-subprogram value to carry a static link or display, because the
+nesting level of the designated subprogram would no longer be restricted at
+compile time.  This would break the interoperability-with-C property, and
+would be less efficient.
+
+3  Possible implementations:
+
+There are two ways to support downward closures that we would
+recommend, if downward closures are to be supported.  Both ways
+recognize the fact that downward closures really need a separate
+feature from the callback style of access-to-subprograms:
+
+    - Limited access-to-subprogram types.
+
+    - Access-to-subprogram parameters.
+
+Limited access types were in an earlier version of Ada 9X.  Since
+they would be limited, assignment would be disallowed, so
+downward-closure-style parameter passing could be allowed, and would
+be safe.  The compiler would implement limited access-to-subprogram
+types with a static link or display.  Non-limited ones would retain
+the interoperability-with-C property.  The syntax would be something
+like this:
+
+    type Integer_Action is limited access procedure(I: Integer);
+                        -- ^^^^^^^
+    procedure Iterate(S: Integer_Set; Action: Integer_Action);
+        -- Call Action on each member of S.
+
+Type conversion from limited to non-limited would be illegal.
+
+Access-to-subprogram parameters would be an extension to access
+parameters (not to be confused with parameters of a named access
+type).  The syntax would be something like this:
+
+    procedure Iterate(S: Integer_Set;
+                      Action: access procedure(I: Integer));
+        -- Call Action on each member of S.
+
+This is quite similar to the syntax used in Pascal.  As for any access
+parameter, the access type would be anonymous.  Parameter type matching
+would be based on the designated profile.  Access parameters already use
+run-time accessibility checks -- this new kind would do likewise.  Thus,
+assignment would be allowed, but the accessibility checks would prevent
+dangling pointers.  In our iterator example, if Iterate were to try to
+copy Action to a global variable (during the call to Iterate from
+Count), then Constraint_Error would be raised, because Count.Increment
+is too deeply nested.  The value of an access-to-subprogram parameter
+would need to have a static link or display.  Library-level access types
+could retain the interoperability-with-C property.
+
+Of the two workable methods outlined above, the access-to-subprogram
+parameters method would be somewhat simpler in Reference Manual
+terms, because it would be able to piggyback on the existing access
+parameters feature for its rules and semantics.  The implementation
+complexity seems equivalent.  Efficiency of the limited access types
+method would be slightly better, because it would not be necessary to
+pass in information needed for the run-time accessibility checks.
+Limited access types would be the first elementary limited types;
+we would have to reword the parameter passing rules to avoid a
+contradictory requirement to pass by copy and by reference.  (It
+doesn't really matter which is done, actually.)
+
+For implementations with static links, the implementation of either
+method is straightforward.  Such implementations already need to
+include a static link in at least some access-to-subprogram values,
+and the downward-closure ones would be the same.
+
+However, for implementations with displays, either method is an
+implementation burden, because:
+
+    - The current rules do not require carrying the display
+      with the access-to-subprogram value, whereas the new
+      rules would.
+
+    - The size of the display is not easily known at compile time.
+      Its size can be calculated at run time, or a maximum possible
+      size can be known if there is a restriction on nesting depth.
+      Either way, managing the passing of the unknown size display
+      causes complexity. ...
+
+It should also be noted that an implementation with displays would be
+less efficient than one with static links, because an indirect call
+would require copying the entire display.  It's not that big of a
+deal, however -- it just means copying several words of memory, and
+there would be no *distributed* overhead.
+
+...
+
+4  Conclusion
+
+We (reluctantly) recommend not supporting downward closures, because:
+
+    - An implementation burden exists for display-based implementations.
+
+    - Workarounds exist.
+
+    - It seems like too big a change to make to the language at this
+      late date.
+
+I say "reluctantly" recommend, because it is clear to me that the
+functionality is desirable, and if we were designing Ada 9X from
+scratch, we would support downward closures.
+
+================ End of condensed form of LSN 1083
+
 !example
 
 Consider the problem of integrating a function Fn of one variable X between
@@ -231,7 +465,7 @@
 procedure Main is
    Result: Float;
 begin
-   Result := Integrate.Do_It(G'Access, 0.0, 1.0);
+   Result := Integrate.Do_It(G'Access, 0.0, 1.0);  -- OK
     ...
 end Main;
 
@@ -324,7 +558,6 @@
 The idea is that we now extend the type Integrator as necessary to enable it
 to pass any auxiliary data such as the nonlocal variable X.
 
-
 with Integrate;
 procedure Main is
    type G_Integrator is new Integrate.Integrator with null record;
@@ -386,9 +619,17 @@
     ...
 end Main;
 
-Note that this is precisely how we originally tried to write it. There are no
-longer any problems with accessibility because the rules are similar to those
-for access parameters.
+Note that this is precisely how we originally tried to write it. There are
+no longer any problems with accessibility because the accessibility of the
+parameter type is deemed to be infinite.
+
+An alternative proposal might be to mirror more closely the procedure
+parameter facility of Pascal and so sweep the access mechanism under the
+rug. This would mean that the calls of Integrate.Do_It would have actual
+parameters of just F and G rather than F'Access and G'Access. Although this
+might be more natural if starting from scratch, nevertheless given the
+existence of access-to-subprogram types for callback etc, it seems more
+natural to make the notations uniform.
 
 Finally, it should be noted that neither of the above workarounds were
 applicable to Ada 83 which did not have access-to-subprogram types. Instead a
@@ -466,7 +707,7 @@
 !reference RM9X-3.10.2(16);4.0
 !reference AARM-12.3(12.p,12.q);4.0
 !reference LSN-1042 on Accessibility Checks in Generics
-!from Bob Duff $Date: 2001/09/08 01:42:48 $ $Revision: 1.2 $
+!from Bob Duff $Date: 2002/01/24 04:54:12 $ $Revision: 1.3 $
 !discussion
 
 Two issues related to access types and the accessibility rules came
@@ -879,7 +1120,7 @@
 !topic LSN on Accessibility Checks in Generics
 !key LSN-1042 on Accessibility Checks in Generics
 !reference MS-12;4.6
-!from Bob Duff $Date: 2001/09/08 01:42:48 $ $Revision: 1.2 $
+!from Bob Duff $Date: 2002/01/24 04:54:12 $ $Revision: 1.3 $
 !discussion
 
 This Language Study Note discusses accessibility checks, and their
@@ -2712,6 +2953,43 @@
 
 2. You do not pay for loading a static link in the normal case where the
 pointer points to a global procedure.
+
+****************************************************************
+
+From: John Barnes
+Sent: Tuesday, January 22, 2002  10:13 AM
+
+I just sent a new version of AI-254 on downward closures to
+Randy so I guess it will be on the net soon.
+
+I felt that you might like to hear a further moan from me on
+the topic.
+
+Over Christmas I needed to solve a pair of non-linear
+algebraic equations. I turned to Ada, my favourite language
+for hacking such things. I quickly knocked up a general
+Newton-Raphson thing hoping that it would be simple enough
+to pass the functions to be solved as as access-to-function
+taking a vector and returning a vector. But I immediately
+fell into the downward closures pit. I had to make a lot of
+stuff global that shouldn't have been. In fact I ended up
+with a package named Variables and context clauses saying
+with Variables; use Variables; everywhere. Disgusting.
+
+Clearly I should have called the package F_Global_Common. I
+am permanently amazed that what I did so easily in 1962
+using Algol 60 is beyond Ada 95 without introducing various
+steamhammers.
+
+End of moan.
+
+****************************************************************
+
+From: Robert Dewar
+Sent: Tuesday, January 22, 2002  6:53 AM
+
+I am a little surprised that this particular problem was not trivially
+solved using a generic procedure.
 
 ****************************************************************
 

Questions? Ask the ACAA Technical Agent