From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Lynn Winebarger Newsgroups: gmane.emacs.devel Subject: Re: Ideal performance of ELisp Date: Sat, 13 Aug 2022 07:13:02 -0400 Message-ID: References: <83o7wuva9o.fsf@gnu.org> <83mtceupbx.fsf@gnu.org> <83lerxvfnu.fsf@gnu.org> <838rnxvdcq.fsf@gnu.org> <83r11ptksn.fsf@gnu.org> <83a68dti6w.fsf@gnu.org> <874jykzvx9.fsf@yahoo.com> <83fsi4sttn.fsf@gnu.org> <838rnws5c7.fsf@gnu.org> <838rntocb8.fsf@gnu.org> Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="00000000000017522e05e61d7c89" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="24470"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Eli Zaretskii , Po Lu , Alan Mackenzie , emacs-devel , Yuan Fu To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sat Aug 13 13:14:24 2022 Return-path: Envelope-to: ged-emacs-devel@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 1oMp60-000689-8E for ged-emacs-devel@m.gmane-mx.org; Sat, 13 Aug 2022 13:14:24 +0200 Original-Received: from localhost ([::1]:58422 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oMp5z-0008IQ-8i for ged-emacs-devel@m.gmane-mx.org; Sat, 13 Aug 2022 07:14:23 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:44274) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oMp4z-0007Wx-Dn for emacs-devel@gnu.org; Sat, 13 Aug 2022 07:13:21 -0400 Original-Received: from mail-pl1-x62d.google.com ([2607:f8b0:4864:20::62d]:45751) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oMp4t-0008RG-Q6; Sat, 13 Aug 2022 07:13:21 -0400 Original-Received: by mail-pl1-x62d.google.com with SMTP id 13so2736468plo.12; Sat, 13 Aug 2022 04:13:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc; bh=aYDty0j82+5pjoGyylN5X383UcJogVb6PsGPkCezdHc=; b=WHYSE5URR8xvovSLL2MUVP6xHOKftPaurD8RAPRF2o+VfkAlQNefungw3h4VDoJQfw 0Ul9f8mZxdqG1ChJKJbviit9qjYDRslUHo2WLEGEo3st5Nx9zsl1sDaFd4iz3WHYi41K CsN50MWpNjdU5Igyv9ZMBrz/DtcWN+vgD7S4HzoGn8seMm5rDcRH2+evv05POgmpXDpy 2nrbUoyDAeNIuAxTaMGjqNQjzK4ZlD6lCymxtM5I44dkATGzw+YKS1eUnKTQx5t4Fzq2 k6BVmlU7CXEPMNxJGI5FE9RVdvvrzMJEcTMf22aFxOxIWEsKF7HLGqiYkWzivdQIsdie aooA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc; bh=aYDty0j82+5pjoGyylN5X383UcJogVb6PsGPkCezdHc=; b=sG5Ot/xGHlo288kc6QCE0ioISuZZlCjnPQ1hY8aM3whS60nX8OcEJZHIxHQtYVOdH2 htsRtqI9uSMzep7sUEFebusKe+gJ952aaHlWlgCnW+ybTXV3Pr/Ve7oPE32G/SG43Pub PrSmCQePFpK/HTyXEZ0KtRuaYGFJMxMG5+OGVoCYrRWytJkcNdBVU9FBDeUfFmkX/8hg HGtQEtJD06YjGK6c33ZSMhQadRTzOyZ+jlALD++jqxv0IdN+FFF2gEdALdAQ1bqffjaF WSa9x8wkiSU5OcuuiKC7cFQV4aSGSDe+6xs7Ii4rNaVppnJA4uhLPyQWJhyfe27unEe1 Ws+Q== X-Gm-Message-State: ACgBeo3TIXCf2oulathrvBHZK8kFenY1EWkHktfebuq3BpqCVeNZoOK0 31v22cWfb+PqURIPph4U/nNXZMfUTvKu0KQ4Vq0= X-Google-Smtp-Source: AA6agR6vRi+Llarti1Z49ofe1ZDKl5Tqi6xtIrHz9sEPS91Orx6RDIqM+MblbBIGWBf3AXNXx9q2nVHg/SvYo+Vh+eU= X-Received: by 2002:a17:90a:2948:b0:1f3:1b42:a810 with SMTP id x8-20020a17090a294800b001f31b42a810mr8716384pjf.203.1660389193895; Sat, 13 Aug 2022 04:13:13 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2607:f8b0:4864:20::62d; envelope-from=owinebar@gmail.com; helo=mail-pl1-x62d.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:293406 Archived-At: --00000000000017522e05e61d7c89 Content-Type: text/plain; charset="UTF-8" On Sat, Aug 13, 2022, 6:51 AM Lynn Winebarger wrote: > On Fri, Aug 12, 2022, 10:11 PM Stefan Monnier > wrote: > >> > Once the VM supports proper tail recursion, it's straightforward to >> > generate automata that never perform a function call, at least not as >> part >> > of the recognizer. >> >> It was straightforward beforehand as well (using a `while` loop instead >> of recursion). And if you do use recursion, then it's not very much >> simpler with `lexical-binding` than without because you still have to >> take into account the possibility that the function gets redefined >> during your recursion :-( >> > > I think you're mistaking self-tail recursion for tail recursion. I mean > proper tail recursion in Clinger's sense. Any program written in CPS form > will not "accumulate stack" (note the scare quotes, I know the details > depend on implementation). You can use a while loop with a trampoline to > emulate it, sure, but that's not the same as having all control transfers > take place by simple branching. If you lift all the lambdas, there's no > implicit memory allocation either. I used to write code like that all the > time - it's just "higher order assembly language". > > You're right about the hiccup introduced by having a "Lisp-2" without > locally scoped function names. That could be solved by introducing an > explicit "function lambda" whose parameters provide lexically scoped > function variables, or by simply using funcall to dispatch to closures on > ordinary variables. As long as the dispatch happens on locally scoped > names, the compiler should be able to tell if they are constants. > I should have said "(eval-when-compile #'funcall)" in place of "funcall", to guarantee the operator is a constant involving no runtime lookup of a function symbol. > >> Don't get me wrong: `lexical-binding` is definitely very useful for >> native compilation (and it does help for tail-calls in some cases, >> e.g. in `named-let`), but I suspect that for the foreseeable future >> it'll stay hard to be competitive with something like tree-sitter when >> writing the code in ELisp > > > This is Emacs. Even if there was a new VM with these features, and a > transpiler for porting existing ELC files, available today, I wouldn't be > sure it would be integrated anytime soon. > I just think the main barrier to introducing such improvements was, > historically, the dynamic scoping in the massive lisp code base of Emacs. > With that removed, I don't think Eli's skepticism is warranted. This was > all hashed out in the 1980s. > > Lynn > > > > --00000000000017522e05e61d7c89 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Sat, Aug 13, 2022, 6:51 AM Lynn Winebarger <owinebar@gmail.com> wrote:
=
On Fri, Aug 12, 2022, 10:11 PM Stefan= Monnier <monnier@iro.umontreal.ca> wrote:
> Once the VM supports proper tail recursion, it= 's straightforward to
> generate automata that never perform a function call, at least not as = part
> of the recognizer.

It was straightforward beforehand as well (using a `while` loop instead
of recursion).=C2=A0 And if you do use recursion, then it's not very mu= ch
simpler with `lexical-binding` than without because you still have to
take into account the possibility that the function gets redefined
during your recursion :-(
I think you're mistaking self-tail recursion f= or tail recursion.=C2=A0 I mean proper tail recursion in Clinger's sens= e.=C2=A0 Any program written in CPS form will not "accumulate stack&qu= ot; (note the scare quotes, I know the details depend on implementation).= =C2=A0 You can use a while loop with a trampoline to emulate it, sure, but = that's not the same as having all control transfers take place by simpl= e branching.=C2=A0 =C2=A0If you lift all the lambdas, there's no implic= it memory allocation either.=C2=A0 I used to write code like that all the t= ime - it's just "higher order assembly language".=C2=A0=C2=A0=

You're right about = the hiccup introduced by having a "Lisp-2" without locally scoped= function names.=C2=A0 That could be solved by introducing an explicit &quo= t;function lambda" whose parameters provide lexically scoped function = variables, or by simply using funcall to dispatch to closures on ordinary v= ariables.=C2=A0 As long as the dispatch happens on locally scoped names, th= e compiler should be able to tell if they are constants.
I should have said "(eval-when-com= pile #'funcall)" in place of "funcall", to guarantee the= operator is a constant involving no runtime lookup of a function symbol.




Don't get me wrong: `lexical-binding` is definitely very useful for
native compilation (and it does help for tail-calls in some cases,
e.g. in `named-let`), but I suspect that for the foreseeable future
it'll stay hard to be competitive with something like tree-sitter when<= br> writing the code in ELisp

This is Em= acs.=C2=A0 Even if there was a new VM with these features, and a transpiler= for porting existing ELC files, available today, I wouldn't be sure it= would be integrated anytime soon.
I just think the = main barrier to introducing such improvements was, historically, the dynami= c scoping in the massive lisp code base of Emacs.=C2=A0 With that removed, = I don't think Eli's skepticism is warranted.=C2=A0 This was all has= hed out in the 1980s.

Ly= nn



--00000000000017522e05e61d7c89--