Quicksort Activity
This simple example presents the Quicksort algorithm in two forms: a “functional” form (see Annex B.1.1) similar to how the algorithm might be naturally expressed in a functional programming language and an “in place” form (see Annex B.1.2) that makes efficient use of memory. The intent is to show the flexibility of the Alf notation in expressing different algorithmic styles while maintaining a consistent underlying semantic mapping.
For completeness, both forms of the example are notated as complete Alf activity definitions. While such unit definitions are only available at the extended conformance level, the statement sequences bodies of these definitions could alternatively be attached to UML model as behavioral snippets, for example by including the Alf text as the body of an opaque behavior (see Subclause 9.1). In this case, the functional implementation would conform entirely to the full conformance level and the “in place” implementation would conform entirely to the minimum conformance level.
-
The Quicksort activity noted below highlights the flow-oriented capabilities and concise OCL-like notation available in Alf at the full conformance level. Figure B -102 shows a graphical representation of this same activity.
activity Quicksort(in list: Integer[0..*] sequence):
Integer[0..*] sequence // See Note 1
{
if (list->isEmpty()) { // See Notes 2 & 3
return null; // See Notes 4 & 5
} else {
x = list[1]; // See Notes 6 & 7
list->removeAt(1);
return QuickSort(list->select a (a < x))-> // See Note 8
including(x)->
union(QuickSort(list->select b (b >= x)));
}
}
Notes
-
Alf allows the use of the usual UML multiplicity notation (see Subclause 10.5.2). The keyword “sequence” indicates that the input list is an ordered sequence of integers that allows repetition of values.
-
An Alf if statement has a C-like syntax and similar semantics (see Subclause 9.8).
-
An OCL-like notation can be used for sequence operations (see Subclause 8.3.17) such as isEmpty.
-
As would be expected, a return statement is used in Alf to provide the return value for an activity (see Subclause 9.14).
-
In Alf, “null” denotes the empty set (see Subclause 8.3.15).
-
Alf uses the C-like notation of “=” for assignment (and “==” for equality). However, Alf does not require that the types for local names be explicitly declared (see Subclause 9.6). The type for x is determined implicitly here as Integer, the result type of the expression being assigned to the name. Alternatively, Alf also allows explicit type declaration, either in the form “let x: Integer = list[1];” or the C-like form “Integer x = list[1];”.
-
Alf provides a familiar index notation for accessing the elements of a sequence (see Subclause 8.3.16). Note, however, that indexing is from 1, not 0.
-
Alf provides on OCL-like notation for flow expansion expressions (see Subclause 8.3.18). The expression “list->select a (a < x)” is used to select all elements of list that are less than x. Note that there is no required ordering of the tests on the elements of list, which may all be carried out concurrently.
There are two major notational differences from OCL. First, the notation for an iterator variable is different. Instead of the OCL form “select(a | …)”, Alf uses “select a (…)”. This avoids ambiguity with the use of “|” for the Boolean “or” operator in Java/C syntax. Second, Alf requires that an iterator variable always be given. Java-like expression syntax is not as rigorously object-oriented as OCL syntax, 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. For example, the OCL expression “devices-> select(oclIsKindOf(Sensor))” is written in the form “devices->select device (device instanceof Sensor)” in Alf.
Figure B 102 Activity Diagram for Quicksort
Quicksort “In Place” Implementation
The QuicksortInPlace activity notated belowhighlights the flexibility of Alf to all both a functional or procedural implementation of the algorithm equally naturally. The procedural notation used in this form is entirely available at the minimum conformance level and is very similar syntactically to code in C or Java. (The equivalent graphical representation of this activity is too complicated to easy show here.)
activity QuicksortInPlace
(inout list: Integer[0..*] sequence, // See Note 1
in low: Integer, in high: Integer)
{
if (low < high) {
l = low; // See Note 2
h = high;
p = list[high];
do { // See Note 3
while ((l < h) && (list[l] <= p)) { // See Note 4
l = l+1;
}
while ((h > l) && (list[h] >= p)) {
h = h-1;
}
if (l < h) {
t = list[l];
list[l] = list[h];
list[h] = t;
}
} while (l < h);
t = list[l];
list[l] = list[high];
list[high] = t;
QuicksortInPlace(list, low, l-1);
QuicksortInPlace(list, l+1, high);
}
}
Notes
-
Alf allows activity parameters with any of the UML directions, including out and inout (see Subclause 10.4.8).
-
Statements within the statement sequence of a block delimited by “{…}” are executed sequentially (see Subclause 9.1).
-
An Alf do…while statement has the familiar C-like syntax and semantics (see Subclause 9.11).
-
Alf uses the usual infix notation for arithmetic and relational operations (see Subclauses 8.6.1 and 8.6.4). The conditional and operator “&&” has the C-like semantics of only evaluating its second argument if the first argument is true (see Subclause 8.6.8).
Share with your friends: |
