# [e-lang] Map Pattern Syntax (was: REST and capabilities (was Re: Developing a capability security tools marketplace))

Mark S. Miller e-lang@mail.eros-os.org
Tue, 06 Aug 2002 08:00:38 -0700

```My answer to Ken below also provides background for my upcoming answer to Paul.

At 05:21 PM 8/5/2002 Monday, Ken Kahn wrote:
>> Mark S. Miller wrote:
>> >
>> >    def makePoint(["x" => x, "y" => y] | _) :any { ... }
>> >
>
>Maybe it is too many years working with Prolog but shouldn't that be
>
>def makePoint(["x" => x, "y" => y | _]) :any { ... }
>
>?

It was inspired by that Prolog idiom for lists, so let's first look at lists.

Lisp lists have dotted notation:
(x y . rest)

Prolog-oids (Prolog, and other Herbrand-term-oriented horn clause languages,
like FCP) are the same in concept, but with different characters:
[x, y | rest]
In Prolog-oids, this syntax can be used both for expressions (in the body)
or for patterns (in the head).

E does something similar, but with a further pun.  E is an expression
language with infix operators.  In an expression context, we'd write:
[x, y] + rest
Unlike Lisps "." and Prolog-oid's "|", which are consing symbols, E's "+"
means append.  Combined with the square bracket notation but put on the
outside, this enables consing to be expressed as easily as in Lisp or
Prolog, but enables other useful list construction expressions to be
expressed as easily:
[a, b] + midList + [x, y]

On the pattern side, E recognizes only the subset of this syntax
corresponding to cons.  It will accept the first example but not the second
one.
? def [x, y] + rest := [1, 2, 3, 4]
# value: [1, 2, 3, 4]

? [rest, x, y]
# value: [[3, 4], 1, 2]

E's notation
["x" => 3, "y" => 7]
constructs a single-valued map, where for each key there is exactly one
value.  Maps may be composed using the "|" operator

? def m := ["x" => 3, "y" => 7] | ["y" => 4, "z" => 9]
# value: ["y" => 7, "z" => 9, "x" => 3]

You can think of this as the union of the two maps, with the left map
dominating where they collide.

On the pattern side, 0.8.20 will accept the subset of this syntax which is
cons-like:

? def ["x" => x] | rest := m
# value: ["y" => 7, "z" => 9, "x" => 3]

? [x, rest]
# value: [3, ["y" => 7, "z" => 9]]

In a map pattern, each of the keys is an expression and each of the values
is a pattern.  Execution and scoping proceeds strictly left-to-right, which
is normally the case in E, but was not immediately obvious how to achieve in
the expansion of this construct.  The first key-expression is evaluated, the
first value is looked up.  If found, it is matched against the first
value-pattern and the remaining map without this key-value association is
formed use starting at the next association.  If there is a terminal "|
pattern", then it is matched against the final remaining map, without the
associations already matched.  If there is no terminal "| rest", then the
expansion includes a test that the final remaining map is empty.  If at any
step any lookup fails or any pattern match fails, then the match as a whole
fails.

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

Cheers,
--MarkM

```