How Tail Call Optimization Works
eklitzke.org
eklitzke.org
Then, I used argtags as the basis for tlet: a macro that looks like it is defining local functions using syntax similar to labels or flet, but actually compiles to argtags, so everything ends up as a tagbody.
The calls are always tail calls, whether or not in tail position. You cannot accidentally blow the stack, but you can accidentally expect a call to return, which it won't!
This is all found here:
http://www.kylheku.com/cgit/lisp-snippets/tree/tail-recursio...
There is a complementary cross-module tail calling system in here which provides a defun-like construct deftail for defining tail calling functions. That's based on a trampoline dispatch loop: tail calls unwind up to the loop, passing their arguments to it, along with the next function to be called.
[1] Later I found out that Steele also offered the viewpoint back in the 1970's that tail calls can be seen as goto with arguments.
I understood none of it, but I know it has deep meaning and I respect it.
More info: https://2ality.com/2015/06/tail-call-optimization.html
Edit: Babel may have tried, but couldn't do it for all cases, so they stopped trying? https://github.com/babel/babel/issues/256
So I'm curious what this has to do with the languagr spec? Couldn't a smart compiler/interpreter do this before ES6 already?
function factorial(n, accumulator=1) {
if (n <= 1) {
if (n < 0) throw "Arument must not be negative";
return accumulator;
}
return factorial(n-1, n * accumulator);
}
It's not to tricky to manually convert tail recursion into a loop, but for mutually recursive functions, you'd probably be best off manually transforming your mutually recursive functions into a trampoline variant of continuation passing, where each function returns a tuple of function and arguments to a trampoline loop that just repeatedly invokes the returned function on the returned arguments.
function trampoline(f, ... args) {
while (true) {
f, args = f(*args);
if (args == null) { return f; }
}
}
function fatorial_impl(n, accumulator)
if (n <= 1) {
if (n < 0) throw "Arument must not be negative";
return [accumulator, null];
}
return [factorial_impl, [n-1, n * accumulator]];
}
function factorial(n) {
return trampoline(factorial_impl, n, 1);
}
TCO isn't merely an optimisation in the same sense of local/global value numbering/common sub-expression elimination , dead-code elimination, loop-invariant expression hoisting, etc.
No but "optimisation" implies the normally observable semantics are not altered, which is not the case at all with TCE (aka "guaranteed TCO"). Removing TCE from a language makes it a completely different language e.g. Erlang would be severely restricted as it has no imperative loops.
In particular this is runtime inspectable via func.caller so it really is a behavioral language change to allow the elision of stack frames.
Browsers don't have a say in this. They're making the decision to not be compliant with the specification, so they effectively don't support ES6.
It impacts the correctness of algorithms. For some algorithms it's the difference between using O(1) stack space and O(n) or more, where the latter would blow the stack and effectively crash the program.
"Implementations of Scheme must be properly tail-recursive. Procedure calls that occur in certain syntactic contexts called tail contexts are tail calls. A Scheme implementation is properly tail-recursive if it supports an unbounded number of active tail calls. A call is active if the called procedure may still return. Note that this includes regular returns as well as returns through continuations captured earlier by call-with-current-continuation that are later invoked. In the absence of captured continuations, calls could return at most once and the active calls would be those that had not yet returned. A formal definition of proper tail recursion can be found in Clinger's paper [5]. The rules for identifying tail calls in constructs from the (rnrs base (6)) library are described in section 11.20."
in Chapter 5, Semantic Concepts (http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_cha...). Clinger's paper is "Proper Tail Recursion and Space Efficiency" (https://www.cs.tufts.edu/~nr/cs257/archive/will-clinger/prop...).
The Rationale for "properly tail recursive" is,
"Intuitively, no space is needed for an active tail call, because the continuation that is used in the tail call has the same semantics as the continuation passed to the procedure containing the call. Although an improper implementation might use a new continuation in the call, a return to this new continuation would be followed immediately by a return to the continuation passed to the procedure. A properly tail-recursive implementation returns to that continuation directly.
"Proper tail recursion was one of the central ideas in Steele and Sussman's original version of Scheme. Their first Scheme interpreter implemented both functions and actors. Control flow was expressed using actors, which differed from functions in that they passed their results on to another actor instead of returning to a caller. In the terminology of the report, each actor finished with a tail call to another actor.
"Steele and Sussman later observed that in their interpreter the code for dealing with actors was identical to that for functions and thus there was no need to include both in the language.
"While a proper tail recursion has been a cornerstone property of Scheme since its inception, it is difficult to implement efficiently on some architectures, specifically those compiling to higher-level intermediate languages such as C or to certain virtual-machine architectures such as JVM or CIL.
"Nevertheless, abandoning proper tail recursion as a language property and relegating it to optional optimizations would have far-reaching consequences: Many programs written with the assumption of proper tail recursion would no longer work. Moreover, the lack of proper tail recursion would prevent the natural expression of certain programming styles such as Actors-style message-passing systems, self-replacing servers, or automata written as mutually recursive procedures. Furthermore, if they did not exist, special “loop” constructs would have to be added to the language to compensate for the lack of a general iteration construct. Consequently, proper tail recursion remains an essential aspect of the Scheme language."
(http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale...)
The language specification describes, indirectly, all of the valid programs in the language. With proper tail call elimination as part of the language semantics, simple recursion is a valid iteration technique in those programs. Without proper tail call elimination as part of the language semantics, it is not.
[1] Technically, a hardware stack is not required. However, any programming language with a 'function' abstraction will be required to record the return location somewhere (if not function arguments and other stuff); without tail call elimination, the space for those records grows linearly with function call depth, no matter how it is stored.
Obviously this is just support in the instructions.
I just wish we'd live in a world where people were willing to write code using TCE and just say "wontfix" when users of non-compliant browsers complain that "the code crashes", but alas, in 2021 browsers can just choose to not fix non-compliances and blame the website instead. This is just fucked up.
https://stackoverflow.com/questions/6830192/how-to-run-javas...
The truth is that it would have been very expensive for MS to add it to Edge (which was built around incompatible calling conventions), and that cross-realm tail calls (calling into code from another I frame) would be hard to implement in Firefox.
Now that Edge switched to Chromium, the only problem left is with FF. It could be spec’ed around, but the consensus in the TC-39 isn’t there anymore :-(
You just implement them any which way (eg with loops), and the user of those functions never has to know. That's how eg reduce or map or filter work in Python.
That holds in general for combinators.
Haskell is actually a bad example to use here, because the tail recursive foldl is rarely used. Thanks to laziness, foldr is usually preferred, and it is not tail recursive.
OCaml or Scheme are perhaps better references? Especially given the history of Javascript: the author originally wanted to write a Lisp, but got told by management to add curly braces.
With guarded recursion. foldl' has its place.
What's the modern view here? I think it's bimodal: either TCO is a defining feature of the language, or a best-effort optimization that nobody should rely on.
I think a third option is that tail calls are only guaranteed if you add a special attribute (eg. [[musttail]]) and that attribute fails to compile if your code is written in such a way that a true tail call cannot be guaranteed.
The LLVM backend supports a "musttail" marker on function calls (https://llvm.org/docs/LangRef.html#call-instruction), but it specifies a set of constraints that must be met for "musttail" to be valid. I have been experimenting with a Clang change that would plumb a C++ [[musttail]] attribute through the C++ frontend to LLVM, but it requires some care to make sure we satisfy LLVM's constraints.
goto function(parameter1, parameter2);
Edit: Hmm there is an issue in handling the stack space I suppose, because there are live old parameter objects already in the place you want to put your new parameters. An ugly but possibly workable way of handling it is to have two areas for parameters. One used for odd recursion depths and another used for even ones.
Message 1
Message 2
Message 3
Message 3
Message 2
Message 1
A call to a destructor is a normal call. If you need to call destructors, then it means your tail call is a call to a destructor and not what you're seeing in the code. It's a fundamental semantical problem. You can't have "make the last call in this function be an implicit call to some function" and "make the last call be the explicit call to this other function" at the same time.
Either you push a copy of the object to the list, in which case it is fine. Or you push a pointer/reference to the object, in which case it becomes dangling.
void foo(const char* str) {
if (*str == '\0') return;
printf("%c", str[0]);
std::string x = str + 1;
return foo(x.c_str());
}> fails to compile if your code is written in such a way that a true tail call cannot be guaranteed
[[clang:musttail]] f(a, b);
[[clang:musttail]] return f(a, b);
I don't think that is feasible, it would change the semantics of the language. You can always put your destructors in an inner scope if you want them to run first:
int Func() { { TypeWithDestructor a; int ret = a.get(); } [[clang:musttail]] return ret; }
This means that TCO can't be done across calls where the amount of stack space used for arguments in the callee is larger than that of the caller. (In cases where the stack space used by the callee is less than the caller, the caller just needs to leave "wasted" stack space as if amount of stack space used by arguments were the same.) It wouldn't be much of a point on architectures where the cdecl calling convention passes enough arguments in registers to cover the majority of functions, except that some of these ABIs (notably Windows x64 calling convetion, but not Linux x64_64 SysV ABI) require the caller to allocate shadow space on the stack for all register-passed arguments. (Edit: I was wrong, the Windows shadow space on the stack is a fixed 32 bytes, regardless of the number of register-passed arguments.)
This motivates a couple of ABI questions:
1. Why does the Windows x64 ABI require the caller to pre-allocate "shadow space" to potentially spill register-passed arguments? It's wasteful if it's not needed (especially in ABIs with a redzone), and it reduces opportunities for TCO. (Edit: ahh, unlike Linux, the Windows x64 calling convention has no redzone. I guess this then becomes "Why doesn't Windows x64 provide a redzone?")
2. Why not define a calling convention that is callee-cleanup where the post-cleanup stack pointer is passed in a designated register (or at the top of the stack) to the callee? I understand that it might not make sense to pay the cost (fewer arguments passed in registers, and often an extra stack spill) for the majority of functions, but it seems an oversight that there's not a calling convention that (in the absence of destructors) always allows tail calls to be optimized.
I guess the answer to both questions is that most TCO opportunities are within a single DLL, so the compiler is free to create non-exported versions of functions with custom calling conventions. Is this right?
[0] https://en.wikipedia.org/wiki/X86_calling_conventions plus their variants on other architectures
LLVM mostly follows this path: it allows full TCO only when using the “fastcc” (i.e. “whatever LLVM feels like generating”) and some calling conventions from functional languages (like GHC) that have a specific carve out for it.
Shouldn't TCE be trivial with callee cleanup?
When I (the function) get called, I get X bytes of stack in arguments, then start pushing variables and whatnot. When I return, I simply put my return value at the start of my stack space, pop everything else, then jump back.
In a tail call, all I need to do is put the next functions arguments at the start of my stack space, pop everything else, then jump to its address.
Obviously in IRL CPUs some of this data would be kept in registers instead of the stack, but the mechanism should be the same.
In the article's printf example, the compiler is able to perform TCO only because it uses at most 5 pointer/integer arguments (with number of fp arguments passed in al) and at most 6 fp arguments, so it's caller-cleanup, but with no cleanup to perform.
Under SvsV (Linux, etc.) x86_64 ABI, varargs calls, the number of fp arguments passed in XMMx registers is passed in al, but nothing to directly indicate how much stack space is used by arguments (and it's also obviously caller-cleanup). The printf example from the article works because all of the arguments fit in registers.
But IMO that does not seem like it's worth it considering how less predictable it would make drop.
If a variable is captured by the tail-called function (i.e. the function receives the unique or borrowed pointer) then you can do TCO with an extra argument (said variable, owned/unique) and clean up at the end of the "loop".
If the variable isn't captured by the tail-called function, then it's unobservable (except through side effects) if it's deallocated before the tail call.
When it’s a semantic language feature like in Scheme, it should be called “Tail Call Elimination” because lack of it changes program semantics (thus not merely optimization)
Tail calls are not eliminated; rather it is ensured that a function call in tail position is a tail call.
This is a useful view/terminology. Without the code transformation that implements tail calls, there is nothing special about a function call in tail position; it proceeds exactly like a call not in a tail position. Therefore, it is not a different kind of call. It becomes one after the code transformation: it becomes a tail call.
In a factorial function, fac(n-1) would be a tail call, but 0+fac(n-1) would not. It would be nice if one could annotate (and thus make the compiler verify) tail calls.
This always comes up, but honestly, I've never really run into the problem where I mistook a non-tail call for a tail call. (And I've programmed the majority of my career in languages like Haskell, OCaml and Erlang.)
Of course, I'm always in favour of the compiler verifying more stuff. It just doesn't seem very pressing.
It was never a problem for me because I never trust the compiler to do TCE and structure my code to be independent of it. But it IS a problem.
Perhaps I have only used "good macros" or something, which do not make seemingly tail calls into non-tail calls?
Or perhaps you've only used good macros. But it is incredibly easy for a macro to end up with (+ 0 x) where you think it will end up with "x".
It's also possible that you have used a macro that ended with (+ 0 x), the optimizer turned it into "x" and you got the tail call eliminated but were not guaranteed to get that, and it may blow up on another Scheme implementation.
That's what I don't like about it; The compiler definitely knows if it did TCE or cannot, and it does change program semantics if it did or didn't. So why can't I just annotate the code saying "well, I intend this to TCE, please complain if you can't?"
So that further separates the concept "tail call" from "call in tail position".
Any position can be the tail position if we just wave he right magic wand at it, so the concept becomes meaningless. All we are left with is the style of call: returning versus goto-like.
Haskell does have several macro systems, but they are not nearly as pervasively used as in Lisp languages. (Mostly, because laziness makes it easier to add eg something as foreign as even eg Prolog as an embedded DSL without macros. And, of course, adding to Haskell syntax feels less natural than in Lisp.)
The conversion of a regular call to a tail call could easily be applied to non-tail positions (e.g. it could be requested by some "please make this a tail call" annotation). The tail position is where that can be done without changing the meaning (of programs that meet certain restrictions, at least).
The semantics of not being able to return, and not acquiring any stack-like space is what makes the call a tail call, whether or not it is in a tail position. If we make a call that doesn't return, that call is then the last action the function performs, which puts it at the tail of its activities.
The terminology also gives us nice ways to talk about vaguely related things, also, like:
"execvp is a kind of big tail call in Unix; it calls a new program, such that it's impossible to return to the original, which is entirely replaced (not just the stack frame of the caller of execvp)".
"A boot-loader branching into firmware is a kind of tail call."
That very much sounds like a [regular subroutine] call has been eliminated.
> Tail calls are not eliminated
This sounds like rather delicate semantics. A call has been eliminated. It was in the tail position. It was replaced by something else, which you call the "tail call". Maybe you'd prefer RSCITLEIOTC (regular subroutine call in tail location elimination in favour of tail call)?
I think tail call elimination is good enough to communicate the concept, whereas (when it's not purely an optimisation) tail call optimisation is not good enough, because calling it an "optimisation" is such a dangerous trap.
Edit: Added mutual recursion explicitly.
You'd have a point if they were talking about implementation semantics, but they're talking about language semantics. A Scheme program can assume TCE, a CL program can not, an SBCL program can.
SBCL will only perform TCO at specific optimization levels, so you can't even rely on it in SBCL.
The former will run on other implementations.
Inlining doesn't change what a call stack looks like - the call stack frames are still there, yes possibly just a metadata annotations on real call stack frames and recovered when needed.
With tail calls, the call stack frames are completely gone, and cannot be recovered.
Try this thought experiment - can you implement tail calls in Java and meet the same language specification? I think you cannot. Therefore it is not an optimisation. If you can please email me how and I will implement it and you can publish the paper and get the glory!
Is this because Java exposes stack traces in a way most languages don't?
But I don't think it's unusual for a language to expose call stacks? Ruby, Python, C#, etc all do it.
(I haven’t looked, but I would expect modern Java implementations already make up quite a bit of the stack trace only when it is needed, for example when inlining calls)
And, traditionally, it _is_ unusual to expose call stacks to calling programs for Algol-style languages (implementations typically dumped a call stack and might add a way for a program to walk its stack, but that would be implementation-dependent)
Without exceptions or a repl, where would you use them, other than in a crash dump?
Yes they do. But they can't make up the stack for tail calls because the information is simply gone. If you've got a set of mutually functions that are tail calling, and you suddenly need to generate a stack trace, how do you know how many times the functions have been called and which order they were called? That info was never recorded - it's just done. Inlining is static info and much simpler - it is recorded and isn't gone.
But I assume that kind of information is probably not enough for Java.
Now, whether that’s worth the implementation effort, of course, would depend on whether the construct is used a lot, and that’s a catch-22.
For functions jumping into other functions, I guess that, when the program counter says you’re in baz while the first stack frame says foo got called, you could infer that foo called bar and bar called baz from metadata that the compiler would have to add.
Now, if foo can get into baz along multiple routes, you would have to record something, but I would guess there are plenty of those simpler cases. For those, the main challenge would be to infer recursion count for a recursive call.
[0] https://www.hanselman.com/blog/release-is-not-debug-64bit-op... , ctrl-f for this stack trace is showing the runtime reality.
You can absolutely record these things under TCO, in much the same way you'd record virtual stackframes when inlining.
If you think it is, then you should go ahead and publish it because you've discovered a new language implementation technique.
You seem to have a very Java-centered view of the universe, because it is absolutely not true in most languages that inlined calls preserve call stacks. Call stacks are debug information, and there’s absolutely no requirement for compilers to preserve debug information while doing optimization. Requiring that would be lunacy, and it would prohibit a huge number of optimizations (or require costly bookkeeping).
I don’t know what the situation is in Java-land, but if Java preserves inlining information in call stacks using bookkeeping, then good for it, I guess. It can’t come for free, so you’re taking a performance hit for that pleasure. It’s certainly not something that is common, or commonly understood as a requirement for optimization.
Add another record where? On some kind of stack of records from calls? That will grow linearly with the number of calls? So that's a call-stack is it? The whole point of TCO was to eliminate the stack and you've re-invented it there! If you have an infinite tail-call (like a web server accepting requests in a loop) you'll have an infinitely long list of records with your idea.
> It’s certainly not something that is common, or commonly understood as a requirement for optimization.
In many languages (Python, Ruby, Java, etc) they are not debug information - they're part of the program semantics and (from experience!) if you change them you'll break programs.
Is the debugger part of the language specification? No.
When I say 'can you observe the difference as a programmer' you can mentally expand that to 'can you observe the difference as a programmer who is working off a copy of the language specification'. Otherwise someone armed with a debugger can look at the machine code and then we might as well say all implementation decisions are observable by the user, and then I think we're being a bit silly.
> you won't be able to access the first variable
I'm not familiar with this part of JavaScript off the top of my head sorry - do you mean using a debugger again here?
Neither is "the stack trace".
(I've worked professionally with multiple language specifications and implementing them.)
Of course, the optimizer is still constrained by the spec in the obvious ways: copy operations can only be elided when the compiler can show that they are redundant (in some precise sense that the spec presumably lays out).
It follows of course that this 'optimisation' may impact observable behaviour. This makes some sense as C++ code shouldn't be doing 'real work' in copy-constructors, but it's still a rather ugly concession to pragmatism. edit Which, come to think it, describes the whole C++ language ;-P
[0] https://stackoverflow.com/a/12953129/
[1] https://en.wikipedia.org/wiki/Copy_elision#Return_value_opti...
For example, they don't mention stack overflows at all. But since standards compliant compilers spit out code that suffers from them, I assume they are allowed.
So I assume you could make a standard compliant compiler that doesn't nothing but immediately overflows the stack.
Interesting thought. I imagine just about every language spec (with the possible exception of assembly languages) states something like If memory is exhausted, a handler is executed or If memory is exhausted, the behaviour is undefined, and it's always going to be up to the compiler/interpreter to make reasonable use of the available memory on the specific target platform.
Would a C compiler be non-compliant if it generated code that used 100x the memory that would be used by code generated by typical C compiler? How about 1,000,000,000x so that its generated programs always failed immediately?
Java is an interesting case for this, as it famously doesn't require that a garbage collector needs to be included at all (unlike .Net which does). In Java, not only are you permitted to have a conservative GC, you're permitted to have no GC whatsoever (something OpenJDK now offers [0]). Apparently [1] Java requires that the collector (if it exists) will run before the JVM throws OutOfMemoryError.
I imagine the formal methods folks must have done some thinking on this topic, as their whole field is about doing better than just go ahead and test it out. Could a standards-compliant C compiler used in a safety-critical domain generate code that, only very occasionally, uses a billion times the memory it typically uses?
Somewhat related: one of the motivations behind the Zig language seems to have been a frustration with clumsy handling of memory-exhaustion. [2][3]
[0] https://openjdk.java.net/jeps/318
[1] https://www.kdgregory.com/index.php?page=java.outOfMemory
I would have expected some words to those effects, but extensive browsing and grepping in the C++ spec did not reveal such language. (They do not mention the call stack at all, which is a fair enough decision.)
I was first looking into this, because I had hoped the standard would specify a way to check for whether the next call would blow up the stack before you actually engaged in the call.
> Would a C compiler be non-compliant if it generated code that used 100x the memory that would be used by code generated by typical C compiler? How about 1,000,000,000x so that its generated programs always failed immediately?
You could ask the same for speed of execution. I think it would be standards compliant, but not very useful. Standard compliance ain't the only thing people look for in a compiler.
In practice, you could make a C++ compiler that does the standard compliant thing to virtually all of people's programs, by just emitting the nethack executable regardless of input. After all, virtually all real world C++ programs have undefined behaviour somewhere, and undefined behaviour is allowed to 'travel backwards in time'. (Ie undefined behaviour anywhere makes the whole execution undefined, not just after it is encountered.)
Hey, you could even just start nethack instead of producing any files with your compiler at all. Enough undefined behaviour goes all the way to compile time, like eg not closing your quotes, I think.
> I imagine the formal methods folks must have done some thinking on this topic, as their whole field is about doing better than just go ahead and test it out. Could a standards-compliant C compiler used in a safety-critical domain generate code that, only very occasionally, uses a billion times the memory it typically uses?
I think for safety-critical code, you solve this conundrum by relying on extra guarantees that your compiler implementation makes, not just on the standard.
As for the standards, the drafts are public and usually 98% like the final ones.
The missing 2% are clarifications only relevant for compiler vendors and language lawyers, whose employers can afford sponsoring ISO work anyway.
Yes, but other instances of copy-elision are still at the discretion of the compiler, right?
So even if move semantics aren't supported for the specific type, the target type gets built inplace.
The most fundamental is whether we can write a program which halts in one case and doesn't in the other.
An alternative is whether we can write an if/then/else branch to distinguish between the two cases. Note that this is less general than the above, since we can always use an if/then/else to implement a halt/no-halt program, but we can't always go the other way (due to the Halting Problem). This definition is useful, since if/then/else can cause arbitrarily-large changes to a program's behaviour; whereas we can't "use" a difference which affect halting.
Another definition, which is more subjective, is whether we can do the above "reliably". For example, any optimisation that makes a program faster could be observed by a language which allows access to a clock. Whilst hackers and debuggers might find these useful, it's not the sort of thing that a "reasonable" programmer would do (i.e. code which relies on this sort of thing shouldn't pass code review). I'd probably count inspecting stack traces, or running a debugger on ourselves, in this category.
The messy subjectivness of the latter is why I like to limit the capabilities of what I'm developing with: I don't have to care about timing altering the behaviour of a program which can't access a clock.
And you can tell if you blew up the stack by setting up an exception handler (or lisp condition or whatever equivalent).
That only works if there's some way to tell whether the stack blew up (as you say: catching exceptions, lisp conditions, or whatever equivalent). I'd put those language features in the 'messy' category: useful on occasion; not used by most code; makes all code harder to reason about (hence the subjective "reasonably-unobservable" category above)
> I'd probably count inspecting stack traces, or running a debugger on ourselves, in this category.
I would put such things in the "unreliable" category, since it's the sort of thing that may vary between compilers (including future versions), and may depend on internal details of dependencies which are subject to change.
I certainly wouldn't let them through code review; it can be hard trying to understand 'foo(bar)' in terms of 'the function "foo" applied to the input "bar"', I'd rather avoid the extra complications of having to think about 'pushing a fresh stack frame, clearing registers A, setting the instruction pointer to B, adding C instructions to the ALU's adder pipeline, forcing a flush of D cache lines, ...'
I wouldn't consider the memory layout of something like a stack to be part of the semantics of the language, unless that language actually includes features to directly refer to the stack (get its contents or size, etc).
But the 1s and 0s are not specified by the language (in almost all cases.) They're out of scope.
The line is: what has been formally specified by the language spec as being part of the language.
It doesn’t necessarily change the semantics, but it does change what kind of programs are sure to crash your machine, and what kind are going to run fast, which is also an important property of programming languages.
Yeah, this is exactly what I meant. The semantics of the language are the same regardless (i.e. the meanings of programs doesn’t change), but in practice it makes a huge difference.
Other language standards keep this from affecting the semantics of the language by simply leaving it out of the semantics of the language. When the expected behavior is undefined, the implementors can do anything they want without, strictly speaking, affecting the semantics of the language.
In python, it's mostly visible through exception objects.
In Tcl and R, it's in common use because it is standard practice to do things in your caller's scope instead of your own.
In C++ (and any language with destructors), many routines are invisibly not TCEable because the language semantics require the destructor to run after the tail call returns - which means that a change to a different part of the code determines if a specific function is TCEable or not.
So, despite your claim being technically true, it is in practice often informally specified by the language or standard library.
But then many languages are quite loose with stack size requirement anyways, as well as stack traces (e.g. JVM's can include details about the internal implementation and/or automatic compiler transforms, e.g. concerning lambdas, methodhanles, invokedynamic etc).
In the "best" case, you'll get a stack overflow exception. In worse cases, your exception/condition system will kick in at a time which is essentially non-deterministic (it's usually deterministic but depends on a lost of things you may have no visibility into).
But if TCE is available, you might even have no allocations after some startup. That's different semantics which are part of the language (e.g. in the case of Scheme) and thus not an "optimization".
There are only two hard things in computer science: off-by-one errors, cache invalidation, and naming things.
In the Scheme world, often a hybrid stack-heap calling convention called Cheney on the MTA is used in which all calls are tail calls [3].
[1]: https://en.m.wikipedia.org/wiki/Calling_convention
Most compilers do that, for most compiled languages.
This is not just inlining, it's a function with multiple entry points, which is not popular.
And that was very popular when memory was scarce. The typical BASIC for the 6502 used it. See for example http://hackzapple.org/scripts_php/index.php?menu=14&mod=8517... (search for “The CHARGET Subroutine”). Here, it is used for speed, too (otherwise, at least one of the functions would have to do an indirect load, which is cumbersome and slow on a 6502. The self-modifying code is a lot faster)
It also often was used when one had, say, a function to output a character and another function that printed a specific character. Combined with a creative use of the BIT instruction, one could even have functions printing _any_ character, a space, a question mark, or a CR share their tails (https://retrocomputing.stackexchange.com/a/11132)
But yes, nowadays I guess it is rare, although, with an ABI designed for it, it could be used to make a call with a default argument value fall through into the more generic code)
You'd turn it off at the object file level if you're writing asm and doing tricks there (x264 asm has some fallthroughs like this), but there isn't a way to say only these two functions need to be in the same order.
Some linkers already can merge functions that happen to compile to the same code, even though that corrupts stack frames (foo calls bar, but the linker makes it call baz instead. https://stackoverflow.com/a/61865960)
It’s ‘just’ a matter of learning the build system new tricks.
I found a short discussion on this at https://gcc.gnu.org/legacy-ml/gcc/2000-02/msg00575.html that contains https://gcc.gnu.org/legacy-ml/gcc/2000-02/msg00599.html, which says
“The P3 SSE stuff we've done generates multiple entry points, but it does that within the backend prologue expander. There's nothing to generate multiple regular prologues. Though it shouldn't be that hard to do.
It's not impossible to believe that the bulk of the compiler would work with them, as long as flow knows how to properly create the CFG. LABEL_ALTERNATE_NAME was invented for this, though it appears that the code to properly deal with it is sitting on a branch waiting for accounting to say it has been paid for.“
That was in February 2000. I wouldn’t know whether that comment was close to the truth or what gcc currently supports.
For llvm, the thread at https://lists.llvm.org/pipermail/llvm-dev/2018-October/12715... gives some cases where this could be used, but reading it, it doesn’t look it is solved in the way I gave (see for example https://lists.llvm.org/pipermail/llvm-dev/2018-October/12717.... https://lists.llvm.org/pipermail/llvm-dev/2018-October/12715... calls it “more like separate functions with a common tail.”, so I’m not alone in that.
That thread also indicates that DWARF has support for helping debuggers figure out the correct name of such a function.
""" Languages like Erlang must implement tail call optimizations, since persisted data is stored as "loop variables" in infinite loops. This happens when we write code like this:
loop(Data) ->
....
...
loop(newData).
What is the loop(Data), loop(newData) doing? Would be great if someone could elaborate on this point.
[0] Tail Call Optimization: The Musical: https://www.youtube.com/watch?v=-PX0BV9hGZY
I'm learning a great deal from the responses here, thank you.
If you are in the same position I was (self-taught dev looking to improve your general understanding) I can't recommend this course/book highly enough:
- Book: http://csapp.cs.cmu.edu/3e/home.html - Lectures: https://scs.hosted.panopto.com/Panopto/Pages/Sessions/List.a...
It’s also astonishing to me that people in a position to explain even moderately complex computing ideas continue to treat recursion as somehow hard to reason about. It’s calling a function. A function that calls itself is still just a function calling another function. Two mutually recursive functions calling each other are just two functions calling two other functions. That’s so much easier to follow than state changing in a single function call.
Calling a function can be easily, and incorrectly, modeled by representing the arguments as variables stored at a fixed position in memory. (As function calls used to work.) Once you introduce recursion, this model breaks down and you are forced to think in terms of activation records/stackframes.
Probably those people learnt function calls in the former way first, meaning that recursion represented a conceptual leap for them.
I remember javascriptcore solving this issue by using a "shadow stack"
Or you can use the rr-debugger, and just return back to the exact sequence of calls, and reject the need to pick between optimization and debugging :D
https://stackoverflow.com/questions/65225761/trying-to-delib...
I was experimenting with a simple indirect-threaded interpreter, which I wanted to write in a "nice" style (1 function per opcode) but have compiled in an "optimized" way (state machine). Playing around in Godbolt, I found out that the compilers managed to detect & optimize even indirect tail calls, i.e. tail calls to function pointers. This was indeed on a toy example (i.e. like 5 functions, not a real interpreter with 100 different opcodes) but still truly amazing.
The reason for this was, I was trying to replicate LuaJIT2 - Mike Pall was complaining that the reason interpreters written in C are slow is, that the compiler cannot optimize & register-allocate a large function containing a switch statement for 100 opcodes. Instead, he wrote the interpreter in asm, and made sure all important variables are kept in registers. My thesis was that we could do the same thing by having a bunch of functions tail-calling each other, with all important variables as parameters (which would be optimized into registers). Better, actually, because the compiler could improve register allocation within each "opcode"/function.
This is because you don't understand humans. Which is more clear to you?
repeat special-task 5 times.
(do special-task n times) = (do special-task n - 1 times)
(do special-task 0 times) = Don't do anything.
do special-task 5 times.
*(not 100% sure on this, HNers, prove me wrong if possible, I'm open to being wrong).
And that, in turn, I think is because most beginners are first introduced to mutation and statements and all kinds of “do” stuff instead of trivial algebra with trivial types.
If the core primitives at the start are:
1. Computation producing output
2. Computation of input producing output
3. Wrapping #2 in a function
I could see introducing recursion in an easily understandable way on day one.
I’d even say that people usually have a good grasp on recursion even if they don’t know that’s what it’s called. Multiplication is just recursive addition. Exponents are just recursive multiplication. And so on.
Imperative thinking is computational. All forms of thinking are computational by definition.
> Expressions are fundamentally easier to reason about, and there’s no reason they would be more difficult to a beginner.
What does expressions have to do with anything. Recursion can be both defined in an expression and as an imperative jump instruction. The concept is orthogonal to expressions.
>I’d even say that people usually have a good grasp on recursion even if they don’t know that’s what it’s called. Multiplication is just recursive addition. Exponents are just recursive multiplication. And so on.
But people don't think of multiplication this way. The teacher doesn't teach multiplication to you in terms of recursion she literally teaches you it with the "times" keyword. What's 5 * 6? Add 5 to 5, 6 times.
It has bearing on language. Nobody outside of programming/mathematics communicates concepts recursively. Our communication is a reflection of how we think naturally. Recursion takes training. Looping is just learning syntax for a concept we already know about: repetition.
I meant in the mathematical sense. Math doesn’t have imperative statements and side effects.
> What does expressions have to do with anything. Recursion can be both defined in an expression and as an imperative jump instruction. The concept is orthogonal to expressions.
In case it wasn’t clear, I’ve been arguing this whole time for teaching pure FP concepts. Starting with computing a value, then computing a value from input, then with a function returning a value computed from its input... then with a function computing a value recursively from its input. Recursion is the fundamental building block for repetition in FP. Even if you can express it with a loop-like expression it eventually desugars to recursion.
> But people don't think of multiplication this way. The teacher doesn't teach multiplication to you in terms of recursion she literally teaches you it with the "times" keyword. What's 5 * 6? Add 5 to 5, 6 times.
That... is recursion. It’s mind boggling to me that it’s not plain as day, here in this context. It’s literally:
(+ 5 (+ 5 (+ 5 (+ 5 (+ 5 5))))))
5 * 6 = 5 + 5 + 5 + 5 + 5 + 5
5 * 6 = 5 + 5 * 5
> It has bearing on language. Nobody outside of programming/mathematics communicates concepts recursively. Our communication is a reflection of how we think naturally. Recursion takes training. Looping is just learning syntax for a concept we already know about: repetition.
From a learning perspective, they’re literally just different syntax for the same thing. Recursion is just moving the repetition intent to the body of the loop and eliminating intermediary values. There’s no reason other than tautology that one syntax is easier to learn than the other.
I don’t think it’s about so large and broad a group, or about human language. No one speaks in dynamic property access or dependency inversion or binary compilation or a zillion other concepts in programming that aren’t misrepresented as “hard to understand”.
My point isn’t that it’s something that would be immediately obvious to a beginner, but that its difficulty is often overstated when introduced.
First, realizing that you can have separate instances of functions at the same time -- different stack frames. Making the mental leap from "the content of x in function f" to "the content of x in f(0), and also the content of x in f(1)" is a leap of abstraction, but not necessarily a tremendous one.
Second, mentally modeling recursion when it gets complicated. Simple recursive cases are easy to model in your head, because either there is little state to keep track of, or because you can extrapolate the pattern between function calls, mentally compressing the state of the whole call tree.
Tail-call optimization, for example, is really easy to mentally model because you only have to keep track of the state of one function's variables at a time -- unless you start passing continuations or thunks into your function calls, in which case you're carrying a stack of unlimited complexity into each function call. It's still just a function call, with the same number and types of arguments, but now one or more of those arguments contains turing-complete, recursive programs of unlimited complexity.
This similar to the worst-case mentally-complicated recursion without TCO, where you can build a complex graph of function calls, scopes, shared data accesses, and mutated copies of what used to be the same data, that can all be present at once, and where you might need to keep track of all of them in order to track down and understand something that you need to understand.
You can, of course, build similarly tangled-up structures in a purely-iterative manner, but the upside is that the complexity will be confined to the data state -- there will be no call tree to mentally model, and no need to track variable scope.
---
Shorter version: if the efficiency and elegance of recursion (with appropriate compiler/runtime optimizations, like TCO) is like zip compression for your mental model of code complexity, then there exist recursive-program equivalents of zip bombs.
---
Even shorter version: recursion itself isn't hard to reason about, but recursive programs can be very hard to reason about
https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...
Not complaining.. but curious that this one feature gets so much visibility. Is it just because it is quite easy to understand?
Some FP compilers such as Guile compile to a CPS intermediate language, and the concept of CPS is known within people writing compilers and the FP community, but quite unheard of in the general programming community it seems.
Nit: the IP will be advanced by 1 before the nop is executed. IP always points to the instruction following the one which is currently being executed. Which is important for IP-relative addressing and, as mentioned later, calls.
xor %eax %eax (2 bytes)
mov $0x0,%edi (5 bytes)
Is this a normal ratio? Does -Os much better?
I understand the argument against doing TCO in a low level language like Rust (debugging stack traces, etc). But as an opt-in? Yes, please!
OCaml, which is like Rust's muse/parent, does it. Kotlin and Clojure do that as well, IIRC.
Like eg a state machine where one state = one function. That's also the example in the corresponding Lambda the Ultimate paper.
But yes, getting TCO for simple self-recursive function is better than nothing.
As an ObjC example, there's an objc_msgSend call between every two methods in a stack trace, but you never see it.
In practice this has never been a problem for me.
https://llvm.org/docs/CodeGenerator.html#sibling-call-optimi...
This is because it is not declared static, and thus is visible outside that translation unit.
a() { b(); i++; }
or should we code for tco?