Version 1.3 of ai05s/ai05-0287-1.txt

Unformatted version of ai05s/ai05-0287-1.txt version 1.3
Other versions for file ai05s/ai05-0287-1.txt

!standard 3.2.4(0)          12-03-13 AI05-0287-1/02
!standard 8.6(17/2)
!class Amendment 12-02-13
!status Amendment 2012 12-02-13
!status ARG Approved 10-0-0 12-02-24
!status work item 12-02-13
!status received 11-12-08
!priority Medium
!difficulty Medium
!subject Some questions on subtype predicates
!summary
We define the current instance of a subtype. We disallow recursive predicates. We only allow static subtypes with predicates in a loop_parameter_specification.
!problem
(1) The standard does not define the "current instance" of a subtype, but 3.2.4 uses it extensively. We need to correct this.
(2) It's possible to write recursive subtype predicates (that is, predicates that invoke the same predicate). This is very confusing at best and causes definitional problems for static predicates, so it should be banned.
(3) A dynamic subtype with a static predicate is allowed in a loop_parameter_specification. It would be fairly complex to determine the actual values to iterate at runtime; such a subtype should not be allowed in a loop_parameter_specification.
!proposal
(See wording.)
!wording
(1) Add the following as the penultimate sentence of 8.6(17/2):
Similarly, if a usage name appears within the declarative region of a subtype_declaration and denotes that same subtype_declaration, then it denotes the current instance of the subtype.
(2) Add after 3.2.4(15/3):
If a predicate applies to a subtype, then that predicate shall not mention any other subtype to which the same predicate applies.
AARM Reason: This is intended to prevent recursive predicates, which cause definitional problems for static predicates. Inside of the predicate, the subtype name refers to the current instance of the subtype, which is an object, so a direct use of the subtype name cannot be recursive. But other subtypes naming the same type might:
type Really_Ugly is private;
private subtype Ugly is Really_Ugly; type Really_Ugly is new Integer with Static_Predicate => Really_Ugly not in Ugly;
(3) Modify 3.2.4(18/3):
The discrete_subtype_definition of a loop_parameter_specification shall not denote a {nonstatic subtype to which predicate specifications apply or any} subtype to which Dynamic_Predicate specifications apply.
!discussion
For (3), we make the rule the same as when the subtype is allowed in other "extended" contexts like case choices and variants: the subtype is static with only static predicates. (We also have to allow dynamic subtypes without any predicates in loops for compatibility, of course). The allowed case can be implemented in a number of special ways for the iteration; dynamic cases pretty much have to be implemented as:
for I in S'range loop if I in S then <<loop body>> end if; end loop;
(Assuming the S'range means the range of S, ignoring any predicate.) This form can be very expensive (if S'range contains many values, and the predicate only includes a few) and in any case can be written by the user when necessary.
This rule is also similar to that for the prefix of the attributes First_Valid and Last_Valid (see 3.5.5(7.1/3) and AI05-0297-1.
!corrigendum 3.2.4(0)
Insert new clause:
[A placeholder to cause a conflict; the real wording is found in the conflict file.]
!corrigendum 8.6(17/2)
Replace the paragraph:
If a usage name appears within the declarative region of a type_declaration and denotes that same type_declaration, then it denotes the current instance of the type (rather than the type itself); the current instance of a type is the object or value of the type that is associated with the execution that evaluates the usage name. This rule does not apply if the usage name appears within the subtype_mark of an access_definition for an access-to-object type, or within the subtype of a parameter or result of an access-to-subprogram type.
by:
If a usage name appears within the declarative region of a type_declaration and denotes that same type_declaration, then it denotes the current instance of the type (rather than the type itself); the current instance of a type is the object or value of the type that is associated with the execution that evaluates the usage name. Similarly, if a usage name appears within the declarative region of a subtype_declaration and denotes that same subtype_declaration, then it denotes the current instance of the subtype. These rules do not apply if the usage name appears within the subtype_mark of an access_definition for an access-to-object type, or within the subtype of a parameter or result of an access-to-subprogram type.
!ACATS Test
!ASIS
No change needed.
!appendix

From: Steve Baird
Sent: Thursday, December  8, 2011  3:07 AM

The subtype predicate RM section (3.2.4) doesn't define the current instance of
a subtype - it assumes that is defined elsewhere. But RM 8.6 only defines the
current instance of a type, not of a subtype.

I don't think the current instance of a subtype is defined anywhere.

A simple solution might be to append something like the following to 8.6(17/2).

   Similarly, if a usage name appears within the declarative region
   of a subtype_declaration and denotes that same subtype_declaration,
   then it denotes the current instance of the subtype.

Do we want to have some sort of a special exemption for membership tests?

In the type case, 8.6(17/2) provides a special exemption ("This rule does not
apply if ... ") in some cases when the type name is used as the designated type
of an access type.

Do we want a similar exemption in order to allow something like the following
example (which would otherwise be illegal):

     subtype Power_Of_Two is Positive with
       Dynamic_Predicate => (if Power_Of_Two mod 2 = 1
                             then Power_Of_Two = 1
                             else (Power_Of_Two / 2) in Power_Of_Two); ?

Probably not, but I raise the question.

****************************************************************

From: Yannick Moy
Sent: Thursday, December  8, 2011  5:08 AM

I agree this is not a good idea. It makes the predicate unreadable.

****************************************************************

From: Bob Duff
Sent: Thursday, December  8, 2011  7:36 AM

> Probably not, but I raise the question.

I agree with "probably not".  If we did so, why would "in" be the only
exception?  I mean, why not allow (for ex.):

    subtype T is Integer with
        Static_Predicate => T < 100 or T = T'Last;

?

Answers: Because it's confusing, not all that useful, and causes implementation
difficulty.  Also, it's too late in the game to be adding functionality that was
never envisioned during the design phase.

****************************************************************

From: Robert Dewar
Sent: Thursday, December  8, 2011  8:12 AM

Well I don't really understand why this should be illegal, but FWIW gnat allows
this now and handles it fine. If it is illegal, I guess we will have to
understand why and put in a (to me arbitrary, since I don't understand it)
restriction to reject this.

****************************************************************

From: Bob Duff
Sent: Thursday, December  8, 2011  8:28 AM

Well, Steve showed me this example in private email:

with Text_IO;
procedure Pow is
  subtype Power_Of_Two is Positive with
    Dynamic_Predicate => (if Power_Of_Two mod 2 = 1
                          then Power_Of_Two = 1
                          else (Power_Of_Two / 2) in Power_Of_Two); begin
  for Iii in Integer range 1 .. 1234 loop
      if Iii in Power_Of_Two then
          Text_IO.Put_Line (Iii'Img);
      end if;
  end loop;
end Pow;

It prints one line containing " 1", which is not "fine".  ;-) If you look at the
-gnatD output, you'll see some wrong code.

The reason it should be illegal, is that within the declaration of Power_Of_Two,
"Power_Of_Two" denotes an object, not a subtype, so you can't say "in
Power_Of_Two". Unless, of course, we add some exception(s) to the current
instance rule as Steve outlined.

****************************************************************

From: Robert Dewar
Sent: Thursday, December  8, 2011  8:35 AM

> The reason it should be illegal, is that within the declaration of
> Power_Of_Two, "Power_Of_Two" denotes an object, not a subtype, so you
> can't say "in Power_Of_Two".
> Unless, of course, we add some exception(s) to the current instance
> rule as Steve outlined.

OK, thanks for clarification, sorry for not understanding quicker, but yes, I
think this should be illegal, and I think GNAT is wrong to accept it!

****************************************************************

From: Randy Brukardt
Sent: Thursday, December  8, 2011  12:46 PM

>I agree with "probably not".  If we did so, why would "in" be the only
>exception?  I mean, why not allow (for ex.):
>
>    subtype T is Integer with
>        Static_Predicate => T < 100 or T = T'Last;

We don't allow T'Last *anywhere* for a subtype that has a predicate, so I'd
hardly expect it to work here! (A restriction that I didn't think was necessary,
but I'm not going to re-argue that now.) But I could imagine allowing the name
in (sub)type conversions, aggregates, case expression limbs, etc. But that
doesn't make much sense (see below).

Bob also wrote:
> Robert Dewar <dewar@adacore.com> wrote:
>
> > > Do we want a similar exemption in order to allow something like
> > > the following example (which would otherwise be illegal):
> > >
> > >       subtype Power_Of_Two is Positive with
> > >         Dynamic_Predicate =>  (if Power_Of_Two mod 2 = 1
> > >                               then Power_Of_Two = 1
> > >                               else (Power_Of_Two / 2) in Power_Of_Two); ?
> > >
> > > Probably not, but I raise the question.
> >
> > Well I don't really understand why this should be illegal, but FWIW
> > gnat allows this now and handles it fine. If it is illegal, I guess
> > we will have to understand why and put in a (to me arbitrary, since
> > I don't understand it) restriction to reject this.
...
> The reason it should be illegal, is that within the declaration of
> Power_Of_Two, "Power_Of_Two" denotes an object, not a subtype, so you
> can't say "in Power_Of_Two".
> Unless, of course, we add some exception(s) to the current instance
> rule as Steve outlined.

And we don't want to add those exceptions, IMHO.

Almost all(?) uses of a subtype name that can appear in an expression involve
evaluating the predicate (membership, type conversion, case libs). Which is what
we are defining here! One could imagine that involving a recursive evaluation of
the predicate, but that usually would be an infinite recursion (the twisted
example above appears to have been designed so that recursive evaluation would
in fact terminate). I don't think it is worth the complication to compilers to
support this recursion, such uses are either mistakes or very tricky (as above),
and since the rules "naturally" ban this anyway, I don't think there is any
reason to create an exception to allow this.

In case anyone is not convinced, consider the following (which would be allowed
if we allowed the current instance to represent a subtype in all places where
that makes [some] sense):

    subtype Really_Ugly is Natural with
        Static_Predicate => (case Really_Ugly is
                               when Really_Ugly => True,
                               when others => False);

    Put (1 in Really_Ugly); -- What does this print??

[This is OK since the rules for predicate-static add no additional restrictions
to case limbs, assuming that the current instance can represent a subtype.]

****************************************************************

From: Bob Duff
Sent: Thursday, December  8, 2011  1:01 PM

> We don't allow T'Last *anywhere* for a subtype that has a predicate,
> so I'd hardly expect it to work here!

Good point.  T'Size, then.

> > Unless, of course, we add some exception(s) to the current instance
> > rule as Steve outlined.
>
> And we don't want to add those exceptions, IMHO.

Agreed.

****************************************************************

From: Brad Moore
Sent: Thursday, December  8, 2011  3:53 PM

Not that it matters much, but this particular problem
 is likely better expressed as a static predicate as in;


type Unsigned_32 is mod 2 ** 32;
subtype Power_Of_Two is Unsigned_32
with Static_Predicate =>
  Power_Of_Two = 0 or else
    (Power_Of_Two - 1 and Power_Of_Two = 0);

****************************************************************

From: Robert Dewar
Sent: Thursday, December  8, 2011  4:42 PM

UGH! I particularly hate seeing fancy tricks like this in predicates, which
should be about clear documentation :-)

****************************************************************

From: Randy Brukardt
Sent: Thursday, December  8, 2011  5:27 PM

Argeed. Which clarifies even more that we don't want to allow the current
subtype name to be used in memberships and type conversions, since those would
be recursive and thus could only be used in some form of fancy trick.

****************************************************************

From: Brad Moore
Sent: Thursday, December  8, 2011  8:00 PM

> UGH! I particularly hate seeing fancy tricks like this in predicates,
> which should be about clear documentation :-)

I agree, except performance can be desirable attribute as well, and this is a
quick and efficient check.

Probably the think to do is have the predicate call an inline function, e.g,
Is_A_Power_Of_Two, and hide the implementation of the function in the body of
the package. (Along with suitable comments to explain the trick)

****************************************************************

From: Bob Duff
Sent: Thursday, December  8, 2011  8:23 PM

> >> type Unsigned_32 is mod 2 ** 32;
> >> subtype Power_Of_Two is Unsigned_32 with Static_Predicate =>
> >> Power_Of_Two = 0 or else (Power_Of_Two - 1 and Power_Of_Two = 0);

You need some parentheses there.

Credit where credit is due:  Gary Dismukes reminded me of this.

****************************************************************

From: Brad Moore
Sent: Thursday, December  8, 2011  9:41 PM

> Credit where credit is due:  Gary Dismukes reminded me of this.

Thanks for pointing that out.

> UGH! I particularly hate seeing fancy tricks like this in predicates,
> which should be about clear documentation :-)

The thought just occurred to me, this seems to be a tough crowd.
My jokes get "Aagh!", and my tricks get "UGH!"

I suspect what people really want to say is "ARG!", but fortunately that is a
reserved word. :-)

****************************************************************

From: Tucker Taft
Sent: Thursday, December  8, 2011  10:46 PM

Unless I am really confused, this should be Power_Of_Two > 0 and then
((Power_Of_Two-1) and Power_Of_Two) = 0

I think your version implies that 0 is a power of 2 (I suppose if you are
considering 2**(-inf) a power of 2 then it is ;-), and has the wrong precedence
for "and" relative to "=".

Also, this would have to be a dynamic predicate, since you are using operators
that are not permitted in the non-static-expression part of static predicates
(bit-wise "and" and "-").

Static predicates really only allow relationals and logical operators in the
non-static-expression part.  No arithmetic.

****************************************************************

From: Brad Moore
Sent: Thursday, December  8, 2011  11:14 PM

Thanks for the correction and clarification, Tuck.
I'll look forward to the day when I have an Ada 2012 compiler to help catch some
of my errors.;-)

****************************************************************

From: Robert Dewar
Sent: Thursday, December  8, 2011  11:34 PM

> Probably the think to do is have the predicate call an inline
> function, e.g, Is_A_Power_Of_Two, and hide the implementation of the
> function in the body of the package. (Along with suitable comments to
> explain the
> trick)

But then it can't be a static predicate :-)

Would be interesting to be able to write user defined static functions :-)

****************************************************************

From: Randy Brukardt
Sent: Friday, December  9, 2011  12:30 AM

That was one of the options in the expression function proposal - seriously.
I didn't pursue it, as it would require some sort of special rule to determine
whether the function could be used as static. (The easiest one would be to only
allow a function in a static expression when the function name statically
denotes an expression function, and the "substituted" function body is a static
expression. Defining "substituted" didn't look easy, unfortunately.)

Having this capability would allow breaking up giant static expressions (and
I've had a few of these). Conditional expressions help with that, but functions
would help more.

(The other options for expression functions were to allow expression functions
in interfaces similarly to null procedures, and to allow them as the default for
a generic formal subprogram. The former requires a bit of additional conformance
checking for overloading/overriding, and the latter doesn't have a particularly
good syntax [Ada already having used the obvious choice for something else]. So
neither of these were pursued, either).

****************************************************************

From: Bob Duff
Sent: Friday, December  9, 2011  9:48 AM

> The thought just occurred to me, this seems to be a tough crowd.
> My jokes get "Aagh!", and my tricks get "UGH!"

You're misquoting -- I didn't write the UGH part -- I think that was Robert.

By the way, you might enjoy the book "Hacker's Delight", by Henry Warren.  It's
filled with all sorts of bit fiddling tricks.  I found it delightful.

****************************************************************

From: Steve Baird
Sent: Tuesday, December 13, 2011  8:23 AM

> In case anyone is not convinced, consider the following (which would
> be allowed if we allowed the current instance to represent a subtype
> in all places where that makes [some] sense):
>
>     subtype Really_Ugly is Natural with
>         Static_Predicate => (case Really_Ugly is
>                                when Really_Ugly => True,
>                                when others => False);
>

Randy made the point (at least implicitly) that allowing recursive subtype
predicates in static predicates is even worse than allowing them in dynamic
predicates.

There seems to be a general consensus that we don't want to allow them in either
case, but the static case would introduce definitional problems in the language
(the dynamic case leads to unwanted implementation complexity and perhaps makes
programs harder to understand, but at least it seems to be well defined).

In private communication, I pointed out that we still have this problem even
with the simple no-special-exemptions rule we seem to be converging on for
determining when a name denotes the current instance of a subtype.

Steve Baird wrote:
> Unfortunately, I think we may need to do some more work to really
> eliminate this problem because, in the case of a first-named subtype,
> it is possible to (in effect) name the subtype as a subtype (not as an
> object) within the full view of the type declaration by means of an
> intervening subtype declaration.
>
> Consider:
>
>     type Really_Ugly is private;
>   private
>     subtype Ugly is Really_Ugly;
>     type Really_Ugly is new Integer with
>       Static_Predicate => Really_Ugly not in Ugly

After some discussion about the scope of the problem (e.g., can we get the same
sort of problem if the initial view of the type is introduced by an incomplete
type declaration instead of a private type declaration?), Bob suggested that if
we really want to ban recursive subtype predicates, then we should simply say so
explicitly.

Bob Duff wrote:
> Something like this:
>
>     If a predicate applies to a subtype, then that predicate shall
>     not mention any [other?] subtype to which the same predicate applies.
>
> The RM wording says that the predicate of Really_Ugly applies to Ugly,
> so the above would be forbidden.  Maybe "mention any [other?] subtype"
> needs to be "denotes the declaration of any [other?] subtype".

Is there general agreement that both
   a) there is a problem here that needs solving and
   b) explicitly banning recursive subtype predicates (for both static
      and dynamic predicates) is the right approach ?

****************************************************************

From: Randy Brukardt
Sent: Tuesday, December 13, 2011  1:28 PM

...
> Is there general agreement that both
>    a) there is a problem here that needs solving and
>    b) explicitly banning recursive subtype predicates (for both static
>       and dynamic predicates) is the right approach ?

Can't speak for the "general" :-), but I agree that there is a problem that
needs fixing and that Bob's solution seems like a good solution. (I would expect
that Bob would agree, since it is his solution.)

****************************************************************

From: Gary Dismukes
Sent: Tuesday, December 13, 2011  2:21 PM

> Is there general agreement that both
>    a) there is a problem here that needs solving

I, at least, agree.

> and
>    b) explicitly banning recursive subtype predicates (for both static
>       and dynamic predicates) is the right approach ?

Yes, looks like the way to go.

(There's also the smaller matter that you pointed out of defining current
instance for subtypes.  Not a big concern, but seems like we should fix that as
well.)

****************************************************************

From: Robert Dewar
Sent: Tuesday, December 13, 2011  2:52 PM

> Can't speak for the "general" :-), but I agree that there is a problem
> that needs fixing and that Bob's solution seems like a good solution.
> (I would expect that Bob would agree, since it is his solution.)

I agree with this too

****************************************************************

From: Bob Duff
Sent: Tuesday, December 13, 2011  3:21 PM

Well, I don't think there are ANY problems with Ada that NEED solving.

But yes, this is a problem, and we ought to solve it if we can, and I agree with
myself about the best solution.  ;-)

****************************************************************

From: Randy Brukardt
Sent: Monday, Feburary 13, 2011  7:58 PM

Way back in early December (in mail that I'm turning into an AI for the upcoming
meeting), Bob gave the following example:

> Well, Steve showed me this example in private email:
>
> with Text_IO;
> procedure Pow is
>   subtype Power_Of_Two is Positive with
>     Dynamic_Predicate => (if Power_Of_Two mod 2 = 1
>                           then Power_Of_Two = 1
>                           else (Power_Of_Two / 2) in Power_Of_Two);
> begin
>   for Iii in Integer range 1 .. 1234 loop
>       if Iii in Power_Of_Two then
>           Text_IO.Put_Line (Iii'Img);
>       end if;
>   end loop;
> end Pow;
>
> It prints one line containing " 1", which is not "fine".  ;-) If you
> look at the -gnatD output, you'll see some wrong code.
>
> The reason it should be illegal, is that within the declaration of
> Power_Of_Two, "Power_Of_Two" denotes an object, not a subtype, so you
> can't say "in Power_Of_Two".
> Unless, of course, we add some exception(s) to the current instance
> rule as Steve outlined.

Everyone agreed with Bob here -- except that GNAT is (or at least was) in fact
right on this program!

We all forgot that memberships now allow objects on the RHS of the "in" (added
in Ada 2012 to allow choice lists). So

(Power_Of_Two / 2) in Power_Of_Two

is legal (both Power_Of_Two being interpreted as objects) and essentially means:

  (Power_Of_Two / 2) = Power_Of_Two

which might as well have been written:

   Power_Of_Two = 0.

Substituting that in the example, we get exactly the result Bob reported.

I suspect that the writer of this code did not intend this result, but hey, you
get what you write. (Perhaps a warning would be a good idea [if the same object
is used on both sides of "in"], but it seems unlikely to come up in practice, so
I'm not sure it is worth the work.)

****************************************************************

From: Randy Brukardt
Sent: Tuesday, December 20, 2011  5:07 PM

[Split from the thread that became AI05-0297-1. - Editor.]

...
> Yes.  I mean, the following are illegal:
>
>     subtype S is Integer range 1..Non_Static(...) with
>         Static_Predicate => ...;
>
>     ...array(S) of ... -- Illegal!
>
>     case ... is
>         when S => ...; -- Illegal!
>
> Right?

Right. The first case isn't interesting (it's illegal for any form of
predicate), but the second is more interesting (it's only allowed for static
subtypes, which necessarily have to have static predicates if they have any).
But how about:

     for I in S loop -- Legal (I think).

I think this is legal with the current rules. S is allowed if it has a static
predicate, and there is no requirement that the subtype itself be static. Surely
S'First/S'Min_Value is no harder to implement than this combination of dynamic
and static constraints. So the question becomes whether we ought to use the same
rule here and for the attribute (if any).

And note that changing this (if we do) is *not* upward compatible, so we need to
at least decide this much now.

****************************************************************

From: Bob Duff
Sent: Tuesday, December 20, 2011  5:45 PM

> Right. The first case isn't interesting (it's illegal for any form of
> predicate),

Right, you can throw that red herring back into the ocean.  ;-)

>... but the second is more interesting (it's only allowed for static
>subtypes, which necessarily have to have static predicates if they have
>any).

Right.

>... But how about:
>
>      for I in S loop -- Legal (I think).
>
> I think this is legal with the current rules. S is allowed if it has a
> static predicate, and there is no requirement that the subtype itself
> be static.

Hmm.  I thought that was illegal.  But you are right -- it appears to be legal
according to the RM.  The discussion in AI05-0153-3 seems to indicate that this
is a mistake (mea culpa).  AI05-0262-1 is indicated on this para, but I see no
change for that AI.

...

> And note that changing this (if we do) is *not* upward compatible, so
> we need to at least decide this much now.

Indeed.  I'm inclined to make the above 'for' loop illegal.

****************************************************************

From: Randy Brukardt
Sent: Tuesday, December 20, 2011  6:15 PM

...
> Hmm.  I thought that was illegal.  But you are right -- it appears to
> be legal according to the RM.  The discussion in
> AI05-0153-3 seems to indicate that this is a mistake (mea culpa).
> AI05-0262-1 is indicated on this para, but I see no change for that AI.

I think the paragraph was split, and this sentence now stands alone. But it
wasn't actually changed.

...
> > And note that changing this (if we do) is *not* upward compatible,
> > so we need to at least decide this much now.
>
> Indeed.  I'm inclined to make the above 'for' loop illegal.

I can believe that was the intent.

...

****************************************************************

Questions? Ask the ACAA Technical Agent