From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: "Garreau\, Alexandre" Newsgroups: gmane.emacs.devel Subject: How other pattern-matching lisps do [Was: Re: pcase ` meaning [Was: Re: Replace trivial pcase occurrences in the Emacs sources]] Date: Sun, 28 Oct 2018 05:45:54 +0100 Message-ID: <87d0rud6gt.fsf_-_@portable.galex-713.eu> References: <20151216202605.GA3752@acm.fritz.box> <87wprqitj5.fsf@fencepost.gnu.org> <56893C8C.3060200@yandex.ru> <87oad2irtd.fsf@fencepost.gnu.org> <5689456A.1010601@yandex.ru> <87egdy8tyz.fsf@fencepost.gnu.org> <56895FDE.4060406@yandex.ru> <8760za8r4a.fsf@fencepost.gnu.org> <87h9iunkcg.fsf@web.de> <87h8hc4xw2.fsf_-_@web.de> <83tvlcsnee.fsf@gnu.org> <87pnw037ar.fsf@web.de> <83ftwvs7y9.fsf@gnu.org> <877ei7mkfh.fsf@web.de> <87a7mze7tl.fsf@web.de> <87zhuykjjh.fsf@web.de> <871s8aesdc.fsf@portable.galex-713.eu> <87tvl6dc3e.fsf_-_@portable.galex-713.eu> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: blaine.gmane.org 1540701883 23352 195.159.176.226 (28 Oct 2018 04:44:43 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 28 Oct 2018 04:44:43 +0000 (UTC) User-Agent: Gnus (5.13), GNU Emacs 25.1.1 (i686-pc-linux-gnu, GTK+ Version 3.22.11) of 2017-09-15, modified by Debian Cc: Eli Zaretskii , emacs-devel@gnu.org, Stefan Monnier , Dmitry Gutov To: Michael Heerdegen Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Oct 28 05:44:38 2018 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gGcwI-0005z8-9r for ged-emacs-devel@m.gmane.org; Sun, 28 Oct 2018 05:44:38 +0100 Original-Received: from localhost ([::1]:38732 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gGcyO-0004VQ-Nh for ged-emacs-devel@m.gmane.org; Sun, 28 Oct 2018 00:46:48 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:41336) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gGcxi-0004V7-KD for emacs-devel@gnu.org; Sun, 28 Oct 2018 00:46:07 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gGcxh-0000jG-GC for emacs-devel@gnu.org; Sun, 28 Oct 2018 00:46:06 -0400 Original-Received: from portable.galex-713.eu ([2a00:5884:8305::1]:55348) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1gGcxh-0000id-6X; Sun, 28 Oct 2018 00:46:05 -0400 Original-Received: from localhost ([::1] helo=portable.galex-713.eu) by portable.galex-713.eu with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.89) (envelope-from ) id 1gGcxX-0005Q6-5v; Sun, 28 Oct 2018 05:45:57 +0100 PGP-FINGERPRINT: E109 9988 4197 D7CB B0BC 5C23 8DEB 24BA 867D 3F7F Accept-Language: fr, en, eo, it, br In-Reply-To: <87tvl6dc3e.fsf_-_@portable.galex-713.eu> (Alexandre Garreau's message of "Sun, 28 Oct 2018 03:44:21 +0100") X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:5884:8305::1 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:230750 Archived-At: On 2018-10-28 at 03:44, Garreau, Alexandre wrote: > Initially I expected this would have worked [=E2=80=A6] > > #+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 > > [=E2=80=A6] > > It even more feel wrong that, this, doesn=E2=80=99t work, for no reason (= it > can=E2=80=99t be incompatible with the minilanguage): > > #+BEGIN_SRC emacs-lisp > (pcase [1 2] > ([a b] (+ a b))) > #+END_SRC > > Yet that=E2=80=99s the most intuitive and straightforward way of using pa= ttern > 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 =E2=80=98quote=E2=80=99, =E2=80=98quasiquote=E2=80=99, =E2=80= =98unquote=E2=80=99, =E2=80=98unquote-splicing=E2=80=99, =E2=80=98?=E2=80= =99, > =E2=80=98_=E2=80=99, =E2=80=98$=E2=80=99, =E2=80=98and=E2=80=99, =E2=80= =98or=E2=80=99, =E2=80=98not=E2=80=99, =E2=80=98set!=E2=80=99, =E2=80=98get= !=E2=80=99, =E2=80=98...=E2=80=99, and =E2=80=98___=E2=80=99 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=E2=80=99t support backquotes), so its solution stays compatible: it uses sequences constructors such as =E2=80=9Ccons=E2=80=9D, =E2=80=9Clist=E2=80=9D, =E2=80=9Clist*=E2=80=9D (im= proper lists), or =E2=80=9Carray=E2=80=9D/=E2=80=9Cvec=E2=80=9D as patterns: #+BEGIN_SRC lisp (match (list 1 2) ((list x y) (+ x y))) #+END_SRC It has several interesting forms pcase doesn=E2=80=99t seem to have (at lea= st not documented): such as =E2=80=9C(as binding pattern)=E2=80=9D, which matc= hes `pattern', and binds it to `binding' (so you can keep a binding though binding subelement of it), or =E2=80=9C(type type &optional pattern)=E2=80= =9D for matching if it=E2=80=99s a given type, also more specific (hence semantic) = and shorter and simpler than =E2=80=9C(and (pred typep) &optional pattern)=E2= =80=9D. Then all other cl implementations I found (named either =E2=80=9Cmatch=E2= =80=9D, either =E2=80=9Cunify=E2=80=9D: the later is commutative, the former not) doesn=E2= =80=99t 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=E2=80=99s first optima [2], which of course m= atch raw lists and such by default, but also have really interesting special patterns, such as =E2=80=9C(places symbol)=E2=80=9D, that will bind to symb= ol, but using symbol-macrolet, so that setf/cl-letf will work, or `(assoc 1 alist-pattern)' (so =E2=80=9C(match '((1 . 2)) ((assoc 1 x) x))=E2=80=9D re= turns 2), to match content of an alist, or =E2=80=9Cproperty=E2=80=9D 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=E2=80=99t freely available online /Li= sp, Third Edition/: it doesn=E2=80=99t appear to be free software, but it=E2=80= =99s 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=E2=80=99s this fear of equal in common lisp?), but it uses the special list (? symbol) to bind symbols. Simply replacing =E2=80=9C'?=E2=80=9D per =E2=80=9C'var=E2=80=9D, make it = work in emacs-lisp, but as it is not free there=E2=80=99s 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 =E2=80=9Clist= =E2=80=9D or =E2=80=9Cvector=E2=80=9D/=E2=80=9Carray=E2=80=9D, 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=E2=80=99t work because multiple backquotes doesn=E2=80=99t 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