[e-lang] impl: collections
markm at cs.jhu.edu
Sat May 14 14:15:09 EDT 2005
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
> - 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
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
> - 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()
# 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
? def x := "".diverge(char)
# value: .diverge()
# 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
> 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
More information about the e-lang