Repetition Evaluations

Repetitions have not been presented in earlier chapters, because we wanted to concentrate on the core of gbeta. However, we have to present them now in order to be able to specify how gbetarepetitions dier from ^Betarepetitions.

Repetitions are not entities. They are collections of attributes whose names 159

are computed by combining a shared name for all the attributes in the collec-tion with a number, the index of the chosen attribute. The index can be any

member of the set^f1:::n^gfor some natural numbern, the range of the

tion. The range is the number of attributes in the repetition; it is obtained by evaluation of an integervalued expression when the part object containing the repetition is created (and all its attributes are created with it), and it may be changed dynamically. Repetitions can be recognized syntactically by the use of expressions enclosed in square brackets, both in declarations and in the use of computed names. For example:

(# R: [3] @integer; (* 3 object attrs: R[1], R[2], R[3] *) do (* R.range = 3 *)

(* access the second attribute in 'R' *) 5->R[2];

(* use of 'R[4]' would be an error here *) (* add two attributes 'R[4]' and 'R[5]' to 'R' *) 2->R.extend; (* R.range = 5 *)

(* new attributes have the usual initial values *) R[4]+1->R[1]; (* R[1] = 1 *)

(* throw out all 5 attributes, get 4 new ones *) 4->R.new; (* R.range = 4, R[1] = 0 *)

#) ^Ex.

8-1

Note that the notion of computed names introduces a special version of the

MessageNotUnderstooderror which cannot be ruled out statically. The prob-lem is that both the range of a given repetition and the indices used in computed names may be the result of arbitrary computations, so it is generally an unde-cidable problem to determine statically whether or not a given attribute in a repetition exists. However, it is almost safe to test whether a given repetition attribute access will succeed by means of an^ifimperative:

(if R.range>=3 then 0->R[3] if) ^Ex.

8-2

This only fails if another thread modies^Rbetween theEvaluationand the body of the^ifimperative. This is not normally considered as a loophole in the type analysis but rather as an entirely separate (and more politically correct) kind of run-time error, `Index out of range'. We have not added a construct ingbeta which makes it possible to implement this example in a safe way, but a variant of the^whenimperative could be used; see Sect. 9.1.3 for more information on

when.

So far, this describes repetitions in ^Beta and in gbeta equally well. How-ever, there is a special syntactic shorthand for multiple assignments associated with repetitions. ^Betaandgbetahave dierent semantics for such repeated as-signments in some cases. The syntax for a repeated assignment is just like that of an ordinaryAssignmentEvaluation, but the source and destination entities are repetitions. The semantics is a repeated assignment operation which evaluates the rst attribute of the left hand side and assigns the resulting value to the rst attribute of the right hand side, then repeats for the two attributes with index two, and so on. The receiving repetition is in all cases adjusted such that

8.1. INCOMPATIBLE CHANGES 161 both repetitions have the same range. For example, the assignment^R1->R2has the same eect as the whole^do-part in context of the following example, both in ^Betaand in gbeta:

(# R1: [3] @char;

R2: [0] @char do (if true

// R1.range>R2.range then R1.range-R2.range->R2.extend // R1.range<R2.range then R2.range-R1.range->R2.delete if);

(for i:R1.range repeat R1[i]->R2[i] for)

#) ^Ex.

8-3

Betaandgbetado not include the primitive repetition operation^delete, but such an operation is needed in the implementation in order to get the right semantics for these repeated assignments; the ^deleteoperation would remove as many attributes as the given integer argument species, starting from the highest indices and going downwards. The whole operation happens atomically, such that the range of the two repetitions will be equal until the end of the^for imperative.

In Mjolner^Beta, repetitions of object attributes have dierent assignment semantics, depending on whether they denote instances of basic patterns, like

integerand^char, or instances of composite patterns. For composite patterns, the repetition assignment works like a repeated reference assignment. Ingbeta there is no such distinction between basic patterns and composite patterns, but the repeated reference assignment can be specied with another syntax ingbeta, namely a syntax which is similar to ordinary, single reference assignment. For example, the imperative R3[]->R4[]in gbeta and ^R3->R4in ^Beta work like the whole^do-part in the following context:

(# Point: (# x,y: @integer #);

R3: [2] @Point;

R4: [7] ^{^}Point do (if true

// R3.range>R4.range then R3.range-R4.range->R4.extend // R3.range<R4.range then R4.range-R3.range->R4.delete if);

(for i:R3.range repeat R3[i][]->R4[i][] for)

#) ^Ex.

8-4

In^Beta it would be possible to declare^R4as a repetition of object attributes, e.g. R4: [7] @Point, and carry out the same repetition assignment. That is rejected in gbeta because the implied execution of R3[i][]->R4[i][]would be rejectedreference assignment can only be applied to a variable object at-tribute, because it means that the attribute must vary.

In general, the coercion markers applied to repetition assignments ingbeta are carried over to the body of the implied ^for imperative, so for example

R5[]->R6means the same as the^do-part in this example:

(# printer: (# s: ^{^}string enter s[] do INNER #);

R5: [2] @string;

R6: [7] ^{^}printer do (if true

// R5.range>R6.range then R5.range-R6.range->R6.extend // R5.range<R6.range then R6.range-R5.range->R6.delete if);

(for i:R5.range repeat R5[i][]->R6[i] for)

#) ^Ex.

8-5

One way to explain the eect of R5[]->R6is that it gives some^stringobjects as arguments, by reference, to some stored procedure invocations, which are less-equal than^printer, and then calls them.

The benets obtained by redening the semantics of repetition assignment ingbetacompared to ^Betaare the following:

There is no distinction between basic patterns and composite patterns;

such a distinction is nowhere else assumed and it would be a semantic anomaly to introduce it here.

There is no support for `reference assignment to an object attribute', such as with^R4in the^Betaimperative^R3->R4above. Again, that would be a semantic anomaly. We should note that this is the actually implemented semantics in the Mjolner compiler. The explanation of repetition assign-ment in [74] could very well be interpreted to mean something much closer to the semantics in gbeta.

The simple, mechanical construction of the implied ^forimperative from any given repetition assignment ensures that the connection between syn-tax and semantics for repetition assignment is consistent with the rest of the language.

The various combinations of coercion markers on repetition assignments mean dierent things, and they may all be useful.

However, there are certainly also some problems left:

It would probably not be meaningful to require that arbitrarily complex assignment operations should be executed repeatedly as an atomic lan-guage operation. What if such a complex repeated assignment would attempt to change the range of one of the repetitions during the opera-tion? The repetitions should not support that, that's what the atomicity is all about. What would it mean to execute such a repeated assignment atomically if each iteration might execute arbitrary code? Should all other threads stop, or should the run-time system be required to maintain locks on repetitions that are being used in assignments?

The alternative, being that such an operation would not have to be atomic, does not seem to be attractive either. It would be a very unpleasant perspective if all repetition assignment operations could potentially cause

`Index out of range' errors.

8.1. INCOMPATIBLE CHANGES 163

It seems inconsistent that a repetition of object attributes supports the

newoperation. This allows us to, e.g., access two dierent objects via the computed name ^R1[2]in the rst example above. Normally, an object attribute will denote the same object in the entire lifetime of the part object of which it is an attribute. However, removing this possibility would seriously damage the backward compatibility of gbetaand create a need for alternative ways to handle such common facilities as the manipulation of mutable strings (i.e. the^textpattern in^Beta).

It might be benecial to exploit and widen the static knowledge about the length of certain repetitions and thereby be able to declare certain operations safe. This could be done by making some (explicitly marked) repetitions xed-length, and then statically prohibit the operations ^new and ^extend on these repetitions. If the range were a compile-time constant then even some accesses to attributes in the repetition could be checked statically. Fixed-length repetitions might also allow for a more ecient representation in some cases. Nevertheless, there would be many cases where the variable and mutable range would be very useful, and arbitrary computations to select attributes from a repetition are also useful indeed.

The conclusion is probably that repetition assignments are too complex to allow for a denition which is both consistent and safe. Either we must single out the basic patterns and disallow repeated value assignments for the general case (reference assignments are simpler), or we must accept that repetition as-signment cannot be executed atomically, even though it is a primitive operation in the language. Actually, there would be problems with requiring atomicity for assignment of very long repetitions, also in the case of repetitions of instances of basic patterns. The basic problem with a non-atomic failable primitive opera-tion is that a highly safety oriented programming style must abandon it entirely;

the ^extendand ^newoperations on the two repetitions are made into run-time errors for arbitrary periods of time, and there is no test which will determine whether or not they can be executed safely at any given point in time. This is no better than having the potential for a MessageNotUnderstooderror at all times.

One solution could be to dene the semantics of repeated assignments to carry out as many iterations as possible after the initial length synchronization, i.e., until the end of the shortest repetition is reached. That would make the operation safe, it would not require atomicity and would therefore allow the consistent, fully general value assignment semantics. It would then be possible for programmers to check if the expected number of assignments were performed, and handle the problem gracefully if not.

Another solution would be to remove the support for repetition assignments altogether and require that programmers write the corresponding^forloops ex-plicitly. Since repetitions should arguably not be used publicly anywaythey are simply too low-level and too inexible to be part of widely used interfaces such a forced extra verbosity might actually make it even more clear that they are meant to be used locally in the implementation of real abstractions. It

might be necessary to add a primitive operation which would adjust the range of a given repetition eciently. It should not be impossible for a production quality compiler to generate code with the same performance for the explicit

forimperative version as it could do for the repetition assignment shorthand.