How other pattern-matching lisps do [Was: Re: pcase ` meaning [Was: Re: Replace trivial pcase occurrences in the Emacs sources]]

["Garreau\, Alexandre" <galex-713@galex-713.eu>]

On 2018-10-28 at 03:44, Garreau, Alexandre wrote:
> Initially I expected this would have worked […]
>
> #+BEGIN_SRC emacs-lisp
>   (defun evaluate (exp env)
>     (pcase exp
>       (('add x y)       (+ (evaluate x env) (evaluate y env)))
>       (('call fun arg)  (funcall (evaluate fun env) (evaluate arg env)))
>       (('fn arg body)   (lambda (val)
>                             (evaluate body (cons (cons arg val) env))))
>       ((pred numberp)     exp)
>       ((pred symbolp)     (cdr (assq exp env)))
>       (_                  (error "Unknown expression %S" exp))))
> #+END_SRC
>
> […]
>
> It even more feel wrong that, this, doesn’t work, for no reason (it
> can’t be incompatible with the minilanguage):
>
> #+BEGIN_SRC emacs-lisp
>   (pcase [1 2]
>     ([a b] (+ a b)))
> #+END_SRC
>
> Yet that’s the most intuitive and straightforward way of using pattern
> matching.

Okay, so I went to search what is done in other pattern matching lisp
form.  The closer, yet quite straightforward, implementation of pattern
matching I found is the one found in Guile [0], claimed to be used in most
scheme implementation, which supports as well quasiquoting, but also raw
lists and vectors, because, according its manual:
>   The names ‘quote’, ‘quasiquote’, ‘unquote’, ‘unquote-splicing’, ‘?’,
> ‘_’, ‘$’, ‘and’, ‘or’, ‘not’, ‘set!’, ‘get!’, ‘...’, and ‘___’ cannot
> be used as pattern variables.

As you can see, it also supports `not', and some facilities for OOP.

I also found a cl library named cl-match [1], which also use its
minilanguage by default (but doesn’t support backquotes), so its
solution stays compatible: it uses sequences constructors such as
“cons”, “list”, “list*” (improper lists), or “array”/“vec” as patterns:

#+BEGIN_SRC lisp
  (match (list 1 2)
    ((list x y) (+ x y)))
#+END_SRC

It has several interesting forms pcase doesn’t seem to have (at least
not documented): such as “(as binding pattern)”, which matches
`pattern', and binds it to `binding' (so you can keep a binding though
binding subelement of it), or “(type type &optional pattern)” for
matching if it’s a given type, also more specific (hence semantic) and
shorter and simpler than “(and (pred typep) &optional pattern)”.

Then all other cl implementations I found (named either “match”, either
“unify”: the later is commutative, the former not) doesn’t do real
successive pattern matching, but simple destructuring (without `and',
`or', guards, or any minilanguage), yet unlike cl-destructuring-bind, in
a simpler way (without lambda-list-like arguments), and rather than
erroring out (making it unsuitable to successive tries of pattern
matching), they return either an environment, or something such as
'fail.  So it can be trivially used to make successive pattern-matching.

Going in this direction there’s first optima [2], which of course match
raw lists and such by default, but also have really interesting special
patterns, such as “(places symbol)”, that will bind to symbol, but using
symbol-macrolet, so that setf/cl-letf will work, or `(assoc 1
alist-pattern)' (so “(match '((1 . 2)) ((assoc 1 x) x))” returns 2), to
match content of an alist, or “property” for plists.

There are some others, generally a subset of what I described until
then, such as cl-unification [3].

One of these, the simpler I found, is one I found in an lisp files
archive annex [4] of a book that wasn’t freely available online /Lisp,
Third Edition/: it doesn’t appear to be free software, but it’s trivial
to understand: what it does is just match recursively plain conses
(hence lists), not even arrays or string, since it does eql on anything
else (just as case already wrongly do: what’s this fear of equal in
common lisp?), but it uses the special list (? symbol) to bind symbols.
Simply replacing “'?”  per “'var”, make it work in emacs-lisp, but as it
is not free there’s little interest in doing so.

In the end, I believe, before to even support arbitrary lists for when
the car is not a predefined pattern, it would be handy to support
constructors (hence simple new predefined patterns) such as “list” or
“vector”/“array”, that would make possible to remove all the confusing
backquotes.

However something such as (pcase-defmacro list (&rest args) ``(,@args))
(nor (pcase-defmacro list (&rest args) `(cons 'list args))) wouldn’t
work because multiple backquotes doesn’t seem to work.

[0] (info "(guile) Pattern Matching")
[1] https://common-lisp.net/project/cl-match/doc/clmatch-api.htm
[2] https://github.com/m2ym/optima
[3] https://common-lisp.net/project/cl-unification/
[4] http://people.csail.mit.edu/phw/Books/lisp.zip