--- ai05s/ai05-0153-2.txt 2009/11/04 06:26:38 1.6 +++ ai05s/ai05-0153-2.txt 2010/02/12 06:58:46 1.7 @@ -1,14 +1,14 @@ -!standard 3.2.2(7) 09-10-29 AI05-0153-2/04 +!standard 3.2.2(7) 10-02-12 AI05-0153-2/05 !class Amendment 09-10-16 !status work item 09-10-16 !status received 09-10-16 !priority Medium !difficulty Medium -!subject Discontiguous scalar constraints and extended discriminant constraints +!subject Set constraints and extended discriminant constraints !summary -Add list scalar constraints to the language, and extend the available +Add set scalar constraints to the language, and extend the available discriminant constraints. !problem @@ -27,14 +27,14 @@ !wording -List scalar constraints: +Set scalar constraints: Modify 3.2(7/2): The set of possible values for an object of a given type can be subjected to a condition that is called a *constraint* (the case of a null constraint that specifies no restriction is also included); the rules for which values satisfy a given kind -of constraint are given in 3.5 for range_constraints {and list_constraints}, +of constraint are given in 3.5 for range_constraints {and set_constraints}, 3.6.1 for index_constraints, and 3.7.1 for discriminant_constraints. The set of possible values for an object of an access type can also be subjected to a condition that excludes the null value (see 3.10). @@ -48,41 +48,41 @@ Modify 3.2(9/2): A subtype is called an unconstrained subtype if its type has unknown discriminants, -or if its type allows range, {list,} index, or discriminant constraints, but the subtype +or if its type allows range, {set,} index, or discriminant constraints, but the subtype does not impose such a constraint; otherwise, the subtype is called a constrained subtype (since it has no unconstrained characteristics). Replace 3.2.2(6) with: scalar_constraint ::= - range_constraint | list_constraint | digits_constraint | delta_constraint + range_constraint | set_constraint | digits_constraint | delta_constraint Add after 3.5(4): -list_constraint ::= when discrete_choice_list +set_constraint ::= when discrete_choice_list [Author's note: I used "when" and "discrete_choice_list" here to be consistent with other parts of the language. We could use other syntaxes, but that would just make it harder to remember the correct syntax IMHO. Alternatives are discussed in the discussion section.] -A value *belongs* to the discrete_choice_list of a list_constraint if it is of +A value *belongs* to the discrete_choice_list of a set_constraint if it is of the type of the choices of the list, and it is either equal to one of the expressions of the list or it belongs to one of the discrete_ranges of the list. -A value *satisfies* a list_constraint if it belongs to the discrete_choice_list +A value *satisfies* a set_constraint if it belongs to the discrete_choice_list of the constraint. -The *lower bound* of a list_constraint is the smallest value +The *lower bound* of a set_constraint is the smallest value used in an expression or the lower bound of a discrete range in the discrete_choice_list of the constraint, unless the list only contains null range choices, in which case it is the largest value used in the lower bound of -a discrete range. The *upper bound* of a list_constraint is the largest value +a discrete range. The *upper bound* of a set_constraint is the largest value used in an expression or the lower bound of a discrete range in the discrete_choice_list of the constraint, unless the list only contains null range choices, in which case it is the smallest value used in the upper bound of a discrete range. -AARM Reason: We define upper and lower bounds for list_constraints so that +AARM Reason: We define upper and lower bounds for set_constraints so that the existing assumption that all discrete subtypes have such bounds is maintained. We have the special case for all null range choices so that the bounds in that case represent a null range as well. For instance, for Natural when 3 .. 1 | 11 .. 10, @@ -90,33 +90,13 @@ give given bounds of 11 .. 1 (which make more sense). End AARM Reason. -A list_constraint is *discontiguous* if there exists a value that belongs to the range -defined by the lower and upper bound of the constraint that does not belong to the -list_constraint, or if the list_constraint has more than one choice of which one or more -are null ranges. A scalar subtype is *discontiguous* if it has a discontiguous -list_constraint. - -[Editor's Note: Steve Baird suggests that this concept be called "complex" or some -other such name as "discontiguous" is confusing in the case of null ranges. That's -a reasonable point; but the best term isn't obvious and the wording changes needed -are purely search-and-replace, so I left it for discussion.] +A scalar subtype is a *set subtype* if it has a set_constraint, or is a subtype +defined by a subtype_indication without a range_constraint whose subtype_mark +denotes a set subtype. -AARM Ramification: We require staticness for the discrete_choices, so the lower and -upper bounds can be determined at compile-time (we don't want to have to do a -complex calculation to determine S'First). This also allows us to make legality -depend on whether the list_constraint is contiguous. -End AARM Ramification. - -AARM Reason: We define lists that have multiple choices and one or more null ranges -as discontigious so that they cannot be used in arrays and slices. Otherwise, users -could be confused by the bounds. Such things could have a contiguous set of values: -Arr(Natural when 5 | 5 .. 4) and Arr(Natural when 3 .. 1 | 11 .. 10) both would be -allowed without the extra rule. -End AARM Reason. - Add after 3.5(5): -For a subtype_indication containing a list_constraint, the type of the expressions +For a subtype_indication containing a set_constraint, the type of the expressions (if any) in the discrete_choice_list are expected to be of the type determined by the subtype_mark of the subtype_indication. The type of any discrete_range in the discrete_choice_list shall resolve to that of the subtype_mark of the subtype_indication. @@ -124,12 +104,12 @@ Legality Rules An others choice may not appear in a discrete_choice_list used in a -choice_list_constraint. +set_constraint. [Author's note: We probably could figure out a useful meaning for "others" in this case, but it is unlikely to be intuitive.] -The type of a subtype_indication containing a list_constraint shall be discrete. +The type of a subtype_indication containing a set_constraint shall be discrete. [Author's note: This concept could be extended to all scalar types, but that is dubious as equality operations on real types are often not recommended; it seems @@ -137,22 +117,35 @@ only ranges would fix this, but seems inconsistent with the rest of the language. Also, allowing real choice_lists would require separating the syntax.] -The expressions and discrete_ranges of the discrete_choice_list of a list_constraint +The expressions and discrete_ranges of the discrete_choice_list of a set_constraint shall be static. -[Author's note: See the AARM note above. Perhaps we could make a useful definition without -requiring this, but it would be a lot harder to describe and implement.] +AARM Ramification: We require staticness for the discrete_choices, so the lower and +upper bounds can be determined at compile-time (we don't want to have to do a +complex calculation to determine S'First). It also makes the implementation of +loops possible, and allows case completeness checking to not require values outside +of the set. +End AARM Ramification. + +[Author's note: Perhaps we could make a useful definition without requiring this, +but it would be a lot harder to describe and implement.] +A discrete_range that appears in a discrete_choice_list of a set_constraint shall not +represent a null range. + +[Author's note: We need this to eliminate all kinds of useless cases. See the +discussion. Note that we can do this only if we require static choices.] + Modify 3.5(7): -A constrained scalar subtype is one to which a range constraint {or list +A constrained scalar subtype is one to which a range constraint {or set constraint} applies. The *range* of a constrained scalar subtype {with a range constraint} is the range associated with the range constraint of the subtype. -The *range* of a constrained scalar subtype {with a list constraint} is the -range determined by the lower bound and upper bound of the constraint. The +{The *range* of a constrained scalar subtype {with a set constraint is the +range determined by the lower bound and upper bound of the constraint.} The *range* of an unconstrained scalar subtype is the base range of its type. -[Author's note: Most places where the range of a list constraint would be used +[Author's note: Most places where the range of a set constraint would be used have special rules so that we don't actually use it. We define it so that S'First and S'Last are well-defined.] @@ -160,7 +153,7 @@ A range is compatible with a scalar subtype S if and only if: * it is a null range; or - * S has a list constraint and each value of the range belongs to the + * S has a set constraint and each value of the range belongs to the discrete_choice_list; or * S is unconstrained or has a range constraint and each bound of the range belongs to the range of the subtype. @@ -168,9 +161,9 @@ A range_constraint is compatible with a scalar subtype if and only if its range is compatible with the subtype. -A list_constraint is compatible with a scalar subtype if and only if - * the value of each expression of the discrete_choice_list satisfies the list - constraint of the subtype, or if the subtype does not have a list +A set_constraint is compatible with a scalar subtype if and only if + * the value of each expression of the discrete_choice_list satisfies the set + constraint of the subtype, or if the subtype does not have a set constraint, belongs to the range of the subtype; and * each range of the discrete_choice_list is compatible with the subtype. @@ -182,33 +175,37 @@ subtype. This means that legality rules and the definition of dynamic semantics for the -use of list_constraints do not have to worry about ancestors of the type +use of set_constraints do not have to worry about ancestors of the type End AARM Discussion. Add after 3.5(9): -The elaboration of a list_constraint consists of the elaboration of the +The elaboration of a set_constraint consists of the elaboration of the discrete_choice_list. Expressions and discrete_ranges of the discrete_choice_list are evaluated in an arbitrary order, and are converted to the type of the subtype_mark of the subtype_indication which contains the -list_constraint. +set_constraint. + +Add to 3.5(14): -[Author's note: Should S'Range be illegal/raise Program_Error if the subtype has -a discontiguous list constraint? It's a dubious construct, but since you can -always write it explicitly (it's defined to be equivalent to S'First..S'Last), -it's hard to say that it should be illegal. And not allowing S'First or S'Last -seems bad (it is useful to find the smallest or largest value even without -using the range).] +S'Range is illegal if S statically denotes a set subtype. S'Range raises +Program_Error is S is a set subtype. +AARM Reason: Technically S'Range is S'First..S'Last, which is well defined. +But it often considered to be the same as the S, and that is not true if +S is a set subtype. So we make it illegal (if we know statically that the +subtype is a set subtype) or raise Program_Error otherwise (as in a generic +unit instantiated with a set subtype). + Add as the last sentence of 3.6(9): -An index subtype shall not statically denote a discontiguous subtype. +An index subtype shall not statically denote a set subtype. Add as the last sentence of 3.6(21): The elaboration of an array_type_definition raises Program_Error if the index -subtype is a discontiguous subtype. +subtype is a set subtype. AARM Reason: We don't want to create "holey" array types. By raising Program_Error, we prevent generic contract problems. But we also have a legality @@ -218,12 +215,12 @@ Add after 3.6.1(5): The discrete_range of an index_constraint shall not statically denote a -discontiguous subtype. +set subtype. Add as the last sentence of 3.6.1(8): The elaboration of an index_constraint raises Program_Error if any -discrete_range is a discontiguous subtype. +discrete_range is a set subtype. AARM Reason: We don't want to create "holey" array subtypes. By raising Program_Error, we prevent generic contract problems. But we also have a legality @@ -233,7 +230,7 @@ Add after 3.8.1(5): The discrete_range of a discrete_choice shall not be a subtype_indication with -a list_constraint. +a set_constraint. AARM Reason: This is needed to avoid ambiguity. Otherwise, it would be impossible to tell where the subtype_indication ended and the case choices start in something @@ -246,13 +243,13 @@ Legality Rules -The discrete_range of a slice shall not statically denote a discontiguous +The discrete_range of a slice shall not statically denote a set subtype. Add as the last sentence of 4.1.2(7): The evaluation of a slice raises Program_Error if any discrete_range is a -discontiguous subtype. +set subtype. AARM Reason: We don't want to create "holey" slices, especially as slices can be required to be passed by reference (for by-reference component types). By @@ -267,19 +264,19 @@ Modify 4.9(29): -* A scalar constraint is static {if it has a list_constraint, }if it has no +* A scalar constraint is static {if it has a set_constraint, }if it has no range_constraint, or one with a static range; [Author's note: strictly speaking, we don't need to modify this sentence, as a -scalar constraint with a list_constraint "has no range_constraint". But that's +scalar constraint with a set_constraint "has no range_constraint". But that's very tricky!] [For static matching, 4.9.1(1.2/2), see below; it's modified by both parts here.] Add an AARM note after 5.4(7): -AARM Ramification: This implies that for a static discontiguous subtype, only -the values belonging to that subtype should be covered. If instance, if we have: +AARM Ramification: This implies that for a static set subtype, only the values +belonging to that subtype should be covered. If instance, if we have: subtype Small_Odds is Natural when 1 | 3 | 5 | 7; case Small_Odds'(My_Func) is @@ -293,7 +290,7 @@ Add an AARM note after 5.5(9): AARM Ramification: This description implies that for loops will properly iterate -over just the values defined by a discontiguous subtype. For instance, if we +over just the values defined by a set subtype. For instance, if we have subtype Small_Odds is Natural when 1 | 3 | 5 | 7; @@ -356,7 +353,7 @@ AARM Reason: A discriminant_constraint that contains a discrete_range is mutable, in the sense that the discriminant(s) can be changed (to a different value that -also belongs to the range or list). "Known to be constrained" +also belongs to the range or set). "Known to be constrained" exists specifically to avoid problems with renames and the like when discriminants change, so we need to add this case to it. The subtype is constrained, but not enough to prevent problems. @@ -369,8 +366,8 @@ lower bound of the range or subtype is used as the initial value. If the range or subtype is null, Constraint_Error is raised.} -AARM Reason: A discriminant constraint that defines a range or list of -acceptable discriminant values means that any value in the range or list is +AARM Reason: A discriminant constraint that defines a range or set of +acceptable discriminant values means that any value in the range or set is acceptable for that discriminant. We select the lower bound in order that programs are portable (although depending on that is dubious). @@ -387,7 +384,7 @@ [Editor's note: We didn't check for null ranges in discriminant_constraints, because the range could have been dynamic and the constraint could have been used -such that no object is every created. This could be fairly common and could cause +such that no object is ever created. This could be fairly common and could cause programs to fail to elaborate if a table is empty or the like.] Replace 3.7.1(3) by: @@ -397,7 +394,7 @@ discriminant_value ::= expression | discrete_range -[Editor's note: discrete_range includes subtype_indication, so it includes list +[Editor's note: discrete_range includes subtype_indication, so it includes set constraints (which aren't a range, but changing the name of the non-terminal would be rather disruptive).] @@ -424,7 +421,7 @@ [Editor's note: Compatibility is only defined for constraints and ranges; we really want compatibility of subtypes here. Maybe there is a better way to write this, but there are really 4 cases to worry about: subtype with range -constraint, subtype with list constraint, subtype_mark alone, and range alone.] +constraint, subtype with set constraint, subtype_mark alone, and range alone.] Replace 3.7.1(11) with @@ -463,10 +460,8 @@ Replace 4.9.1(1.2/2): * both are static and: - - if discrete, each value that belongs to one also belongs to the other, - each have equal lower bounds and equal upper bounds, and both or - neither are discontiguous; - - if real, each have equal lower bounds and equal upper bounds; + - if set constraints, each value that belongs to one also belongs to the other; + - if range contraints, each have equal lower bounds and equal upper bounds; - if index constraints, have equal corresponding bounds; - if discriminant constraints: * for each discriminant given by an expression in one, the @@ -477,20 +472,10 @@ the constraints, ranges, or subtypes statically match. AARM Ramification: - The first bullet means that list constraints and range constraints can be - statically matching of they define the same set of values. For instance - range 1 .. 4 matches when 1 | 2 | 3 | 4 as well as when 4 | 1 .. 2 | 3. - - We have to include the bounds in the first bullet in case the constraints - represent null ranges. We don't want range 6 .. 3 to match range 3 .. 2 - as the bounds are different, even though the value sets are the same - (there are no values that belong to either range). - - We have to include whether constraints are discontiguous to handle cases - where null ranges are involved: - when 10 .. 3 should not match when 10 .. 9 | 7 .. 3 - when 5 .. 5 should not match when 5 | 7 .. 3 - as the latter is treated as discontiguous in both cases. + Set constraints and range constraints that represent the same set of + values do not statically match. For instance + range 1 .. 4 does not match when 1 | 2 | 3 | 4 as well as when 4 | 1 .. 2 | 3, + but the two set constraints do statically match. AARM Reason: The rules for discriminant constraints are complex so that appropriate @@ -529,8 +514,8 @@ would be illegal if this is treated as a single subtype indication (-1 is not in Natural), but could be legal if treated as a choice_list. -Thus we need a different keyword to introduce a list_constraint in order to -avoid this incompatibilty. We then require all list constraints to be static, as +Thus we need a different keyword to introduce a set_constraint in order to +avoid this incompatibilty. We then require all set constraints to be static, as there isn't enough value to dynamic ones (and having fully dynamic ones would make implementing looping, the 'First and 'Last attributes into a nightmare). @@ -543,10 +528,10 @@ We also considered "with", but that seems to be used by a different planned enhancement. Several people suggested using "in". But that is unfortunately ambiguous. Consider -the following case limbs if "in" was used in list_constraints: +the following case limbs if "in" was used in set_constraints: when Natural in 1 .. 3 => when Object in 1 .. 3 => -The first is a subtype_indication with a list_constraint, while the second is a +The first is a subtype_indication with a set_constraint, while the second is a Boolean expression. Using this grammar would require unifying subtype_indications with expressions, and that would bring up the problem of resolution. Currently, subtype_indications are resolved with no context, while expressions are resolved @@ -562,16 +547,16 @@ Unfortunately, the syntax ambiguity noted for the "range" still occurs: when Natural when 1 .. 10 | 12 | 14 => -is ambiguous as to where the list_constraint ends. +is ambiguous as to where the set_constraint ends. To fix the original ambiguity problem, we appear to have two choices: - (1) Add parens around the choice list in a list_constraint: + (1) Add parens around the choice list in a set_constraint: when Natural when (1 .. 10 | 12) | 14 => - (2) Make list_constraints illegal in discrete_choice_lists. In that + (2) Make set_constraints illegal in discrete_choice_lists. In that case, the example given here is syntactically illegal. Both of these possibilities work. We used the second, since there -doesn't seem to be much need to support list_constraints directly +doesn't seem to be much need to support set_constraints directly in choice lists (a named subtype can always be used if necessary). We defined the illegality with wording, because otherwise we would have to duplicate @@ -589,8 +574,12 @@ require potentially unlimited lookahead to tell apart from the beginning of an expression.) It also completely avoids the need for funny rules to eliminate ambiguity. + +At the St. Petersburg ARG meeting, it was suggested that curly brackets would +be better, as they are usually used to represent sets. -The author actually prefers this alternative, but it seems just too radical. +The author actually prefers either of these alternatives, but they seem just +too radical. --- @@ -630,7 +619,7 @@ could be a useful shorthand for useful sets. For loops allow discontiguous subtypes so that iterating over useful sets can -easily be accomplished. Since list_constraints are static, it is reasonably +easily be accomplished. Since set_constraints are static, it is reasonably easy to generate code to iterate in the proper order. (If dynamic constraints were allowed, this would become more difficult.) @@ -648,14 +637,25 @@ to the language. --- + +We make null ranges in set_constraints illegal. Handling null ranges is messy and +useless in set constraints, and since the values are required to be static we +can just ban them. + +This is not totally satisfactory, as it could cause trouble with length constants +used in constraints: + + Natural when 1 | 3 | 5 .. Array_Length -The rules for null ranges in list_constraints are designed to be as simple as possible. -We don't really care what the result is in these cases (these constraints are intended -to be used to define sets, and empty sets are not very interesting), so long as the -following prinicples are followed: - * Identical range and list constraints have the same properties: +is illegal if Array_Length < 5. As such expressions are common in aggregates, +it does not seem unlikely that they would occur in set_constraints as well (which +are modeled on aggregates). + +However, not making them illegal is messy, as we have to properly define the bounds. +We tried rules that followed this principles: + * Identical range and set constraints have the same properties: -- range 3 .. 1 and when 3 .. 1 have the same bounds (and no values) - * List constraints that represent no elements have bounds that represent a null + * Set constraints that represent no elements have bounds that represent a null range: -- when 3 .. 1 | 11 .. 10 has bounds 11 .. 1 If we used the "natural" rule, we'd end end up with bounds of 3 .. 10, which seems @@ -671,24 +671,10 @@ -- when 3 .. 2 | 5 has bounds 3 .. 5. An alternative rule that was considered was to completely ignore null ranges unless -the list_constraint only includes null ranges. That complicates the rules, and also leads +the set_constraint only includes null ranges. That complicates the rules, and also leads to unusual results -- the last example above ends up with bounds of 5 .. 5. - -We also considered doing without the special rule making constraints with null ranges -automatically discontiguous. Combined with the above suggestion, pretty much all constraints -with null ranges would be allowed in arrays and slices. That allows very confusing -constructs: - Arr (Natural when 3 .. 2 | 5) - -A final alternative considered was simply to make null ranges illegal in list_constraints. -Since choices in a list have to be static, that is possible. But it could cause trouble -with length constants used in constraints: - Natural when 1 | 3 | 5 .. Array_Length - -would become illegal if Array_Length < 5. As such expressions are common in aggregates, -it does not seem unlikely that they would occur in list_constraints as well (which -are modeled on aggregates). +These rules caused no end of headaches, so we decided to just do without them. ---

Questions? Ask the ACAA Technical Agent