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

[Mark S. Miller]

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