Subject: bug#59576: closed (Re: bug#59576: 29.0.50; named-let doesn't support dynamic binding)

From: [email-masked] (GNU bug Tracking System)
Date: Mon, 21 Aug 2023 12:19:02 +0000

Your bug report

#59576: 29.0.50; named-let doesn't support dynamic binding

which was filed against the emacs package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
59576: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=59576
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#59576: 29.0.50; named-let doesn't support dynamic binding
From: Mattias Engdegård <[email-masked]>
To: Stefan Monnier <[email-masked]>
Cc: [email-masked], Tom Levy <[email-masked]>
Date: Mon, 21 Aug 2023 14:17:59 +0200
List-Id: <debbugs-submit.debbugs.gnu.org>

26 nov. 2022 kl. 18.45 skrev Stefan Monnier <[email-masked]>:

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

Subject: 29.0.50; named-let doesn't support dynamic binding
From: Tom Levy <[email-masked]>
To: [email-masked]
Date: Fri, 25 Nov 2022 16:34:18 +0000
List-Id: <debbugs-submit.debbugs.gnu.org>

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