GNU bug report logs - #67116
byte-compile-let: reversing the order of evaluation of the clauses CAN make a difference.

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 67116 in the body.
You can then email your comments to 67116 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: Alan Mackenzie <acm <at> muc.de>
To: bug-gnu-emacs <at> gnu.org
Cc: Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: byte-compile-let: reversing the order of evaluation of the clauses
 CAN make a difference.
Date: Sat, 11 Nov 2023 22:48:43 +0000

Hello, Emacs.

Emacs master branch.

In lisp/emacs-lisp/bytecomp.el (byte-compile-let), when the following
form (from jit-lock--debug-fontify):

                          (let
                              ((beg pos)
                                (end (setq pos
                                               (next-single-property-change
                                                pos 'fontified
                                                nil (point-max)))))
                            (put-text-property beg end 'fontified nil)
                            (jit-lock-fontify-now beg end))

gets byte compiled, the order of evaluating BEG and END gets reversed so
that END gets evaluated first.  Since the value for END contains (setq
pos ...), BEG gets this updated value of POS rather then the original
intended value.

This particular bug in jit-lock.el can be fixed by using let* rather
than let, but this isn't the point.  I believe (without testing) that
the interpreted code for the form would evaluate BEG before END, hence
testing it interpreted (e.g. under edebug) will give a false sense of
correctness.

The comment in byte-compile-let:

      ;; Bind the variables.
      ;; For `let', do it in reverse order, because it makes no
      ;; semantic difference, but it is a lot more efficient since the
      ;; values are now in reverse order on the stack.

, is not true.  It can make a semantic difference.  So doing the binding
in reverse order is a bug.

-- 
Alan Mackenzie (Nuremberg, Germany).

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

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Alan Mackenzie <acm <at> muc.de>
Cc: bug-gnu-emacs <at> gnu.org
Subject: Re: byte-compile-let: reversing the order of evaluation of the
 clauses CAN make a difference.
Date: Sat, 11 Nov 2023 23:52:38 -0500

> In lisp/emacs-lisp/bytecomp.el (byte-compile-let), when the following
> form (from jit-lock--debug-fontify):
>
>                           (let
>                               ((beg pos)
>                                 (end (setq pos
>                                                (next-single-property-change
>                                                 pos 'fontified
>                                                 nil (point-max)))))
>                             (put-text-property beg end 'fontified nil)
>                             (jit-lock-fontify-now beg end))
>
> gets byte compiled, the order of evaluating BEG and END gets reversed so
> that END gets evaluated first.

Sounds like a bug.  Do you have some recipe to reproduce it?
I looked at the bytecode but it's a bit hard to tell what's going on
there, since the var names are lost along the way.

> The comment in byte-compile-let:
>
>       ;; Bind the variables.
>       ;; For `let', do it in reverse order, because it makes no
>       ;; semantic difference, but it is a lot more efficient since the
>       ;; values are now in reverse order on the stack.
>
> , is not true.  It can make a semantic difference.  So doing the binding
> in reverse order is a bug.

Note that this is talking about the actual binding operations, which is
separate from the computation of the values that are to be given.
What this is saying is that

    (let ((X1 E1)
          (X2 E2))
      ...)

can be compiled to

    <compute E1>
    <compute E2>
    varbind X2
    varbind X1

since computing E pushes it value on the stack, so after the two
"compute" we have the values of E1 and E2 on the stack and we can pop
them in reverse order.  And indeed it should make no difference if we
do the `varbind X1` before or after `varbind X2` as long as they get
the right value and as long as we don't compute anything which depends
on those vars in-between.


        Stefan

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67116 <at> debbugs.gnu.org, acm <at> muc.de
Subject: Re: bug#67116: byte-compile-let: reversing the order of evaluation of
 the clauses CAN make a difference.
Date: Sun, 12 Nov 2023 08:13:39 +0200

> Cc: 67116 <at> debbugs.gnu.org
> Date: Sat, 11 Nov 2023 23:52:38 -0500
> From:  Stefan Monnier via "Bug reports for GNU Emacs,
>  the Swiss army knife of text editors" <bug-gnu-emacs <at> gnu.org>
> 
> > In lisp/emacs-lisp/bytecomp.el (byte-compile-let), when the following
> > form (from jit-lock--debug-fontify):
> >
> >                           (let
> >                               ((beg pos)
> >                                 (end (setq pos
> >                                                (next-single-property-change
> >                                                 pos 'fontified
> >                                                 nil (point-max)))))
> >                             (put-text-property beg end 'fontified nil)
> >                             (jit-lock-fontify-now beg end))
> >
> > gets byte compiled, the order of evaluating BEG and END gets reversed so
> > that END gets evaluated first.
> 
> Sounds like a bug.

It does?  I always thought that the order of evaluation in a let form
is unspecified, and in practice I had several bugs of exactly this
nature, which I fixed by using let*, as expected.

Why on Earth should we require any particular order of evaluation in a
let form??

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

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Alan Mackenzie <acm <at> muc.de>
Cc: 67116 <at> debbugs.gnu.org, Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: bug#67116: byte-compile-let: reversing the order of evaluation of the
 clauses CAN make a difference
Date: Sun, 12 Nov 2023 15:21:32 +0100

>                           (let
>                               ((beg pos)
>                                 (end (setq pos
>                                                (next-single-property-change
>                                                 pos 'fontified
>                                                 nil (point-max)))))
>                             (put-text-property beg end 'fontified nil)
>                             (jit-lock-fontify-now beg end))
> 
> gets byte compiled, the order of evaluating BEG and END gets reversed so
> that END gets evaluated first.  Since the value for END contains (setq
> pos ...), BEG gets this updated value of POS rather then the original
> intended value.

No, the generated code looks correct. Do you have any reason to believe it's not?

(Of course I always blame the compiler first. It's programmer tradition!)

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

From: Alan Mackenzie <acm <at> muc.de>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 67116 <at> debbugs.gnu.org, acm <at> muc.de,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#67116: byte-compile-let: reversing the order of evaluation
 of the clauses CAN make a difference.
Date: Sun, 12 Nov 2023 14:22:26 +0000

Hello, Eli.

On Sun, Nov 12, 2023 at 08:13:39 +0200, Eli Zaretskii wrote:
> > Cc: 67116 <at> debbugs.gnu.org
> > Date: Sat, 11 Nov 2023 23:52:38 -0500
> > From:  Stefan Monnier via "Bug reports for GNU Emacs,
> >  the Swiss army knife of text editors" <bug-gnu-emacs <at> gnu.org>

> > > In lisp/emacs-lisp/bytecomp.el (byte-compile-let), when the following
> > > form (from jit-lock--debug-fontify):

> > >                           (let
> > >                               ((beg pos)
> > >                                 (end (setq pos
> > >                                                (next-single-property-change
> > >                                                 pos 'fontified
> > >                                                 nil (point-max)))))
> > >                             (put-text-property beg end 'fontified nil)
> > >                             (jit-lock-fontify-now beg end))

> > > gets byte compiled, the order of evaluating BEG and END gets reversed so
> > > that END gets evaluated first.

> > Sounds like a bug.

> It does?  I always thought that the order of evaluation in a let form
> is unspecified, and in practice I had several bugs of exactly this
> nature, which I fixed by using let*, as expected.

No.  The order of _evaluation_ is specified as top to bottom.  The order
of _binding_ is unspecified.  Quoting from the elisp.info page "Local
Variables":

     All of the VALUE-FORMs in BINDINGS are evaluated in the order they
     appear and _before_ binding any of the symbols to them.

and a little later on the same page:

     On the other hand, the order of _bindings_ is unspecified:

> Why on Earth should we require any particular order of evaluation in a
> let form??

To make the value of a form unambiguous?  In any case, we do require a
particular order.

-- 
Alan Mackenzie (Nuremberg, Germany).

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

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Alan Mackenzie <acm <at> muc.de>
Cc: 67116 <at> debbugs.gnu.org, Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#67116: byte-compile-let: reversing the order of evaluation of
 the clauses CAN make a difference
Date: Sun, 12 Nov 2023 15:41:57 +0100

> No, the generated code looks correct.

Sorry, actually it doesn't. There's a bug here, will fix. Thank you!

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

From: Alan Mackenzie <acm <at> muc.de>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: acm <at> muc.de, bug-gnu-emacs <at> gnu.org
Subject: Re: byte-compile-let: reversing the order of evaluation of the
 clauses CAN make a difference.
Date: Sun, 12 Nov 2023 14:54:40 +0000

Hello, Stefan.

On Sat, Nov 11, 2023 at 23:52:38 -0500, Stefan Monnier wrote:
> > In lisp/emacs-lisp/bytecomp.el (byte-compile-let), when the following
> > form (from jit-lock--debug-fontify):

> >                           (let
> >                               ((beg pos)
> >                                 (end (setq pos
> >                                                (next-single-property-change
> >                                                 pos 'fontified
> >                                                 nil (point-max)))))
> >                             (put-text-property beg end 'fontified nil)
                                (message "jit-lock-fontify-now %s %s" beg end)
> >                             (jit-lock-fontify-now beg end))

> > gets byte compiled, the order of evaluating BEG and END gets reversed so
> > that END gets evaluated first.

> Sounds like a bug.  Do you have some recipe to reproduce it?

Certainly!  In the code fragment above in jit-lock--debug-fontify,
insert the diagnostic line as above.  Byte compile this function.  Then
M-x jit-lock-debug-mode.  Now scrolling any (previously unfontified)
sections of a buffer will fail to fontify those sections.  In *Messages*
it can be seen that the printed values of BEG and END are identical,
hence the call to jit-lock-fontify-now does nothing.

> I looked at the bytecode but it's a bit hard to tell what's going on
> there, since the var names are lost along the way.

> > The comment in byte-compile-let:

> >       ;; Bind the variables.
> >       ;; For `let', do it in reverse order, because it makes no
> >       ;; semantic difference, but it is a lot more efficient since the
> >       ;; values are now in reverse order on the stack.

> > , is not true.  It can make a semantic difference.  So doing the binding
> > in reverse order is a bug.

> Note that this is talking about the actual binding operations, which is
> separate from the computation of the values that are to be given.
> What this is saying is that

>     (let ((X1 E1)
>           (X2 E2))
>       ...)

> can be compiled to

>     <compute E1>
>     <compute E2>
>     varbind X2
>     varbind X1

> since computing E pushes it value on the stack, so after the two
> "compute" we have the values of E1 and E2 on the stack and we can pop
> them in reverse order.

It seems apparent that the computations are being done in reverse order,
too.  That can be seen in the above *Messages* output as well as in
byte-compile-let in bytecomp.el:

      (dolist (var (if is-let (reverse clauses) clauses))
        (unless is-let
          (push (byte-compile-push-binding-init var) init-lexenv))
        (let ((var (if (consp var) (car var) var)))
          (if (byte-compile-bind var init-lexenv)
              (pop init-lexenv))))

..  (reverse clauses) happens before the code for any of the value forms
gets generated.

> And indeed it should make no difference if we
> do the `varbind X1` before or after `varbind X2` as long as they get
> the right value and as long as we don't compute anything which depends
> on those vars in-between.

Yes, that is all true.  But the byte compiler generates code which does
the _evaluation_ of the values in the wrong order, according to the
description of let on page "Local Variables" of the elisp manual.

This is a bug in either the byte compiler or the documentation of let.
I would tend towards the first of these alternatives.

Whatever, that let in jit-lock--debug-fontify would probably be safer if
it were a let*.

>         Stefan

-- 
Alan Mackenzie (Nuremberg, Germany).

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

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 67116 <at> debbugs.gnu.org, acm <at> muc.de
Subject: Re: bug#67116: byte-compile-let: reversing the order of evaluation
 of the clauses CAN make a difference.
Date: Sun, 12 Nov 2023 11:49:55 -0500

>> Sounds like a bug.
> It does?  I always thought that the order of evaluation in a let form
> is unspecified,

I'm not sure if we say so explicitly somewhere, but ELisp's order of
evaluation is very much always "left to right" and that carries over to
`let`.

> Why on Earth should we require any particular order of evaluation in
> a let form??

That's a popular bikeshedding subject, actually.

On one side you have the proponents of leaving the order unspecified
(like in C and Scheme) on the premise that it allows more choice for the
compiler, on the other you have the proponents of specifying the order
so as to remove an ugly corner case that bites programmers.

I am personally not swayed by the optimization argument (tho the OCaml
bytecode compiler had a good argument in favor of right-to-left
evaluation order) and in the case of ELisp, there's a lot of code out
there which already relies on the current evaluation order.


        Stefan

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

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Alan Mackenzie <acm <at> muc.de>
Cc: 67116 <at> debbugs.gnu.org
Subject: Re: byte-compile-let: reversing the order of evaluation of the
 clauses CAN make a difference.
Date: Sun, 12 Nov 2023 12:06:27 -0500

>> Sounds like a bug.  Do you have some recipe to reproduce it?
> Certainly!  In the code fragment above in jit-lock--debug-fontify,
> insert the diagnostic line as above.  Byte compile this function.  Then
> M-x jit-lock-debug-mode.  Now scrolling any (previously unfontified)
> sections of a buffer will fail to fontify those sections.  In *Messages*
> it can be seen that the printed values of BEG and END are identical,
> hence the call to jit-lock-fontify-now does nothing.

Hmm, indeed, thanks.
Apparently Matthias already found the problem, I'm looking forward to
his explanations.

>> since computing E pushes it value on the stack, so after the two
>> "compute" we have the values of E1 and E2 on the stack and we can pop
>> them in reverse order.
>
> It seems apparent that the computations are being done in reverse order,
> too.  That can be seen in the above *Messages* output as well as in
> byte-compile-let in bytecomp.el:
>
>       (dolist (var (if is-let (reverse clauses) clauses))
>         (unless is-let
>           (push (byte-compile-push-binding-init var) init-lexenv))
>         (let ((var (if (consp var) (car var) var)))
>           (if (byte-compile-bind var init-lexenv)
>               (pop init-lexenv))))
>
> ..  (reverse clauses) happens before the code for any of the value forms
> gets generated.

AFAICT "the code for any of the value forms" is generated by
`byte-compile-push-binding-init`.  When `is-let` is true, the above loop
does not call it at all, it only emits the code which does the
`varbind` thingies.  When `is-let` is true the calls to
`byte-compile-push-binding-init` are performed just before this loop
(and non-reversed).

Maybe having written this code I'm unable to see what it actually does
instead of seeing what I want(ed) it to do, but my impression is that if
it really does it in the wrong order, we'd have noticed a long time ago.

My crystal ball doesn't want to talk to me today, but my hope is that
it's a bug in something like our new-ish variable/constant-propagation
optimization.

> This is a bug in either the byte compiler or the documentation of let.
> I would tend towards the first of these alternatives.

+1


        Stefan


PS: BTW, Alan, thanks for putting me in `Cc:`; even better would
    have been to put me in `X-Debbugs-Cc:`.

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

From: Drew Adams <drew.adams <at> oracle.com>
To: Alan Mackenzie <acm <at> muc.de>, Eli Zaretskii <eliz <at> gnu.org>
Cc: "67116 <at> debbugs.gnu.org" <67116 <at> debbugs.gnu.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: RE: [External] : bug#67116: byte-compile-let: reversing the order of
 evaluation of the clauses CAN make a difference.
Date: Sun, 12 Nov 2023 19:32:23 +0000

> > It does?  I always thought that the order of evaluation in a let form
> > is unspecified, and in practice I had several bugs of exactly this
> > nature, which I fixed by using let*, as expected.
> 
> No.  The order of _evaluation_ is specified as top to bottom.  The order
> of _binding_ is unspecified.  Quoting from the elisp.info page "Local
> Variables":
> 
>      All of the VALUE-FORMs in BINDINGS are evaluated in the order they
>      appear and _before_ binding any of the symbols to them.
> 
> and a little later on the same page:
> 
>      On the other hand, the order of _bindings_ is unspecified:
> 
> > Why on Earth should we require any particular order of evaluation in a
> > let form??
> 
> To make the value of a form unambiguous?  In any case, we do require a
> particular order.

Yes.  And FWIW Common Lisp does the same (which
likely means that most other Lisps at that time
did the same).

  first evaluates the expressions value1, value2,
  and so on, in that order, saving the resulting values.
  Then all of the variables varj are bound to the
  corresponding values in parallel

https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node83.html

Message #37 received at 67116-done <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Alan Mackenzie <acm <at> muc.de>
Cc: 67116-done <at> debbugs.gnu.org, Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#67116: byte-compile-let: reversing the order of evaluation of
 the clauses CAN make a difference
Date: Mon, 13 Nov 2023 12:19:27 +0100

> There's a bug here, will fix.

Now fixed on master. I'm very pleased that you reported this bug.
(Of course it didn't have anything to do with order of evaluation at all but you already understood that.)

I didn't do a deep analysis of what code was affected by the bug but measuring changes in the bytecode size, which is usually quite good, only two places turned up: jit-lock--debug-fontify, which you already noticed, and
c-forward-sws in cc-engine.el, where the code

	      (c-put-in-sws rung-pos
			    (setq rung-pos (point)
				  last-put-in-sws-pos rung-pos)))

was probably affected here. (Obviously the bug was out to get you personally, Alan.)

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

From: Alan Mackenzie <acm <at> muc.de>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: 67116 <at> debbugs.gnu.org, acm <at> muc.de,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#67116: byte-compile-let: reversing the order of evaluation
 of the clauses CAN make a difference
Date: Mon, 13 Nov 2023 13:14:21 +0000

Hello, Mattias.

On Mon, Nov 13, 2023 at 12:19:27 +0100, Mattias Engdegård wrote:
> > There's a bug here, will fix.

> Now fixed on master. I'm very pleased that you reported this bug.
> (Of course it didn't have anything to do with order of evaluation at
> all but you already understood that.)

Thanks for the fix!

Yes, Stefan M. was right, here.  I think it was caused by a (relatively)
recent optimisation introduced into the compiler.

> I didn't do a deep analysis of what code was affected by the bug but
> measuring changes in the bytecode size, which is usually quite good,
> only two places turned up: jit-lock--debug-fontify, which you already
> noticed, and c-forward-sws in cc-engine.el, where the code

> 	      (c-put-in-sws rung-pos
> 			    (setq rung-pos (point)
> 				  last-put-in-sws-pos rung-pos)))

> was probably affected here. (Obviously the bug was out to get you
> personally, Alan.)

I'll have a look at that, sometime.  It somehow doesn't feel particularly
urgent at the moment.

-- 
Alan Mackenzie (Nuremberg, Germany).

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

From: Richard Stallman <rms <at> gnu.org>
To: Drew Adams <drew.adams <at> oracle.com>
Cc: 67116 <at> debbugs.gnu.org, acm <at> muc.de, eliz <at> gnu.org, monnier <at> iro.umontreal.ca
Subject: Re: bug#67116: byte-compile-let: reversing the order of evaluation of
 the clauses CAN make a difference.
Date: Mon, 13 Nov 2023 21:56:13 -0500

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

    > first evaluates the expressions value1, value2,
    > and so on, in that order, saving the resulting values.
    > Then all of the variables varj are bound to the
    > corresponding values in parallel

That is what `let' did in MacLisp, and what it does in Emacs Lisp too.

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Previous Next

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