Re: Ideal performance of ELisp

[Lynn Winebarger <owinebar@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2316 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 3337 bytes --]