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