Rationale for Ada 2012
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.
© 2011, 2012, 2013 John Barnes Informatics.
Sponsored in part by: