[e-lang] Killing the MatchBindExpr

[Mark S. Miller]

The following is based on an idea of Dean's, as refined (or at least mutated) 
by Alan, MarcS, Tyler, and me.

Dean observes that the MatchBindExpr is generally useful only when used as the 
conditional in a conditional flow of control context like an 'if'. When used 
in this context, it is also not problematic. The problems come from making the 
MatchBindExpr into a full fledged expression, merely in order to use it as the 
conditional in this context. By being a full fledged expression which returns 
a boolean, Kernel-E then has to cope with the consequences of control flow 
continuing past a match failure, into the code where the variables defined by 
the pattern are in scope, but where they haven't been bound by a successful 
pattern match. To reiterate a previous example:

      ? [1,2] =~ [x, y :char]
      # value: false

      ? y
      # value: <ref broken by problem: <ClassCastException: \
      #         Integer doesn't coerce to a Character>>

My previous email failed to point out the worst problem with the above 
behavior: The definition of 'y' is guarded by ':char'. Surely, then, within 
the resulting scope, we can count on 'y' having a character as its value? The 
above counter-example shows that E is currently not faithful to this intuition.

Dean suggests that, instead, Kernel-E should bundle pattern match with if-like 
conditional control flow, combining them into one construct. Here are two 
possibilities, the if-match and the extended-switch, either of which could 
replace the current MatchBindExpr in Kernel-E

1) if-match:

    e ::= if (e1) =~ p1 {e2} else {e3}

The if-match would be in addition to the existing 'if' production. As with the 
existing 'if', e2 is evaluated in the scope resulting from the 'if' head, here 
e1 and p1; but e3 is not. In E, we'd allow the normal 'else if' chaining to 
mix these two forms of 'if' without worry. Such chaining would expand into 
Kernel-E nesting just like it does now.

Currently, the E switch expression expands to an 'else if' chain, with 
MatchBindExprs as the conditions of these 'if's. If the if-match replaces 
MatchBindExpr in Kernel-E, then switch could expand to an if-match chain in 
essentially the same way.

Alternatively, we could promote the switch expression into Kernel-E. In order 
for the switch to have all the power needed to express all other match 
constructs, we could add an optEjector-expression argument ('e2' below) to the 
head of the switch expression:

2) extended-switch:

    e ::= switch (e1,e2) { <match pi {ei}>* }

In E, e2 would be optional. If e2 is present, then if all patterns fail to 
match, the diagnostic from the last failure is reported to e2's value. If e2 
is absent, it defaults to null and the last failure is thrown, which is 
consistent with switch's current behavior. By adding the optEjector argument, 
we can distinguish match-failure from a thrown exception.

Since E already contains the switch expression, adding extended-switch to E 
and Kernel-E does not really increase the size of E. If we also remove 
MatchBindExpr from E and Kernel-E, then Kernel-E stays about the same size and 
E actually gets smaller.

Many languages (such as C and Java) have constant-time switch constructs (at 
least when the case values are dense). Currently, if the E programmer writes a 
simple switch which should be compiled to a constant time dispatch, this is 
first  expanded to an 'else if' chain. Although Dan reports that gcc will 
actually optimize some 'else if' chains to constant time dispatches, that's a 
lot to ask of an optimizer. But if the switch is passed through directly to 
Kernel-E, then it should be easier for reasonable E implementations to 
recognize some of the simple cases they can turn into constant time dispatches.

Because of these issues, initially I wanted to just add the extended-switch to 
E and Kernel-E, and forget about the if-match. However, this fantasy did not 
survive the first two actual examples I tried to convert, which are shown 
below. For each, their conversion to if-match is trivial, and the resulting 
code is just as readable and concise. OTOH, their conversion to 
extended-switch is fine as a Kernel-E expansion, but is too verbose to impose 
on the E programmer. If we decide to put extended-switch into Kernel-E, we 
should consider adding if-match to E and expanding it to extended-switch as 
shown below.

E and Kernel-E would then both stay about the same size. Both would shed the 
MatchBindExpr. In exchange, E would take on the if-match and Kernel-E would 
take on the extended-switch. Doing so would cure both languages of the scoping 
irregularities of the current MatchBindExpr.


in webServerAuthor.emaker
original:
                     if (action =~ `GET /@{fileName} HTTP/1.@{trailer}`) {
                         filePath := fileName
                     }
with if-match:
                     if (action) =~ `GET /@{fileName} HTTP/1.@{trailer}` {
                         filePath := fileName
                     }
with switch:
                     switch (action) {
                         match `GET /@{fileName} HTTP/1.@{trailer}` {
                             filePath := fileName
                         }
                         match _ {}
                     }


in darpaBrowser.caplet
original:
             if (text.endsWith("/")) {
                 #...
             } else if (text =~ `http://@host/@path`) {
                 #...
             } else {
                 #...
             }
with if-match:
             if (text.endsWith("/")) {
                 #...
             } else if (text) =~ `http://@host/@path` {
                 #...
             } else {
                 #...
             }
with extended-switch:
             if (text.endsWith("/")) {
                 #...
             } else {
                 escape ej {
                     switch (text, ej) {
                         match `http://@host/@path`) {
                             #...
                         }
                     }
                 } catch _ {
                     #...
                 }
             }

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

     Cheers,
     --MarkM