> 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