"Like `let*' but ....."

"Like `let*' but ....."

[Alan Mackenzie]

Hello, Emacs.

The doc string of pcase-let* reads, in its entirety:

       "Like `let*' but where you can use `pcase' patterns for bindings.
    BODY should be an expression, and BINDINGS should be a list of bindings
    of the form (PAT EXP)."

What is not clear is precisely HOW `pcase' patterns are used for
bindings, and what the semantics of (PAT EXP) are.

There is no other documentation of pcase-let* that I'm aware of.

Would somebody please explain it to me?  In particular, I want to
understand the following form from byte-compile-file-form-defalias in
bytecomp.el:

       (pcase-let*
           ;; `macro' is non-nil if it defines a macro.
           ;; `fun' is the function part of `arg' (defaults to `arg').
           (((or (and (or `(cons 'macro ,fun) `'(macro . ,fun)) (let macro t))
                 (and (let fun arg) (let macro nil)))
             arg)
            ;; `lam' is the lambda expression in `fun' (or nil if not
            ;; recognized).
            ((or `(,(or `quote `function) ,lam) (let lam nil))
             fun)
            ;; `arglist' is the list of arguments (or t if not recognized).
            ;; `body' is the body of `lam' (or t if not recognized).
            ((or `(lambda ,arglist . ,body)
                 ;; `(closure ,_ ,arglist . ,body)
                 (and `(internal-make-closure ,arglist . ,_) (let body t))
                 (and (let arglist t) (let body t)))
             lam))
         (unless (byte-compile-file-form-defmumble
                  name macro arglist body rest)
           (when macro
             (if (null fun)
                 (message "Macro %s unrecognized, won't work in file" name)
               (message "Macro %s partly recognized, trying our luck" name)
               (push (cons name (eval fun))
                     byte-compile-macro-environment)))
           (byte-compile-keep-pending form))))

What eludes me is points such as:
(i) what variables are being bound?
(ii) To what values?
(iii) What do the `or's and `and's on Line 4, etc. mean?

Incidentally, when I expand that form with macroexpand-all and print it
with pp, the resulting form is 173 lines long, totally inscrutable, a
typical portion of it looking like this:

                                          (if
                                              (null x)
                                              (let*
                                                  ((x
                                                    (cdr x)))
                                                (if
                                                    (consp x)
                                                    (let*
                                                        ((x
                                                          (car x))
                                                         (x
                                                          (cdr x)))
                                                      (if
                                                          (null x)
                                                          (funcall pcase-0 t x)
                                                        (funcall pcase-0 nil arg)))
                                                  (funcall pcase-0 nil arg)))
                                            (funcall pcase-0 nil arg)))
                                      (funcall pcase-0 nil arg)))
                                (funcall pcase-0 nil arg)))
                          (funcall pcase-0 nil arg)))
                    (funcall pcase-0 nil arg)))
              (funcall pcase-0 nil arg))))

Is this efficient, in either run-time or the size of the byte code produced?

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: "Like `let*' but ....."

[Clément Pit-Claudel]

On 2017-01-24 16:12, Alan Mackenzie wrote:
> What is not clear is precisely HOW `pcase' patterns are used for
> bindings, and what the semantics of (PAT EXP) are.

Hi Alan,

I find that mentally translating (pcase-let* ((<x> <y>)) <z>) to (pcase <y> (<x> <z>)) helps.  This translation is mostly correct, with the added twist that the former is undefined if <y> doesn't match <x>.

Then everything is as in the pcase documentation. Hopefully this helps!

Cheers,
Clément.

Re: "Like `let*' but ....."

[Michael Heerdegen]

Hello Alan,

> The doc string of pcase-let* reads, in its entirety:
>
>        "Like `let*' but where you can use `pcase' patterns for bindings.
>     BODY should be an expression, and BINDINGS should be a list of bindings
>     of the form (PAT EXP)."
>
> What is not clear is precisely HOW `pcase' patterns are used for
> bindings, and what the semantics of (PAT EXP) are.

I think Clément's has answered that correctly.  And for the semantics of
the patterns see C-h f pcase.


> What eludes me is points such as:
> (i) what variables are being bound?
> (ii) To what values?
> (iii) What do the `or's and `and's on Line 4, etc. mean?

If you are interested in learning to understand `pcase' patterns: if you
want to test what effect matching a pattern against some value has, I
had written the following thing some time ago:

#+begin_src emacs-lisp

(defun my-pcase-matcher (pattern)
  "Turn pcase PATTERN into a predicate.
For any given pcase PATTERN, return a predicate P that returns
non-nil for any EXP when and only when PATTERN matches EXP.  In
that case, P returns a list of the form (bindings . BINDINGS) as
non-nil value, where BINDINGS is a list of bindings that pattern
matching would actually establish in a pcase branch.

Example:

  (setq matcher
        (my-pcase-matcher
         '`(,(and (pred integerp) x)
            ,(and (pred integerp)
                  (pred (< 0))
                  y))))

  (funcall matcher '(1 0))
    ==> nil

  (funcall matcher '(1 2))

    ==>
   (bindings
    (x . 1)
    (y . 2))"
  (let ((arg  (make-symbol "exp")))
    `(lambda (,arg)
       ,(pcase--u
         `((,(pcase--match arg (pcase--macroexpand pattern))
            ,(lambda (vars)
               `(list
                 'bindings
                 ,@(nreverse
                    (mapcar (lambda (pair) `(cons ',(car pair) ,(cdr pair)))
                            vars))))))))))
#+end_src


> Incidentally, when I expand that form with macroexpand-all and print it
> with pp, the resulting form is 173 lines long, totally inscrutable, a
> typical portion of it looking like this: 
>
>                                           (if
>                                               (null x)
>                                               (let*
>                                                   ((x
>                                                     (cdr x)))

Note that you should bind print-circle -> t and print-gensym -> t when
printing to get a semantically equivalent printed representation of the
macroexpansion.


> Is this efficient, in either run-time or the size of the byte code
> produced?

Those highly nested expressions come from destructuring.  I think the
expansion is nearly as effecient as it could be.  Dunno about the byte
code size.


Regards,

Michael.

Re: "Like `let*' but ....."

[Stefan Monnier]

> Those highly nested expressions come from destructuring.
> I think the expansion is nearly as effecient as it could be.

There's definitely room for improvement.  Some of it would be
easier/cleaner to fix in the byte-compiler than in the pcase macro.

The most costly part is the use of (funcall pcase-N ...).  Such forms
are used to avoid duplicating the body of a branch (in the case of
`pcase-let` that means duplicating the body of the `pcase-let`), so
they're important to avoid potential code size blow up, but they impose
a significant performance cost.  Luckily, in many cases we can avoid
them (e.g. when the body is small, or when the patterns are simple
enough that they don't lead to any duplication at all).

BTW, regarding the big pcase-let* in byte-compile-file-form-defalias,
it was partly an experiment in the use of pcase patterns.

OT1H I'm not convinced the result speaks very much in favor of pcase,
OTOH if you try to rewrite this code without pcase it's not
pretty either.

I'll read it for you:

           ;; `macro' is non-nil if it defines a macro.
           ;; `fun' is the function part of `arg' (defaults to `arg').
           (((or (and (or `(cons 'macro ,fun) `'(macro . ,fun)) (let macro t))
                 (and (let fun arg) (let macro nil)))
             arg)

This part binds two vars: `fun` and `macro`.
Basically, it binds `fun` to the value of `arg` except that if `arg` is
a "macro value", `fun` gets the value of the macro's function (and
`macro` gets value t rather than nil).

            ;; `lam' is the lambda expression in `fun' (or nil if not
            ;; recognized).
            ((or `(,(or `quote `function) ,lam) (let lam nil))
             fun)

This only binds `lam`.  It takes the `fun` apart and extracts a lambda
expression from it (or nil if it can't).

            ;; `arglist' is the list of arguments (or t if not recognized).
            ;; `body' is the body of `lam' (or t if not recognized).
            ((or `(lambda ,arglist . ,body)
                 ;; `(closure ,_ ,arglist . ,body)
                 (and `(internal-make-closure ,arglist . ,_) (let body t))
                 (and (let arglist t) (let body t)))
             lam))

This tries to take apart `lam` and extract two parts: `arglist` and `body`.

The complexity here is that `arg` doesn't hold a "macro value"
(i.e. something of the form (macro . FUN)), but instead it holds an
expression that will return a macro value.  So `arg` can be of the form

    (quote (macro . FUN))
    (cons 'macro 'FUN)
    (cons 'macro #'FUN)
    (cons 'macro (internal-make-closure ...))
    ...

and of course FUN is usually of the form (lambda ...) but it can also be
a plain symbol, or a #<subr ...> object or god knows what else.


        Stefan

Re: "Like `let*' but ....."

[Alan Mackenzie]

Hello, Stefan.

On Wed, Jan 25, 2017 at 00:08:01 -0500, Stefan Monnier wrote:

[ .... ]

> BTW, regarding the big pcase-let* in byte-compile-file-form-defalias,
> it was partly an experiment in the use of pcase patterns.

> OT1H I'm not convinced the result speaks very much in favor of pcase,
> OTOH if you try to rewrite this code without pcase it's not
> pretty either.

> I'll read it for you:

>            ;; `macro' is non-nil if it defines a macro.
>            ;; `fun' is the function part of `arg' (defaults to `arg').
>            (((or (and (or `(cons 'macro ,fun) `'(macro . ,fun)) (let macro t))
>                  (and (let fun arg) (let macro nil)))
>              arg)

> This part binds two vars: `fun` and `macro`.
> Basically, it binds `fun` to the value of `arg` except that if `arg` is
> a "macro value", `fun` gets the value of the macro's function (and
> `macro` gets value t rather than nil).

OK, I think I might have got the semantics now.  The `arg' at the end of
that thing is the object upon which the pcase pattern at the beginning
of it acts on.  The `or's and `and's are pcase ones, not the primitives.
The variables which are bound are precisely the cadrs of the three
element lists beginning `(let ...)', none of the variables bound in the
pcase form surviving after that form terminates.  Er, actually that
isn't true, looking at `lam' in the next bit.  Variables bound within
the pcase pattern remain bound over the entire pcase-let* form (unless,
of course, a subsequent binding rebinds the same symbol).

Am I right?

>             ;; `lam' is the lambda expression in `fun' (or nil if not
>             ;; recognized).
>             ((or `(,(or `quote `function) ,lam) (let lam nil))
>              fun)

> This only binds `lam`.  It takes the `fun` apart and extracts a lambda
> expression from it (or nil if it can't).

>             ;; `arglist' is the list of arguments (or t if not recognized).
>             ;; `body' is the body of `lam' (or t if not recognized).
>             ((or `(lambda ,arglist . ,body)
>                  ;; `(closure ,_ ,arglist . ,body)
>                  (and `(internal-make-closure ,arglist . ,_) (let body t))
>                  (and (let arglist t) (let body t)))
>              lam))

> This tries to take apart `lam` and extract two parts: `arglist` and `body`.

> The complexity here is that `arg` doesn't hold a "macro value"
> (i.e. something of the form (macro . FUN)), but instead it holds an
> expression that will return a macro value.  So `arg` can be of the form

>     (quote (macro . FUN))
>     (cons 'macro 'FUN)
>     (cons 'macro #'FUN)
>     (cons 'macro (internal-make-closure ...))
>     ...

> and of course FUN is usually of the form (lambda ...) but it can also be
> a plain symbol, or a #<subr ...> object or god knows what else.


>         Stefan

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: "Like `let*' but ....."

[Alan Mackenzie]

Hello, Clément.

On Tue, Jan 24, 2017 at 16:26:55 -0500, Clément Pit-Claudel wrote:
> On 2017-01-24 16:12, Alan Mackenzie wrote:
> > What is not clear is precisely HOW `pcase' patterns are used for
> > bindings, and what the semantics of (PAT EXP) are.

> Hi Alan,

> I find that mentally translating (pcase-let* ((<x> <y>)) <z>) to
> (pcase <y> (<x> <z>)) helps.  This translation is mostly correct, with
> the added twist that the former is undefined if <y> doesn't match <x>.

> Then everything is as in the pcase documentation. Hopefully this helps!

Yes, it does, I think.  Thanks!

> Cheers,
> Clément.

-- 
Alan Mackenzie (Nuremberg, Germany).