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.

> 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
`. ,`.

>> >> 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.

> Note that people also might expect
>
>     (pcase l (`(,a . ,b) (setq b a)))
>
> to modify l...

They might indeed.  But if so, they'll be disappointed ;-)

>> >> The design of `pcase` assumes you want to optimize away the tests that
>> >> are common to the various patterns.  That can't be done with dynamic
>> >> patterns.
>> > Or it's a bit more difficult, at least...
>> I think it's more than "a bit more difficult", because deciding how to
>> optimize the tests will almost always take significantly more time than
>> just doing the tests.  So in order to do it dynamically and be useful,
>> you still need to have 2 stages, where you optimize at one stage and
>> then use the result several times later (to recoup the cost of the
>> optimization).
> Wait, I think there was a misunderstanding here. I don't mean that the
> pcase pattern should depend structurally on let-bound variables
> appearing in it. That does sound impossible to me (except with dynamic
> scoping).

To me "dynamic patterns" means patterns which are only know at run time
because the pattern itself depends on a runtime value, as in something like:

    (let ((pat (if FOO '(pred symbolp) '1)))
      ...
      (pcase V
        ...
        ((match pat) EXP)
        ...))

Not sure what you meant by it, then.

>> > The difficult part, in fact, is deciding that we want the arglist to
>> > be part of the exposed function API: given an "arglist" function, the
>> > rest of the implementation seems unproblematic,
>> 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`.

>> Lexical scoping fundamentally means that variables don't have names:
>> (lambda (x) x) and (lambda (y) y) should be indistinguishable (that's
>> what α-renaming says, anyway).
> But they're not.

;-)

> I don't see why pcase-call should be in the "funcall" category of
> being unable to distinguish the two, rather than in the "equal"
> category of being able to.

The notion of equality between functions is pretty delicate (and this
fundamental problem was the original motivation for the development of
type classes, BTW).

>> 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.

>> >> > disallowing the modification of name in X.
>> >> That's rather hard to do (and I don't see what would be the benefit here).
>> > I meant adding a cautionary note about it in the documentation, not
>> > actively preventing it.
>> So we're replacing the current "don't do that" with another "don't do
>> that", neither of which is detected by the byte-compiler?
> Yes. Emacs Lisp isn't free of "don't do that"s, and reducing the
> "don't do that" space drastically is better than pointing out the tiny
> fraction of it which remains as evidence that we shouldn't do the
> reduction in the first place.

I don't see your proposal as reducing the "don't do that" space.

>> >> The current implementation amounts to "we should signal an error but we
>> >> don't bother doing so and just warn against it in the manual".
>> >> Patch welcome ;-)
>> > You mean a patch that would make pcase less powerful by making what I
>> > want to do impossible rather than merely difficult?
>> The way I see it, it would make what you want to do possible because
>> what you suggest would merely give meaning to programs previously invalid.
>> In contrast, with the current behavior your proposal implies breaking
>> backward compatibility.
> I think what you mean is you'd rather break backward compatibility in
> two steps rather than one, by first causing errors, then redefining
> the new errors not to happen? Because if so, I totally agree.

That's right.  The first (breaking) step would be "my fault" and would
hence free you to do the second step without introducing
incompatibilities ;-)

> IOW, I'd like ` (as a pcase macro) to behave like ` already does:
> constant-time `(,@l), linear-time `(,@l 3).

I suggest you start with a `pip-backquote` pcase-macro and experiment
with it, to see how useful it is.  You'll then presumably have more
concrete examples to argue for the replacement of the current ` 

> 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).  That seems quite different
from going from O(1) to O(N²).

>> But that presumes a C implementation of `pcase--check-length` since
>> (< (length X) 4) can be a very bad idea when X is a long list.
> Even a Lisp implementation that isn't a wrapper around (length X)
> would avoid unnecessary predicates.

Indeed.  I won't be the one writing the code which tries to guess when
that's more efficient and when it's less efficient.

>> > It's strange to read quotes that yo
>> ...?
> Well, it's strange to read quotes that you only half-deleted from your
> email, Pip! (Sorry).

;-)

> (I think it's interesting that you can't evaluate "proper" pcase at
> run time; at least, I don't see how you'd implement a pcase-dyn
> function that evaluates its second argument etc. before interpreting
> it. It's easy to do with dynamic binding. I think that's because our
> implementation of lexical binding is too limited, but I'm not sure.)

I don't understand what your `pcase-dyn` would be expected to do, so
I don't know how dynamic scoping might coming into the picture.

> The strong limitation is "you can only add new pcase patterns if they
> have predictable complexity (in code size, run time, or memory usage,
> presumably)".

Not at all.  You can define any pcase pattern you like with
`pcase-defmacro`, just like you can define any function or macro you
like with `defun` and `defmacro`.

> By solving polynomial roots? I think it's better to use
> (pcase-defmacro * ...) for a Kleene star macro...which it turns out
> isn't precisely trivial to implement with lexical scoping.

Why would lexical scoping make a difference?


        Stefan