Hi Christian
Yes the more general solution is a rather more powerful beast that can
do much more than transitive closure.
I suspect the underlying recursive iterator should be called recurse
with transitiveClosure a simple invocation thereof. As a generic
recursive iterator there can be two 'accumulators' one initializable
only with an 'already visited set' that is maintained by the recursion,
the other 'acc' optionally allowing the recurse body to accumulate and
return user relevant values rather than the final 'already visited set'.
Regards
Ed Willink
Christian W. Damus wrote:
> 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<--------
>