FeML: a skeleton of a femto-ML with nothing but polymorphic variants and functions

A year or two ago, Darius Bacon and I were talking about making a sort
of variant of Scheme with ML-like pattern-matching as the basic
primitive.  You have a slightly more complicated lambda, but you don’t
need cond, car, cdr, eq, or null? in the base language, just cons or
quasiquote, plus the pattern-matching lambda and either labels or
define.

For example:

    (define assoc 
      (lambda (key ((key . value) . more)) (cons key value)
              (key (x . more))             (assoc key more)
              (key ())                     '()))

Here `lambda` takes an arbitrary set of pattern-action pairs and
matches the patterns in order against the argument list, evaluating
and returning the action expression for the pattern that matches.  In
this case, first we check to see if the key is the caar of the list of
key-value pairs, and if so, we return its (reconstructed) car;
otherwise, if there are more items in the list, we recurse down the
list; otherwise, if the list is the empty list, we return the empty
list.

(It’s not clear what happens if you say `(assoc 3 4)`.  Should that be
an error, or should it have unspecified behavior to permit compiler
optimization?)

This is awfully close to Prolog, although you wouldn’t do it this way
in Prolog: