[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#43100: 28.0.50; pcase not binding variables conditionally
From: |
Stefan Monnier |
Subject: |
bug#43100: 28.0.50; pcase not binding variables conditionally |
Date: |
Wed, 02 Sep 2020 10:16:52 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) |
>> 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