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

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

[Tom Levy]

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

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

[Mattias Engdegård]

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

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

[Tom Levy]

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

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

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

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

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

[Mattias Engdegård]

26 nov. 2022 kl. 18.45 skrev Stefan Monnier <monnier@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).