From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Tom Levy Newsgroups: gmane.emacs.bugs Subject: bug#59576: 29.0.50; named-let doesn't support dynamic binding Date: Fri, 25 Nov 2022 16:34:18 +0000 Message-ID: Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="10088"; mail-complaints-to="usenet@ciao.gmane.io" To: 59576@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Fri Nov 25 17:56:24 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oybzv-0002C5-Ni for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 25 Nov 2022 17:56:19 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oybzi-0001qP-DC; Fri, 25 Nov 2022 11:56:06 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oybzf-0001pe-2W for bug-gnu-emacs@gnu.org; Fri, 25 Nov 2022 11:56:03 -0500 Original-Received: from debbugs.gnu.org ([209.51.188.43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oybze-0000Ik-PL for bug-gnu-emacs@gnu.org; Fri, 25 Nov 2022 11:56:02 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1oybze-0007NL-G7 for bug-gnu-emacs@gnu.org; Fri, 25 Nov 2022 11:56:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Tom Levy Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 25 Nov 2022 16:56:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 59576 X-GNU-PR-Package: emacs X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.166939532428300 (code B ref -1); Fri, 25 Nov 2022 16:56:02 +0000 Original-Received: (at submit) by debbugs.gnu.org; 25 Nov 2022 16:55:24 +0000 Original-Received: from localhost ([127.0.0.1]:37045 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oybz1-0007MO-RE for submit@debbugs.gnu.org; Fri, 25 Nov 2022 11:55:24 -0500 Original-Received: from lists.gnu.org ([209.51.188.17]:58144) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oybz0-0007MG-Cy for submit@debbugs.gnu.org; Fri, 25 Nov 2022 11:55:22 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oybyy-0001Xt-Ty for bug-gnu-emacs@gnu.org; Fri, 25 Nov 2022 11:55:21 -0500 Original-Received: from [145.40.109.133] (helo=145.40.109.133) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oybyx-0008QG-07 for bug-gnu-emacs@gnu.org; Fri, 25 Nov 2022 11:55:20 -0500 Original-Received: from root by 145.40.109.133 with local (Exim 4.94.2) (envelope-from ) id 1oybec-0001tP-MU for bug-gnu-emacs@gnu.org; Fri, 25 Nov 2022 16:34:18 +0000 X-Host-Lookup-Failed: Reverse DNS lookup failed for 145.40.109.133 (failed) Received-SPF: none client-ip=145.40.109.133; envelope-from=root@145.40.109.133; helo=145.40.109.133 X-Spam_score_int: 36 X-Spam_score: 3.6 X-Spam_bar: +++ X-Spam_report: (3.6 / 5.0 requ) BAYES_00=-1.9, DKIM_ADSP_CUSTOM_MED=0.001, FORGED_GMAIL_RCVD=1, FREEMAIL_FORGED_FROMDOMAIN=0.243, FREEMAIL_FROM=0.001, FSL_HELO_BARE_IP_1=2.347, HEADER_FROM_DIFFERENT_DOMAINS=0.25, NML_ADSP_CUSTOM_MED=0.9, NO_DNS_FOR_FROM=0.001, RDNS_NONE=0.793, SPF_NONE=0.001, SPOOFED_FREEMAIL=0.001, SPOOFED_FREEMAIL_NO_RDNS=0.001, SPOOF_GMAIL_MID=0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:249020 Archived-At: 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 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