logoalt Hacker News

kerkeslagertoday at 1:32 AM1 replyview on HN

> More importantly, Lua has a crucial feature that Javascript lacks: tail call optimization. There are programs that I can easily write in Lua, in spite of its syntactic verbosity, that I cannot write in Javascript because of this limitation. Perhaps this particular JS implementation has tco, but I doubt it reading the release notes.

> [...] In my programs, I have banned the use of loops. This is a liberation that is not possible in JS or even c, where TCO cannot be relied upon.

This is not a great language feature, IMO. There are two ways to go here:

1. You can go the Python way, and have no TCO, not ever. Guido van Rossum's reasoning on this is outlined here[1] and here[2], but the high level summary is that TCO makes it impossible to provide acceptably-clear tracebacks.

2. You can go the Chicken Scheme way, and do TCO, and ALSO do CPS conversion, which makes EVERY call into a tail call, without language user having to restructure their code to make sure their recursion happens at the tail.

Either of these approaches has its upsides and downsides, but TCO WITHOUT CPS conversion gives you the worst of both worlds. The only upside is that you can write most of your loops as recursion, but as van Rossum points out, most cases that can be handled with tail recursion, can AND SHOULD be handled with higher-order functions. This is just a much cleaner way to do it in most cases.

And the downsides to TCO without CPS conversion are:

1. Poor tracebacks.

2. Having to restructure your code awkwardly to make recursive calls into tail calls.

3. Easy to make a tail call into not a tail call, resulting in stack overflows.

I'll also add that the main reason recursion is preferable to looping is that it enables all sorts of formal verification. There's some tooling around formal verification for Scheme, but the benefits to eliminating loops are felt most in static, strongly typed languages like Haskell or OCaml. As far as I know Lua has no mature tooling whatsoever that benefits from preferring recursion over looping. It may be that the author of the post I am responding to finds recursion more intuitive than looping, but my experience contains no evidence that recursion is inherently more intuitive than looping: which is more intuitive appears to me to be entirely a function of the programmer's past experience.

In short, treating TCO without CPS conversion as a killer feature seems to me to be a fetishization of functional programming without understanding why functional programming is effective, embracing the madness with none of the method.

EDIT: To point out a weakness to my own argument: there are a bunch of functional programming language implementations that implement TCO without CPS conversion. I'd counter by saying that this is a function of when they were implemented/standardized. Requiring CPS conversion in the Scheme standard would pretty clearly make Scheme an easier to use language, but it would be unreasonable in 2025 to require CPS conversion because so many Scheme implementations don't have it and don't have the resources to implement it.

EDIT 2: I didn't mean for this post to come across as negative on Lua: I love Lua, and in my hobby language interpreter I've been writing, I have spent countless hours implementing ideas I got from Lua. Lua has many strengths--TCO just isn't one of them. When I'm writing Scheme and can't use a higher-order function, I use TCO. When I'm writing Lua and can't use a higher order function, I use loops. And in both languages I'd prefer to use a higher order function.

[1] https://neopythonic.blogspot.com/2009/04/tail-recursion-elim...

[2] https://neopythonic.blogspot.com/2009/04/final-words-on-tail...


Replies

kerkeslagertoday at 7:10 AM

EDIT 3: Looking at Lua's overall implementation, it seems to be focused on being fast and lightweight.

I don't know why Lua implemented TCO, but if I had to guess, it's not because it enables you to replace loops with recursion, it's because it... optimizes tail calls. It causes tail calls to use less memory, and this is particularly effective in Lua's implementation because it reuses the stack memory that was just used by the parent call, meaning it uses memory which is already in the processor's cache.

The thing is, a loop is still going to be slightly faster than TCOed recursion, because you don't need to move the arguments to the tail call function into the previous stack frame. In a loop your counters and whatnot are just always using the same memory location, no copying needed.

Where TCO really shines is in all the tail calls that aren't replacements for loops: an optimized tail call is faster than a non-optimized tail call. And in real world applications, a lot of your calls are tail calls!

I don't necessarily love the feature, for the reasons that I detailed in the previous post. But it's not a terrible problem, and I think it at makes sense as an optimization within the context of Lua's design goals of being lightweight and fast.