AI22-0169-1
!standard 3.2.1(5) 26-07-14 AI22-0169-1/01
!standard 3.10.1(8.1/6)
!standard 8.6(17.2/6)
!class Amendment
!status work item 26-07-14
!status received 26-07-01
!assigned author Tucker Taft
!submitter Tucker Taft
!priority Medium
!difficulty Medium
!subject More flexible recursive types
Allow recursive types so long as it is clear that the default initial value of any subcomponent that is a recursive instance of the type (or something that includes such a component) is not infinitely recursive.
Given the proposals for optional objects (AI22-0152-1) and for unbounded indefinite objects (AI22-0148-1), it seems possible to support recursive types without requiring the use of access types as intermediaries. Recursive types are fundamental for structures such as syntax trees, binary trees, or b-trees, and also useful for other types such as linked lists. There are two places in the RM where recursive types are disallowed, one is in 3.2.1(5) which directly outlaws them, and one is in 8.6(17.2/6) which indicates when a name is interpreted as denoting the current instance of the type, rather than the first subtype of the type itself. Another relevant case is the use of a subtype_mark that denotes an incomplete view (3.10.1(8.1/6)), since declaring a mutually recursive set of types will generally require declaring an incomplete view.
Should we revise these rules to allow more general cases of recursive types, so long as infinite recursion is avoided? (Yes.)
Change the rules of 3.2.1(5) to allow a subcomponent of a type being of the type itself, so long as the default initial value for the subcomponent (or something that contains it) does not itself contain such a subcomponent. The wording has to make sure this is straightforward to implement.
Change 3.10.1(8.1/6) to allow incomplete views as components, so long as the incomplete view is completed before the enclosing type is frozen.
Change 8.6(17.2/6) to allow subtype_marks in a subtype_indication to refer to the immediately enclosing type more generally.
Modify 3.2.1(5):
A given type shall not have a subcomponent whose type is the given type itself{ (or its corresponding class-wide type), unless the subcomponent is part of a subcomponent whose default initial value is either the null value, or is statically constrained to not include a subcomponent of the given type (or its class-wide type)}.
Add after 3.10.1(8.1/6):
Modify 8.6(17.2/6):
Recursive data structures are quite common, particularly when doing any sort of programming language or structured language analysis (e.g. XML, JSON, HTML) since these languages are typically defined by a recursive grammar, meaning their syntax trees are recursive. Recursive structures are also fundamental to many other sorts of data structures, such as b-trees, binary trees, red-black trees, etc. One of the goals of the two "object-ownership" AIs proposed for Ada 202Y (AI22-0148-1 on unbounded indefinite objects, and AI22-0152-1 on optional objects) is to dramatically reduce the need for explicit use of access types, while providing the memory safety of object-based ownership.
Given these goals, it seems important to allow more general use of recursive types, where the recursive types use optional objects (we already allow this in AI22-0152-1), or to use variant records, where at least one variant is not recursive, or to use unbounded arrays of recursive elements, where the array defaults to being of zero length. Note that there is a hole in the current language if we allow class-wide types as components, since you would have infinite recursion if a type had its class-wide type as a direct component. We therefore disallow that case along with the direct recursion of the specific type, unless the default initial value is guaranteed not to contain further recursive instances.
To ensure we don't have infinite recursion, we have proposed a "trick" of requiring that the default initial value of the subcomponent whose type matches the enclosing type have a default initial value that does not have such a subcomponent, or have an enclosing subcomponent that has such as default. This "trick" means that when an object of the type is declared with any allowed values for its discriminants or its bounds, but without an explicit initial value, it is guaranteed that the (non-discriminant) components of this object can be default initialized without infinite recursion.
Here are various examples of recursive types that satisfy the requirements proposed by this AI.
type Binary_Tree is record
Payload : Element_Type;
Left, Right : null or Binary_Tree;
end record;
Both Left and Right have defaults of null, which does not contain a recursive instance.
type JSON;
type JSON_Vec is array(Positive range <>) of JSON;
type JSON (Kind : JSON_KInd) is record
case Kind is
when None => null;
when Num => Num_Val : Long_Float;
when Str => Str_Val : String := "";
when Obj => Obj_Val : JSON := (Kind => None);
when Vec => Vec_Val : JSON_Vec := [];
end case;
end record;
The Obj component has a default initial value that does not include another recursive instance, and the components of the Vec component are enclosed in Vec, whose initial value is constrained to not have any components at all.
type Syntax_Tree (Kind : Node_Kind) is record
case Kind is
when Leaf =>
Val : Leaf_Type;
when Unary =>
Unop : Operator;
Opnd : Syntax_Tree := (Leaf, <>);
when Binary =>
Binop : Operator;
Left, Right : Syntax_Tree := (Leaf, <>);
end case;
end record;
The Opnd, Left, and Right components each have defaults that do not include a recursive instance.
ACATS C-Tests are needed for this new feature; a B-Test checking cases that are not allowed is also needed.
See ARG GitHub issue #176 for the original question and answers.