bug#26073: bug in generator function with nested dash anaphoric macros

bug#26073: bug in generator function with nested dash anaphoric macros

[Paul Pogonyshev]

To reproduce:

(iter-do (y (funcall (iter-lambda (x)
                       (--each x
                          (let ((y (--map (- it) it)))
                            (iter-yield y))))
                     '((1 2) ( 3 4))))
  (print y))

This should print (-1 -2) and (-3 -4), but instead results in an error.
If you comment out the `iter-yield' form, the example evaluates---
producing different output, of course, but at least without errors.

This looks related to bug #26068, but is not fixed by the patch in
that bug. It is likely related to that both nested dash forms use
`it' variable, and it looks like the wrong (outer) `it' is passed to (- it).

Paul

bug#26073: Simplified testcase

[Paul Pogonyshev]

This form should evaluate to -2:

(iter-next (funcall (iter-lambda ()
                      (let ((it 1))
                        (iter-yield (funcall (lambda (it) (- it)) (1+ it)))))))

However, it evaluates to -1 instead.

bug#26073: workaround

[Paul Pogonyshev]

[-- Attachment #1: Type: text/plain, Size: 395 bytes --]

Attached patch is a workaround for the bug. It adds special handling
of lambdas to `cl--sm-macroexpand', similar to the way it handles
`let'. However, there is an unhandled case of "binding" symbols to
forms. I'm also not sure what would be correct behavior in old
non-lexical-scope code (do we still care?).

So, this patch cannot really go in as-is, but it can serve as a base
for a real fix.

[-- Attachment #2: 0001-Fix-for-rebinding-in-lambdas-in-generator-functions.patch --]
[-- Type: text/x-patch, Size: 1308 bytes --]

diff --git a/lisp/emacs-lisp/cl-macs.el b/lisp/emacs-lisp/cl-macs.el
index 58bcdd52ac..52d946a0c0 100644
--- a/lisp/emacs-lisp/cl-macs.el
+++ b/lisp/emacs-lisp/cl-macs.el
@@ -2092,6 +2092,21 @@ except that it additionally expands symbol macros."
                                 (car exp))
                              ,(nreverse nbs)
                              ,@body)))))
+            (`(function (lambda . ,(or `(,params . ,body) _dontcare)))
+             (let (found nbs)
+               (dolist (param params)
+                 (let* ((sm (assq param env)))
+                   (push (if (not (cdr sm))
+                             param
+                           (let ((nexp (cadr sm)))
+                             (setq found t)
+                             (unless (symbolp nexp) (error "FIXME"))
+                             nexp))
+                         nbs)))
+               (when found
+                 (setq exp `(function (lambda
+                                        ,(nreverse nbs)
+                                        ,@body))))))
             ;; FIXME: The behavior of CL made sense in a dynamically scoped
             ;; language, but for lexical scoping, Common-Lisp's behavior might
             ;; make more sense (and indeed, CL behaves like Common-Lisp w.r.t

bug#26073: workaround

[Stefan Monnier]

> Attached patch is a workaround for the bug. It adds special handling
> of lambdas to `cl--sm-macroexpand', similar to the way it handles
> `let'. However, there is an unhandled case of "binding" symbols to
> forms. I'm also not sure what would be correct behavior in old
> non-lexical-scope code (do we still care?).

Hmm... I'm wondering why generator.el uses cl-symbol-macrolet like that,
but indeed the precise behavior of cl-symbol-macrolet is currently
a bit fishy.


        Stefan

bug#26073: workaround

[Paul Pogonyshev]

> I'm wondering why generator.el uses cl-symbol-macrolet like that

Because that's how it works. It needs to store variables in an outer
scope so that their values are preserved between calls to `iter-next'
on the same iterator. Therefore it "rebinds" local variables to
different symbol and declares those symbols in outer scope, so that
they become non-local variables captured by resulting closures.

It's not a problem within generator function builder, rather it's a
bug in in `cl-symbol-macrolet' that incorrectly applies `bindings' to
forms with lambdas. The bug is that it rebinds variables even inside
`lambda', not realizing that they (at least in lexical scope) are
shadowed by the lambda's arguments. In comparison, it does handle
shadowing with `let' properly.

Paul

On 20 March 2017 at 01:49, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>> Attached patch is a workaround for the bug. It adds special handling
>> of lambdas to `cl--sm-macroexpand', similar to the way it handles
>> `let'. However, there is an unhandled case of "binding" symbols to
>> forms. I'm also not sure what would be correct behavior in old
>> non-lexical-scope code (do we still care?).
>
> Hmm... I'm wondering why generator.el uses cl-symbol-macrolet like that,
> but indeed the precise behavior of cl-symbol-macrolet is currently
> a bit fishy.
>
>
>         Stefan

bug#26073: workaround

[Paul Pogonyshev]

To see the wrong expansion:

(progn
  (pp (macroexpand-all '(cl-symbol-macrolet ((it xxx))
                          (let ((it 1))
                            (iter-yield (funcall (lambda (it) (- it))
(1+ it)))))))
  nil)

Too see it in the generator function:

(progn
  (pp (macroexpand-all '(cl-symbol-macrolet ((it xxx))
                          (iter-lambda ()
                            (let ((it 1))
                              (iter-yield (funcall (lambda (it) (-
it)) (1+ it))))))))
  nil)

Particularly these lines are wrong in the latter:

>                           #'(lambda
>                               (it)
>                               (- cps-binding-xxx-))

bug#26073: workaround

[Stefan Monnier]

retitle 26073 How should cl-symbol-macrolet interact with rebindings?
thanks

The problem here is indeed different from the one in bug#26068.
bug#26068 was clearly triggering a (known) bug in cl-symbol-macrolet.

Here it's triggering a (known) misfeature.  The source code has the
following comments about it:

             ;; CL's symbol-macrolet treats re-bindings as candidates for
             ;; expansion (turning the let into a letf if needed), contrary to
             ;; Common-Lisp where such re-bindings hide the symbol-macro.
and
            ;; FIXME: The behavior of CL made sense in a dynamically scoped
            ;; language, but for lexical scoping, Common-Lisp's behavior might
            ;; make more sense (and indeed, CL behaves like Common-Lisp w.r.t
            ;; lexical-let), so maybe we should adjust the behavior based on
            ;; the use of lexical-binding.

more concretely cl-symbol-macrolet implements the following semantics:

      (cl-symbol-macrolet ((x <e>))
        ... (let ((x <foo>)) ..x..))
    =>
        ... (cl-letf ((<e> <foo>)) ..<e>..)

whereas Common-Lisp's symbol-macrolet wants the following semantics instead:

    => ... (let ((x <foo>)) ..x..)

As mentioned in the comment, it probably makes sense to change
cl-symbol-macrolet in lexical-binding code to follow Common-Lisp's
semantics (tho we'd want to give access to the old semantics if the user
explicitly uses cl-letf).

Not sure what might break if we do that: the main user of
cl-symbol-macrolet outside of generator.el AFAIK is the with-slots of
eieio, so the question is whether some users of with-slots expect
a subsequent `let` binding to temporarily change the slot's value.
I just checked and it seems that no code in Emacs itself relies on this
behavior, so maybe it's "safe" to change it.


        Stefan

bug#26073: workaround

[Paul Pogonyshev]

[-- Attachment #1: Type: text/plain, Size: 2446 bytes --]

I frankly don't know how it should behave and whether fixing it for
generators would break 'with-slots'. What I can see, however, is that
generator functions with nested lambdas do not work properly. And you
cannot realisctically say "don't use those", because lambdas can be just
introduced by macros without you even thinking about it. And then the
function unexpectedly produces wrong results without any hint of what might
be wrong.

Paul

On 26 September 2017 at 16:38, Stefan Monnier <monnier@iro.umontreal.ca>
wrote:

> retitle 26073 How should cl-symbol-macrolet interact with rebindings?
> thanks
>
> The problem here is indeed different from the one in bug#26068.
> bug#26068 was clearly triggering a (known) bug in cl-symbol-macrolet.
>
> Here it's triggering a (known) misfeature.  The source code has the
> following comments about it:
>
>              ;; CL's symbol-macrolet treats re-bindings as candidates for
>              ;; expansion (turning the let into a letf if needed),
> contrary to
>              ;; Common-Lisp where such re-bindings hide the symbol-macro.
> and
>             ;; FIXME: The behavior of CL made sense in a dynamically scoped
>             ;; language, but for lexical scoping, Common-Lisp's behavior
> might
>             ;; make more sense (and indeed, CL behaves like Common-Lisp
> w.r.t
>             ;; lexical-let), so maybe we should adjust the behavior based
> on
>             ;; the use of lexical-binding.
>
> more concretely cl-symbol-macrolet implements the following semantics:
>
>       (cl-symbol-macrolet ((x <e>))
>         ... (let ((x <foo>)) ..x..))
>     =>
>         ... (cl-letf ((<e> <foo>)) ..<e>..)
>
> whereas Common-Lisp's symbol-macrolet wants the following semantics
> instead:
>
>     => ... (let ((x <foo>)) ..x..)
>
> As mentioned in the comment, it probably makes sense to change
> cl-symbol-macrolet in lexical-binding code to follow Common-Lisp's
> semantics (tho we'd want to give access to the old semantics if the user
> explicitly uses cl-letf).
>
> Not sure what might break if we do that: the main user of
> cl-symbol-macrolet outside of generator.el AFAIK is the with-slots of
> eieio, so the question is whether some users of with-slots expect
> a subsequent `let` binding to temporarily change the slot's value.
> I just checked and it seems that no code in Emacs itself relies on this
> behavior, so maybe it's "safe" to change it.
>
>
>         Stefan
>

[-- Attachment #2: Type: text/html, Size: 3153 bytes --]

bug#26073: workaround

[Stefan Monnier]

> I frankly don't know how it should behave and whether fixing it for
> generators would break 'with-slots'. What I can see, however, is that
> generator functions with nested lambdas do not work properly. And you
> cannot realisctically say "don't use those", because lambdas can be just
> introduced by macros without you even thinking about it. And then the
> function unexpectedly produces wrong results without any hint of what might
> be wrong.

Maybe my previous answer was not phrased properly, but it was just
discussing how it should be fixed, rather than whether it should
be fixed.


        Stefan

bug#26073: workaround

[Philipp Stephani]

[-- Attachment #1: Type: text/plain, Size: 885 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> schrieb am Di., 26. Sep. 2017 um
16:47 Uhr:

>
> Not sure what might break if we do that: the main user of
> cl-symbol-macrolet outside of generator.el AFAIK is the with-slots of
> eieio, so the question is whether some users of with-slots expect
> a subsequent `let` binding to temporarily change the slot's value.
> I just checked and it seems that no code in Emacs itself relies on this
> behavior, so maybe it's "safe" to change it.
>

At least the docstring of `with-slots' and the EIEIO manual both state:
"Both ‘setf’ and ‘setq’ can be used to set the value of the slot." In
particular, it doesn't state that `let' can be used for this purpose. So as
long as `setf' and `setq' continue working, I think it should be OK to
change the behavior (it should still be documented as incompatible Lisp
change though).

[-- Attachment #2: Type: text/html, Size: 1212 bytes --]

bug#26073: workaround

[Stefan Monnier]

> At least the docstring of `with-slots' and the EIEIO manual both state:
> "Both ‘setf’ and ‘setq’ can be used to set the value of the slot." In
> particular, it doesn't state that `let' can be used for this purpose. So as
> long as `setf' and `setq' continue working, I think it should be OK to
> change the behavior (it should still be documented as incompatible Lisp
> change though).

Right, the interaction with `let` is not documented, but some packages
may still rely on it.  What this means is that fixing bug#26073 for
Emacs-26 may require introducing a second cl-symbol-macrolet so as not
to risk breaking packages using the old semantics.

I think for `master` it's OK to just change cl-symbol-macrolet (and risk
breaking other packages).


        Stefan

bug#26073: workaround

[Stefan Monnier]

I just installed a patch into `master` which should hopefully fix this
problem without introducing new ones.


        Stefan

bug#26073: workaround

[Noam Postavsky]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> I just installed a patch into `master` which should hopefully fix this
> problem without introducing new ones.

The examples given still fail on current master.

(require 'generator)
(setq lexical-binding t) ; for easier *scratch* evaluation
(iter-do (y (funcall (iter-lambda (x)
                       (dolist (it x)
                         (let ((y (mapcar (lambda (it) (- it)) it)))
                           (iter-yield y))))
                     '((1 2) ( 3 4))))
  (print y)) ;=> Lisp error: (wrong-type-argument number-or-marker-p (1 2))

(iter-next (funcall (iter-lambda ()
                      (let ((it 1))
                        (iter-yield (funcall (lambda (it) (- it)) (1+ it)))))))  ;=> -1

bug#26073: workaround

[Stefan Monnier]

> The examples given still fail on current master.
>
> (require 'generator)
> (setq lexical-binding t) ; for easier *scratch* evaluation
> (iter-do (y (funcall (iter-lambda (x)
>                        (dolist (it x)
>                          (let ((y (mapcar (lambda (it) (- it)) it)))
>                            (iter-yield y))))
>                      '((1 2) ( 3 4))))
>   (print y)) ;=> Lisp error: (wrong-type-argument number-or-marker-p (1 2))
>
> (iter-next (funcall (iter-lambda ()
>                       (let ((it 1))
>                         (iter-yield (funcall (lambda (it) (- it)) (1+ it)))))))  ;=> -1

Duh, the code failed to handle vars introduced by `lambda' (and
`condition-case').  I installed a patch which fixes the above example
(and hopefully the rest, but given my past track record on this you'd
be foolish to believe it).


        Stefan

bug#26073: workaround

[Noam Postavsky]

tags 26073 fixed
close 26073 27.1
quit

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> Duh, the code failed to handle vars introduced by `lambda' (and
> `condition-case').  I installed a patch which fixes the above example
> (and hopefully the rest, but given my past track record on this you'd
> be foolish to believe it).

Works for me [1: 6b183f85e0].  I've added the latter example as a test
case [2: 82379efaaf].

[1: 6b183f85e0]: 2018-02-08 21:41:21 -0500
  * lisp/emacs-lisp/cl-macs.el (cl--sm-macroexpand): Handle lambda!
  https://git.savannah.gnu.org/cgit/emacs.git/commit/?id=6b183f85e02ae1b8527c1bbfa8c5e2c914d28f7c

[2: 82379efaaf]: 2018-02-14 21:31:06 -0500
  ; Add test for iter-lambda variable shadowing (Bug#26073)
  https://git.savannah.gnu.org/cgit/emacs.git/commit/?id=82379efaaf92e964875c0648b45bcae27b54d213

bug#26073: workaround

[Stefan Monnier]

>> I'm wondering why generator.el uses cl-symbol-macrolet like that
> Because that's how it works. It needs to store variables in an outer
> scope so that their values are preserved between calls to `iter-next'
> on the same iterator. Therefore it "rebinds" local variables to
> different symbol and declares those symbols in outer scope, so that
> they become non-local variables captured by resulting closures.

Could you give me some concrete (but simple) example?

> bug in in `cl-symbol-macrolet' that incorrectly applies `bindings' to
> forms with lambdas.

Yes, I understand this part of the problem (and fixing it should
actually be easier than for `let` since in lexical-binding mode, all
lambda args are lexically scoped, regardless of special-variable-p).
[ Note: I haven't looked at your suggested patch, but I agree with your
  problem&solution description so your patch is probably right.  ]


        Stefan

bug#26073: workaround

[Paul Pogonyshev]

> Could you give me some concrete (but simple) example?

Basically, when you define a generator function

    (iter-defun foo ()
      (let ((x (bar 1)))
        (iter-yield x)
        (iter-yield (+ x (bar 2)))))

the resulting iterator must somehow preserve value of `x' after
the first yield-point.  Therefore, the iterator function will
look something like this (simplified):

    (defun foo-iterator ()
      (let* (outer-scope-x
             to-execute
             (step-1 (lambda ()
                       (setf to-execute step-2)
                       (setf outer-scope-x (bar 1))
                       (throw 'yield outer-scope-x)))
             (step-2 (lambda ()
                       (throw 'yield (+ outer-scope-x (bar 2))))))
        (setf to-execute step-1)
        (build-iterator-object ...)))

Here `outer-scope-x' is the rebinding of `x' needed to somehow
send its value from first step closure to the second.

Iteration

    (let ((iter (foo-iterator)))
      (iter-next iter)
      (iter-next iter))

will then look like (omitting all the internal crap):

    (let ((iter (foo-iterator)))
      (call-to-execute iter)   ; here to-execute = step-1
      (call-to-execute iter))  ; here to-execute = step-2

But remember that the caller of `iter-next' knows nothing about
how iterator internally works and has no idea what it really
does and how it achieves the documented behavior (or doesn't,
when there is a bug).

Paul