[E-Lang] An Attempted Restatement of Hydro's Semantics

[Tyler Close]

At 05:27 AM 4/2/01 -0700, Mark S. Miller wrote:
>Thanks for the clarifying response.  I'll respond in several parts, out of
>order.
>
>At 04:26 AM Monday 4/2/01, Tyler Close wrote:
> >Your terminology proposal pre-supposes some of your conclusions. I think
> >this is a big mistake. Please stick to the terminology presented in the
> >Hydro docs until you convince us that a reduced namespace is appropriate.
>
>Not at this time.  This rephrasing *is* my way of understanding things, and
>for thinking about how they might be simpler.  I am *not* proposing that we
>adopt this terminology, and I explicitly said I hope the terms "mapoid" and
>"setoid" die quickly.  So please correct my semantics where I stray, as
>you've done, and bear with me for now on terminology.  Thanks.

Fair enough. I was just trying to preempt any premature decisions. If we 
all agree that we're not choosing a design direction, but just learning, 
then that's fine.



> >>                                       Mapoids and Setoids
> >>
> >>
> >>There are two kinds of containers, distinguished by their answer to
> >>"isPairAssociative()".  For now, I'll call a pair-associative container a
> >>"mapoid", and a non-pair associative container a "setoid".  (These ugly
> >>words are mine, not Tyler's, and I hope they're only temporary.)
> >
> >In this message, you seem to be attempting to merge the concepts of a queue
> >and a multiset. This is a mistake. A multiset can be used as if it were a
> >LIFO queue (stack), but it is impossible to use it as a FIFO queue. The 
> FIFO
> >queue is an often used data structure that you can't get rid of.
> >
> >There are also implementation reasons for using separate types. With a
> >queue, you know that push / pop is the "primary" operation, whereas with a
> >multiset, searching / inserting is the "primary" operation. It's 
> possible to
> >optimize out a lot of the inner data structure overhead in cases where the
> >client code is only using these "primary" operations. Having the client 
> code
> >tell you at construction time what the "primary" operation will be is
> >important.
>
>This relates to a mystery I find increasingly puzzling.
>
>I expected to find some class in Hydro that corresponds to what one might
>refer to as an immutable indexable  list (as represented in current E by a
>ConstList). Mutability aside, virtually all languages have an indexable
>list-like abstraction, usually called either "array", "list", "vector", or
>"sequence". What is the corresponding abstraction from Hydro? I looked and
>looked and couldn't find it.

As Dean has already pointed out, the only reason to provide an indexable 
list is to make iteration using C style for(;;) loops possible. For example,

     for(int i = 0; i != v.length; ++i)
         System.out.println(v[i]);

E does not use C style for(;;) loops and so does not need indexing.

The Hydro collection types (queue, set, map, sorted set, sorted set) do all 
provide an indexed subset operation: "head(long)". For example, if you were 
showing the first 25 results of a search, you would write:

     for value in results head(25) {
         ...
     }

You can also do something similar to indexing with:

     def fifth := results head(5) reversed() peek()

In 2 years of programming with Hydro, I have never felt the need for a 
C-style indexed array (the DynamicArray that was in Hydro v1 never got 
used). I don't have any code that actually does the above operation.

It is also worth pointing out that providing an indexed interface would be 
misleading. Programmers accustomed to arrays do not expect collection 
elements to jump around to different positions. As you know, the elements 
in a hashtable do jump around on element removal.


>Instead, I found several almost-lists, none of which would seem to be
>necessary if there was a real list.

Queue is the "real list".


>First, your suggested implementation of
>
>     ["a", "b", "c"]
>
>in Hydro (and switching to Java notation to avoid infinite regress) seems to
>be:
>
>     Initializer.Maker.current().make(new Object[] { "a", "b", "c" })
>
>This results in an instance of Initializer, which is indeed a
>non-pair-associative collection, and therefore a setoid by the taxonomy in
>my previous message.  When asked to enumerate its elements, it does
>enumerate these in the expected order.  However, from the name and the docs,
>Initializer doesn't seem intended to be useful by itself, but rather only to
>make other collections.  Consistent with this expected lack of usefulness, I
>could find no indexing operation in the Initializer API.

Initializer is meant to be used as a collection initializer (ie: 
constructing the collection abstractions: queue, map, set, sorted map, 
sorted set) and as a "tuple". Wherever E uses the square brackets, I expect 
that to be a call to Initializer.Maker.

I don't think indexing is useful, but if you really want it, then I would 
be willing to add it to the Initializer interface. Note that here again, 
E's tuple break out syntax is much more powerful. For example:

     def [ first, second, third ] := results

>I also looked at Hydro's Set, List, and Sequence, none of which seemed to
>fit the bill.  I wondered whether this absence might be driven by
>implementation consideration, but I know you know the rope data structure
>(similar to the Xanadu Model-T enfilade, which I believe you are also
>familiar with).  A rope can do all immutable list operations with adequate
>efficiency.

Yes, and both the hashtable and redblacktree implementations use this 
technique (for fast counting of subsets and to efficiently implement the 
immutability abstraction).

The only reason its not there is because you don't need it. If you want it 
anyways, then I think the best place is on the Initializer interface.

>An indexable list is one of the first tools a programmer will reach for.  It
>must be there.  We'll already surprise them enough when they find out it
>must be immutable.

I know MarcS has said this before too, but he's never shown a plausible 
example. E's for loop really obviates the need for index operations.

Tyler