Issue 13944: [OCL-2.1 RTF] Transitive closure operator (ocl2-rtf)
Source: NASA (Dr. Nicolas F. Rouquette, nicolas.f.rouquette(at)jpl.nasa.gov)
Nature: Uncategorized Issue
Severity:
Summary: Specification: Object Constraint Language, formal/06-05-01
Section: 7.6 Collection Operations
Summary:
The concept of transitive closure is very useful for specifying well-formedness constraints on binary relations.
For a binary relation r:A->A and elements x,y,z in A, r(x,y) is true when r relates x to y and r is transitive whenever for any x,y,z in A, r(x,y) and r(y,z) imply r(x,z). The transitive closure of a binary relation r:A->A is the smallest relation, ^r:A->A, that contains r and is transitive.
In the UML specification, the definition of Classifier::allParents() : Classifier[*] as “all the direct and indirect ancestors of a generalized Classifier” could be equivalently paraphrased as the transitive closure of the Classifier::parents() : Classifier[*] relation.
Specifying the notion of transitive closure for the OCL specification can be problematic as this notion refers to a meta-property not expressible in first order logic (i.e., the smallest relation satisfying a given property). However, the notion of transitive closure can be specified in the context of a particular API for evaluating OCL iterator expressions such as that of the Eclipse OCL implementation of the OCL2.0 specification:
http://help.eclipse.org/ganymede/index.jsp?topic=/org.eclipse.ocl.doc/references/overview/OCLOverview.html
http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.mdt/org.eclipse.ocl/plugins/org.eclipse.ocl/src/org/eclipse/ocl/internal/evaluation/IterationTemplateClosure.java?root=Modeling_Project&view=markup
A synopsis of the algorithm for computing the transitive closure as an OCL iterator expression is available here:
http://dev.eclipse.org/newslists/news.eclipse.modeling.mdt.ocl/msg01390.html
Resolution:
Revised Text: Add an additional section before 7.6.5
7.6.5 Closure Operation
The iterators described in the preceding sections return results from the elements of a collection. The
closure supports returning results from the elements of a collection, the elements of the elements of a
collection, the elements of the elements of the elements of a collection, and so forth. This can be useful for
iterating over a transitive relationship such as a UML generalization. The closure operation uses the same
syntax as the select and reject iterators and is written as one of
source->closure( v : Type | expression-with-v )
source->closure( v | expression-with-v )
source->closure( expression )
The returned collection of the closure iteration is an accumulation of the source collection, and the
collections resulting from the recursive invocation of expression-with-v in which v is associated exactly
once with each distinct element of the returned collection. The iteration terminates when expression-with-v
returns empty collections or collections containing only already accumulated elements. The collection type
of the result collection is the unique form (Set or OrderedSet) of the original source collection. If the
source collection is ordered, the result is in depth first preorder. The result satisfies the postcondition:
post: let sourceAndResult : Set(Type) = source->asSet()->union(result) in
sourceAndResult = sourceAndResult->collect(expression)
For a simple parent-children relationship and known parents
parents->closure(children)
computes the set of parents.children, parents.children.children, parents.children.children.children etc.
In the opposite direction
self->asOrderedSet()->closure(mother)
computes the maternal line.
For a more complex relationship such as UML Classifier generalization
aClassifier.generalization()->closure(general.generalization).general()->including(aClassifier)
computes the set comprising aClassifier and all its generalizations. The closure recurses over the
Generalizations to compute the transitive set of all Generalizations. The generalized classifier is collected
from each of these before including the originating aClassifier in the result.
As with all other iterators, self remains unchanged throughout the recursion, and an implicit source
attempts to resolve features against iterators.
At the end of 7.8 Resolving Properties add
A closure iteration may introduce an implicit iterator-variable at each level of recursion and so multiple
iterator-variable candidates for consideration as the implicit self. Since all candidates have the same static
type, it is only the least deeply nested candidate, with respect to the iteration body, that need be considered
as the implicit iterator-variable for a closure.
In 8.3.7 IteratorExp add
IteratorExp closure
[1] There is exactly one iterator.
context IteratorExp
inv: name = 'closure' implies iterator->size() = 1
[2] The collection type for an OrderedSet or a Sequence source type is OrderedSet. For any other source the
collection type is Set.
context IteratorExp
inv: name = 'closure' implies
if source.type.oclIsKindOf(SequenceType) or source.type.oclIsKindOf(OrderedSetType) then
type.oclIsKindOf(OrderedSetType)
else
type.oclIsKindOf(SetType)
endif
[3] The source element type is the same as type of the body elements or element.
context IteratorExp
inv: name = 'closure' implies
source.type.oclAsType(CollectionType).elementType =
if body.type.oclIsKindOf(CollectionType)
then body.type.oclAsType(CollectionType).elementType
else body.type
endif
[4] The element type is the same as the source element type.
context IteratorExp
inv: name = 'closure' implies
type.oclAsType(CollectionType).elementType
= source.type.oclAsType(CollectionType).elementType
In 11.9.1 add
closure
The closure of applying body transitively to every distinct element of the source collection.
source->closure(iterator | body) =
anonRecurse(source, Result{})
where:
anonRecurse is an invocation-site-specific helper function synthesized by lexical substitution of iterator,
body, add and Result in:
context OclAny
def: anonRecurse(anonSources : Collection(T), anonInit : Result(T)) : Result(T) =
anonSources->iterate(iterator : T; anonAcc : Result(T) = anonInit |
if anonAcc->includes(iterator)
then anonAcc
else let anonBody : OclAny = body in
let anonResults : Result(T) = anonAcc->add(iterator) in
if anonBody.oclIsKindOf(CollectionType)
then anonRecurse(anonBody.oclAsType(Collection(T)), anonResults)
else anonRecurse(anonBody.oclAsType(T)->asSet(), anonResults)
endif
endif)
where:
T is the element type of the source collection.
Result is 'OrderedSet' if the source collection is ordered, 'Set' otherwise.
add is 'append' if the source collection is ordered, 'including' otherwise.
The anonymous variables 'anonRecurse', 'anonAcc', 'anonInit', 'anonResults' and 'anonSources' are named
for exposition purposes; they do not form part of the evaluation environment for body.
Actions taken:
May 31, 2009: received issue
April 25, 2011: closed issue
Discussion:
The omission of a closure iterator has been noted by many OCL users. The suggestion is
practical, but since it is a transitive closure the use of the name closure as in the
referenced implementation could be misleading. Conversely the use of a clearer name
such as transitiveClosure() is a bit verbose. Since closure() has already started to be used
and its usage is clearly associated with a context object rather than a global scope,
insisting on the longer name seems unnecessarily pedantic.
A closure iterator is specified below generalising the referenced Eclipse MDT/OCL
implementation to operate on an OrderedSet as well as a Set.
[Design note. An attempt to extract a more generic recurse() building block proved
fruitless. A more general recurse might for instance support transitiveExists,
transitiveForAll etc. It was not clear that, for instance a Bag of multiple encounters was
of any practical use, and the Bag could anyway be generated by an iteration over the
transitiveClosure. Similarly an elaboration to allow a user function of the encounters
requires two bodies and multiple iterate results. Once again it is easier to provide the
simple transitiveClosure and then invoke the user function on the result. Any enhanced
efficiency from the combined operation could still be obtained by an OCL 'compiler' that
optimises a transitiveClosure(...)->forAll(...).]
End of Annotations:=====
m: "Rouquette, Nicolas F"
To: "issues@omg.org"
CC: Pete Rivett ,
"mariano.belaunde@orange-ftgroup.com" ,
"cdamus@zeligsoft.com"
Date: Sun, 31 May 2009 19:29:59 -0700
Subject: [OCL-2.1 RTF] Transitive closure operator
Thread-Topic: [OCL-2.1 RTF] Transitive closure operator
Thread-Index: AcndKINWuHg3EKFBQoG/kJ8NTDawbAA47VgQAQ6t/HA=
Accept-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
X-Source-IP: ums-smtp.jpl.nasa.gov [128.149.137.72]
X-Source-Sender: nicolas.f.rouquette@jpl.nasa.gov
X-AUTH: Authorized
Specification: Object Constraint Language, formal/06-05-01
Section: 7.6 Collection Operations
Summary:
The concept of transitive closure is very useful for specifying well-formedness constraints on binary relations.
For a binary relation r:A->A and elements x,y,z in A, r(x,y) is true when r relates x to y and r is transitive whenever for any x,y,z in A, r(x,y) and r(y,z) imply r(x,z). The transitive closure of a binary relation r:A->A is the smallest relation, ^r:A->A, that contains r and is transitive.
In the UML specification, the definition of Classifier::allParents() : Classifier[*] as .all the direct and indirect ancestors of a generalized Classifier. could be equivalently paraphrased as the transitive closure of the Classifier::parents() : Classifier[*] relation.
Specifying the notion of transitive closure for the OCL specification can be problematic as this notion refers to a meta-property not expressible in first order logic (i.e., the smallest relation satisfying a given property). However, the notion of transitive closure can be specified in the context of a particular API for evaluating OCL iterator expressions such as that of the Eclipse OCL implementation of the OCL2.0 specification:
http://help.eclipse.org/ganymede/index.jsp?topic=/org.eclipse.ocl.doc/references/overview/OCLOverview.html
http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.mdt/org.eclipse.ocl/plugins/org.eclipse.ocl/src/org/eclipse/ocl/internal/evaluation/IterationTemplateClosure.java?root=Modeling_Project&view=markup
A synopsis of the algorithm for computing the transitive closure as an OCL iterator expression is available here:
http://dev.eclipse.org/newslists/news.eclipse.modeling.mdt.ocl/msg01390.html
- Nicolas.
From: Pete Rivett [mailto:pete.rivett@adaptive.com]
Sent: Tuesday, May 26, 2009 7:14 AM
To: Rouquette, Nicolas F
Subject: FW: Submitting the report and revised OCL2.1 specification
From: [mailto:mariano.belaunde@orange-ftgroup.com]
Sent: 25 May 2009 04:04
To: ocl2-rtf@omg.org
Subject: Submitting the report and revised OCL2.1 specification
Hi OCL2.1 RTF members,
I have submitted to the OMG:
- The OCL2.1 RTF report (ptc/09-02-04)
- The revised OCL2.1 specification with change bars (ptc/09-02-02).
The RTF report will be presented to the Architecture Board during next meeting
in Costa Rica (22-26 June).
Do not hesitate to let me know about any error or editorial problem.
Regards,
Mariano
<> <>
Mariano Belaunde
Senior Researcher in Modelling Techniques
Orange Labs
8 Avenue Pierre Marzin
22300 Lannion France
tel +33 2 96 05 30 85
mariano.belaunde@orange-ftgroup.com
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AqcGAOt3J0vUnw4U/2dsb2JhbACUI4RSwGiEKwQ
Date: Tue, 15 Dec 2009 19:54:24 +0000
From: Ed Willink
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-GB; rv:1.9.1.5) Gecko/20091204 Thunderbird/3.0
To: ocl2-rtf@omg.org
Subject: Re: Issue 13944 - closure iterator
X-Plusnet-Relay: b4652f5784053af08df34dce0d6f55ac
Hi
Attached resolution specifies a closure iterator for Set-based Trees and Chains as suggested and prototyped within Eclipse. The specification is generalised to provide a depth-first pre-order result for OrderedSet -based Trees as well.
Regards
Ed Willink