bug#43100: 28.0.50; pcase not binding variables conditionally

[Pip Cet]

Hello Stefan,

On Sun, Aug 30, 2020 at 6:07 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>
> >> IIUC you want
> >>
> >>     (pcase V
> >>       ((or (pred symbolp) name)
> >>        (let ((foo 'bar)) name)))
> >>
> >> to behave like
> >>
> >>     (cond
> >>      ((symbolp V) (let ((foo 'bar)) name))
> >>      (t (let ((name V)) (let ((foo 'bar)) name))))
> >>
> >> ?
> >
> > Yes, that's correct. It's also how (pcase V ((or (pred symbolp) name)
> > name) behaves...
>
> Indeed, but that's an accident.  Ideally it should either signal an
> error at macro-expansion time, or return nil when V is a symbol.

So, as I half-expected, the reaction to "pcase isn't powerful enough"
is "let's make it less powerful" :-)

Seriously, I get the impression you strongly feel pcase shouldn't be
(more) powerful, it should instead make non-explicit but fairly strong
complexity promises.

I disagree: in practice, complexity promises and optimization based on
them are often unnecessary. In fact, there's a Lisp tradition of using
assq and memq rather than building ad-hoc hash tables, even though
that often means run time is theoretically O(n^2) rather than O(n
log(n)).

> Since the current implementation doesn't go to the effort of doing
> either of those, we instead limit ourselves to recommend against using
> such patterns (IOW, "use at your own risks").

> >> I'd rather not go there
> > You'd rather have the behavior of (pcase V ((or pred symbolp) name)
> > EXPR) depend on the complexity of EXPR?
>
> 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.

> A code size explosion due to a particular implementation choice is
> undesirable, but a code size explosion imposed by the semantics is much
> more problematic.

Again, I don't think that's the case here.

> > I think it would be nice to have a lexical three-argument version of
> > pcase which specifies which variables are output values, treating the
> > remaining ones as input values, to make it easier to build
> > non-constant patterns.
>
> 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...

> > IOW, if you want to call a function with arguments determined by
> > pcase-like patterns, why not introduce pcase-call so something like
> > the following would work:
> >
> > (defun f (hello world) (cons hello world))
> >
> > (let ((space " ") (hw "hello world"))
> >   (pcase-call 'f ((concat hello space world) hw)))
>
> How do you intend to implement this?

Proof-of-concept attached; I'm no longer sure I want to be able to say
(concat hello space world) rather than (concat hello (pred (equal
space)) world); it's inconsistent to use `equal' here rather than `eq'
for ordinary symbols (can't we at least use `eql'?), and I'm too
worried about adding an optional argument called `space' and changing
the interpretation of pcase-calls far away.

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, though some
workarounds for lexical binding are required (if nothing else, this is
an interesting exercise in how painful lexical binding can be to work
with).

> > As for duplicating the body, that is an implementation detail. You can
> > easily avoid it by producing
> >
> > (let ((name name))
> >   (cond ((symbolp V) X)
> >     (progn (setq name V) X)))
>
> So it's more like my option of returning nil, except it would return
> the value of a surrounding `name` variable?  That could be done, but I'm
> not convinced it'd be more often useful.

I started out with a fairly explicit practical problem: parsing GCC
machine descriptions, which are (essentially) sexps but have made the
mistake of having "optional" non-final parts, and I think it would be
great to express that in a pcase pattern, both for the obvious reasons
of legibility and for some non-obvious reasons of my own.

> > 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. If we had read-only bindings, pcase would
probably use them, but we don't.

> >> The "intended" behavior instead would be to behave like
> >>
> >>     (cond
> >>      ((symbolp V) (let ((name nil)) (let ((foo 'bar)) name)))
> >>      (t (let ((name V)) (let ((foo 'bar)) name))))
> >>
> >> That's already the behavior you get if you switch the two:
> >>
> >>     (macroexpand '(pcase V
> >>                     ((or (and (pred foo) name) (pred symbolp))
> >>                      (let ((foo 'bar)) name))))
> >>     =>
> >>     (let* ((pcase-0 (lambda (name) (let ((foo 'bar)) name))))
> >>       (cond ((foo V) (funcall pcase-0 V))
> >>             ((symbolp V) (funcall pcase-0 nil))
> >>             (t nil)))
> >
> > I don't see where the nil comes from, or why it's a useful choice for
> > a default value.
>
> It comes from the absence of a binding for `name` and was chosen because
> nil is the standard default value in Elisp.

Sorry, I meant I don't see anything in the pcase input that justifies
our using a nil value.

> It comes from this code in pcase.el:
>
>                     (let ((args (mapcar (lambda (pa)
>                                           (let ((v (assq (car pa) vars)))
>                                             (setq vars (delq v vars))
>                                             (cdr v)))
>                                         prevvars)))
>                       ;; If some of `vars' were not found in `prevvars', 
> that's
>                       ;; OK it just means those vars aren't present in all
>                       ;; branches, so they can be used within the pattern
>                       ;; (e.g. by a `guard/let/pred') but not in the branch.
>                       ;; FIXME: But if some of `prevvars' are not in `vars' we
>                       ;; should remove them from `prevvars'!
>                       `(funcall ,res ,@args)))))))
>
> The computation of `args` searches in `vars` for the bindings expected
> by the branch (stored in `prevvars` the first time we encountered that
> branch).  The assq+cdr will return nil if a var from `prevvars` isn't
> found in `vars`.

Yes, it's the precise code I want to change.

> >> the fact that the behavior depends on the order of elements in `or` is
> >> an undesirable side effect of the implementation technique.
> > It also depends on the complexity of the branch.
> > It seems to me there are at least three consistent ways of behaving
> > (throw an error, bind name to nil, bind name to name), with an
> > inconsistent fourth way being what's currently implemented.
>
> 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?

> >> I don't know of a simple implementation.
> > Here's my better-than-nothing attempt.  I don't think that's complex;
> > if anything, it's too trivial.
>
> So you give it a search-based semantics.

I don't think the semantics are at all unclear, except for the greedy
vs shy question. The implementation could be very different, reasoning
about the length of sequences matched by pcase subpatterns, of course.

> The problem with it for me is that if we turn
>
>     `(,a ,@b)
>
> into
>
>     (append `(,a) b)

List-final ,@ is too special, IMHO, to be turned into an (append)
pattern at all.

> the pcase match will take a lot more time than the equivalent
>
>     `(,a . ,b)
>
> Of course, you can try and handle these "easy" cases more efficiently,
> but then your ,@ will sometimes be very cheap and sometimes very
> expensive (depending on when an optimization can be applied), which
> I think is a misfeature (it's for this same reason that I dislike CL
> keyword arguments for functions).

I think it's an implementation detail. Some reasoning about the
minimum and maximum length of sequences matched by pcase patterns
could help ordinary pcases, too, though:

(pcase '(a b c d)
  (`(,a ,b ,c ,d) (list a b c d)))

could call (pcase--check-length EXPVAL 4 4) rather than calling consp
four times, potentially descending into expensive predicates that are
unnecessary.
It's strange to read quotes that yo
In general, of course, multiple ,@s in the same list will be slow
because it's a difficult problem.

> I think it's fine to have such a search-based `append` (because it's
> "reliably expensive") but I'd rather not automatically use it for ,@

Again, I think that's a fundamental difference between us when it
comes to the philosophy behind pcase. If I understand you correctly,
you deliberately want to limit pcase, moving away from the intuitive
definition of it that I gave above, because there might be a situation
in which people expect better performance than our limited
implementation can give them. Is that correct?

I think that's a weak reason for a strong limitation, but of course
those are subjective questions. For example, I don't expect (pcase 9
((* x x) x)) to work, and the intuitive try-everything oracle would
work for it. In any case, if there is such a fundamental difference of
opinion, pcase simply isn't what I should be looking at.

> [ BTW, you don't need (nor want) `eval` in your definition.  ]

Thank you! Premature "optimization"...

Thanks again!

pcall.el
Description: Text Data