[E-Lang] Immutable map operations
Wed, 28 Mar 2001 00:44:33 -0800
I should make clear that though I have proposed several ideas for syntax
support in other messages, I am not currently advocating them: I'm
perfectly happy to determine that syntactic support for any particular
operation is not worth the syntactic baggage. I am proposing ideas in
order to explore the space and see what we might discover.
At 09:04 AM 3/26/2001, Tyler Close wrote:
> > >I don't think this requires supporting syntax for maps. Sorted maps
> > >are a different story. E currently only has unique maps,
> > in which case
> > >subset/split doesn't really have any useful meaning.
> > Multimaps do have
> > >a meaningful subset operation, but it probably doesn't require
> > >supporting syntax.
> > At Xanadu, we got a lot of efficiency from being able to iterate
> > collections in chunks:
>Agreed. The Hydro interface supports such use; however, given the
>approach you are taking to the issue, I don't see how you can justify
>the creation of special operator syntax for this.
Actually, I was not proposing any special operator for iteration in
chunks--I think the current iteration is just fine. Syntactic support for
split of a list or string (as you note above) is *extremely* useful,
however. I (and Kevin Dana) wrote an Ascii-only string package for Java
that used split, inspired by Ropes and Python split operations. It is
based on a generalization of the following observation: typically when you
compute s.substring(0, n), you also compute s.substring(n, s.length()). I
walked through all the uses of substring within Elib, for example, and
found only 3 or 4 for which this was not true.
> > I thought that was resolved some time ago, where there's a
> > default '=='
> > behavior, and one can supply one. Were there remaining open issues?
>The Object.equals() method in Hydro compares any two collections. I
>imagine MarkM will demand that the collections additionally be of the
>same type. For example, I believe that according to MarkM, a queue and
>a stack can never be equal, even if they currently contain equivalent
>elements in the same inspection order.
Immutable ones should be. In addition, there should probably be an
operation to compare the elements of two collections at a point in time
> > >All of the comparison operators ( < <= <=> >= > ) have meaningful
> > >operations for maps.
> > Since their meaning does not leap out at me, perhaps you
> > could elucidate (a pointer to a description would be sufficient).
Since that's defined by "difference", whose definition for collections I
could not find, it's not even clear to me what that answer is for Hydro's
Maps. Plausible meanings of X < Y are:
- all elements of X are < all elements of Y
- all elements of X less than the greatest element of Y, and all elements
of Y are greater than the least element of X
- X has fewer elements than Y
- Y.keys().contains(x.keys()) and the associated values are the same
- for every element of X, there exists an element in Y that it is less than
Etc. All of these are useful, all of them can obviously be expressed with
X < Y if that's where your head happens to be at. None of them are
obviously a better match than all the others.
BTW The PartiallyComparable comment says that MarkM "discovered"
irreflexive partial ordering. Seems like the concept was around
before. Does it really come from him?
> > I would point out however,
> > that the lack of immediately apparent, incontrovertible
> > meaning, combined
> > with infrequent use suggests that a message name would be better.
>If you believe in set operations, then you necessarily believe in
Yes, however, I believe in so many comparison operations that I don't know
what simply saying "<" would mean (e.g., containment, lexicographic,
> > >All of the set operations ( | & ^ ~ ) have meaninful operations for
> > >maps. Some of these are the same as your "b) Variant"
> > operations. "|"
> > >is the same as "withAll", "& ~" is the same as "withoutAll".
Only if you are willing to ignore the values of one or both of the
maps. That means they are not set operations anymore, and all the
mathematical assumptions no longer hold up. For example, the following are
no longer true: ~~X == X, (X & ~Y) | Y == X | Y, X & Y == Y & X, etc. If
sometimes the argument is a Map and sometimes a Set, then I would be even
more confused by the contract.
It seems like the real contract for Maps is not what sets do, but is just
close enough that it could be wedged into the convenient punctuation, and
we have to agree to ignore the problems. This feels like an artifact of
under-specified contracts. It typically results either from multiple
inheritance (interface inheritance as well as implementation inheritance)
or text-match method naming as in E. In E, there is no contract for "&",
it's just a string. There's no place to document that the associated
implementation is associative or commutative or supports basic
set-theoretic axioms. But those guarantees are important, and I would much
rather have assurance that they held for sets, regions, functions,
bitvectors, etc. than have other semantics wedged into them to leverage the
I should mention that I have much less of a problem with these operations
in the context of Sets of various sorts (regions, functions, etc.). There
the semantics holds.
> > Yes. These however seem to be good examples of things that either deserve
> > a message name (e.g., intersect) or are not frequent enough to deserve
> > special syntactic support (~).
>You were the one who suggested that "withAll" deserves syntactic
>support (I agree). The "|" operator is "withAll".
Just to clarify, "withAll" is high on the list of the operations that might
be worth syntactically supporting. Using "|" to designate "withAll" is
part of the Hydro proposal. The problem is that it suffers from the
semantic discontinuity with actual set semantics. I made a few other
proposals in my previous message that haven't gotten much reaction yet.
>(~) is already supported by the language. The "& ~" syntax is a very
>old idiom for masking one set with another, typically bit sets. It's
>seems a little strange to me that both you and Bill find it strange to
>apply the same idiom to a collection of objects.
It sounds like you are talking about sets, where I was talking about
Maps. If so, please revisit just thinking about Maps because I mostly
agree on Sets. Maps are not collections of objects, they are keyed
collections of objects, and my understanding of the Hydro proposal is that
it would treat only the keys as a set, and the values would go along for
the ride. For sets, the real issue is whether you support unbounded
collections. If X is bounded within an unbounded coordinate space (e.g.,
Integers), ~X isn't.
>If its good for a
>collection of bits, it must be good for a collection of objects.
Eh? FYI: This logic is backwards (or rather, contravariant rather than
covariant), and so doesn't justify anything (and fails to typecheck :-).
>I think the biggest problem here is that most everyone here is
>approaching the problem from the perspective of mutable objects.
It may sound like that, but I'm focused on how to make immutables
approachable and attractive to new programmers.
>a step back and look at the way you work with the immutables that are
>already in the language: the integer / bitfield, the string, the
>character. All the way back to C, people have been happily using these
>immutables. My syntax proposal comes from trying to make collections
>have the same "look and feel" as these other immutables.
All the immutables you named have scalars as their elements, all of which
conform to well understood mathematical properties, axioms, etc. A
collection of user-defined movie objects do not have the same long history
of mathematical study :-) By this I don't mean to say it's not worth
trying to make operations work consistently across collections of bits and
collections of foo; it just shouldn't be too big a surprise if some things
don't work as well.
>stumbling block to this is the horrific String+ operator. I was very
>happy to see you make an argument against it. If only I could find the
>argument that would make MarcS countenance its removal.
Hmmmmm. Hard one, that. We'll have to work on him :-)