4 ms·
> Why don't languages give tail calls their own syntax rather than making it an optimization? Grumpy old man answer: because if you need "special syntax" to ex
by ajross 9y ago
> Why don't languages give tail calls their own syntax rather than making it an optimization?
Grumpy old man answer: because if you need "special syntax" to express the fact that your recursively defined function can technically be evaluated in constant stack space, you probably should be writing it as an iterative function to begin with.
The whole point about recursion as a software engineering paradigm is that it's a clearer way to express the problem and thus less likely to be mistakenly implemented. Special syntax is the opposite of clear.
Iteration ain't that hard either folks, and it has the notable advantage of mapping more obviously to the behavior of actual machines we use to execute our code.
- catnaroek 9y agoStructured looping constructs are rather removed from how a machine works - not that this is inherently a bad thing. The way it actually works in a physical machine is via jumps into code that has already run, i.e. self-reference, i.e. recursion.
- adrianratnapala 9y agoMy way of saying the same thing is that there is surprisingly little difference between the recursive and iterative models when you start breaking things down. Indeed, if I were to add an explicit tail syntax to some language, it would probably involve the "goto" keyword.
- ajross 9y agoA loop can be turned into branch-based code with an absolutely trivial transformation (e.g. evaluate the test, branch to the end if false, branch back to the start at the end), I don't quite know what you mean by that. 3GL compilers were available with working looping syntax within years of the first programmable computers. FIVE decades later, and as this thread proves, we still don't have general algorithms to turn recursive solutions into iterative ones at the compiler level. It's true that it's more abstracted than machine code. It's absoultely not true that it's equivalently complicated to tail recursion detection.
- catnaroek 9y ago> It's absoultely not true that it's equivalently complicated to tail recursion detection. Tail recursion doesn't need to be “detected”. The correct implementation of all tail calls, recursive or otherwise, is to overwrite the current activation record, rather than save it.
- goialoq 9y agoHow is a keyword (such as OCaml's 'rec') less clear than rewriting the whole function in an iterative form, with junk like temporary loop variables? > mapping more obviously to the behavior of actual machines we use to execute our code. There's a reason we usually don't write in assembly.
- Spivak 9y agoShould the compiler do what you mean or do what you say? Is it good design to have a system where your code only works because the compiler was able to recognize an optimization? Why not make it explicit?
- ernst_klim 9y ago>Why not make it explicit Because we want programming languages to hide the hardware complexity behind elaborated semantics. Programming languages are for humans, not for machines.
- mikebenfield 9y ago> because if you need "special syntax" to express the fact that your recursively defined function can technically be evaluated in constant stack space, you probably should be writing it as an iterative function to begin with. Why? I find recursive functions are often simpler to understand and write than iteration. Why does the compiler need to stop me from doing so? You write "technically" as though it were just an obscure technicality that it's possible to implement a function call without taking up excessive stack space, but to my mind it's a fundamental fact. > Iteration ain't that hard either folks, and it has the notable advantage of mapping more obviously to the behavior of actual machines we use to execute our code. In what sense is this true? Recursive function: update these variables (in registers or memory) and jump back up to this instruction. Iteration: update this variable and jump back up to this instruction.
- Spivak 9y agoIt is an obscure technicality: your code only works because a compiler optimization makes it work. If a different compiler executed your code exactly as written it would crash. Or another way, two pieces of code that are logically equivalent will succeed or crash depending on whether it's written in such a way that the compiler can recognize an optimization. I'm in favor of having special syntax because compilers shouldn't really be in the business of 'do what I mean not what I say'.
- nybble41 9y agoDespite the name "tail call optimization", the proper implementation of tail calls is not "just" an optimization. Preserving a stack frame for a function which has nothing left to do is incorrect behavior on the part of the compiler which negatively impacts both the time and space complexity of the resulting object code. The code, as written, does not require a stack frame. If the compiled object code crashes it is not because it was executed "exactly as written", but because the compiler inserted something beyond what was written. The Scheme approach of mandating the use of tail calls for every call which occurs in "tail position" is the correct one, in my opinion.
- 9y ago