bug#43100: 28.0.50; pcase not binding variables conditionally

[Stefan Monnier]

>> >> I just want the complexity to be predictable without having to guess
>> >> which optimization will be applicable.
>> > So it's better to have a predictably-bad `append' rather than a
>> > sometimes-bad one?
>> In my book, yes.
> That's a very unusual book!

I wouldn't know, it's the only one I have.

> This isn't real-time programming or crypto, so I fail to see the
> damage "faster is better" might cause here.

Because the problem goes in the other direction: the programmer gets
used to seeing it work fast on some uses and then assumes it's
always so, and then gets bitten on other uses.
I think a good API should avoid such surprises.

[ This said, I no doubt introduced several APIs which don't obey this rule.
  But then I plead not guilty because of temporary insanity.  ]

>> > But how does that affect ,@? We could make that predictably bad, too!
>> I think the expectation (coming from the use of ,@ in non-patterns)
>> would be that it is fairly cheap, but yes, I guess it's an option.
>> Could be coupled with a warning when ,@ can be replaced by an efficient
>> `. ,`.
> I don't think we should warn about that; we should simply do the best
> we can do, and warn the user when that's surprisingly bad (i.e. when
> we have to iterate over the list building sublists).

It's important to try and make sure that warnings can be silenced by
improving the code.  When the coders really need the slow search, how
would they silence the warning (other than `with-suppressed-warnings`,
obviously)?

In contrast if we warn when the ,@ can be replaced by `, .` then the
warning can always be silenced without having to resort to
`with-suppressed-warnings`.

>> >> >> More specifically, I'd rather not choose a semantics that imposes
>> >> >> duplicating the branch body, since we have no control over its size and
>> >> >> that can hence lead to potential code size explosion.
>> >> > You're right, and it's a good thing that the duplication of the branch
>> >> > body is a fixable implementation detail rather than something imposed
>> >> > by the semantics.
>> >> It's only fixable if you disregard the "more or less" above.
>> >> I find it to be a pretty bad wrinkle in the semantics.
>> > So setq the outer binding if it changed?
>> Oh, yuck!  That'd be adding injury to insult.
> Would work, though!

And would result in hideous semantics in corner cases.

> What I meant was using SYMBOL as short-hand for (pred (equal SYMBOL))
> when it's not in a white-list of symbols to be bound instead of
> compared.  That was the intention of my example.

Ah, sorry, I completely misunderstood ;-)

There's also a case to be made for SYMBOL to be an accepted short form
for `(pred SYMBOL)` in some cases.  I don't think using
whitelists/blacklists to decide how to treat a given SYMBOL pattern will
scale (nor be sufficiently clear for the casual reader), so I think we
should aim for a slightly less concise syntax.  Given the limits of the syntax
accepted by the Elisp reader, we may have to resort to using

    (= EXP)

as shorthand for

    (pred (equal EXP))

or

    =SYMBOL

as shorthand for

    (pred (equal SYMBOL))

AFAIK There is currently no good hook in `pcase.el` to implement the
latter without actually changing `pcase.el`.

> I think dynamic patterns, as you use the term, should be possible

They very much are possible, of course.  E.g.:

    (defun pcase-match-p (PATTERN OBJECT)
      "Return non-nil if OBJECT matches PATTERN."
      (eval `(pcase ',OBJECT (,PATTERN t)) t))

and then use (pred (pcase-match-p EXP))

If you want to extract data from OBJECT, then you'll presumably want to
define a `pcase-match` function which instead of a boolean returns
a list of values (corresponding to the value of the variables that were
bound in the PATTERN) and that will take more work than the above
3 lines, but should still be easy to do.

> but punitively slow

Yup.

>> >> We have `help-function-arglist`, so it's not that hard.
>> >> But it's not guaranteed to work.
>> > Oh, thanks for pointing that out.  It's not very good, though, is it?
>> It's good enough for `C-h o`.
>
> C-h o says
>
> (+ &rest NUMBERS-OR-MARKERS) and (1+ NUMBER)

Indeed and that info comes straight from `help-function-arglist`.

> help-function-arglist says
>
> (&rest rest) and (arg1)

I suggest you start with `C-h o help-function-arglist` ;-)

>> >> I'm sorry, I don't understand what those sexps (and their «optional"
>> >> non-final parts») have to do with pcase's handling of `or` patterns
>> >> where the different branches don't bind the same set of variables.
>> > Well, maybe I'm just missing an obvious way of doing it.
>> Could be, but I have no idea what "it" is.
>
> Matching something like Emacs defuns, which may have a docstring or
> not, I'd like to do
>
> `(defun ,symbol ,@(or `(,(and (pred stringp) docstring))) `())  . ,body)
>
> It seems wasteful to have two almost-identical patterns to match the
> variants, and I'd like docstring to have a useful default value.

Currently `pcase` should give nil as value to `docstring` if the above
`or` matches via the second alternative, so at least the "useful
default" part is already covered ;-)

But yes, currently, you have to write it like

    `(defun ,symbol ,args
      . ,(or `(,(and (pred stringp) docstring)  . ,body)
             body))

or if you want a more explicit default for `docstring`:

    `(defun ,symbol ,args
      . ,(or `(,(and (pred stringp) docstring)  . ,body)
             (and (let docstring "") body)))

In this particular case it's not too terrible, but it gets much worse if
you have to add more optional stuff to it, like `declare` and
`interactive` (the pattern's size is exponential in the number of
optional elements).

Your `append` handles it more elegantly in the source code (and less
efficiently at run-time).  In theory we could get our cake and eat it
too, but that would involve adding something similar to a parsing
algorithm and would likely require a significant amount of work.

>> > And, again, performance of ` is unpredictable unless you know the
>> > details of the optimization. Should we get rid of ` next?
>> AFAIK performance is O(N) where N is the number of cons cells in the
>> output (minus those cons-cells which are preserved as-is, I guess but
>> that doesn't make much of a difference).
> It means (,@l) is O(1), but (,@l 3) is O(N).

Indeed.  It's not as drastic as the O(1) of `. ,` vs O(N²) of `append`,
but point taken.

I think it's time you

    (pcase-defmacro pip-\` ...)

and experiment with it.

> By the way, I'm also quite confused by this comment:
>
> ;; - implement (not PAT).  This might require a significant redesign.
>
> (pcase-defmacro not (pat)
>   `(app (lambda (expval) (not (pcase expval (,pat t))))
>         (pred identity)))
>
> would work, wouldn't it?

[ AKA
    (pcase-defmacro not (pat)
      `(pred (lambda (expval) (not (pcase expval (,pat t))))))
]

Yes, it works but it doesn't give me the efficiency and semantics that
a "true" `not` pattern should give.  If you look at Racket's `match`
(from which I took a lot of inspiration in the Emacs-25 refresh of
pcase), you'll see that their negation pattern is trivial to implement
(it's basically just swapping the "things to do upon success" with the
"things to do upon failure") but gives the right semantics and
efficiency.  E.g. `(not (not PAT))` behaves just like PAT (including
variable bindings and such).


        Stefan