Rationale for Ada 2012

John Barnes
Contents   Index   References   Search   Previous   Next 

2.4 Type invariants

Type invariants are designed for use with private types where we want some relationship to always hold between components of the type. Like pre- and postconditions there are both specific invariants that can be applied to any type and class wide invariants that can only be applied to tagged types.
One example mentioned above and discussed in the Introduction was a type Stack with specific invariant Is_Unduplicated. Thus we write
type Stack is private
   with Type_Invariant  => Is_Unduplicated(Stack);
After calls of Push and Pop and any other operations that manipulate the stack, the function Is_Unduplicated is called to ensure that there are no duplicates on the stack.
The monitoring is controlled by the pragma Assertion_Policy in the same way as pre- and postconditions. If an invariant fails (that is, has value False) then Assertion_Error is raised.
The invariant Is_Unduplicated is a curious example because it cannot be violated by Pop anyway since if there were no duplicates then removing the top item cannot make one appear.
Moreover, Push needs to ensure that the item to be added is not a duplicate of one on the stack already and so essentially much of the checking is repeated. Indeed, when writing Push we should be able to assume that no items are already duplicated and hence all we need to do is check that the new item to be added is not equal to one of the existing items (so n comparisons). However, a general function Is_Unduplicated will need to compare all pairs and thus require a double loop (so n(n+1)/2 comparisons).
The reader is invited to meditate over this conundrum. One's first reaction might be that this is a bad example. However, one way to ensure reliability is to introduce redundancy. Thus if the encoding of Is_Unduplicated and Push are done independently then there is an increased probability that any error will be detected.
The aspect Type_Invariant requires an expression of a Boolean type. The mad programmer could therefore also write
type Stack is private
   with Type_Invariant;
which would thus be True by default and so useless! Actually it might not be entirely useless since it might act as a placeholder for an invariant to be defined later and meanwhile the program will compile and execute.
Type invariants are useful whenever a type is more than just the sum of its components. Note carefully that the invariant may not hold when an object is being manipulated by a subprogram having access to the full type. In the case of Push and Pop and the invariant Is_Unduplicated this will not happen but consider the following simple example.
Suppose we have a type Point which describes the position of an object in a plane. It might simply be
type Point is
   record
      X, Y: Float;
   end record;
Now suppose we want to ensure that all points are within a unit circle. We could ensure that a point lies within a square by means of range constraints by writing
type Point is
   record
      X, Y: Float range –1.0 .. +1.0;
   end record;
but we need to ensure that X**2 + Y**2 is not greater than 1.0, and that cannot be done by individual constraints. So we might declare a type Disc_Pt with an invariant as follows
package Places is
   type Disc_Pt is private
      with Type_Invariant => Check_In(Disc_Pt);
   function Check_In(D: Disc_Pt) return Boolean
      with Inline;
   ...    -- various operations on disc points
private
   type Disc_Pt is
      record
         X, Y: Float range –1.0 .. +1.0;
      end record;
   function Check_In(D: Disc_Pt) return Boolean is
      (D.X**2 + D.Y**2 <= 1.0);
end Places;
Note that we have used an expression function for Check_In. Expression functions were outlined in the Introduction (see 1.3.2) and will be discussed in detail in .}section 3.5. They are very useful for small functions in situations like this and typically will be given the aspect Inline on the specification as shown.
Now suppose that we wish to make available to the user a procedure Flip that reflects a Disc_Pt in the line x = y, or in other words interchanges its X and Y components. The body might be
procedure Flip(D: in out Disc_Pt) is
   T: Float;    -- temporary
begin
   T := D.X;  D.X := D.Y;  D.Y := T;
end Flip;
This works just fine but note that just before the assignment to D.Y, it is quite likely that the invariant does not hold. If the original value of D was (0.1, 0.8) then at the intermediate stage it will be(0.8, 0.8) and so well outside the unit circle.
So there is a general principle that an intermediate value not visible externally need not satisfy the invariant. There is an analogy with numeric types. The intermediate value of an expression can fall outside the range of the type but will be within range when the final value is assigned to the object. For example, suppose type Integer is 16 bits (a small machine) but the registers perform arithmetic in 32 bits, then a statement such as
J := K * L / M;
could easily produce an intermediate result K * L outside the range of Integer but the final value could be in range.
In many cases it will not be necessary for the user to know that a type invariant applies to the type; it is after all merely a detail of the implementation. So perhaps the above should be rewritten as
package Places is
   type Disc_Pt is private;
   ...   --various operations on disc points
private
   type Disc_Pt is
      record
         X, Y: Float range –1.0 .. +1.0;
      end record
      with Type_Invariant =>
                       Disc_Pt.X**2 + Disc_Pt.Y**2 <= 1.0;
end Places;
In this case we do not need to declare a function Check_In at all. Note the use of the type name Disc_Pt in the invariant expression. This is another example of the use of a type name to denote a current instance (this is familiar from way back in Ada 83 with task type names).
We now turn to consider the places where a type invariant on a private type T is checked. These are basically when it can be changed from the point of view of the outside user. They are
after default initialization of an object of type T,
after a conversion to type T,
after assigning to a view conversion involving descendants and ancestors of type T,
after a call of T'Read or T'Input,
after a call of a subprogram declared in the immediate scope of T and visible outside that has a parameter (of any mode including an access parameter) with a part of type T or returns a result with a part of type T
Note that by saying a part of type T, the checks not only apply to subprograms with parameters and results of type T but they also apply to parameters and results whose components are of the type T or are view conversions involving the type T. Observe that parameters of mode in are also checked because, as is well known, there are accepted techniques for changing such parameters.
But note that checks on in parameters only apply to procedures and not to functions. This was a retrospective change after ISO standardization as explained in Section 9.5 of the Epilogue.
Beware, however, that the checks do not extend to deeply nested situations, such as components with components that are access values to objects that themselves involve type T or worse. Thus there are holes in the protection offered by type invariants. However, if the types are straightforward and the writer does not do foolish things like surreptitiously exporting access types referring to T then all will be well. It is another example of there being no defence against foolish programmers.
The checks on type invariants regarding parameters and results can be conveniently implemented in the body of the subprogram in much the same way as for postconditions. This saves duplicating the code of the tests at each point of call.
If a subprogram such as Flip which is visible outside is called from inside then the checks still apply. This is not strictly necessary of course, but fits the simple model of the checks being in the body and so simplifies the implementation.
If an untagged type is derived then any existing specific invariant is inherited for inherited operations. However, a further invariant can be given as well and both will apply to the inherited operations. This fits in with the model of view conversions used to describe how an inherited subprogram works on derivation. The parameters of the derived type are view converted to the parent type before the body is called and back again afterwards. As mentioned above, view conversions are one of the places where invariants are checked.
However, if we add new operations then the old invariant does not apply to them. In truth, the specific invariant is not really inherited at all; it just comes along for free with the inherited operations that are not overridden. So if we do add new operations then we need to state the total invariant required.
Note that this is not quite the same model as specific postconditions. We cannot add postconditions to an inherited operation but have to override it and then any specific postconditions on the parent are lost. In any event, in both cases, if we want to use inheritance then we should really use tagged types and class wide aspects.
So there is also an aspect Type_Invariant'Class for use with private tagged types. The distinction between Type_Invariant and Type_Invariant'Class has similarities to that between Post and Post'Class.
The specific aspect Type_Invariant can be applied to any type but Type_Invariant'Class can only be applied to tagged types. A tagged type can have both an aspect Type_Invariant and Type_Invariant'Class.
Type_Invariant cannot be applied to an abstract type.
Type_Invariant'Class is inherited by all derived types; it can also be applied to an abstract type.
Note the subtle difference between Type_Invariant and Type_Invariant'Class. Type_Invariant'Class is inherited for all operations of the type but as noted above Type_Invariant is only incidentally inherited by the operations that are inherited.
An interesting rule is that Type_Invariant'Class cannot be applied to a full type declaration which completes a private type such as Disc_Pt in the example above. This is because the writer of an extension will need to see the applicable invariants and this would not be possible if they were in the private part.
So if we have a type T with a class wide invariant thus
type T is tagged private
   with Type_Invariant'Class => F(T);
procedure Op1(X: in out T);
procedure Op2(X: in out T);
and then write
type NT is new T with private
   with Type_Invariant'Class => FN(NT);
overriding
procedure Op2(X: in out NT);
not overriding
procedure Op3(X: in out NT);
then both invariants F and FN will apply to NT.
Note that the procedure Op1 is inherited unchanged by NT, procedure Op2 is overridden for NT and procedure Op3 is added.
Now consider various calls. The calls of Op1 will involve view conversions as mentioned earlier and these will apply the checks for FN and the inherited body will apply the checks for F. The body of Op2 will directly include checks for F and FN as will the body of Op3. So the invariant F is properly inherited and all is well.
Remember that if the invariants were specific and not class wide then although Op1 will have checks for F and FN, Op2 and Op3 will only check FN.
In the case of the type Disc_Pt we might decide to derive a type which requires that all values are not only inside the unit circle but outside an inner circle – in other words in an annulus or ring. We use the class wide invariants so that the parent package is
package Places is
   type Disc_Pt is tagged private
      with Type_Invariant'Class => Check_In(Disc_Pt);
   function Check_In(D: Disc_Pt) return Boolean
       with Inline;
   ...      -- various operations on disc points
private
   type Disc_Pt is tagged
      record
         X, Y: Float range –1.0 .. +1.0;
      end record;
   function Check_In(D: Disc_Pt) return Boolean is
      (D.X**2 + D.Y**2 <= 1.0);
end Places;
And then we might write
package Places.Inner is
   type Ring_Pt is new Disc_Pt with null record
      with Type_Invariant'Class => Check_Out(Ring_Pt);
   function Check_Out(R: Ring_Pt) return Boolean
      with Inline;
private
   function Check_Out(R: Ring_Pt) return Boolean is
      (R.X**2 + R.Y**2 >= 0.25);
end Places.Inner;
And now the type Ring_Pt has both its own type invariant but also that inherited from Disc_Pt thereby ensuring that points are within the ring or annulus. It is unfortunate that we could not make the size of the inner circle a discriminant but a discriminant cannot be of a real type. Ah well, perhaps in Ada 2020??
Finally, it is worth emphasizing that it is good advice not to use inheritance with specific invariants but they are invaluable for checking internal and private properties of types.

Contents   Index   References   Search   Previous   Next 
© 2011, 2012, 2013 John Barnes Informatics.
Sponsored in part by:
The Ada Resource Association:

    ARA
  AdaCore:


    AdaCore
and   Ada-Europe:

Ada-Europe