Why is there no tail recursion optimization in Emacs lisp, not but like other scheme?

Question

Emacs lisp is a dialect of LISP and especially Scheme. Most of scheme interpreters do have a optimization of Tail Recursion, but emacs lisp doens't. I searched the reason in `info elisp' for a while, but I fail to find it.

P.S. Yes, there is other iteration syntax in elisp like `while', but I still cannot find a good reason why they didn't implement tail recursion like other scheme interpreters.

Overby

What gave you the impression that elisp was especially related to scheme?? As lisps go, the two are very different. – Edgington

It's not a dialect of Scheme at all. It's a dialect of Lisp, and most Lisp dialects don't do tail recursion. – Inclining

It's probably most closely related to Maclisp, which is from the 1970's. It didn't have tail recursion. – Inclining

@Edgington I think I was confused with something else. I thought elisp is a dialect of scheme, but as you said, it seems it isn't. And I also assume that tail recursion is a common thing in LISP world, but it was wrong... – Overby

@Overby Tail call elimination is a common thing in Lisp: it was just much less common in the 1960s which is when the Lisps elisp is based on originated. Scheme was the first Lisp-family language to mandate tail call elimination, in the 1970s. – Goodin

Answer 1

Emacs Lisp was created in the 1980's. The Lisp dialect that the Emacs author (Richard Stallman) was most familiar with at the time was MIT Maclisp, and Emacs Lisp is very similar to it. It used dynamic variable scoping and did not have lexical closures or tail recursion optimization, and Emacs Lisp is the same.

Emacs Lisp is very different from Scheme. The biggest difference is that Scheme is lexically scoped, but this was only recently added to Emacs Lisp, and it has to be enabled on a per-file basis (by putting ;;; -*- lexical-binding: t -*- on the first line) because doing it by default would cause many incompatibilities.

There has been some work to replace Emacs Lisp with Guile, a Scheme dialect. But it's not clear whether it will ever reach fruition.

Inclining

I think you're probably referring in that last paragraph to the guile emacs project, in which the elisp interpreter is replaced by guile. That's not about replacing elisp with scheme, though -- the point is that guile has been made to support elisp directly. If that is what you were thinking of, then in fact significant hard work has gone into that project -- although whether it ever matures to the point where it could and would actually become part of the standard GNU Emacs is anyone's guess. – Edgington

@Edgington Thanks, I've revised that last paragraph. – Inclining

Answer 2

Emacs Lisp has had dynamic scoping as its main/only scoping rule for the first 25 years of its life. Dynamic scoping is basically incompatible with optimization of tail-recursion, so until Emacs-24 (which introduced lexical scoping) there was very little to no interest in this optimization.

Nowadays, ELisp could benefit sometimes from optimization of tail recursion, and there's been some patches submitted to do that, but that hasn't yet been integrated. The lack of tail-recursion optimization as well as the relatively inefficient implementation of function calls has influenced ELisp style, such that recursion is not used very often, which in turns reduces the benefits of adding the optimization of tail calls.

Virtue

I doubt it's a "chicken'n'egg" problem. I think if tail-recursion optimization was added, people would start using tail-recursion (well, at least in the Emacs source code). – Hyperkeratosis

It's clearly not just a chicken'n'egg problem, no. Tail recursion has visible effects in terms of backtraces, interactions with advice-add (and hence tracing, debug-on-entry, ...). This implies an inertia opposed to the introduction of TCO. If we had had TCO from the beginning, we'd be using it very happily indeed, but now its introduction is more problematic and its earlier absence makes its introduction less beneficial (which is the chicken'n'egg part of the problem). – Virtue

Answer 3

Looks like someone has made an implementation of TCO in Emacs Lisp: https://github.com/Wilfred/tco.el. I haven't played with it myself, but you might want to give it a whirl if you're interested in seeing TCO in Emacs Lisp.

Paganize

Answer 4

Emacs 28 introduced the macro named-let, which can be used to evaluate a tail-recursive loop expression in an optimized way.

While there's no direct support for auto-optimizing functions yet, we can use the above macro inside those functions; or if you are adventurous, set native-comp-speed to 3 (also Emacs 28+): Self TCO by GCCEmacs

Shellieshellproof