[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [Newsgroup Home]
[news.eclipse.modeling.mdt.ocl] Re: OCL closures implementation
Hi, Ed,

See some replies in-line, below.

Cheers,

Christian


On Wed, 2009-08-12 at 08:03 +0100, Ed Willink wrote: 
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().

That sounds more clear; good. 


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.

Oh, yes.  The implicit collect is a very good point!


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>)
I think the "iterate" syntax uses a semicolon to separate the accumulator from the iterator variables, which are usually separated by commas.  The accumulator isn't an iterator variable, so it needs to be set apart.


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.
That's different from other iterators, in which the resulting collection kind generally is determined by the source collection kind.  And I wonder whether OCL really wants to have another iterator as complex as the "iterate" _expression_, with accumulators and such.  Don't get me wrong, I like this idea of iterate-like syntax because it solves both of these problems, but I wonder whether it's not over-kill.

OTOH, the recursive nature of this iterator is already very different from other iterators:  it iterates over more than just the source collection!  Really, quite a different beast.

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.

Yes, repetition of elements doesn't seem very useful in a transitive closure, which is really only interested in finding reachable objects.  The number of occurrences of any object would only be useful if the result could indicate where they were found, which it doesn't.


	Regards

		Ed Willink


Christian W. Damus wrote:


--------8<--------