Ad/2010-08-01 Concrete Syntax for a uml action Language for Foundational uml (Alf) Second Revised Submission

0.4Issues To Be Discussed

The Alf surface syntax primary reflects a C legacy that should also be familiar to Java, C++ and C# programmers. However, a strength of OCL is the facilities it has for denoting expressions that operate on collections. Alf adopts a number of syntactic conventions from OCL to capitalize on this strength.

For example, in an Alf invocation expression such as orders.process(), if the target expression orders evaluates to a sequence of values, then the operation process is called on each member of the sequence (see Subclause 8.3.10). For carrying out operations on sequences themselves, Alf also adopts the OCL “->” notation, which, in the case of Alf, has a particularly appropriate interpretation in terms of the underlying activity “flow” semantics.

The Alf model library also includes a number of predefined collection functions similar to those available in OCL. For example, the expression

orders->includes(thisOrder)

tests whether the sequence of values orders includes thisOrder as a member (see Subclausse 8.3.17 and Subclause 11.5).

Alf further provides an OCL-like notation that maps to fUML expansion regions for carrying out actions over sequences of values. For example, the implicit sequence invocation example given above can be written as the explicit sequence expansion expression

orders->collect order (order.process())

This notation is particularly useful in selecting subsets of a sequeunce, such as

customerOrders = orders->select order (order.customer==thisCustomer)

Note that the notation here is similar but not identical to that of OCL. There are two major notational differences. First, the notation for an iterator variable is different. Instead of a form such as “select(v | …)”, Alf uses “select v (…)”. This avoids ambiguity with the use of “|” for the Boolean “or” operator in C syntax. Second, Alf requires that an iterator variable always be given. C-like expression syntax is not rigorously object-oriented, as OCL syntax is, and, therefore, not as amenable to an implicit form for the iterator context. By requiring that the iterator variable be explicit, no special form is necessary for the expressions used within the collection operation construct.

Overall, though, many OCL expressions may be carried over into Alf in a very similar form. For example, the following OCL expression is the core part of a specification of the quicksort algorithm:

quicksort(xs->select(a | aincluding(x)
->union(quicksort(xs->select(b | b>=x)))

The equivalent Alf expression is

quicksort(xs->select a (aincluding(x)

->union(quicksort(xs->select b (b>=x)))

and is fully executable. (See Annex B.1 for a full exposition of this quicksort example.)

The basic capability in Alf to handle sequences of values is not as versatile as OCL collections, however. This is because Alf sequences reflect the semantics of multiplicity within the execution of activities and, as such are flat sequences of values. Nevertheless, this is sufficient to provide the basis for defining more a sophisticated library of collection classes, which is included as part of the Alf standard model library (see Annexes 11.6 and B.4).

Alf is designed to allow a modeler familiar with typical imperative programming to use Alf in largely that style, while still providing the facilities for a more sophisticated modeler to take advantage of the underlying concurrent, data-flow nature of fUML action semantics. The key to this design is the assignment expression in Alf (see Subclause 8.8).

To a modeler familiar with imperative languages, local name assignments in Alf may be used in much the same way as regular variable assignments. However, such assignments are actually mapped to appropriate object flows carrying the result of the right-hand side expression of the assignment, consistent with the underlying fUML activity/action abstract syntax and semantics (see Subclause 17.24).

Alf even allows local names to be reassigned as if they were variables. The appropriate object flow to use is determined lexically. Reassignment within a loop is handled using the loop variables of a loop node.

For example, consider the following efficient imperative implementation of the quicksort algorithm:

activity quicksort(in out list: Integer[*] sequence,

in low: Integer, in high: Integer) {

if (low < high) {

l = low;

h = high;

p = list[high];
do {

while ((l < h) && (list[l] <= p)) {

l = l+1;

}

while ((h > l) && (list[h] >= p)) {

}

if (l < h) {

list[l] = list[h];

list[h] = t;

}

} while (l < h);

list[l] = list[high];

list[high] = t;
quicksort(list, low, l-1);

quicksort(list, l+1, high);

}

}

Note how the names l, h and list are reassigned within the overall do while loop. This loop is mapped to a fUML loop node (see Subclause 18.10) with loop variables for l, h and list. (Note that even though the assignments to list only change a single member of the list, the underlying object flow semantics require this be done by reassigning the entire list – see Subclause 8.8 on the semantics of such an indexed assignment and Subclause 17.24 on its mapping to fUML.) Similarly, the two while loops nested within the do while loop are mapped to loop nodes with loop variables for l and h, respectively.

Clearly, in order to allow this mapping to be done in general, it is necessary to have some restrictions on the lexical use of assignments. However, in general, these are no more restrictive than the definite assignment rules in Java.

In particular, note how, with this approach, the sample quicksort algorithm can be written equally naturally in a form very similar to how it would be specified declaratively in OCL, as shown earlier, and also in form very similar to a traditional imperative implementation, as shown above. Further, these styles can be freely mixed as appropriate. And, in all cases, the surface syntax may be mapped to fully executable fUML abstract syntax.

Proposals shall discuss the relationship to formal specification languages and how an action language “program” may be proven.

Alf semantics is formally specified via the mapping of its concrete surface notation to the fUML abstract syntax. The semantics of fUML are defined by the fUML Execution Model, which is ultimately grounded in base semantics specified using first-order logic. Thus, any Alf text mappable to fUML can, in principle, ultimately be reduced to a set of statements in first-order logic. This would not, of course, be practical to do manually, but it could provide the basis for automated tools to allow the proof of correctness assertions about Alf programs. Developing such tools is an important area for future research.

As described above, Alf syntax is designed to be familiar and usable both to the modeler comfortable primarily with traditional imperative languages as well as those also comfortable with more declarative or functional languages, such as OCL. Further, Alf is designed to make it particularly simple to write small “snippets” of action code within a larger overall UML model. Indeed, in this respect, Alf might be best considered to be a “scripting language for models”.

For example, while Alf requires strong type checking consistent with the UML typing model, the Alf syntax minimizes the amount of explicit type declaration that must actually be provided by the modeler. Note, for example, that, in the imperative quicksort example above, the initial assignment

l = low;

p = list[high];

to be a single Integer, since list is an ordered list of Integer.

However, Alf also allows for explicit typing of local names, if desired, either in a form using the usual UML colon notation for typing:

let l : Integer = low;

or in the perhaps more familiar form

Integer l = low;

In addition, the use of sequence expressions allows for compact navigation and manipulation of the instances of structural modeling constructs. In particular, select expressions can be used to make natural queries into the object model. For example, the expression

Customer->select problemCustomer (
Order->exists order (
order.customer==problemCustomer &&
order.delinquency>gracePeriod)))

selects all customers for which an order exists with a delinquency greater than allowed.

Finally, while the majority of Alf syntax is based on a familiar C/Java or OCL legacy, Alf is designed to be fully syntactically and semantically integrated with the graphical UML models in which it will largely be embedded. Thus, Alf allows such standard UML textual notations as are already specified in the UML standard. This includes, for instance, using the “::” punctuation for qualified names (though use of “.” is also allowed—see Subclause 8.2) and the “name: type” notation for typed element declarations.

Moreover, it is a goal of the design of Alf to minimize the restrictions on the kinds of UML models within which Alf can be used, even if the enclosing models include constructs not within the fUML subset. The seamless integration of Alf semantics with most UML modeling semantics means that there is no jarring dissonance in thinking about Alf versus thinking about the overall model. Indeed, the modeler may consider Alf as just another surface notation for an underlying UML model representation, to be used within the context of a consistent, fully executable model. (See Subclause 6.1 for further discussion of this.)

Annex C defines a non-normative LL grammar equivalent to the normative grammar presented in the main body of the specification (which is written for clarity of presentation rather than to demonstrate parsability). The LL grammar generally requires a lookahead of 1, with only a limited number of cases requiring a lookahead of more than 1 but no greater than 3 and a single case in which potentially unlimited lookahead is required.

The primary difficulties in the parsability of Alf are due to combining a C-legacy syntax (which is known to be difficult to parse) with additional accepted UML textual notations, such as notations for typing and multiplicity. However, the implementation of a compete parser using standard LL technology shows that the language is still tractable to parse. See Annex C for further discussion.