[E-Lang] Immutable map operations

Dean Tribble tribble@e-dean.com
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:
>Dean 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 
(e.g., c1.sameNow(c2)).

> > >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())
- 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
>comparison operators.

Yes, however, I believe in so many comparison operations that I don't know 
what simply saying "<" would mean (e.g., containment, lexicographic, 
numeric).  :-)

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

>The only
>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 :-)