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<--------