Lists/Maps/Sets (Was Re: The story of E, part 2 (fwd))

[Mark S. Miller]

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