[E-Lang] Enough Rope... (was: An Attempted Restatement of Hydro's Semantics)

[Mark S. Miller]

At 04:26 AM Monday 4/2/01, Tyler Close wrote:
>In this message, you seem to be attempting to merge the concepts of a queue 
>and a multiset. 

Yes, into the afore-mentioned indexable immutable list, with an expectation 
of a rope-like implementation for list-like uses, and possibly supplemented 
by an internal hash table for membership testing, or any other lookup by 
element.  I believe this can replace the FIFO and LIFO Queues and the 
Initializer, as previously mentioned, and, with an optional internal hash 
table, the unordered multiset as well.


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

I believe otherwise, but, as always, I'm willing to be convinced.


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

Again, ropes do all these adequately well.  If you want further 
optimization, I'm happy to have several implementation of the same contract, 
when these really are semantically identical, and differ only in 
performance.  If a program without access to the clock cannot distinguish 
them, I'm even happy to have them be ==.  This does not create a multitude 
of types, but only a multitude of ways of advising the implementation about 
expected usage.  An example is my above suggested rope data structure, for 
list-like uses, vs rope + hashtable for multiset-like uses.


>I don't think you need the "-oid" names. I think it is reasonable to talk in 
>terms of a queue, map or set.

For setoids, for example, we need three names.  In my awful terminology, 
these are set, multiset, and setoid.  sets and multisets are disjoint types, 
and setoids are the supertype that includes both.  Since "multiset" sounds 
like an adjective applied to "set", I considered using "set" for the 
supertype and "uniset" for the subtype, but that conflicts with the math 
usage of "set".

>>(Note that I'm also purposely avoiding the Hydro doc's merged view of setoid
>>and mapoid -- that a setoid is a mapoid in which key and value are the same.
>>My reason for avoiding this view will become clear in later email, but I
>>hope my restatement is accurate despite this change of style.  We could
>>also have said that a mapoid is a setoid where the setoid elements are of
>>the form [key, value], but we'll avoid that view as well.)
>
>I'm curious to find out what you've got cooking here. I've spent a lot of 
>time thinking about this and am certain that this view of a set is the 
>"right" one.

Glad to see those scare-quotes.  Such certainty would be pretty scary 
otherwise.

For a pair-associative collection (a mapoid), we agree that for

    map[i]  -> v

and 

    for i => v in map { ... }

the "i"s are the keys and the "v"s are the values.  For a 
non-pair-associative collection (a setoid) we also agree that the "v"s are 
the elements.  However, in Hydro, in at least the for-loop, the "i"s are 
also the elements.  As I mentioned, I haven't been able to find a "map[i]" 
equivalent yet for setoids, so I don't know what you have in mind there.

I suggest that, for setoids, the "i"s above be position in the enumeration 
order.  Then, if x and y are replacing FIFO multisets, (x | y) would be 
union, from the set perspective, and append, from the list perspective.



        Cheers,
        --MarkM