[e-lang] impl: collections

[Mark Miller]

Dean Tribble wrote:
> As the biggest and most oft-used library, we spent some time discussion 
> collections.  There are several issues with the collection classes "as 
> is" ("as are"?).  Some of these are consistency issues.  Kevin, myself, 
> and others have identified some on the list.  These consistency issues 
> hurt more when you are trying to reimplement.  This is a little bit of a 
> seed for discussion, but mostly a place for MarkM to clarify the current 
> intent.
> 
> - Some operations on lists preserve the restrictions on element types, 
> whereas other do not (e.g., list.with(element)).  I think this is 
> largely because diverge() produces a copy with no restrictions, rather 
> than keeping the current element type.

I am not at all convinced that my original intentions wrt this issue were 
coherent, nor am I attached to them. We can indeed consider changing them, so 
long as we're reasonably sensitive to the need not to break too much old code.

In any case, the original intention was that the types associated with Const* 
collections are informative queries, not restrictions. ("*" here stands for 
"List", "Set", or "Map"). For any kind of collection, whether Const*, Flex*, 
or RO* ("RO" stands for "Read Only"), the types are not intended to restrict 
what kinds of collections you can derive from it. Rather, it informs you that 
this collection may only ever contains elements of the given kind. 
'list.with(element)' is therefore intended to accept any kind of element, and 
diverge/0 is intended to yield a Flex* that's unconstrained as to the types it 
may hold.

The types on a Flex* must therefore restrict what you can place into that 
collection itself. Otherwise, the collection would violate its claim that it 
may only ever contain elements of the kind it stated. Likewise, when an RO* 
collection says that it may only ever contain elements of the given kind, the 
corresponding Flex* must never accept elements that would cause this claim to 
be violated.


> - Strings are in many ways lists of characters, but they don't compare 
> equal to a corresponding list of characters.

These indeed shouldn't compare equal (using ==), because they aren't. However, 
E's collection classes are confused about that in one special case, which I 
agree is a mistake:

     ? def x := [].diverge(char)
     # value: [].diverge()

     ? x.snapshot()
     # value: ""

It does not actually make any sense for x.snapshot() to return a String rather 
than a ConstList of chars. An open question is whether the following is also a 
mistake:

     ? def x := "".diverge(char)
     # value: [].diverge()

     ? x.snapshot()
     # value: ""

(To fix the first and preserve the second, we would need to introduce a notion 
of a FlexString, and its value would probably print above as
     # value: "".diverge()
. The motivation is to avoid any temptation to use Java's StringBuffer 
collection.)


> However lists with 
> different element types but the same elements all compare equal.

This is a bug. They should not compare equal (using ==), since they aren't.

Both cases should compare asBigAs (using <=>), since they contain the same 
elements in the same places.


> - Flex and Const versions of objects need to not be type related (so a 
> guard at a security boundary will catch you when you return a flexi list 
> rather than a snapshot).

The easy-to-use guards, List[T] or T[], Set[T], and Map[T1,T2] only accept 
Const*s, and so will prevent leakage of a Flex* or RO*. This does not fix the 
underlying problem -- we're still violating our "no subtypes that add 
authority" design rule -- but this at least ameliorates the problem some.


> There are other issues having to do with the design that we'd like 
> improved, but that's perhaps different than trying to figure out what 
> the intent of the current design is :-)

Yes. Both discussions are worth having.

-- 
Text by me above is hereby placed in the public domain

     Cheers,
     --MarkM