GNU bug report logs - #51982
Erroneous handling of local variables in byte-compiled nested lambdas

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 51982 in the body.
You can then email your comments to 51982 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Paul Pogonyshev <pogonyshev <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: Erroneous handling of local variables in byte-compiled nested lambdas
Date: Fri, 19 Nov 2021 21:31:13 +0100

[Message part 1 (text/plain, inline)]

Steps to reproduce:

1) save attached file as `wtf.el';
2) execute from command line:

    $ emacs --batch --eval "(byte-compile-file \"wtf.el\")"
    $ emacs --batch -L . --eval "(require 'wtf)" --eval "(print (funcall
(wtf 1)))"

Results, of the first command (byte-compilation):

    In wtf:
    wtf.el:9:17:Warning: reference to free variable ‘it’

of the second:

    Symbol’s value as variable is void: it

Expected results: byte compilation succeeds without warnings, second
command prints "1".

Note that if you change line "(let ((fn #'(lambda () it)))" to e.g. "(let
((fn #'(lambda () nil)))", everything works as expected.  However, 'fn' _is
not even used_ when function `wtf' is called with non-nil argument, which
further conforms that the observed behavior is a bug.  Another indication:
when the function is not byte-compiled (e.g. delete file `wtf.elc' after
the first command), it produces expected results.

Function, of course, doesn't make any sense.  It is a result of removing
contents of real failure until it is as small as possible.

Paul

[Message part 2 (text/html, inline)]

[wtf.el (text/x-emacs-lisp, attachment)]

Message #8 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Paul Pogonyshev <pogonyshev <at> gmail.com>
Cc: mattiase <at> acm.org, Stefan Monnier <monnier <at> iro.umontreal.ca>,
 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in
 byte-compiled nested lambdas
Date: Sat, 20 Nov 2021 05:44:38 +0100

Hello Paul,

thanks for the report, I can reproduce the issue, there is something
going wrong when compiling.  I guess this is something for Mattias or
Stefan maybe? (CC'd)

#+begin_src emacs-lisp
; -*- lexical-binding: t -*-

(defun wtf (x)
  (let ((it 0))
    #'(lambda ()
        (let ((fn #'(lambda () it)))
          (if x
              (let ((it x))
                it)
            (funcall fn))))))
#+end_src

Byte compile:

>     wtf.el:9:17:Warning: reference to free variable ‘it’

(funcall (wtf 1))

>     Symbol’s value as variable is void: it

while expected result is 1.  Uncompiled code works as expected.

TIA,

Michael.

Message #11 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Sat, 20 Nov 2021 09:45:30 +0100

20 nov. 2021 kl. 05.44 skrev Michael Heerdegen <michael_heerdegen <at> web.de>:

> there is something going wrong when compiling.

Yes, looks like a bug in cconv. Fun! I'll have a look.

Message #14 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#51982: Erroneous handling of local variables in
 byte-compiled nested lambdas
Date: Sat, 20 Nov 2021 11:51:18 +0100

Mattias Engdegård <mattiase <at> acm.org> writes:

> Yes, looks like a bug in cconv. Fun! I'll have a look.

Ok - that's what I guessed.  Thanks for checking.

Michael.

Message #17 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Paul Pogonyshev <pogonyshev <at> gmail.com>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: mattiase <at> acm.org, Stefan Monnier <monnier <at> iro.umontreal.ca>,
 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Sat, 20 Nov 2021 17:54:49 +0100

[Message part 1 (text/plain, inline)]

Just to note: I consider this bug pretty important. The example function
looks artificial, but I got the real failure by combining macros from
different packages (`dash.el' for all the `it' bindings, plus `pcase' and
`iter2' for lambdas, but I'm pretty sure you could get a failure with
nested complicated `pcase' alone, if you want to go "only built-in" route).
So, while it is apparently unlikely, you still can stumble into an
incomprehensible breakdown in any sofisticated function by nesting enough
macros that work otherwise and actually produce code that should work also
in this case. But doesn't, when byte-compiled.

Paul

On Sat, 20 Nov 2021 at 05:44, Michael Heerdegen <michael_heerdegen <at> web.de>
wrote:

> Hello Paul,
>
> thanks for the report, I can reproduce the issue, there is something
> going wrong when compiling.  I guess this is something for Mattias or
> Stefan maybe? (CC'd)
>
> #+begin_src emacs-lisp
> ; -*- lexical-binding: t -*-
>
> (defun wtf (x)
>   (let ((it 0))
>     #'(lambda ()
>         (let ((fn #'(lambda () it)))
>           (if x
>               (let ((it x))
>                 it)
>             (funcall fn))))))
> #+end_src
>
> Byte compile:
>
> >     wtf.el:9:17:Warning: reference to free variable ‘it’
>
> (funcall (wtf 1))
>
> >     Symbol’s value as variable is void: it
>
> while expected result is 1.  Uncompiled code works as expected.
>
> TIA,
>
> Michael.
>

[Message part 2 (text/html, inline)]

Message #20 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Paul Pogonyshev <pogonyshev <at> gmail.com>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Sat, 20 Nov 2021 18:04:04 +0100

20 nov. 2021 kl. 17.54 skrev Paul Pogonyshev <pogonyshev <at> gmail.com>:

> I consider this bug pretty important.

You are not alone! However, it's been there for quite a long time so you cannot count on an eventual fix to be back-ported to Emacs 28, much less older releases. If you value compatibility with old versions, be prepared for work-arounds.

For that matter I know exactly what's wrong and am currently weighing various solutions.

Message #23 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Paul Pogonyshev <pogonyshev <at> gmail.com>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Sat, 20 Nov 2021 18:22:43 +0100

[Message part 1 (text/plain, inline)]

> you cannot count on an eventual fix to be back-ported to Emacs 28

Uh, it's not even released yet. Are the stabilization rules so strict that
even a *fix* cannot go in? Unless it is going to be a rewrite of half the
file...

Paul

On Sat, 20 Nov 2021 at 18:04, Mattias Engdegård <mattiase <at> acm.org> wrote:

> 20 nov. 2021 kl. 17.54 skrev Paul Pogonyshev <pogonyshev <at> gmail.com>:
>
> > I consider this bug pretty important.
>
> You are not alone! However, it's been there for quite a long time so you
> cannot count on an eventual fix to be back-ported to Emacs 28, much less
> older releases. If you value compatibility with old versions, be prepared
> for work-arounds.
>
> For that matter I know exactly what's wrong and am currently weighing
> various solutions.
>
>

[Message part 2 (text/html, inline)]

Message #26 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Paul Pogonyshev <pogonyshev <at> gmail.com>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Sat, 20 Nov 2021 19:34:03 +0100

[Message part 1 (text/plain, inline)]

20 nov. 2021 kl. 18.22 skrev Paul Pogonyshev <pogonyshev <at> gmail.com>:

> > you cannot count on an eventual fix to be back-ported to Emacs 28
> 
> Uh, it's not even released yet. Are the stabilization rules so strict that even a *fix* cannot go in? Unless it is going to be a rewrite of half the file...

Sorry, I'd love to have it in 28 but I don't make the rules.

Meanwhile, here's a lightly tested attempt at a fix. I'm not very satisfied by it because it forces an up-front access of a captured variable; I'd rather sink it to each application of the λ-lifted function.

[cconv-bug51982.diff (application/octet-stream, attachment)]

Message #29 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Paul Pogonyshev <pogonyshev <at> gmail.com>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Sat, 20 Nov 2021 21:53:01 +0100

[Message part 1 (text/plain, inline)]

Thanks for the fix. I'm sure in 2025 it will be released.

On Sat, 20 Nov 2021 at 19:34, Mattias Engdegård <mattiase <at> acm.org> wrote:

> 20 nov. 2021 kl. 18.22 skrev Paul Pogonyshev <pogonyshev <at> gmail.com>:
>
> > > you cannot count on an eventual fix to be back-ported to Emacs 28
> >
> > Uh, it's not even released yet. Are the stabilization rules so strict
> that even a *fix* cannot go in? Unless it is going to be a rewrite of half
> the file...
>
> Sorry, I'd love to have it in 28 but I don't make the rules.
>
> Meanwhile, here's a lightly tested attempt at a fix. I'm not very
> satisfied by it because it forces an up-front access of a captured
> variable; I'd rather sink it to each application of the λ-lifted function.
>
>

[Message part 2 (text/html, inline)]

Message #32 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Paul Pogonyshev <pogonyshev <at> gmail.com>
Cc: Mattias Engdegård <mattiase <at> acm.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in
 byte-compiled nested lambdas
Date: Sun, 21 Nov 2021 08:59:34 +0100

Paul Pogonyshev <pogonyshev <at> gmail.com> writes:

> > you cannot count on an eventual fix to be back-ported to Emacs 28
>
> Uh, it's not even released yet. Are the stabilization rules so strict
> that even a *fix* cannot go in?

Yes - only fixes of regressions introduced by the same release are
allowed at the moment.

I totally understand your anger, but such rules are useful.  If
arbitrary fixes would be allowed at any point of the development cycle
the result would be worse than what we have now.  It's also a quite
common policy.  Yes, it sucks, but it is necessary nonetheless.

Michael.

Message #35 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Sun, 21 Nov 2021 10:59:15 +0100

21 nov. 2021 kl. 08.59 skrev Michael Heerdegen <michael_heerdegen <at> web.de>:

> If arbitrary fixes would be allowed at any point of the development cycle
> the result would be worse than what we have now.  It's also a quite
> common policy.

Yes, but it does cause some inconvenience in a project with Emacs's geological release pace. It is difficult to defend an inability to rapidly release an updated version when a serious bug has been found.

Now, regarding the actual bug. Consider the function

1 (defun f (x)
2   (lambda ()
3     (let ((g (lambda () x)))
4       (let ((x 'a))
5         (list x (funcall g))))))

First of all, the variable x is free in the function starting in line 2, so that function is converted to a closure capturing that variable explicitly.

Next, the function bound to g will be lambda-lifted; ie, converted to (lambda (x) x) which means that the call to g in line 5 must be amended to include the value of x. However, we can't just change (funcall g) to (funcall g x) because x is shadowed by the binding in 4, so a new variable is introduced for this purpose.

The result after cconv is essentially (without the fix):

1 (defun f (x)
2   (internal-make-closure nil (x) nil
3     (let ((g (lambda (x) x)))
4       (let ((x 'a)
5             (closed-x x))
6         (list x (funcall g closed-x))))))

But x is not the right expression for closed-x, because it is a captured variable. The patch fixes this:

1 (defun f (x)
2   (internal-make-closure nil (x) nil
3     (let ((g (lambda (x) x)))
4       (let ((x 'a)
5             (closed-x (internal-get-closed-var 0)))
6         (list x (funcall g closed-x))))))

As I mentioned previously, it would be probably be better to elide closed-x entirely and produce

1 (defun f (x)
2   (internal-make-closure nil (x) nil
3     (let ((g (lambda (x) x)))
4       (let ((x 'a))
5         (list x (funcall g (internal-get-closed-var 0)))))))

In other words, the bug occurs when a variable is captured, lambda-lifted, and shadowed.
I need to take another good look at the code to make sure the change is correct (more eyes on it would be appreciated).

Message #38 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#51982: Erroneous handling of local variables in
 byte-compiled nested lambdas
Date: Mon, 22 Nov 2021 11:29:08 +0100

Mattias Engdegård <mattiase <at> acm.org> writes:

> I need to take another good look at the code to make sure the change
> is correct (more eyes on it would be appreciated).

Would it help if I rebuild Emacs including the patch to look if
everything is fine?

[BTW, how can I tell git-am to not barf about an overlong commit message
and just use the patch?]

Thanks,

Michael.

Message #41 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Mon, 22 Nov 2021 14:56:27 +0100

22 nov. 2021 kl. 11.29 skrev Michael Heerdegen <michael_heerdegen <at> web.de>:

> Would it help if I rebuild Emacs including the patch to look if
> everything is fine?

Thank you, but you might just as well save that effort for later because I just found a case where it doesn't work. A repaired patch will arrive soon (we hope). Sorry!

> [BTW, how can I tell git-am to not barf about an overlong commit message
> and just use the patch?]

The current technological level of mankind is not yet advanced enough for such hyper-problems. Our best brains have struggled with it for decades to no avail.

Message #44 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Mon, 22 Nov 2021 18:35:18 +0100

[Message part 1 (text/plain, inline)]

> I just found a case where it doesn't work. A repaired patch will arrive soon (we hope).

Not one but two patches for your enjoyment, representing two alternative solutions. Patch A is an extension of the original proposal and is simpler but perhaps less performant; patch B is messier but may result in better code.

To connect to the previous example, cconv transforms the function

(defun f (x)
  (lambda ()
    (let ((f (lambda () x)))
      (let ((x 'a))
        (list x (funcall f))))))

with patch A into

(defun f (x)
  (internal-make-closure
   nil (x) nil
   (let ((f (lambda (x) x)))
     (let ((x 'a)
           (closed-x (internal-get-closed-var 0)))
       (list x (funcall f closed-x))))))

and with patch B into

(defun f (x)
  (internal-make-closure
   nil (x) nil
   (let ((f (lambda (x) x)))
     (let ((x 'a))
       (list x (funcall f (internal-get-closed-var 0)))))))

This looks like a wash but the optimiser isn't able to elide that superfluous closed-x variable yet, and in Paul's original example the captured variable is only used in one conditional branch which makes it a loss to bind it up-front whereas it's very cheap to materialise at the call site (a single constant-pushing byte op).

On the other hand, patch B does abuse the cconv data structures a little (but it works!). We'll see if Stefan can stomach it.

(This reminds me: we should probably declare internal-get-closed-var as pure and error-free, even though it's not even an actual function.)

[bug51982-A.patch (application/octet-stream, attachment)]

[bug51982-B.patch (application/octet-stream, attachment)]

Message #49 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in
 byte-compiled nested lambdas
Date: Tue, 30 Nov 2021 09:12:20 -0500

Sorry 'bout the delay, and thanks Mattias for finding the bug and the fix.

> @@ -428,10 +428,26 @@ cconv-convert
>                   ;; One of the lambda-lifted vars is shadowed, so add
>                   ;; a reference to the outside binding and arrange to use
>                   ;; that reference.
> -                 (let ((closedsym (make-symbol (format "closed-%s" var))))
> -                   (setq new-env (cconv--remap-llv new-env var closedsym))
> -                   (setq new-extend (cons closedsym (remq var new-extend)))
> -                   (push `(,closedsym ,var) binders-new)))
> +                 (let* ((mapping (cdr (assq var env)))
> +                        (var-def
> +                         (pcase-exhaustive mapping
> +                           (`(internal-get-closed-var . ,_)
> +                            ;; The variable is captured.
> +                            mapping)
> +                           (`(car-safe (internal-get-closed-var . ,_))
> +                            ;; The variable is mutably captured; skip
> +                            ;; the indirection step because the variable is
> +                            ;; passed "by rerefence" to the λ-lifted function.
> +                            (cadr mapping))
> +                           ((or '() `(car-safe ,(pred symbolp)))
> +                            ;; The variable is not captured.  Add a
> +                            ;; reference to the outside binding and arrange
> +                            ;; to use that reference.
> +                            var))))
> +                   (let ((closedsym (make-symbol (format "closed-%s" var))))
> +                     (setq new-env (cconv--remap-llv new-env var closedsym))
> +                     (setq new-extend (cons closedsym (remq var new-extend)))
> +                     (push `(,closedsym ,var-def) binders-new))))
>  
>                 ;; We push the element after redefined free variables are
>                 ;; processed.  This is important to avoid the bug when free
> @@ -449,14 +465,28 @@ cconv-convert
>           ;; before we know that the var will be in `new-extend' (bug#24171).
>           (dolist (binder binders-new)
>             (when (memq (car-safe binder) new-extend)
> -             ;; One of the lambda-lifted vars is shadowed, so add
> -             ;; a reference to the outside binding and arrange to use
> -             ;; that reference.
> +             ;; One of the lambda-lifted vars is shadowed.
>               (let* ((var (car-safe binder))
> -                    (closedsym (make-symbol (format "closed-%s" var))))
> -               (setq new-env (cconv--remap-llv new-env var closedsym))
> -               (setq new-extend (cons closedsym (remq var new-extend)))
> -               (push `(,closedsym ,var) binders-new)))))
> +                    (mapping (cdr (assq var env)))
> +                    (var-def
> +                     (pcase-exhaustive mapping
> +                       (`(internal-get-closed-var . ,_)
> +                        ;; The variable is captured.
> +                        mapping)
> +                       (`(car-safe (internal-get-closed-var . ,_))
> +                        ;; The variable is mutably captured; skip
> +                        ;; the indirection step because the variable is
> +                        ;; passed "by rerefence" to the λ-lifted function.
> +                        (cadr mapping))
> +                       ((or '() `(car-safe ,(pred symbolp)))
> +                        ;; The variable is not captured.  Add a
> +                        ;; reference to the outside binding and
> +                        ;; arrange to use that reference.
> +                        var))))
> +               (let ((closedsym (make-symbol (format "closed-%s" var))))
> +                 (setq new-env (cconv--remap-llv new-env var closedsym))
> +                 (setq new-extend (cons closedsym (remq var new-extend)))
> +                 (push `(,closedsym ,var-def) binders-new))))))

Can we avoid this duplication by moving that code to a separate function?

> +    (let ((f (lambda (x)
> +               (let ((g (lambda () x))
> +                     (h (lambda () (setq x x))))
> +                 (let ((x 'b))
> +                   (list x (funcall g) (funcall h)))))))
> +      (funcall (funcall f 'b)))
> +    (let ((f (lambda (x)
> +               (let ((g (lambda () x))
> +                     (h (lambda () (setq x x))))
> +                 (let* ((x 'b))
> +                   (list x (funcall g) (funcall h)))))))
> +      (funcall (funcall f 'b)))

These two tests are identical aren't they?  Also, can we change the
(setq x x) into something like (setq x (list x x)) and avoid using the
same `b` value for both `x` vars, so as to catch more potential errors?

> @@ -428,10 +428,27 @@ cconv-convert
>                   ;; One of the lambda-lifted vars is shadowed, so add
>                   ;; a reference to the outside binding and arrange to use
>                   ;; that reference.
> -                 (let ((closedsym (make-symbol (format "closed-%s" var))))
> -                   (setq new-env (cconv--remap-llv new-env var closedsym))
> -                   (setq new-extend (cons closedsym (remq var new-extend)))
> -                   (push `(,closedsym ,var) binders-new)))
> +                 (let* ((mapping (cdr (assq var env)))
> +                        (remap-to
> +                         (pcase-exhaustive mapping
> +                           (`(internal-get-closed-var . ,_)
> +                            ;; The variable is captured; remap.
> +                            mapping)
> +                           (`(car-safe (internal-get-closed-var . ,_))
> +                            ;; The variable is mutably captured; remap, but skip
> +                            ;; the indirection step because the variable is
> +                            ;; passed "by rerefence" to the λ-lifted function.
> +                            (cadr mapping))
> +                           ((or '() `(car-safe ,(pred symbolp)))
> +                            ;; The variable is not captured.  Add a
> +                            ;; reference to the outside binding and arrange
> +                            ;; to use that reference.
> +                            (let ((closedsym
> +                                   (make-symbol (format "closed-%s" var))))
> +                              (push `(,closedsym ,var) binders-new)
> +                              closedsym)))))
> +                   (setq new-env (cconv--remap-llv new-env var remap-to))
> +                   (setq new-extend (cons remap-to (remq var new-extend)))))
>  
>                 ;; We push the element after redefined free variables are
>                 ;; processed.  This is important to avoid the bug when free

Looks good (better than patch A).

You say "On the other hand, patch B does abuse the cconv data structures
a little (but it works!)" so the code should say something about
this abuse.  A least I failed to see where the abuse lies.

> @@ -449,14 +466,29 @@ cconv-convert
>           ;; before we know that the var will be in `new-extend' (bug#24171).
>           (dolist (binder binders-new)
>             (when (memq (car-safe binder) new-extend)
> -             ;; One of the lambda-lifted vars is shadowed, so add
> -             ;; a reference to the outside binding and arrange to use
> -             ;; that reference.
> +             ;; One of the lambda-lifted vars is shadowed.
>               (let* ((var (car-safe binder))
> -                    (closedsym (make-symbol (format "closed-%s" var))))
> -               (setq new-env (cconv--remap-llv new-env var closedsym))
> -               (setq new-extend (cons closedsym (remq var new-extend)))
> -               (push `(,closedsym ,var) binders-new)))))
> +                    (mapping (cdr (assq var env)))
> +                    (remap-to
> +                     (pcase-exhaustive mapping
> +                       (`(internal-get-closed-var . ,_)
> +                        ;; The variable is captured; remap.
> +                        mapping)
> +                       (`(car-safe (internal-get-closed-var . ,_))
> +                        ;; The variable is mutably captured; remap, but skip
> +                        ;; the indirection step because the variable is
> +                        ;; passed "by rerefence" to the λ-lifted function.
> +                        (cadr mapping))
> +                       ((or '() `(car-safe ,(pred symbolp)))
> +                        ;; The variable is not captured.  Add a
> +                        ;; reference to the outside binding and arrange
> +                        ;; to use that reference.
> +                        (let ((closedsym
> +                               (make-symbol (format "closed-%s" var))))
> +                          (push `(,closedsym ,var) binders-new)
> +                          closedsym)))))
> +               (setq new-env (cconv--remap-llv new-env var remap-to))
> +               (setq new-extend (cons remap-to (remq var new-extend)))))))

Same comment as before about the code duplication.


        Stefan

Message #52 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Tue, 30 Nov 2021 18:01:59 +0100

[Message part 1 (text/plain, inline)]

30 nov. 2021 kl. 15.12 skrev Stefan Monnier <monnier <at> iro.umontreal.ca>:

> Can we avoid this duplication by moving that code to a separate function?

I extracted a big part of the code into a common function but left the free variable access and mutation outside. (Really want to get rid of `let*`!)

> These two tests are identical aren't they?

No, they exercise different code paths (let and let*).

>  Also, can we change the
> (setq x x) into something like (setq x (list x x)) and avoid using the
> same `b` value for both `x` vars, so as to catch more potential errors?

Yes, thank you, it was an editing mistake. Fixed.

> Looks good (better than patch A).

And here I was prepared to apply patch A since it's slightly more conservative and it seems to be a rare problem anyway.
I've now split the patches in a more sensible (and easily reviewed) way: the first corresponds to patch A, and the second is the diff to B. Take a second look before making up your mind.

> You say "On the other hand, patch B does abuse the cconv data structures
> a little (but it works!)" so the code should say something about
> this abuse.  A least I failed to see where the abuse lies.

There are comments and doc strings such as

  EXTEND is a list of variables which might need to be accessed even from places
  where they are shadowed, because some part of ENV causes them to be used at
  places where they originally did not directly appear.

but with the B patch we put things into `extend` that are not strictly variables but (international-get-closed-var N).
Similarly, `env` has entries like (VAR . (apply-partially F ARG1 ARG2 ..)) where the ARGi are always treated as variables but now they can be access forms as well.

I suppose it doesn't matter much. There is an assertion at the very top of `cconv-convert` which compares the elements by `eq` but it seems to work all right...

Thanks for the review – new patches attached.

[0001-Fix-closure-conversion-of-shadowed-captured-lambda-l.patch (application/octet-stream, attachment)]

[0002-Improved-closure-conversion-of-shadowed-captured-lam.patch (application/octet-stream, attachment)]

Message #55 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in
 byte-compiled nested lambdas
Date: Tue, 30 Nov 2021 17:41:51 -0500

> (Really want to get rid of `let*`!)

FWIW, we could get rid of it in `cconv-convert`.
That would have less impact than doing it in macroexpansion.

[ We could also force dynamically-scoped code to go through (a neutered
  version of) cconv.el , so that bytecomp.el and byte-opt.el can presume
  that `let*` doesn't exist any more.  ]

Tho maybe we'd want to eliminate `let` instead.  ;-)

BTW, have you checked the impact on byte-code quality?

>> These two tests are identical aren't they?
> No, they exercise different code paths (let and let*).

Then that deserves a comment ;-)

>> Looks good (better than patch A).
>
> And here I was prepared to apply patch A since it's slightly more
> conservative and it seems to be a rare problem anyway.
> I've now split the patches in a more sensible (and easily reviewed) way: the
> first corresponds to patch A, and the second is the diff to B. Take a second
> look before making up your mind.
>
>> You say "On the other hand, patch B does abuse the cconv data structures
>> a little (but it works!)" so the code should say something about
>> this abuse.  A least I failed to see where the abuse lies.
>
> There are comments and doc strings such as
>
>   EXTEND is a list of variables which might need to be accessed even
>   from places where they are shadowed, because some part of ENV causes
>   them to be used at places where they originally did not
>   directly appear.
>
> but with the B patch we put things into `extend` that are not strictly
> variables but (international-get-closed-var N).

See below, I think we don't need to put them there.

> Similarly, `env` has entries like (VAR . (apply-partially F ARG1 ARG2 ..))
> where the ARGi are always treated as variables but now they can be access
> forms as well.

I don't think the current code assumes that ARGs are vars here.
You're probably right that it used to be the case and it's not any more,
but that shouldn't cause problems.  The risk I can see is if one of
those ARGs is an expression which refers to a var which gets shadowed,
in which case `cconv--remap-llv` won't rewrite it the way it should.
But I think with your code ARG will either be a simple var or something
of the form (internal-get-closed-var N) so we should be safe.

> @@ -304,6 +304,22 @@ cconv--convert-funcbody
>              `(,@(nreverse special-forms) ,@(macroexp-unprogn body))))
>        funcbody)))
>  
> +(defun cconv--lifted-arg (var env)
> +  "The argument to use for VAR in λ-lifted calls according to ENV."
> +  (let ((mapping (cdr (assq var env))))
> +    (pcase-exhaustive mapping
> +      (`(internal-get-closed-var . ,_)
> +       ;; The variable is captured.
> +       mapping)
> +      (`(car-safe (internal-get-closed-var . ,_))
> +       ;; The variable is mutably captured; skip
> +       ;; the indirection step because the variable is
> +       ;; passed "by reference" to the λ-lifted function.
> +       (cadr mapping))
> +      ((or '() `(car-safe ,(pred symbolp)))
> +       ;; The variable is not captured; use the (shadowed) variable value.
> +       var))))

The docstring or comment at the beginning should mention this function
is specifically for shadowed vars.

Also, If mapping is of the form (car-safe SYMBOL) is `var` really the
correct answer?  Shouldn't it still be (cadr mapping)?

>  (defun cconv-convert (form env extend)
>    ;; This function actually rewrites the tree.
>    "Return FORM with all its lambdas changed so they are closed.
> @@ -428,10 +444,11 @@ cconv-convert
>                   ;; One of the lambda-lifted vars is shadowed, so add
>                   ;; a reference to the outside binding and arrange to use
>                   ;; that reference.
> -                 (let ((closedsym (make-symbol (format "closed-%s" var))))
> +                 (let ((var-def (cconv--lifted-arg var env))
> +                       (closedsym (make-symbol (format "closed-%s" var))))
>                     (setq new-env (cconv--remap-llv new-env var closedsym))
>                     (setq new-extend (cons closedsym (remq var new-extend)))
> -                   (push `(,closedsym ,var) binders-new)))
> +                   (push `(,closedsym ,var-def) binders-new)))

Looks good.
Side note: I don't understand why we `(cons closedsym`, since that
`closedsym` can never appear in another binding (since it's fresh).

[ Version B: ]

> @@ -441,14 +442,16 @@ cconv-convert
>                         (cconv-convert value env extend)))))
>  
>                 (when (and (eq letsym 'let*) (memq var new-extend))
> -                 ;; One of the lambda-lifted vars is shadowed, so add
> -                 ;; a reference to the outside binding and arrange to use
> -                 ;; that reference.
> -                 (let ((var-def (cconv--lifted-arg var env))
> -                       (closedsym (make-symbol (format "closed-%s" var))))
> -                   (setq new-env (cconv--remap-llv new-env var closedsym))
> -                   (setq new-extend (cons closedsym (remq var new-extend)))
> -                   (push `(,closedsym ,var-def) binders-new)))
> +                 ;; One of the lambda-lifted vars is shadowed; if
> +                 ;; necessary, add a reference to the outside binding
> +                 ;; and arrange to use that reference.
> +                 (let* ((lifted-arg (cconv--lifted-arg var env)))
> +                   ;; This means that we may add accessors to ENV and EXTEND
> +                   ;; passing them off as variables, but it's close enough.
> +                   (setq new-env (cconv--remap-llv new-env var lifted-arg))
> +                   (setq new-extend (cons lifted-arg (remq var new-extend)))
> +                   (when (symbolp lifted-arg)
> +                     (push `(,lifted-arg ,var) binders-new))))

Just like I think the `(cons closedsym` is useless in the current (and
in patch A), I think this `(cons lifted-arg` is not needed.

I don't much like this `symbolp` test (which fundamentally seems to
be trying to recover the information about which branch of the `pcase`
we're coming from in `cconv--lifted-arg`).  It at least deserves
a comment explaining why it's doing the right thing.
If we can remove this `symbolp` test recovering info about provenance of
the result of `cconv--lifted-arg` then I think option B is better, but
I prefer otherwise option A.


        Stefan

Message #58 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Wed, 1 Dec 2021 17:04:44 +0100

30 nov. 2021 kl. 23.41 skrev Stefan Monnier <monnier <at> iro.umontreal.ca>:

> [ We could also force dynamically-scoped code to go through (a neutered
>  version of) cconv.el , so that bytecomp.el and byte-opt.el can presume
>  that `let*` doesn't exist any more.  ]

Yes, a dynbind frontend would be handy for other reasons (some syntactic normalisation in case we can't do in macroexpand-all). 

> BTW, have you checked the impact on byte-code quality?

With respect to these patches? Yes: the B patch gives slightly better code because materialising the accessor (internal-get-closed-var N) is as cheap or cheaper than even a stack variable access. But the difference is small and since the case is rare it's probably insignificant.

In fact, there is probably a way of making them produce identical code by constant-propagating such forms in the optimiser. Who knows, might give unexpected improvements to existing code as well. Time for an experiment!

>>> These two tests are identical aren't they?
>> No, they exercise different code paths (let and let*).
> 
> Then that deserves a comment ;-)

Will do.

>>> Looks good (better than patch A).
>> 
>> And here I was prepared to apply patch A since it's slightly more
>> conservative and it seems to be a rare problem anyway.
>> I've now split the patches in a more sensible (and easily reviewed) way: the
>> first corresponds to patch A, and the second is the diff to B. Take a second
>> look before making up your mind.
>> 
>>> You say "On the other hand, patch B does abuse the cconv data structures
>>> a little (but it works!)" so the code should say something about
>>> this abuse.  A least I failed to see where the abuse lies.
>> 
>> There are comments and doc strings such as
>> 
>>  EXTEND is a list of variables which might need to be accessed even
>>  from places where they are shadowed, because some part of ENV causes
>>  them to be used at places where they originally did not
>>  directly appear.
>> 
>> but with the B patch we put things into `extend` that are not strictly
>> variables but (international-get-closed-var N).
> 
> See below, I think we don't need to put them there.
> 
>> Similarly, `env` has entries like (VAR . (apply-partially F ARG1 ARG2 ..))
>> where the ARGi are always treated as variables but now they can be access
>> forms as well.
> 
> I don't think the current code assumes that ARGs are vars here.
> You're probably right that it used to be the case and it's not any more,
> but that shouldn't cause problems.  The risk I can see is if one of
> those ARGs is an expression which refers to a var which gets shadowed,
> in which case `cconv--remap-llv` won't rewrite it the way it should.
> But I think with your code ARG will either be a simple var or something
> of the form (internal-get-closed-var N) so we should be safe.
> 
>> @@ -304,6 +304,22 @@ cconv--convert-funcbody
>>             `(,@(nreverse special-forms) ,@(macroexp-unprogn body))))
>>       funcbody)))
>> 
>> +(defun cconv--lifted-arg (var env)
>> +  "The argument to use for VAR in λ-lifted calls according to ENV."
>> +  (let ((mapping (cdr (assq var env))))
>> +    (pcase-exhaustive mapping
>> +      (`(internal-get-closed-var . ,_)
>> +       ;; The variable is captured.
>> +       mapping)
>> +      (`(car-safe (internal-get-closed-var . ,_))
>> +       ;; The variable is mutably captured; skip
>> +       ;; the indirection step because the variable is
>> +       ;; passed "by reference" to the λ-lifted function.
>> +       (cadr mapping))
>> +      ((or '() `(car-safe ,(pred symbolp)))
>> +       ;; The variable is not captured; use the (shadowed) variable value.
>> +       var))))
> 
> The docstring or comment at the beginning should mention this function
> is specifically for shadowed vars.

Right.

> Also, If mapping is of the form (car-safe SYMBOL) is `var` really the
> correct answer?  Shouldn't it still be (cadr mapping)?

Can there ever be a difference? I don't think so, but prove me wrong!
(If you manage to do that, you will have found a second bug in the original code.)

For context, this is the case when we have a variable mutated by a lambda lifted inner function (that doesn't escape). The variable will be wrapped in a cons but retain its name. Example:

(lambda (x)
  (let ((f (lambda () (setq x (1+ x)))))
    (let ((x 3))
      (list x (funcall f)))))
->
(lambda (x)
  (let ((x (list x))) 
    (let ((f (lambda (x) (setcar x (1+ (car-safe x))))))
      (let ((x 3)
            (closed-x x))
        (list x (funcall f closed-x))))))

> Side note: I don't understand why we `(cons closedsym`, since that
> `closedsym` can never appear in another binding (since it's fresh).

Maybe it's to satisfy the invariant checked by the assertion at the top?

> I don't much like this `symbolp` test (which fundamentally seems to
> be trying to recover the information about which branch of the `pcase`
> we're coming from in `cconv--lifted-arg`).

That's precisely what it is trying to do and no, I don't like it much either.

I suppose cconv--lifted-arg could be made a location function; we could then access and mutate local variables. Something poetically self-referential about that, but I'm not overly fond of the closure creation overhead (better than what it once was but still too high).

>  It at least deserves
> a comment explaining why it's doing the right thing.

> If we can remove this `symbolp` test recovering info about provenance of
> the result of `cconv--lifted-arg` then I think option B is better, but
> I prefer otherwise option A.

I don't see any alternative that is obviously better so I'm applying patch A. We can still go with B later on if we want; the changes are minor.

Good comments, thank you very much!

Message #61 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in
 byte-compiled nested lambdas
Date: Wed, 01 Dec 2021 13:34:01 -0500

>> BTW, have you checked the impact on byte-code quality?
> With respect to these patches?

No I meant w.r.t removing `let*` (or `let` as the case may be).

> Yes: the B patch gives slightly better code because materialising the
> accessor (internal-get-closed-var N) is as cheap or cheaper than even
> a stack variable access. But the difference is small and since the
> case is rare it's probably insignificant.

I'm not worried at all about the performance of this corner-case.

>> Also, If mapping is of the form (car-safe SYMBOL) is `var` really the
>> correct answer?  Shouldn't it still be (cadr mapping)?
> Can there ever be a difference?

There's a big philosophical difference, yes.

>> Side note: I don't understand why we `(cons closedsym`, since that
>> `closedsym` can never appear in another binding (since it's fresh).
> Maybe it's to satisfy the invariant checked by the assertion at the top?

I don't think so because this one just checks that the
`cconv--remap-llv` was called where needed and did its job.

... [ goes and removes that `(cons closedsym` ] ...
... [ `make` ] ...

Oh, you're right!

>> I don't much like this `symbolp` test (which fundamentally seems to
>> be trying to recover the information about which branch of the `pcase`
>> we're coming from in `cconv--lifted-arg`).
> That's precisely what it is trying to do and no, I don't like it much either.

I think another way to do the patch B would be to replace `var` with
`lifted` right when we construct the (apply-partially ...) thingy
(i.e. in the :lambda-candidate part of the function), so those vars that
get remapped to `internal-get-closed-var` wouldn't even make their way
to `extend`.

> I don't see any alternative that is obviously better so I'm applying patch
> A. We can still go with B later on if we want; the changes are minor.

Good.

> Good comments, thank you very much!

[ I resent this implicit suggestion that I could ever write something less
  than a good comment.  ]


        Stefan

Message #64 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Wed, 1 Dec 2021 23:32:49 +0100

1 dec. 2021 kl. 19.34 skrev Stefan Monnier <monnier <at> iro.umontreal.ca>:

>>> BTW, have you checked the impact on byte-code quality?
>> With respect to these patches?
> 
> No I meant w.r.t removing `let*` (or `let` as the case may be).

Yes, and I can confirm that both transformations (let* -> let and the inverse) seem to generate almost or exactly identical bytecode for lexbind code. If you can find an example where it's worse, I'd like to know.

>>> Also, If mapping is of the form (car-safe SYMBOL) is `var` really the
>>> correct answer?  Shouldn't it still be (cadr mapping)?
>> Can there ever be a difference?
> 
> There's a big philosophical difference, yes.

We could declare it an invariant and add an assertion.

> I think another way to do the patch B would be to replace `var` with
> `lifted` right when we construct the (apply-partially ...) thingy
> (i.e. in the :lambda-candidate part of the function), so those vars that
> get remapped to `internal-get-closed-var` wouldn't even make their way
> to `extend`.

Yes, that would probably be even cleaner. Then we wouldn't need to worry about shadowing for those.
I'm not going to do more experimenting with it now but do try it if it makes the code better.

By the way, I did try constant-propagating `(internal-get-closed-var N)` but got less yield than I hoped for. I'll look closer, maybe I made a silly mistake.

>> Good comments, thank you very much!
> 
> [ I resent this implicit suggestion that I could ever write something less
>  than a good comment.  ]

That wasn't for your consumption but to inform the unwashed masses who can't tell the difference!

Message #67 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Paul Pogonyshev <pogonyshev <at> gmail.com>, 51982 <at> debbugs.gnu.org
Subject: Re: bug#51982: Erroneous handling of local variables in byte-compiled
 nested lambdas
Date: Thu, 2 Dec 2021 10:13:31 +0100

> Yes, and I can confirm that both transformations (let* -> let and the inverse) seem to generate almost or exactly identical bytecode for lexbind code. If you can find an example where it's worse, I'd like to know.

And by "yes" I mean "no", since the identical bytecode is only true in the absence of mutation which, as always, throws a spanner in the works. For example, while

(let ((x (sin y)) (y (cos x)))
  (+ x y))))
->
(let* ((x0 (sin y)) (y (cos x)) (x x0))
  (+ x y))))

is a transformation with identical bytecode, mutating one of the variables:

(let ((x (sin y)) (y (cos x)))
  (setq x (1+ x))
  (+ x y))))
->
(let* ((x0 (sin y)) (y (cos x)) (x x0))
  (setq x (1+ x))
  (+ x y))))

will prevent the intermediate from being eliminated. Not a disaster by any means but not good enough as a general method of translation.

Message #70 received at 51982 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Michael Heerdegen <michael_heerdegen <at> web.de>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 51982 <at> debbugs.gnu.org,
 Paul Pogonyshev <pogonyshev <at> gmail.com>
Subject: Re: bug#51982: Erroneous handling of local variables in
 byte-compiled nested lambdas
Date: Fri, 09 Sep 2022 19:59:23 +0200

Skimming this bug report, it seems like the proposed patch was pushed as:

commit 45252ad8f932c98a373ef0ab7f3363a3e27ccbe4
Author:     Mattias Engdegård <mattiase <at> acm.org>
AuthorDate: Mon Nov 22 16:56:38 2021 +0100

    Fix closure-conversion of shadowed captured lambda-lifted vars

If I'm skimming the rest of the thread correctly, there wasn't anything
further to do here, so I'm closing this bug report.  If I misunderstood,
please respond to the debbugs address and we'll reopen.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.