Interestingly, according to the article, Elm can’t tail-call optimize calls appearing in boolean logic operators like && or ||. I just ported its simple example over to OCaml:
let rec is_prefix_of prefix list = match prefix, list with
| [], _ -> true
| _ :: _, [] -> false
| p :: ps, x :: xs -> p = x && is_prefix_of ps xs
And checked its compiled output with the BuckleScript (now ReScript) compiler, and this is turned into a while loop (i.e., tail-call optimized).
In my experience, TCO is often relied on for correct behavior as opposed to just being bonus performance. That means the following is a pretty significant downside!
But since it is only applied under certain circumstances, the downside of is that when it is not applied, we won’t be made aware of it unless we check for it.
Are there any plans to add some sort of syntax to indicate to the compiler that it should error if it can’t perform TCO? OCaml has @tailcall for this purpose and Scala has @tailrec, although in Scala’s case the compiler won’t even try to do TCO unless you request it.
Maybe my coffee hasn’t fully kicked in yet, or maybe it’s been too long since I’ve programmed in a proper functional language, but how or when would TCO change behavior?
One example that comes to mind: TCO can be the difference between “calling this function with these arguments always returns the correct answer” and “calling this function with these arguments sometimes returns the correct answer, and sometimes crashes with a stack overflow.”
If running out of stack frames and/or stack memory counts as making a function partial, then does the OS possibly running out of memory mean that no functions are ever total?
Right? Since “the stack” isn’t an explicit abstraction in most programming languages, I don’t think it’s quite correct/useful to say that a recursive function is partial when it can’t be TCO’d.
I don’t think it’s out of bounds to say that. It really depends on the conceptual model that your language is providing. For example, it seems to be an operating principle of zig: every function in the stdlib that allocates takes an allocator so you can handle out of memory exceptions intelligently.
But, I get your point: it isn’t an explicit part of the conceptual model of most languages so it’s shifting the window a bit to refer to non-TCO functions as partial. I think it’s potentially useful perspective and, for what it’s worth, most languages don’t really describe their functions as total/partial anyways.
Recursion in a language without TCO feels like a fool’s errand. Source: I tried to implement some recursive algorithms in C…. on 16-bit Windows. On a modern CPU, you can probably get away with recursion even if it eats stack, because you have virtual memory and a shitload of address space to recurse into. Not so much on a 286….
Often, if the recursion depth is large enough, the unoptimized version uses a lot of stack space, even potentially an unbounded amount, where the optimized version uses constant space.
So the unoptimized version is not only slower but actually crashes if the stack is used up.
Hmm. I assumed that “bonus performance” would include memory usage. And I would’ve lumped the resulting stack overflow in with “performance” concern, but I guess I can see how that might actually be considered behavior since the “optimized” version will complete and an unoptimized version might not.
It’s just weird because I don’t think anybody would tell me that putting an extra private field that I never use on a class would be a “behavior change” even though that makes my class use more memory and therefore will OOM on some algorithms when it might not OOM if I remove the field.
An additional private field in a class that is used a million times on the stack might be similar, true. The heap may often be bigger (citation needed).
With recursive calls, you can use up a lot of memory for innocent looking code that e.g. just sums up a list of integers.
Interestingly, according to the article, Elm can’t tail-call optimize calls appearing in boolean logic operators like
&&or||. I just ported its simple example over to OCaml:And checked its compiled output with the BuckleScript (now ReScript) compiler, and this is turned into a
whileloop (i.e., tail-call optimized).In my experience, TCO is often relied on for correct behavior as opposed to just being bonus performance. That means the following is a pretty significant downside!
Are there any plans to add some sort of syntax to indicate to the compiler that it should error if it can’t perform TCO? OCaml has
@tailcallfor this purpose and Scala has@tailrec, although in Scala’s case the compiler won’t even try to do TCO unless you request it.Also: how does Elm handle source maps for TCO functions? As I recall, increased debugging difficulty was one of the reason V8 backed out of automatically doing TCE (and switched to backing explicit tail calls instead).
The article buries the lede, but it’s exactly announcement of a tool that checks Elm code for TCO.
Maybe my coffee hasn’t fully kicked in yet, or maybe it’s been too long since I’ve programmed in a proper functional language, but how or when would TCO change behavior?
One example that comes to mind: TCO can be the difference between “calling this function with these arguments always returns the correct answer” and “calling this function with these arguments sometimes returns the correct answer, and sometimes crashes with a stack overflow.”
Put slightly differently, TCO makes some partial functions total.
If running out of stack frames and/or stack memory counts as making a function partial, then does the OS possibly running out of memory mean that no functions are ever total?
Right? Since “the stack” isn’t an explicit abstraction in most programming languages, I don’t think it’s quite correct/useful to say that a recursive function is partial when it can’t be TCO’d.
I don’t think it’s out of bounds to say that. It really depends on the conceptual model that your language is providing. For example, it seems to be an operating principle of zig: every function in the stdlib that allocates takes an allocator so you can handle out of memory exceptions intelligently.
But, I get your point: it isn’t an explicit part of the conceptual model of most languages so it’s shifting the window a bit to refer to non-TCO functions as partial. I think it’s potentially useful perspective and, for what it’s worth, most languages don’t really describe their functions as total/partial anyways.
Recursion in a language without TCO feels like a fool’s errand. Source: I tried to implement some recursive algorithms in C…. on 16-bit Windows. On a modern CPU, you can probably get away with recursion even if it eats stack, because you have virtual memory and a shitload of address space to recurse into. Not so much on a 286….
I definitely agree! I never, ever, write recursive code in a language that doesn’t have a way to at least opt-in to recursion optimization.
But to me, that’s still “performance” and not really “behavior”. But maybe I’m defining these things a little differently.
Not sure if @harpocrates meant this but:
Often, if the recursion depth is large enough, the unoptimized version uses a lot of stack space, even potentially an unbounded amount, where the optimized version uses constant space.
So the unoptimized version is not only slower but actually crashes if the stack is used up.
Hmm. I assumed that “bonus performance” would include memory usage. And I would’ve lumped the resulting stack overflow in with “performance” concern, but I guess I can see how that might actually be considered behavior since the “optimized” version will complete and an unoptimized version might not.
It’s just weird because I don’t think anybody would tell me that putting an extra private field that I never use on a class would be a “behavior change” even though that makes my class use more memory and therefore will OOM on some algorithms when it might not OOM if I remove the field.
An additional private field in a class that is used a million times on the stack might be similar, true. The heap may often be bigger (citation needed).
With recursive calls, you can use up a lot of memory for innocent looking code that e.g. just sums up a list of integers.