[news.eclipse.modeling.mdt.ocl] Re: OCL closures implementation

[Ed Willink <ed@xxxxxxxxxxxxx>]

Hi Christian

>
> Just $0.02 from a still-interested-though-somewhat-remote party  :-)

Glad you're still here.

Your comments and an accidentally off-list discussion with Nicolas 
Rouquette have helped me clarify my thoughts.

The practical implementation of closure is not closure; it is transitive 
closure. closure would require some form of allInstances to discover a 
domain over which to evaluate a predicate. So the new iterator should 
probably be called transitiveClosure().

Whether transitive closure on objects or collections is more fundamental 
is a chicken and egg argument. Both are useful and beauty is in the eye 
of the beholder. The clinching argument to me for which is best is to 
examine the lexical consequences. Imagine that both were available. Then 
we have ample opportunity for

elems.transitiveClosure()
elems->transitiveClosure()

typos and confusion. Only one can be permitted.

If just object closure existed, the interaction with implicit collect 
for collections would be nearly as confusing, so the collection wins for 
lexical ergonomic reasons.

My more general definition using a helper routine is therefore:
-------------------------

The transitiveClosure iterator signature is very similar to iterate

    transitiveClosure(<elem> : T, <acc> : C(T) = <acc-init> |
			<expression-with-elem>)

where

<expression-with-elem> is an iterator body expression that may reference 
<elem> and which returns a collection of type C(T).

<elem> is the name an optional iterator variable for use in 
<expression-with-elem>

<acc> is the optional name of a result variable of type C(T)

<acc-init> is the optional initial value for <acc>.

The default result variable is an empty Set(T).

The invocation

    roots->transitiveClosure(<elem> : T, <acc> : C(T) = <acc-init> | 	
		<expression-with-elem>)

is equivalent to invocation of a helper routine as

    roots->uniqueNameXxx(<acc-init>)

where the synthesized uniqueNameXxx is one of

Set::uniqueNameXxx(uniqueNameYyy : Set(T)) : Set(T) {
    iterate(<elem> : T, acc : Set(T) = uniqueNameYyy |
    if acc->includes(<elem>) then acc
    else let candidates : Set(T) = <expression-with-elem>
        in candidates->uniqueNameXxx(acc->including(<elem>))
    endif)
}

OrderedSet::uniqueNameXxx(uniqueNameYyy : OrderedSet(T)) : OrderedSet(T) {
    iterate(<elem> : T, acc : OrderedSet(T) = uniqueNameYyy |
    if acc->includes(<elem>) then acc
    else let candidates : OrderedSet(T) = <expression-with-elem>
        in candidates->uniqueNameXxx(acc->append(<elem>))
    endif)
}

Bag::uniqueNameXxx(uniqueNameYyy : Bag(T)) : Bag(T) {
    iterate(<elem> : T, acc : Bag(T) = uniqueNameYyy |
    if acc->includes(<elem>) then invalid
    else let candidates : Bag(T) = <expression-with-elem>
        in candidates->uniqueNameXxx(acc->including(<elem>))
    endif)
}

Sequence::uniqueNameXxx(uniqueNameYyy : Sequence(T)) : Sequence(T) {
    iterate(<elem> : T, acc : Sequence(T) = uniqueNameYyy |
    if acc->includes(<elem>) then invalid
    else let candidates : Sequence(T) = <expression-with-elem>
        in candidates->uniqueNameXxx(acc->append(<elem>))
    endif)
}

--------------------------------------------------

Introduction of the optional <acc-init> allows an 'object' iteration to 
include itself in the initialiser for transitiveClosure of its elements.

Introduction of the optional <acc-init> allows the collection type to be 
defined.

Support for OrderedSets provides a defined depth first ordering for such 
transditiveClosures.

Support for Bags and Sequences is more dubious. The definitions above 
give useful results for trees and invalid for graphs.

	Regards

		Ed Willink


Christian W. Damus wrote:
> Hi, Ed,
>
> Good point about the helper operation:  I hadn't considered that the 
> formal definition of the closure() iterator could include additional 
> operations.  Of course, it can!
>
> I can think of a few arguments against the object iterator construct:
>
>   - it would be the first instance of its kind, a new language construct.
>     It probably needs to be able to show that it cannot be implemented
>     by any other mechanism (such as collection iterator) to justify that
>
>   - the "." operator makes "closure" look like a model operation.  An "ocl"
>     prefix could help, but then it still looks like an operation, not an
>     iterator
>
>   - I'm not sure that it's a good idea to always include the initial object
>     in the closure.  It's easy enough to extend the expression to add it
>     (e.g., "root->closure(kids)->including(root)" ) than it is to extend the
>     expression to remove it.  In the latter case, e.g.,
>     "root->closure(kids)->excluding(root)" there's no way to know that
>     root shouldn't be in the closure because it was reached via a cycle
>
> Note that the arrow operator coerces scalar values to singleton sets, so 
> you can do
>
>    root->closure(kids)
>
> to get the closure of the kids association and, if necessary,
>
>    root->closure(kids)->including(kids)
>
> to ensure that the result has the root, also.  If this is a very common 
> case, it may justify an additional iterator, say
>
>    root->withClosure(kids)
>
> that includes the starting collection.
>
> Just $0.02 from a still-interested-though-somewhat-remote party  :-)
>
> Cheers,
>
> Christian
>
>
> On Sun, 2009-08-09 at 22:20 +0100, Ed Willink wrote:
> > Hi Neil, Christian, Nicolas
> >
> > I stumbled over the experimental closure() implementation a few days 
> > ago. It seems interesting. I see this has been raised as OMG Issue 
> > 13944. The RTF committee is so busy that if we want to get this in
> > OCL 2.3 there are better chances if the submission is formatted ready
> > for inclusion in the RTF report.
> >
> > I think the recursive specification difficulty can be easily cured by 
> > using infinite recursion of a helper function and a set that makes 
> > further recursion redundant.
> >
> > After trying to use the closure iterator, I think that an object 
> > iterator form of closure is more fundamental than the collection 
> > iterator. This allows the start object to be included in the results, so 
> > a root and all its kids would be returned by
> >
> > root.closure(it | it.kids)
> >
> > whereas all the kids could be returned by
> >
> > root.kids->forall(kid | kid.closure(it | it.kids))->asSet()
> >
> > The collection iterator is nonetheless useful allowing the shorter
> >
> > root.kids->closure(it | it.kids)
> >
> > An object iterator is of course a new concept and so might bypass the 
> > specification in terms of iterate ordanance.
> >
> > Do you think it worth appending an update to Issue 13944 along these lines?
> >
> > 	Regards
> > 		
> > 		Ed Willink
> >
> > ---------------------------------------------------------------------
> > On Mon, 14 Jul 2008 15:59:16 -0400, Christian W. Damus wrote:
>
> --------8<--------