I think I understood that concept but it still seems a bit strange to me. Doesn't that imply a potentially infinite stack of function calls?
I've seen this idea in other functional program examples as well. Instead of having a sequence of instructions, they have a sequence of function calls. Instead of a function returning to the caller, it calls the next function in the program which is analogous to the virtual machine moving on to the next line of code in the sequence. It implies the program's structure and state is actually expressed within the function call stack and its frames. I admit I'm not sure what the purpose of this is.
Yes, which is exactly why tail calls are so important. Otherwise you'd stack overflow after processing the first few thousand elements of your stream.
> I've seen this idea in other functional program examples as well. Instead of having a sequence of instructions, they have a sequence of function calls. Instead of a function returning to the caller, it calls the next function in the program which is analogous to the virtual machine moving on to the next line of code in the sequence. It implies the program's structure and state is actually expressed within the function call stack and its frames. I admit I'm not sure what the purpose of this is.
Well, if you want to express your function as an actual function, in the mathematical sense, recursion is often the natural way to do it. Things like the call stack are an implementation detail; often a natural way to describe a function is "do this, do that, then do the same thing for all the rest of it", and usually the easiest way to translate that into a program is recursion.
It also tends to be more compositional, because you don't have to worry about control flow (or at least, control flow isn't a special case: all your control flow is just function calls). For example if you are calling several nested functions in an imperative-style loop, there's no way to break out of that loop from the inner function. But if you write the same thing as several mutually recursive functions, you can "break out of the loop" by just not recursing under particular conditions.
In functional code written where general tail call elimination (or special tail call operations) are available, non- or mutually-recursive tail calls are not uncommon.
Heck, non-recursive (potentially fairly nested) tail calls are common in languages without any optimization for it. Anytime you see something like “return f(x)” (or, because operators are implemented via special methods, even “return x+y”) in Python, for instance, you've got a tail call.
If it isn't direct or mutual recursion, it has to be a pretty degenerate case to blow the stack even without elimination, so elimination is must necessary for those cases. But other cases bene for from not having the extra memory usage and reducing pushing stuff onto and popping it off of the stack.
How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack? This doesn't appear to be a compelling example to me.
It probably is a shame that it's called tail call optimisation since nobody wants to mandate low level details for an optimisation.
Not that unlikely i'd say, at lest if the stack size is unreasonably small.
For example, on nodejs, JSON.stringify() chokes with a nested array of 10K depth:
> N=10_000; JSON.stringify(JSON.parse("[".repeat(N) + "]".repeat(N)))
Uncaught RangeError: Maximum call stack size exceeded
at JSON.stringify (<anonymous>)
Imagine that you build some software that lets users nest things —e.g., a circuit designer, a visual programming language, a UI builder, etc— and you wanna save these nested structures as JSON, or process them recursively. Pretty natural fit i'd say. Now, as a user, i'd be pretty upset if my magnum opus of a very complex circuit, or giant visual program, or very busy beast of UI art, starts creashing the program when exceeding a mere 10K elements. My computer has gigabytes of memory! And, presumably, there's a lot still available. But nope, a meager stack can ruin all the fun.
I personally think this is a pretty silly limitation to have on software, especially given today's memory sizes.
A state machine is, in fact, a well-understood method of applying structure to spaghetti.
Typically, we'd see the code that implements the logic for each state gathered together. Since this is where the outgoing transitions get decided, the transitions end up being distributed across their originating states.
you define a function with a clause per state (and some other args including the incoming message), and each clause returns a tuple with the new state and some other stuff. the loop is part of the framework, and handles generic otp stuff like updating code in a running system.
well if the same function is in the "tail" it would still apply a tail call elimination.
But a lot of the time tail call eliminiation is only needed in some extreme cases. it can eliminate stack overflow exceptions by a big amount. C#'s new System.Text.Json would greatly benefit with tail call ops, because it often has a call chain that is recursive and does not call itself (its mostly like ReadObject, ReadObjectAsync, ReadObject, ReadBla, ReadObject, etc. and if the object has a ref to itself system.text.json often blows up.
In Java and Scala this thing can btw. also happen (and I've already seen it) however at least you can configure the stack size there and thus most often eliminate the problem somewhat.
it's an edge case, but one that would be cool to fix, since it makes code often more reasonable especially parsers.
In languages like Scala, Java, C#, and Swift, it basically never happens.
Scalaz and cats use tail calls extensively and wouldn't be possible without them.
last [x] = x
last (_:xs) = last xs
last [] = errorEmptyList "last"