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

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

[Alan Mackenzie]

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).

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> 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

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

[Eli Zaretskii]

> Cc: 67116@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@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??

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

[Alan Mackenzie]

Hello, Eli.

On Sun, Nov 12, 2023 at 08:13:39 +0200, Eli Zaretskii wrote:
> > Cc: 67116@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@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).

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

[Drew Adams]

> > 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

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

[Richard Stallman]

[[[ 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)

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

>> 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

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

[Alan Mackenzie]

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).

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

>> 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:`.

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

[Mattias Engdegård]

>                           (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!)

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

[Mattias Engdegård]

> No, the generated code looks correct.

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

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

[Mattias Engdegård]

> 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.)

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

[Alan Mackenzie]

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).