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 06:51:45 -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="000000000000f99e4d05e61d2f8a" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="40397"; 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 12:52:41 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 1oMokz-000AJJ-09 for ged-emacs-devel@m.gmane-mx.org; Sat, 13 Aug 2022 12:52:41 +0200 Original-Received: from localhost ([::1]:48134 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oMokx-0006su-K9 for ged-emacs-devel@m.gmane-mx.org; Sat, 13 Aug 2022 06:52:39 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:42064) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oMokK-0006Dw-Rz for emacs-devel@gnu.org; Sat, 13 Aug 2022 06:52:00 -0400 Original-Received: from mail-pj1-x102c.google.com ([2607:f8b0:4864:20::102c]:54101) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oMokI-0004o8-Hz; Sat, 13 Aug 2022 06:52:00 -0400 Original-Received: by mail-pj1-x102c.google.com with SMTP id pm17so3071370pjb.3; Sat, 13 Aug 2022 03:51:57 -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=GIwUbB8DWGVKRcpz3fYeZiTMHL4FWd8ovSdpWe9wTII=; b=bJL2jkjjUMOqrWAX7Vjp0CXNsShb8Jmfkrknvg4QTw5KVKVoATPapBzel/pC73PIRt ELVkaD6oaTBqQfKre0glJYHn/Ss6IHCWc5pJ6a6r0ruKVRqveE8AQq/qSU82uOsleULg Kn9pQ+IFkD80baz8OcvwBvLvUwOhGEksIEWd82i7xkz5hSVn++U9SxWQbnQmMITaHzCI VOSfK40SnAhfKYoPOswJtWkboxbbvannh5AMGN7gkbip7kExXlC78sQp54KQ0/Zhx752 0FY/YiJ8Cicazz+WlOeKIaeqM6WCzYLZ8FwnUoA3Y64lwP7gM7myFYq3Gc60Tl1l8skv 64DA== 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=GIwUbB8DWGVKRcpz3fYeZiTMHL4FWd8ovSdpWe9wTII=; b=JXhk7mrv0S35VfDYyrhoCQfN1skuR0hRR4hTAfqUSik1CvEB2HfYnpSY30x/1hCz/W kr+4yjkBcLcDDvFTguRKVcAWd3GPoSnCQkd0sITCR+8Hhid0ueJMMAl+jbvpulDHA/be PwEgR17s+9ZBRIxz7poHkLzmIR82Whx3OHMBcOJ400vdypexw9HQpB2eKD+V0qGjFbzr ZinVGt13/8+Q86Tx5jxuM4Pg5D8gbeiyPa7cd6OWIIulKqB9iZND3bLiHQa+iqtLlf7O Rk4TpRqpaxMQ1TZZ5M4temHe+uqLlJKn78AQJ46qi7ZumMA2Wwy12eZsX9xOzDJHQj6G FquA== X-Gm-Message-State: ACgBeo2KdDECEl8TazIdC8igJmzDIZkuU75yn2JuY8yDslJ0IFcade/+ 2mNLvpIt2oB4FKhUMe0+3uCl6sjMALuITCau6lg= X-Google-Smtp-Source: AA6agR7gs7z/vYVtrluFzbeQOpieM9N9sx3EaP3eSNGqkmUBor99gVub05jahPU5VLTJYLAd82Fc/XW9qOe6SxFrwf4= X-Received: by 2002:a17:902:e30c:b0:171:2036:532c with SMTP id q12-20020a170902e30c00b001712036532cmr8175550plc.121.1660387916880; Sat, 13 Aug 2022 03:51:56 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2607:f8b0:4864:20::102c; envelope-from=owinebar@gmail.com; helo=mail-pj1-x102c.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:293405 Archived-At: --000000000000f99e4d05e61d2f8a Content-Type: text/plain; charset="UTF-8" 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. > 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 --000000000000f99e4d05e61d2f8a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
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.


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



--000000000000f99e4d05e61d2f8a--