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

[Mark S. Miller]

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.


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

The most basic defining characteristic of an indexable list is that you can 
look up an element by its position in the list.  In current E:

    ? def list := ["a", "b", "c"]
    # value: ["a", "b", "c"]
    
    ? list[1]
    # value: "b"

If a built-in enumeration construct is provided (which in E is the for 
loop), it should enumerate the elements of the list in order.  Position in 
the list should then be the same as enumeration order.

    ? for x in list { println(x) }
    a
    b
    c


Instead, I found several almost-lists, none of which would seem to be 
necessary if there was a 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.

 From this and previous correspondence, when I would expect a list-like 
object to be constructed, you seem to consistently suggest a Queue.  
For example:


At 02:52 AM Thursday 3/22/01, Tyler Close wrote:
>[MarkM wrote:]
>> [...] it seems the collection classes that are a necessary part of the
>> definition of Kernel-E are a string type and an immutable list type, since a
>> match clause in an object definition reifies an incoming message into the
>> message name and the list of arguments:
>>
>>     def forwarder {
>>         match [verb, args] {
>>             # ...
>>         }
>>     }
>>
>> Within the match clause, Kernel-E must say what kind of things the variables
>> "verb" and "args" are bound to, and what messages may be sent to these kinds
>> of things.  That's why we can't agree even on what Kernel-E is if we
>> disagree on how the value of "args" above would respond to whatever "+"
>> expands to.
>
>I would say that "args" does not respond to the "+" operator. I think
>"args" should be an instance of
>com.waterken.canal.source.initializer.Initializer. You can only give
>"+" a definition once you have decided on the type of collection that
>you have. Therefore, to append another argument, you could write:
>
>        args := args toFIFO()
>        args += "another arg"
>
>or, to prepend another argument, you would write:
>
>        args := args toLIFO()
>        args += "another arg"


But, as far as I could tell, the resulting args would still not support 
indexing, ie, lookup by position in the enumeration order (or indeed any 
other index).

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.

Given rope-like lists, I see no need for FIFO or LIFO Queues, or for 
Initializers.

There must be a way to do

    ? def list := ["a", "b", "c"]
    # value: ["a", "b", "c"]

or 
    
    ? def list := ["a", "b", "c"] toSomething()
    # value: ["a", "b", "c"]

or something similar, such that it can be followed by

    ? list[1]

or

    ? list someLookupMessage(1)

and get

    # value: "b"

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.


        Cheers,
        --MarkM