======= LSN014.AccOOP ======= /* Written 8:19 am Mar 5, 1991 by davidr@inmet.inmet.com in inmet:ada9x.mail */ /* ---------- "Language Study Note on Access Types" ---------- */ >From davidr@inmet.inmet.com Tue Mar 5 08:19:27 1991 From: davidr@inmet.inmet.com (David Rosenfeld) Subject: Language Study Note on Access Types and OOP Here is the language study note on access types and OOP which Tucker mentioned in a previous message. It outlines the different paths that the MRT explored in coming to the solution in the mapping document. I know Norm has proposed another, (somewhat related), alternative. --------------------------------------------------------------------------- ADA 9X LANGUAGE STUDY NOTE MARCH 5, 1991 THE INTERACTION BETWEEN ACCESS TYPES AND UNIVERSAL TAGGED TYPES This is the first language study note issued by the Ada 9X mapping revision team. We are issuing this note in order to demonstrate that we have explored the issues relative to the "access type problem" raised at the last DR meeting. A brainstorming session was held on January 28, 1991. Present at this discussion were Tucker Taft, David Rosenfeld, Chris Gosling, Bill White, and Rich Hilliard. This note documents the ideas discussed in (and after) this meeting. We are trying to address the problem of access types within the new type model proposed for Ada 9X. The problem has several facets. There is a desire for a dispatch relative to an access type parameter, where in the model previously proposed this is not possible. There is also a desire for a class hierarchy of access types that mirrors the hierarchy of designated types, thus allowing interconvertibility between pointers within that class. These two problems, dispatch and inter-conversion, are related since we base dispatch on the possibility of implicit conversion to the implicitly declared derivable subprograms of the universal type. Two examples were used extensively in the discussions, one is a simple link class, which can be derived to create linkable objects. The other was the abstract syntax tree. -- This is example implements a simple class of double links, and -- and a push and pop routine which implements a stack of things -- inherited from the link class. type Link; type Link_Class_Access is access Link'CLASS; type Link is tagged record Next : Link_Class_Access; Prev : Link_Class_Access; end record; -- Both of these procedures should be inherited by types derived -- from link. -- One purpose of this exercise is to explore language mechanisms -- that would allow that to happen. procedure Push H: in out Link_Class_Access; Item: Link_Class_Access ) is begin Item.Next := H.Next; Item.Prev := H; H.Next := Item; end Push; function Pop(H: in out Link_Class_Access) return Link_Class_Access; is Top: Link_Class_Access := H.Next; begin H.Next := Top.Next; H.Next.Prev := H; return Top; end Pop; -- Assume the following type is declared in some other package type Node is new Link with record Value: integer; end record; At the DR meeting Robert Dewar was concerned that pointers into a class should be useful even when the universal type isn't tagged. He was concerned because the C++ classes required to implement the above example do not require any virtual functions. Instead, they require a cast to convert between a (* link) and (* node), The equivalent situation holds in Ada 9X, provided that unchecked_conversion is used in place of pointer casting. The current rules actually require 2 unchecked conversions. One from Node to Link (after allocating a node), and one from Link to Node, when operations on Node are needed. The following example illustrates: function To_Link_From_Node(...) is new Unchecked_Conversion(...) ; function From_Link_To_Node(...) is new Unchecked_Conversion(...) ; Push(Header, new To_Link_From_Node(Node'(null, null,0);) From_Link_To_Node(Pop(Header)).Value; The unchecked conversion of the allocator is unnecessary if "new Node'(null,null,0)" always allocates a full Node (which it does when Link is tagged), even though in the untagged case it could legally allocate a Link when the result is assigned to a Link_Class_Access). In general we refer to the dispatchable access types associated with T as T'ACCESS. The implication is that like T'CLASS, T'ACCESS is implicitly declared along with the every type. It is also possible allow (or require) that the user declare these types himself. A possible syntax for such a declaration is: type T is ...; type T_Access is access T; type T1 is new T with ...; type T1_Access is new T_Access with access T1; If these types are declared they can then be made private or limited private. This is necessary to preserve complete information-hiding. An implicitly declared T'ACCESS, on the other hand, is more convenient to write. One could argue that if the designated type was [limited] private then the goals of information hiding are met anyway. This is an orthogonal issue, since both the user declared types and the implicitly declared types are essentially identical, or at least can be defined as identical if we determine that this is desirable. One ramification to keep in mind is that "pure" packages must not define access types, and if every type defines a 'ACCESS type implicitly the rules for detecting "pure" packages get more complicated. Possible Solutions We examined four possible solutions to the main problem: 1. Class Reference Types ala C++ 2. Generalized Companion Types 3. Companion Access Types 4. No Special Support. Special Dispatching Class Reference Types One obvious way to solve the problem is to mimic C++ by defining a special dispatching class reference type. Operations on these class reference types correspond to the "virtual" operations in C++. Some mechanism is required to select the tag which controls the dispatch, since the restriction that all tags must match makes no sense with this model. This is a "last resort solution" since it implies that we either junk the entire OO01.ExtPoly proposal, or have two completely separate dispatching mechanisms. Generalized Companion Types Generalized companion types are a mechanism that allows a set of types to be associated with some principle type. These types are not derivable themselves, but get automatically derived along with the principle type, and form a class hierarchy corresponding to the class hierarchy of the principle type. An example solution using generalized companion types is: type Link is ...; type Link'Ptr is access Link; If Node is derived from Link then Node'Ptr is automatically derived at the same type from Link'Ptr and defined to be access Node. There are serious problems with generalized companion types. The first is that the systematic substitution must be extended to the body of operations. This is more fully discussed below. Another problem is that T'CLASS is not a companion type of T (since it is derived from T), even though it looks like one. Also, they create a clear distinction between T'ACCESS'CLASS and T'CLASS'ACCESS (one has a tag with the pointer, and the other has the tag with the data). A simpler model where tags are always with the data is preferred. One advantage to having generalized companion types is that a homogeneous list class can be constructed. No other proposal has this much expressive power. However, homogeneous lists are not possible in C++, and they can be achieved using generics, so the extra expressive power is not worth the added complexity. Generalized companion types are very similar in power and complexity to extendible package types. When we realized this, we took another brief look at package types to see if they could help solve the problem, but quickly decided that it was crazy to go that far when all we wanted was dispatching on access types. Specialized Companion Access Types A much simplified version of the companion type approach relies on systematic replacement of the type name during derivation to make 'ACCESS and 'ACCESS'CLASS meaningful. We can illustrate the approach with the Abstract Syntax Tree Example. type Ast_Node is tagged record ...; -- In some other package type Expr is new Ast_Node with record Src_Pos: Source_Position; end record; subtype Expr_Ptr is Expr'ACCESS; -- We want the following to be inherited by all types derived from -- Expr procedure Walk(E: Expr_Ptr) is begin Print(E.Src_Pos); end Walk; -- In yet another package type Binop_Expr is new Expr with record Left: Expr_Ptr'CLASS; Right: Expr_Ptr'CLASS; end record; subtype Binop_Expr_Ptr is Binop_Expr'ACCESS; procedure Walk(B: Binop_Expr_Ptr) is -- assume B is bound to an access variable which points -- at a tagged Binop_Expr -- This procedure walks the left child, -- performs the action associated with the parent class -- and walks the right child. begin Walk( B.Left); -- This dispatches Walk( B'PARENT); -- This does not dispatch Walk( B.Right); end Walk; The walk of B.Left dispatches because the type of B.Left is universal. The walk of B'Parent does not dispatch because the type of B'Parent is Expr'ACCESS. The code does not work as written, however, since Expr1 is declared in another package and the walk procedure is not directly visible. Qualifying the name completely defeats the purpose of using 'PARENT to begin with since the whole point is to be able to express the idea of performing the parents action without knowing anything about the parent. At this point Tucker revealed a new attribute, T'BASIS, which solves the problem. There are two reasonable approaches to dealing with with types derived prematurely (ie before all the primitive operations of the parent were established); either all the operations are inherited or none are. If the latter, then one can define all prematurely derived types as derived from an anonymous (called the basis type) type declared at the same time as the parent type. The operations of the basis type consist of the inherited and pre-defined operations of the parent type, but do not include the new operations defined in the package. Basis types can be used to reveal the pre-defined or basic operations that may have been overridden for a type, which solves the longstanding problem of how to get back to a hidden pre-defined or basic operation. In our example, "Walk(B'BASIS)" would do precisely what we want, and does not require a package qualification (since Binop_Expr_Ptr'BASIS is a derived type (inheriting Walk from Expr_Ptr) declared in the same package as Binop_Expr_Ptr. 'PARENT will be removed from the language, and replaced with 'BASIS which appears to work better, and has wider utility. T'BASE can be transformed upward compatibly into T'BASIS It is unclear if this is desirable, since T'BASE will be used within generics to declare numeric objects which want to be the same type as a generic formal, but without inheriting the range constraint. Although this affect is achieved with T'BASIS as well as T'BASE, it is accompanied by the side-effect of operator reemergence. This isn't a problem for generics as they currently are defined, but the operator visibility proposal changes that behavior. The statement "Walk(B'BASIS);" in the (now modified) example calls the Expr_Ptr walk without a dispatch. The tag associated with the parameter is not, however, the tag for an Expr_Ptr, but rather the tag for a Binop_Expr. The conversion does not change the tag. This means that within the Expr_Ptr walk, E'TAG need not equal Expr_Ptr'TAG. These semantics are not appropriate for any access to Expr, which creates a distinction between T'ACCESS and "access T." With all this in mind, here are the semantics of 'ACCESS types, with respect to how they relate to regular access types, and what their conversion properties are. Assume the existence of type T is tagged ....; type A_T is access T; type A_TC is access T'CLASS; subtype T_Ptr is T'ACCESS; type T1 is new T ...; type A_T1 is access T1; type A_T1C is access T1'CLASS; subtype T1_Ptr is T1'ACCESS; Allocators for A_T and A_T1 do not place a tag on the heap. Allocators for T_Ptr, T1_Ptr, A_TC and A_T1C allocate a tag with the data. A_T and A_T1 are not inter-convertible. T1_Ptr may be converted to T_Ptr without a constraint (tag) check. T_Ptr may be converted to T1_Ptr subject to a constraint (tag) check. A_TC and A_T1C are interconvertible subject to constraint checks. And they are also convertible to T_Ptr and T1_Ptr. These rules imply that T'ACCESS is in fact access to T'CLASS with the additional property of supporting dispatching operations. Therefore in order to explicitly declare the 'ACCESS types one could say: type T is ... ; type T_Ptr is access T'CLASS; type T1 is new T with ...; type T1_Ptr is new T_Ptr with access T1'CLASS. Or one could limit a "companion type" definition so that it only referred to the universal type associated with principal type, and not the principal type itself. type T is ... ; type T'PTR is access T'CLASS; type T1 is new T with ...; -- T1'PTR is automatically derived along with T1. -- It's designated type is T1'CLASS. Because these 'ACCESS types are a form of companion type, some of the problems with companion types arise. In particular, substitution in the body is required for any derivable function which returns a 'ACCESS type. The following example illustrates the problem: function Unsafe(E: Expr_Ptr) return Expr_Ptr is X : Expr_Ptr := new Expr' ... ; begin return X; end Unsafe; If Unsafe is not overridden for Binop_Expr_Ptr, then it will return an Expr'ACCESS, not an Binop_Expr'ACCESS. The constraint check performed as part of the conversion of the result will fail. This is much to serious an error to leave unchecked at compile time. It is possible to view the 'ACCESS types as subtypes constrained by the tag, and require that all such subtypes in any given call be constrained by the same tag. This would at least allow the constraint check to be moved to the body. A better solution is to require that all functions returning 'ACCESS types become abstract for the derived types, but this prevents reuse for a large body of perfectly reasonable code. A way way to write reusable functions that return 'ACCESS types is to return 'ACCESS'CLASS instead of 'ACCESS. This combined with the rule that universal types are not systematically substituted during derivation still allows for the equivalent functionality of C++. T'ACCESS'CLASS has the same representation as T'ACCESS and can point to the same set of objects as T'ACCESS. The scheme outlined above uses T'ACCESS'CLASS to block the systematic substitution of T'ACCESS during derivation. It is possible to use this characteristic of 'CLASS types to account for the nonstandard (as far as derivation is concerned) behavior of the boolean relational operators declared in standard, but changing the spec of pre-defined "<" to return Boolean'CLASS will cause upwards- compatibility problems for generics with a generic formal function parameter defaulting to the existing spec of "<". No Special Support The original problem was that access types did not support dispatch, and saying ".all" to get dispatch was problematic when the procedure called needed to manipulate the object as a pointer. The Push and Pop routines in the Link example are such operations. Five new rules, along with the original OO01.ExtPoly MI, and a simplified OO02.GenlRef MI can alleviate this problem. 1. Implicit dereferencing may ocurr if an access type is passed opposite an aliased formal parameter. 2. 'ACCESS of an aliased formal parameter returns an access to the universal type. 3. Allocators for tagged types must always allocate a tag with the data (this is different than the above proposal.) 4. Aliased variable declarations of tagged types must always allocate a tag. 5. A non-limited access type may be converted to another access type if both share a collection (ie are declared in the same scope), are both universal, and the designated type of the operand is implicitly convertible to the target designated universal type. With these rules, pointers to universal types can be passed opposite to dispatching operations, and the original pointer can be reconstructed within the body of the procedure if required by using the 'ACCESS attribute on the parameter. Here's a heterogeneous stack, implemented via the link-class: type Link ; type Any_Link_Ptr is access Link'CLASS; type Link is tagged record next: Any_Link_Ptr; prev: Any_Link_Ptr; end record; procedure Push(H: in out aliased Link; Item: aliased Link) is begin Item.Next := H.Next; Item.Prev := H'ACCESS ; H.Next := Item'ACCESS; end Push; function Pop(H : in out aliased Link) return Any_Link_Ptr is Top : Any_Link_Ptr := H.Next; begin H.Next := H.Next.Next; H.Next.Prev := H'ACCESS; return Top; end Pop; Actuals of Any_Link_Ptr can be passed opposite parameters of type "aliased Link", and a dispatch to the appropriate subroutine will occur. If the value of the pointer is required within the procedure, as it is in Push and Pop, the 'ACCESS attribute can be used to re-create it. Since the tag is stored along with the data, the 'ACCESS attribute causes the "original tag" to re-emerge. /* End of text from inmet:ada9x.mail */