GNU bug report logs - #59576
29.0.50; named-let doesn't support dynamic binding

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 59576 in the body.
You can then email your comments to 59576 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: Tom Levy <tomlevy93 <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 29.0.50; named-let doesn't support dynamic binding
Date: Fri, 25 Nov 2022 16:34:18 +0000

Is `named-let' supposed to work when dynamic binding is used (as
opposed to lexical binding)? Because if so, it is broken when the
recursion is not in tail position.

Example:

```
(eval
 '(named-let f ((x 10))
    (if (= 0 x)
        0
      (1+ (f (1- x)))))    ; note: recursion is *not* in tail position
 nil)    ; change to t to enable lexical binding (makes the code work)
```

Output:

```
Debugger entered--Lisp error: (void-variable --cl-f--)
  (funcall --cl-f-- (1- x))
  (1+ (funcall --cl-f-- (1- x)))
  (if (= 0 x) t (1+ (funcall --cl-f-- (1- x))))
  (lambda (x) (if (= 0 x) t (1+ (funcall --cl-f-- (1- x)))))(10)
  funcall((lambda (x) (if (= 0 x) t (1+ (funcall --cl-f-- (1- x))))) 10)
  (named-let f ((x 10)) (if (= 0 x) t (1+ (f (1- x)))))
  eval((named-let f ((x 10)) (if (= 0 x) t (1+ (f (1- x))))) nil)
  (progn (eval '(named-let f ((x 10)) (if (= 0 x) t (1+ (f (1- x))))) nil))
  eval((progn (eval '(named-let f ((x 10)) (if (= 0 x) t (1+ (f ...)))) nil)) t)
  elisp--eval-last-sexp(nil)
  eval-last-sexp(nil)
  funcall-interactively(eval-last-sexp nil)
  call-interactively(eval-last-sexp nil nil)
  command-execute(eval-last-sexp)
```

There is an easy fix. Currently `named-let' is defined as follows:

```
(defmacro named-let (name bindings &rest body)
  ;; ...
  (require 'cl-lib)
  (let ((fargs (mapcar (lambda (b) (if (consp b) (car b) b)) bindings))
        (aargs (mapcar (lambda (b) (if (consp b) (cadr b))) bindings)))
    ;; According to the Scheme semantics of named let, `name' is not in scope
    ;; while evaluating the expressions in `bindings', and for this reason, the
    ;; "initial" function call below needs to be outside of the `cl-labels'.
    ;; When the "self-tco" eliminates all recursive calls, the `cl-labels'
    ;; expands to a lambda which the byte-compiler then combines with the
    ;; funcall to make a `let' so we end up with a plain `while' loop and no
    ;; remaining `lambda' at all.
    `(funcall
      (cl-labels ((,name ,fargs . ,body)) #',name)
      . ,aargs)))
```

I believe the issue is with the following construct:

    (funcall (cl-labels ((,name ...)) #',name) ...)

The `funcall' to the lambda happens outside the scope of `cl-labels'.
As stated in the documentation of `cl-labels', closure capture only
works when lexical binding is in used. So any non-optimised recursive
calls in the body will fail, because `name' is not captured.

The easy fix is to move the `funcall' inside the scope of cl-labels.
However the bindings must be evaluated outside the `cl-labels' (as
explained in the existing comment). This can be achieved using a
simple `let' outside the `cl-labels'. (This actually simplifies the
code, because the bindings can be passed directly to `let' and the
variable `aargs' can be eliminated.)

Note that the generated bytecode with this fix is slightly different:
it looks like, when all recursive calls are in tail position, this fix
prevents the byte-compiler from inlining the outer function call. I am
not sure if that's a significant problem. I included an example with
disassembly below.

(I am not including a patch because I haven't completed the copyright
assignment process yet.)

Cheers,
Tom

------------

Disassembly example:

```
(let ((lexical-binding t))
  (disassemble
   (byte-compile
    '(named-let f ((x 100000))
       (if (= 0 x)
           0
         (f (1- x)))))))  ; note: here recursion *is* in tail position
```

Output with current `named-let' implementation:

```
byte code:
  args: nil
0       constant  100000
1       constant  nil
2:1     stack-ref 1
3       dup
4       constant  0
5       eqlsign
6       goto-if-nil 2
9       constant  0
10      stack-set 2
12      constant  nil
13      goto      3
16:2    stack-ref 2
17      sub1
18      stack-set 3
20      constant  :recurse
21:3    stack-set 1
23      goto-if-not-nil 1
26      return
```

Output with my proposed fix:

```
byte code:
  args: nil
0       constant  <compiled-function>
      doc:   ...
      args: (arg1)
    0       constant  nil
    1:1     stack-ref 1
    2       dup
    3       constant  0
    4       eqlsign
    5       goto-if-nil 2
    8       constant  0
    9       stack-set 2
    11      constant  nil
    12      goto      3
    15:2    stack-ref 2
    16      sub1
    17      stack-set 3
    19      constant  :recurse
    20:3    stack-set 1
    22      goto-if-not-nil 1
    25      return

1       dup
2       constant  100000
3       call      1
4       return
```


And here is a minimal example showing that the byte-compile is unable
to inline a `funcall' to a `let'-bound function:

```
(let ((lexical-binding t))
  (disassemble
   (byte-compile
    '(let ((f #'(lambda (x) (message "%S" x))))
       (funcall f 100000)))))
;; call to f is not inlined

(let ((lexical-binding t))
  (disassemble
   (byte-compile
    '(funcall #'(lambda (x) (message "%S" x)) 100000))))
;; call to lambda is inlined
```

------------

In GNU Emacs 29.0.50 (build 1, x86_64-pc-linux-gnu) of 2022-11-25 built
 on ...
Repository revision: af545234314601ba3dcd8bf32e0d9b46e1917f79
Repository branch: master

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

From: Mattias Engdegård <mattiase <at> acm.org>
To: Tom Levy <tomlevy93 <at> gmail.com>
Cc: Stefan Monnier <monnier <at> iro.umontreal.ca>, 59576 <at> debbugs.gnu.org
Subject: bug#59576: 29.0.50; named-let doesn't support dynamic binding
Date: Sat, 26 Nov 2022 10:48:54 +0100

`named-let` being a looping construct, it makes little sense to use it in dynamic binding where TCO opportunities are severely limited. Ideally we should just signal an error if an attempt to use it in dynbound code is made. Users will thank us for that (at least they should, if they have any sense).

Second-best would be to inhibit all TCO in dynbound code but whom would that really benefit?

(Regarding your proposal, generating worse code in lexbind mode isn't a wonderful outcome.)

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

From: Tom Levy <tomlevy93 <at> gmail.com>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Stefan Monnier <monnier <at> iro.umontreal.ca>, 59576 <at> debbugs.gnu.org
Subject: Re: bug#59576: 29.0.50; named-let doesn't support dynamic binding
Date: Sat, 26 Nov 2022 23:36:10 +1300

Personally I'm fine with `named-let' signalling an error in dynamic
binding mode.

(Regarding worse code in lexical binding mode: There are workarounds.
An ugly one is to include both versions of `named-let' and switch
between them depending on the binding mode. Another solution is to
teach the byte-compiler to inline funcalls to let-bound lambdas;
that's more elegant and might also benefit other code, but I have no
idea how difficult it would be to implement.)

On Sat, 26 Nov 2022 at 22:49, Mattias Engdegård <mattiase <at> acm.org> wrote:
>
> `named-let` being a looping construct, it makes little sense to use it in dynamic binding where TCO opportunities are severely limited. Ideally we should just signal an error if an attempt to use it in dynbound code is made. Users will thank us for that (at least they should, if they have any sense).
>
> Second-best would be to inhibit all TCO in dynbound code but whom would that really benefit?
>
> (Regarding your proposal, generating worse code in lexbind mode isn't a wonderful outcome.)
>

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

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Tom Levy <tomlevy93 <at> gmail.com>, 59576 <at> debbugs.gnu.org
Subject: Re: bug#59576: 29.0.50; named-let doesn't support dynamic binding
Date: Sat, 26 Nov 2022 12:45:40 -0500

> `named-let` being a looping construct, it makes little sense to use it in
> dynamic binding where TCO opportunities are severely limited. Ideally we
> should just signal an error if an attempt to use it in dynbound code is
> made. Users will thank us for that (at least they should, if they have any
> sense).

Indeed, I'm surprised I didn't put something akin to (cl-assert
lexical-binding) in that macro.  It was an oversight.


        Stefan

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

From: Mattias Engdegård <mattiase <at> acm.org>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 59576-done <at> debbugs.gnu.org, Tom Levy <tomlevy93 <at> gmail.com>
Subject: Re: bug#59576: 29.0.50; named-let doesn't support dynamic binding
Date: Mon, 21 Aug 2023 14:17:59 +0200

26 nov. 2022 kl. 18.45 skrev Stefan Monnier <monnier <at> iro.umontreal.ca>:

> Indeed, I'm surprised I didn't put something akin to (cl-assert
> lexical-binding) in that macro.  It was an oversight.

Now done on master (c21103bb76).

Previous Next

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