This paper proposes an extension to OCL that addresses a concern regarding the proliferation of navigation expressions that occur when expressing predicates over objects. Declarative patterns are introduced that can be used to match against object structures so that repeated variables reduce the need for lengthy repeated navigation expressions. Patterns provide the basis for a further contribution that shows how objects can be used as functions.
OCL is a formal language that can be used to express both system invariants and pre and post conditions on system operations. The language is abstract in the sense that it hides away the details of the representation of relationships and by providing collections with associated operations such as union and includes. Constraints on the state of objects in a system can be de ned by applying predicates to path expressions. A path expression navigates from a given instance using `.' to index object properties and association role ends.
Navigation via path expressions occurs frequently in OCL expressions.
Typically, a constraint on an object o will involve a predicate p and two or more path
expressions o.a.b.c and o.i.j.k such that p(o.a.b.c,o.i.j.k) is required
to hold true. A speci cation of an invariant or a pre/post condition will require
multiple constraints to hold simultaneously. Such a proliferation of constraints
involving path expressions can lead to very verbose speci cations as noted in
[
Programming languages such as ML [
This paper proposes an extension to OCL that allows patterns to be used
in constraints. The extension involves two new language constructs: a
caseexpression that dispatches on a value given a collection of patterns, and an
(a) Basic Trees
(b) Trees With Properties
object-expression that is used to construct instances of classes. Together these
new constructs allow OCL context declarations to be used in new ways. In
particular, a special case is identi ed that allows UML classes to be viewed as
properties and functions. The language is similar to the MT language [
Consider the model shown in gure 1(a)1. A binary tree is either a leaf containing an integer value or a pair of trees labelled left and right.
Suppose that we want to identify ordered binary trees where the leaf values increase left to right. One way to do this is to de ne an Ordered property that holds for a sub-set of trees. A property can be de ned as a class that associates 0 or more classes with a class whose instances have the property.
Figure 1(b) shows the class Ordered associated with class Tree that de nes the ordered property on trees. The ordered property uses two auxiliary selectionproperties: Largest and Smallest. The essential idea is that a tree is ordered when all of its sub-trees are ordered and a binary-pair of trees is ordered when the largest element on the left is less or equal to the smallest element on the right.
The OCL speci cation of ordered trees is shown in gure 2. The speci cation exhibits features that are typical of using OCL to de ne properties in this way: navigation: The speci cation of Ordered and Largest both exhibit multiple navigation expressions that are used to apply functions and predicates to values in object slots. Given that the speci cation of ordered trees is relatively small compared to real-world applications, speci cations involving such expressions can become complex and di cult to comprehend. inheritance: Tree is an inductively de ned data type: a tree is a leaf or the binary combination of two trees. Such recursive de nitions can be achieved using an abstract class Tree and concrete sub-classes Leaf and Bin. A property de nition is then de ned in the context of the super-class using oclIsKindOf as a way of selecting the appropriate sub-class. 1 Note that in diagrams by default: association ends have a multiplicity of 1 and are named by the attached class (pluralised where necessary). No cycles are allowed. context Ordered inv : tree . oclIsKindOf ( Leaf ) or ( tree . oclIsKindOf ( Bin ) and children -> includes ( tree . left . ordered ) and children -> includes ( tree . right . ordered ) and tree . left . largest . leaf . value <= tree . right . smallest . leaf . value ) context Largest inv : tree . oclIsKindOf ( Leaf ) implies leaf = tree and tree . oclIsKindOf ( Bin ) implies children -> includes ( tree . left . select ) and children -> includes ( tree . right . select ) and tree . left . select . oclIsKindOf ( Largest ) and tree . right . select . oclIsKindOf ( Largest ) and leaf . value = tree . left . select . leaf . value . max ( tree . right . select . leaf . value ) context Smallest inv : -- similar to Largest children: The structure of a property often follows the recursive structure of the data-type it relates to. For example, a binary tree is ordered when the two sub-trees are also ordered. Another example is that the largest element of two binary trees is the maximum of the largest element of the two sub-trees. The model in gure 1(a) shows that the property classes have self-associations called children that facilitate the de nition of the sympathetic recursion between the property and the class it relates to. 3
Pattern matching has been used in functional programming languages for many years. Languages such as ML, Scheme and Haskell use pattern matching in terms of case-analysis and are the basis for the proposal put forward in this paper. A di erence is that functional programming languages use algebraic data types rather than classes and inheritance, however there is a straightforward translation from classes with inheritance to tagged elements in an algebraic data type.
Model transformation languages [
Graph-based transformation systems use patterns to select parts of a graph and use results from algebra theory to provide a declarative approach to express sharing constraints to be maintained or achieved by transformation rules. Like QVT patterns, these are related to the ideas presented here, but speci cally target model transformation.
Other applications of pattern matching in model based engineering involves
the use of OCL-based patterns to measure model quality [
( Leaf )[ value = v2 ]=( Least )[ tree =r] } Our proposal is that extending OCL with patterns can make speci cations more concise and therefore easier to comprehend and analyse. Concretely, our proposition takes the form of two new types of OCL expression: case-expressions involving patterns, and object expressions that are used to represent class-instances. Having introduced these features we can use them to extend context-de nitions to use patterns in relations and to introduce a new form of functional-de nition.
Figure 3 shows the de nition of a relational property called Ordered. The body of the constraint is de ned by case-analysis on the tree t. The use of case analysis separates out the di erent sub-types in a structured way. Notice how the recursive de nition of Ordered follows the recursive structure of a binary tree. This means that the re exive Ordered::children association de ned in gure 1(b) is implicit in the de nition.
Figure 3 shows the use of a case-expression. The basic form is case v f p ! e; ... g where v and e are OCL expressions and p is a pattern. If the value v matches a pattern p then the result of the case-expression is given by the corresponding e.
Therefore, in gure 3 the relational property Ordered is speci ed by case analysis on the tree t. A tree is either a leaf or a binary-tree. A leaf is always ordered. A binary tree is ordered when the sub-trees l and r are ordered. Objectexpressions are used to specify the condition that the sub-trees are ordered: when an object expression such as (Ordered)[tree=l] is used in a boolean expression then the corresponding well-formedness constraint, de ned using a context-pattern de nition, must hold.
The where-condition is used as a side-condition in gure 3 to require that the greatest element of the left sub-tree is less than or equal to the least element of the right sub-tree. Such a condition uses patterns to call an object-expression used as a function call as described below. context ( Largest )[ tree =t] fun : case t { ( Leaf )[ value =_] ! t; ( Bin )[ left =l; right =r] ! ( Leaf )[ value = v1 . max ( v2 )] where ( Leaf )[ value = ( Largest )[ tree =l ]] and
( Leaf )[ value = ( Largest )[ tree =r ]] } (a) Extending OCLExpression (b) Pattern Abstract Syntax The OCL standard2 de nes the language in terms of an abstract syntax, concrete syntax and a semantics. The abstract syntax takes the form of a model that describes how the class OCLExpression is used to attach constraints to UML model elements. OCL patterns are de ned as an extension to the standard. This section de nes patterns and object expressions as sub-classes of OCLExpression and provides a concrete syntax as a BNF grammar.
Figure 5(a) shows OCLExpression from the standard extended with three new types of expression: CaseExp; Where; ObjectExp. An object expression takes the concrete form (C,i)[n=e; ...] where C is a reference to a class, i is an optional object-identity, n is the name of a eld or association-end, and e is an expression. Therefore, (Point)[x=10;y=20] is a two-dimensional point. The optional object-identities are used to specify that the same object occurs more than once in an expression (and correspondingly in a pattern as described below). Clearly, there are well-formedness constraints regarding the use of objectidentities, however we will omit such discussions here. 2 http://www.omg.org/spec/OCL/2.3.1/
Figure 5(b) shows the de nition of patterns as used in case-expressions and where-expressions. Patterns are used to denote OCL values (including objects) and use variables to match arbitrary components of values. Note that the repeated use of the same variable must always denote the same OCL sub-value when a pattern is matched against a value (modulo identities).
The ConstrainedPattern includes the use of a boolean valued OCLExpression to add a guard to a pattern; this is a way of escaping from the restrictions of patterns into arbitrary boolean expressions for example the pattern p and when e requires that a given value v both matches the pattern p and satis es the arbitrary boolean expression e.
Patterns may denote collections and it is convenient to allow sequencepatterns to be non-deterministic (via operations such as append and union) so that they can be further constrained via guards as described above. Figure 6 de nes the abstract syntax of collection patterns.
Figure 7 proposes a concrete syntax for the pattern language. Notice how the syntax of collection patterns follows that of the equivalent expressions.
Fig. 8. A Functional Language context ( Eval )[ exp =e; env =p] fun : case e { ( Var )[ name =n] ! ( Lookup ( env =p; name =n ]; ( Lambda )[ arg =n; body =e] ! ( Closure )[ arg =n; env =p; body =e ]; ( Alpept )[v1op:=Voa;luaerg ==e]( E!val )[ exp =o; env =p]
v2 : Value = ( Eval )[ exp =e; env =p] in case v1 { ( Clo )[ arg =n; env =p; body =e] ! let p: Env =( Bind )[ name =n; value = v2 ; env =p] in ( Eval )[ exp =e; env =p] } } } context ( Lookup )[ env =p; name =n] fun : case e { ( Empty )[] ! undefined ; ( Bind )[ name =m; val =v; env =p] ! if n=m then v else ( Lookup )[ env =p; name =n] endif This section brie y shows how patterns can be used to specify a standard recursive function. Figure 8 includes a model of the simple -calculus and de nes two properties Eval that maps an expression and an environment to a value, and Lookup that maps an environment and a name to a value. Figure 9 uses patterns to de ne the Eval and Lookup functions. 7
The previous sections have shown how patterns can be used to de ne functions and relations over model elements. Even though the functions are used to de ne evaluation, there is no implication that the speci cations de ne how a system evolves over time. This is because the patterns and associated functions and relations are stateless. (a) A Simple Library (b) Dynamic Execution
Models are often used to describe how a system evolves over time by showing how, complete or partial, system states are modi ed in response to handling an operation. Typically this is expressed using some form of state machine or process model. When an operation is performed, OCL can be used to de ne conditions on a before state, an after state and a relationship between the two. As with invariants, these conditions often involve complex navigation expressions.
Our proposal is that a pattern based approach can be used to de ne system execution in a succinct and declarative way making it easier to the user and tools to appreciate and reason about state changes. To illustrate this we use a simple model of a library shown in gure 10(a) consiting of readers, books and borrowing records. We limit ourselves to the library operations that borrow and return books.
The dynamic execution of a system can be expressed as a lmstrip that consists of a collection of steps. Each step contains a before and after state of the system. Each system operation is de ned a special type of step. For simple sequential systems, lmstrips are sequences of steps where the before state of a step is the same as the after state of the immediately preceding step. For lmstrips that contain concurrency, this condition is loosened appropriately.
Figure 10(b) extends the library model with a lmstrip where the concrete steps are Borrow and Return. The general-purpose constraint that de nes sequential behaviour is shown in gure 11. The invariant uses sequence patterns to require that the steps are linked through the before and after states. In particular P->prepend(s1)->prepend(s2) matches any sequence with two or more elements of the form Seqfs1,s2,...g where P is the sequence with s1 and s2 removed. Notice that the second case-arm is de ned recursively and requires that the lmstrip (Filmstrip)[steps=P] is well-formed. context ( Borrow )[ book = bn ; reader = rn ; before = (Lib ,l )[ books = Set {b =( Book )[ name = bn ]}-> union (B ); readers = R= Set {r =( Reader )[ name = rn ]}-> union (_ ); borrowings = X ]; after = (Lib ,l )[ books = B; readers = R; borrowings = X -> including (x)
where x =( Borrowing )[ book =b; reader =r ]) ] ] inv : true
Each concrete step de nes a library operation and, since these are de ned as classes, they are speci ed separately. Figure 12 shows the de nition of the step that speci es the Borrow operation. It is a useful example of the declarative power achieved by extending OCL with patterns because the body of the invariant form is essentially empty because all of the constraint is expressed as structural relationships between context and inv:. Note that the identity of the library object is declared to be l in both the before and the after which indicates that the change occurs by side-e ect. The Return operation is speci ed in gure 13. 8
This paper has proposed extensions to OCL that aim to address the proliferation of navigation expressions that occur when expressing relationships between different parts of a model. Object expressions complete the range of values that can be denoted by general OCL expressions. Object-identities can be used to express the state changes that occur when a system performs an operation. Patterns are used to denote UML values, they include variables and pattern matching is used to bind variables in order that a pattern explicitly denotes a value. Patterns are used in case-expressions and context-declarations in order to reduce the number of navigation expressions and to introduce a new, functional, form of declaration.
This paper has presented the OCL extensions in terms of examples and
syntax de nitions. Further work is needed to de ne the semantics of patterns and to
integrate them with the semantics given in the standard. No analysis has been
presented of the changes to existing tools that are implied by the addition of
patterns, for example [