Hacker News Reader

Comment by mananaysiempre | Hacker News Reader

You’re wrong in the way in which many people are wrong when they hear about a thing called “tail-call optimization”, which is why some people have been trying to get away from the term in favour of “proper tail calls” or something similar, at least as far as R5RS[1]:

> A Scheme implementation is properly tail-recursive if it supports an unbounded number of active tail calls.

The issue here is that, in every language that has a detailed enough specification, there is some provision saying that a program that makes an unbounded number of nested calls at runtime is not legal. Support for proper tail calls means that tail calls (a well-defined subgrammar of the language) do not ever count as nested, which expands the set of legal programs. That’s a language feature, not (merely) a compiler feature.

[1] https://standards.scheme.org/corrected-r5rs/r5rs-Z-H-6.html#...

View on HN

Thank you for the precise answer.

I still think that the language property (or requirement, or behavior as seen by within the language itself) that we're talking about in this case is "unbounded nested calls" and that the language specs doesn't (shouldn't) assume that such property will be satisfied in a specific way, e.g. switching the call to a branch, as TCO usually means.

Unbounded nested calls as long as those calls are in tail position, which is a thing that needs to be defined—trivially, as `return EXPR(EXPR...)`, in Lua; while Scheme, being based around expressions, needs a more careful definition, see link above.

Otherwise yes. For instance, Scheme implementations that translate the Scheme program into portable C code (not just into bytecode interpreted by C code) cannot assume that the C compiler will translate C-level tail calls into jumps and thus take special measures to make them work correctly, from trampolines to the very confusingly named “Cheney on the M.T.A.”[1], and people will, colloquially, say those implementations do TCO too. Whether that’s correct usage... I don’t think really matters here, other than to demonstrate why the term “TCO” as encountered in the wild is a confusing one.

[1] https://www.plover.com/misc/hbaker-archive/CheneyMTA.html

Cheney on the MTA is a great paper/algorithm, and I'd like to add (for the benefit of the lucky ten thousand just learning about this) that it's pun on a great old song: Charlie on the MTA ( https://www.youtube.com/watch?v=MbtkL5_f6-4 ). The joke is that in both cases it will never return, either because the subway fare is too high or because you don't want to keep the call stack around.

Why do you think that?

Because that's a description of the intended behavior, and I reason about a language as an abstraction that allows one to express an expected behavior ignoring the implementation details.

I know it's not universal: some languages in their infancy lack a formalization and are defined by their reference implentation. But a more theoretical approach has allowed languages like C to strive for years.

I sort of see what you are getting at but I am still a bit confused:

If I have a program that based on the input given to it runs some number of recursions of a function and two compilers of the language, can I compile the program using both of them if compiler A has PTC and compiler B does not no matter what the actual program is? As in, is the only difference that you won’t get a runtime error if you exceed the max stack size?

I think features of the language can make it much easier (read: possible) for the compiler to recognize when a function is tail call optimizable. Not every recursion will be, so it matters greatly what the actual program is.

It is a feature of the language (with proper tail calls) that a certain class of calls defined in the spec must be TCOd, if you want to put things that way. It’s not just that it’s easier for the compiler to recognize them, it’s that it has to.

(The usual caveats about TCO randomly not working are due to constraints imposed by preexisting ABIs or VMs; if you don’t need to care about those, then the whole thing is quite straightforward.)

That is correct, the difference is only visible at runtime. So is the difference between garbage collection (whether tracing or reference counting) and lack thereof: you can write a long-lived C program that calls malloc() throughout its lifetime but never free(), but you’re not going to have a good time executing it. Unless you compile it with Fil-C, in which case it will work (modulo the usual caveats regarding syntactic vs semantic garbage).

Reply on news.ycombinator.com