I've seen a lot of chatter about tail calls, but I don't think I've ever seen actual examples of what they look like. Does anyone use them or is it just something for language nerds to obsess about?
It's a compiler optimization, not something an end user should really ever use. As an end user, it should just look like a function whose final statement is the call to another function (often itself, recursively).
One may be familiar with "stack overflow" which is when a series of function calls (often recursive) go so deep before actually returning that it exhausts the maximum stack space (essentially an array of scopes containing variables/state for each function). A proper tail call will realize that it can reuse the same existing stack frame instead of adding a new one, which essentially makes exhausting the stack impossible and removes the need for the CPU to do all of that bookkeeping.
In performance sensitive workflows it can make a large difference.
It's broader than compiler optimization. You have to implement algorithms in such a way that the recursion is in tail position. Sometimes you may also have to specify that the function is tail-recursive (I believe that's the case in Scala?)
Any time a function ends by calling another function and doesn't do anything else besides perhaps return the value you're using a tail call. It's just the name for a function call that's in tail position.
> Any time a function ends by calling another function and doesn't do anything else besides perhaps return the value you're using a tail call. It's just the name for a function call that's in tail position
It sounds like you already know this, but many people, including myself at one time, think of tail call optimization as a trick for not blowing up the stack when writing recursive functions. However, it's much more general. Tail call optimization doesn't have to be recursive, it can be applied any time the final statement or expression of a function is another function call. It's something like a special form of inlining. And as you say, it's actually possible to apply the optimization in limited cases where the tail called function returns a value![2]
That general optimization is very useful for implementing threaded[1] or continuation passing style VMs since it compiles function calls and all their associated baggage down to a jump and maybe some assignments.
For me the mental leap was that when I call a function, what I'm saying is "do this, then come back to me so I can finish." What if I don't care if the function comes back, because I've already done all the work I need to do? What if I'm really just handing off my results to the function for it to finish the job itself? Then I should give the function the address of whoever called me, and leave. The function I'm calling is replacing me, not assisting me. If a call stack is a series of waypoints that have to be revisited in reverse after a goal is achieved, with a tail call I'm saying "don't bother coming back to me."
I might leave my house, go to an ATM, then go to the grocery store to do my shopping. TCO means that I don't have to stop by the ATM again on the way home.
So my mental model actually doesn't have anything to do with recursion.
One way to look at it is they let you do "low level functional programming", where you can write code that jumps around without using stack space.
If you think about all the standard statements in a language - if, while, async, etc - all of these kinds of constructs can be built out of normal functions once you have tail calls. This makes the language more extensible and reduces the need to introduce new kinds of built-in language constructs and allows more experimentation.
They're really useful for input processing/parsing, recursion, implementing algorithms, etc.
Another way to think about it is that functions can become little 'named blocks' with defined inputs and outputs, and you can combine them together without worrying so much about the runtime costs of functions that take up stack space. So if you have a function with lots of if conditions, while loops, etc, you can convert it into these 'named blocks' instead, which makes maintenance easier.
There are lots of examples. In a way, the fact that none of the main imperative languages support this simple runtime feature is what's stopping people from realising how great tail calls are. There's a bit of a Catch-22 happening.
From my understanding tails calls used more in functional languages where mutations are not welcomed or not allowed. This construction basically gives a way to have unlimited loop without adding more stuff to the call stack. The downside that you are losing call stack and it may be harder to debug.
One may be familiar with "stack overflow" which is when a series of function calls (often recursive) go so deep before actually returning that it exhausts the maximum stack space (essentially an array of scopes containing variables/state for each function). A proper tail call will realize that it can reuse the same existing stack frame instead of adding a new one, which essentially makes exhausting the stack impossible and removes the need for the CPU to do all of that bookkeeping.
In performance sensitive workflows it can make a large difference.