CHAPTER 4: Types

4.8 Mutability

As regards efficiency of representation, consider again our canonical examples of types with discriminants. Then for unconstrained objects such as

ANYONE : PERSON; ANYLINE : LINE;

we expect the compiler to reserve enough storage to accommodate the largest possible value for the type considered. For example, in the case of ANYLINE, 200 characters must be reserved for the string component ANYLINE.DATA. On the other hand, for constrained objects such as:

PAUL : PERSON(SEX => M); JOAN : PERSON(SEX => F); TITLE : LINE(SIZE => 30);

we expect the compiler to reserve no more space than is dictated by the corresponding constraint. Thus in the case of TITLE, just 30 characters are needed for the corresponding string.

Parameter passing rules for objects of record types do not specify whether the effect is to be achieved by copy or by reference. For example, for an in out parameter the semantics specifies that both reading and updating of the associated actual parameter are allowed. But the implementation has freedom to implement parameter passing by copy (for example, for small objects) or by reference (for example, for large objects): this should not matter for correct programs, that is, for programs that are not erroneous. The motivation for these rules is discussed elsewhere (see 8.2), but consider now their interactions with representation and mutability.

Consider for example a procedure to invert a given line (arrange the letters in reverse order) using the function MIRROR previously defined for strings (see 4.5):

procedure INVERT(L : in out LINE) is begin L.DATA := MIRROR(L.DATA); end;

The formal parameter must have the mode in out, since we update the formal parameter. This procedure can be used indifferently for constrained or unconstrained objects:

INVERT(TITLE); -- constrained INVERT(ANYLINE); -- unconstrained

In either case, it does not matter whether the compiler implements parameter passing using the by-copy or by-reference mechanism, since the procedure does not change the size of the line. This would remain true if, in INVERT, we had used a whole record assignment such as

    L :=  (SIZE =>  L.SIZE,  DATA =>  MIRROR(L.DATA));

But consider now a procedure, such as CHANGE, that performs mutations:

procedure CHANGE(L : in out LINE) is SAFE : constant LINE := L; begin ... L := (SIZE => 45, DATA => ... ); -- (1) ... L := (SIZE => 117, DATA => ... ); -- (2) ... L := (SIZE => SAFE.SIZE, DATA => MIRROR(SAFE.DATA)); end;

Calls with an unconstrained object such as

    CHANGE(ANYLINE);

clearly raise no problem. But consider the treatment of a call with a constrained object, such as

    CHANGE(TITLE);

If the parameter passing semantics were purely by copy, such a call would be acceptable: before the call the unconstrained formal parameter would be initialized with the value of the actual parameter TITLE; upon return, the value of the formal parameter would be copied back into TITLE, and this would work since the discriminant value would be the same upon return as before the call. However, the important optimization of passing large records by reference would not be possible. (Alternatively assignments such as (1) and (2) would require a local copy.)

The above call will fail with the Ada semantics: the formal parameter is constrained in exactly the same way as the associated actual parameter. For the formal parameter L, the language actually provides the attribute

    L'CONSTRAINED

which is TRUE if the associated actual parameter is constrained (such as TITLE), FALSE if unconstrained (such as ANYLINE). In the case of the procedure CHANGE called with TITLE as actual parameter, these rules mean that the assignment (1) is incorrect, and will raise the exception CONSTRAINT_ERROR.

4.8.1 The Case Against Static Mutability

One approach to static mutability would be to associate this quality with the type itself: allow types with objects that are always constrained (never mutable), allow types with objects that are never constrained (always mutable), but not types with both constrained objects and unconstrained objects.

With this approach the type PERSON would not be allowed, but we could declare the following types:

type HUMAN(SEX : GENDER) is -- immutable: must be constrained record AGE : INTEGER range 0 .. 123; case SEX is ... -- as in PERSON end case; end record; -- What follows is not in Ada: type MUTANT(SEX : GENDER := F) is -- cannot be constrained mutable record SELF : HUMAN(SEX); end record;

A constraint is required for each object of type HUMAN. This allows the compiler to allocate the exact (minimum) space needed for each such object. Furthermore we know that this space cannot vary, because of the constraint, so that parameter passing by reference can safely be used for all objects of this type.

Conversely, no constraint would ever be allowed for objects of type MUTANT, so that the maximum space would be allocated for each such object. Parameter passing by reference would therefore again be safe.

Whereas this solution allows efficient parameter passing by reference, its drawbacks become apparent precisely in those situations where we need to have both mutable and immutable objects. The first drawback is verbosity. Instead of writing the Ada declarations and statements:

PAUL : PERSON(SEX => M); -- constrained JOAN : PERSON(SEX => F); -- constrained ANY : PERSON; -- mutable ... ANY := PAUL; ... ANY.AGE ...

we would have to write:

PAUL : PERSON(SEX => M); -- constrained JOAN : PERSON(SEX => F); -- constrained ANY : MUTANT; -- mutable ... ANY := (M, PAUL); ... ANY.SELF.AGE ...

in which the use of mutable objects is complicated by the extra component.

The second - and more important - drawback is in terms of space efficiency. Consider the formation of any structure that involves objects of a given type with different discriminant values: for example a genealogy, using another formulation of the type PERSON with an access type:

... type PERSON_NAME is access PERSON; type PERSON(SEX : GENDER := F) is record ... FATHER : PERSON_NAME(SEX => M); MOTHER : PERSON_NAME(SEX => F); SPOUSE : PERSON_NAME; SIBLING : PERSON_NAME; ... end record; MARY : PERSON_NAME(F) := new PERSON'(SEX => F, ... ); JACK : PERSON_NAME(M) := new PERSON'(SEX => M, ... );

The above Ada formulation will take advantage of the fact that objects dynamically created by allocators (see chapter 6) are constrained upon allocation. For example, although the component SPOUSE is not constrained (and can thus designate an object of either gender), a given gender must be selected upon allocation, and the allocated object is thereafter constrained by this value and is immutable:

MARY.SPOUSE := new PERSON'(SEX => M, ... ); JACK.SPOUSE := new PERSON'(SEX => F, ... );

In terms of space efficiency this is optimal: the minimum space is reserved for the object designated by the SPOUSE component. With the static alternative presently being analyzed, however, this would not be the case. The component SPOUSE would have to be declared as follows (assuming the appropriate access type declaration):

    SPOUSE :  MUTANT_NAME;

so that the allocation for the above example would become:

MARY.SPOUSE := new MUTANT'( ... ); JACK.SPOUSE := new MUTANT'( ... );

and in both cases we would have to allocate the maximum space.

The Ada formulation therefore allows an important kind of space optimization. It is very well suited to a quite common situation in the construction of interrelated data structures: although the discriminant of the object designated by a given variable is not known statically (as in the case of SPOUSE and SIBLING) it will be very unlikely to change after allocation. Conversely, the Ada concepts also allow the declaration of a type such as MUTANT in terms of the type PERSON (the inconvenience is inverted):

type MUTANT is -- cannot be constrained record SELF : PERSON; -- unconstrained end record;

Another approach to static mutability would be to associate the mutable quality with formal parameters, rather than with types. For example, consider again the type LINE:

type LINE(SIZE : LENGTH := 100) is record DATA : STRING(1 .. SIZE); end record; SPACE : constant CHARACTER := ' ';

Then we could define a procedure as follows

-- The following is not in Ada: procedure BLANK(L : in out LINE(<>)) is -- not mutable begin for N in 1 .. L.SIZE loop L.DATA(N) := SPACE; end loop; end;

In this hypothetical formulation the subtype indication

    LINE(<>)                    -- not in Ada

would mean that the formal parameter is indeed constrained (and hence immutable) although the discriminant values are borrowed from the associated actual parameter. Parameter passing by reference would be quite safe because of the immutability. Conversely, in this formulation mutability could be indicated by the type mark LINE alone as in

procedure CHANGE(L : in out LINE) is begin L := (SIZE => 80, DATA => (1 .. 80 => SPACE)); end;

and would be applicable only to objects that are unconstrained such as

    ANYLINE :  LINE;

thereby ensuring the safety of by-reference parameter passing in this case as well.

The major drawback of this approach to static mutability (aside from the additional rules and notations) is that it would make it impossible to define an operation that performs mutations in the case of unconstrained objects but not in the case of constrained objects - note that this is actually what happens for the basic operation (:=) of assignment. Thus:

PAUL : PERSON(SEX => M); -- constrained JOAN : PERSON(SEX => F); -- constrained ANY : PERSON; -- unconstrained: initially SEX = F ... ANY := PAUL; -- ":=" mutates ANY := JOAN; -- ":=" mutates again JOAN := ANY; -- ":=" does not mutate

If this property exists for assignment, we are likely to need it also for user-defined operations, which would not be possible with this static approach to mutability. For example, it would not be possible to write a procedure COPY that copies the whole line in the case of unconstrained lines but only the common part in the case of constrained lines. Such a procedure can be written as follows in Ada:

procedure COPY(SOURCE : in LINE; TARGET : out LINE) is begin if TARGET'CONSTRAINED then declare SIZE : LENGTH := TARGET.SIZE; begin if SIZE > SOURCE.SIZE then SIZE := SOURCE.SIZE; end; TARGET.DATA(1 .. SIZE) := SOURCE.DATA(1 .. SIZE); end; else TARGET := SOURCE; end if; end COPY;

4.8.2 Implementation Considerations

• Any object whose type is a type with discriminants defined without default expressions.
• Any object designated by an access value: such objects are constrained by the discriminant value specified for the allocator that creates the object.

Note that the CONSTRAINED attribute cannot be considered as part of the value itself (that is, as a component). To see this point, consider the following example:

subtype TITLE is LINE(SIZE => 45); ANYLINE : LINE; ... procedure SET(A_LINE : in out LINE) is begin ... end; ... procedure PREPARE(A_TITLE : in out TITLE) is begin ... SET(A_TITLE); ... end; ... ANYLINE := TITLE'(SIZE => 45, DATA => (others => ' ')); PREPARE(ANYLINE);

Then if the CONSTRAINED attribute were considered as a boolean component of the value of ANYLINE, it would have to be FALSE (and not updated by the assignment of the value of A_TITLE). However, consider the call SET(A_TITLE) issued from the body of PREPARE when called with the actual parameter ANYLINE. We must have successively:

ANYLINE'CONSTRAINED = FALSE -- since ANYLINE is declared as LINE A_TITLE'CONSTRAINED = TRUE -- since A_TITLE is declared as TITLE A_LINE'CONSTRAINED = FALSE -- since A_LINE is declared as LINE

But this would not be the case in our example: For a by-reference implementation, A_TITLE and A_LINE would both refer to ANYLINE; for a by-copy implementation the value of ANYLINE would be copied to A_TITLE and further to A_LINE; and for either implementation the attribute would be incorrect within the body of PREPARE, and if corrected there, within the body of SET.