Re: Lists/Maps/Sets (Was Re: The story of E, part 2 (fwd)) Mark S. Miller (markm@erights.org)
Sun, 11 Oct 1998 20:39:41 -0700

At 09:48 AM 10/9/98 -0700, Dan Bornstein wrote:
>ScriptX lists had the syntax:
>
> [v1, v2, v3]
>
>ScriptX mappings had the syntax:
>
> [k1 -> v1, k2 -> v2, k3 -> v3]
>
>ScriptX had no raw syntax for sets, however ...
> [v1, v2, v3] as HashedSet
> [v1, v2, v3] as SortedArray

I like this direction a lot. One weird thing that I'm doing though is that I don't have a separate "set" data type. Rather, most purposes should be served by the following 2x2 matrix of collection types: 

	              Table			List
	       ----+----------------------------
	Immutable  |  Mapping		Tuple
	           |
	Mutable    |  TableEditor		Vector

(Btw, I'm *not* attached to these names.)

The suggested convention for representing a set is as a Mapping from the elements of the set as keys to null as the value. All the set operations, when applied to general mappings, do the "set thing" on the domains of the mappings, and do something sensible (and often useful) to the range, for example,
http://erights.org/doc/javadoc/org.erights.e.elib.tables.Mapping.html#and

So adopting this suggestion,

[v1, v2, v3] asSet

would be shorthand for

[v1 => null, v2 => null, v3 => null]

while

[v1, v2, v3] asMapping

would be shorthand for

[0 => v1, 1 => v2, 2 => v3]

I can certainly define the syntax such that, between square brackets, there is either a list of expressions or a list of "expr => expr" pairs, ie, to forbid mixing these. This leaves the ugly issue of "[]". Is this the empty tuple or the empty mapping? I say the empty tuple, and if you want the empty mapping, you'd say

[] asSet

or the equivalent

[] asMapping

depending on what reading you're trying to suggest.

Here's a proposal for the flip side, patterns. In patterns I can currently use a syntax suggestively borrowed from tuple expressions. A silly example: 

	define car([x] + _) {x}
	define cdr([_] + y) {y}

Such tuple patterns extract and bind elements of a Tuple positionally, while also making the rest of the Tuple available. Similarly, here's a pattern syntax as syntactic sugar (not kernel!) for extracting elements from a Mapping associatively, while also making the rest of the Mapping available. First, the conventional expression side:

define props := ["foo" => 3, "bar" => 4] | oldProps

Then, on the pattern side,

define [=="foo" => fooVal, =="bar" => barVal] | rest := props

would bind fooVal to 3, barVal to 4, and rest to the non-occluded part of oldProps, ie, to

oldProps - ["foo", "bar"] asSet

I think I'll reserve this in the bnf and define its meaning, but not implement it for a long time.

(Btw, the pattern "==<expr>" is syntactic sugar for the pattern "<temp> ? <temp> == <expr>".) 

	Thanks for the cool direction,
	--MarkM