The other comment I’d make is C’s malloc and free are equally broken, since most things you might choose to do with a malloc() that returns null (eg. printf'ing an error message) are quite likely to attempt to malloc() something.
Not to mention by the time malloc() returns null, unless your sysadmin has set some harsh rlimits, your system has turn into a swappy bowl of sludge.
The erlang approach of “let it crash” and let the parent process do something sane with the mess is have better.
While I can see the author’s argument in a practical sense, many languages allow expressing recursion without this cost. It’s not that recursion is the problem, it’s that many popular languages have decided to implement function calls in a silly way.
I think, another problem, is that all languages I have used treat ‘stack’ allocation as an operation that will always succeed. There is a practical reason for this, but it’s a dirty lie that hits you in unfortunate situations. The way to get around this described in the post is really ugly and not something you’d ever want to run in production unless maybe if your language run-time did it for you.
The alternate is tail call optimization, which since Stallman is a lispy type of person, has been around since early versions of gcc.
My only beef with relying on tail call optimization is it is very easy to get it wrong…. and the only way to be absolutely certain you did it right is to inspect the assembler produced.
My only beef with relying on tail call optimization is it is very easy to get it wrong…. and the only way to be absolutely certain you did it right is to inspect the assembler produced.
Do you mean in C it’s easy to get wrong? It’s fairly easy to identify a tail call, it’s just that C doesn’t enforce the frame to be compiled away.
If you stop and think awhile about it, you can spot it is or isn’t a tail call.
The point is you have to stop and think.
The difference between a recursive routine that uses a trivial amount of stack and one that blows the stack is very minor and easily created by a minor change by a maintainer.
I cannot speak for the general case, but in my experience as someone who has written a fair amount of code in languages that guarantee tail calls and those that don’t, this has never been an actual problem. Determining if a function has a tail call is a straight forward mechanical operation. In terms of costs in understanding a problem, if something is tail recursive has never been one and, again in my experience, has reduced costs elsewhere for an overall positive effect.
Have you actually experienced this in production enough to be a problem or is it a general concern you have?
I just have a flag in my mind the (relatively few) times I have seen recursion in C, when I have peeked at the disassembly, TCO wasn’t happening until I tweaked the code somewhat. (Usually that somewhat irritating “helper” function split)
In C it’s a different beast because the language spec does not require a tail call convention. That is why I asked at the beginning if you meant specifically in C or tail calls in general.
For the scheme code, yes that is what you do. Are you pointing that out or are you saying that the non-tail-call implementation of tail is difficult to determine if it is a tail call? In Scheme, especially, it should be pretty obvious that the first implementation is not a tail call.
The C language spec does not guarantee proper tail calls, so I would not depend on it at all. In languages which do guarantee it (Erlang, Haskell, Ocaml, Scheme, …) I have not found it to be a problem at all. On the scale of “what’s hard about programming”, determining if a program ends with a function call or not is pretty low compared to other sources of bugs, like determining if a loop condition is correct. In Erlang, one has no choice but to write code with tail calls, and it doesn’t seem to be a problem.
The other comment I’d make is C’s malloc and free are equally broken, since most things you might choose to do with a malloc() that returns null (eg. printf'ing an error message) are quite likely to attempt to malloc() something.
Not to mention by the time malloc() returns null, unless your sysadmin has set some harsh rlimits, your system has turn into a swappy bowl of sludge.
The erlang approach of “let it crash” and let the parent process do something sane with the mess is have better.
While I can see the author’s argument in a practical sense, many languages allow expressing recursion without this cost. It’s not that recursion is the problem, it’s that many popular languages have decided to implement function calls in a silly way.
I think, another problem, is that all languages I have used treat ‘stack’ allocation as an operation that will always succeed. There is a practical reason for this, but it’s a dirty lie that hits you in unfortunate situations. The way to get around this described in the post is really ugly and not something you’d ever want to run in production unless maybe if your language run-time did it for you.
The alternate is tail call optimization, which since Stallman is a lispy type of person, has been around since early versions of gcc.
My only beef with relying on tail call optimization is it is very easy to get it wrong…. and the only way to be absolutely certain you did it right is to inspect the assembler produced.
Do you mean in C it’s easy to get wrong? It’s fairly easy to identify a tail call, it’s just that C doesn’t enforce the frame to be compiled away.
If you stop and think awhile about it, you can spot it is or isn’t a tail call.
The point is you have to stop and think.
The difference between a recursive routine that uses a trivial amount of stack and one that blows the stack is very minor and easily created by a minor change by a maintainer.
I cannot speak for the general case, but in my experience as someone who has written a fair amount of code in languages that guarantee tail calls and those that don’t, this has never been an actual problem. Determining if a function has a tail call is a straight forward mechanical operation. In terms of costs in understanding a problem, if something is tail recursive has never been one and, again in my experience, has reduced costs elsewhere for an overall positive effect.
Have you actually experienced this in production enough to be a problem or is it a general concern you have?
I just have a flag in my mind the (relatively few) times I have seen recursion in C, when I have peeked at the disassembly, TCO wasn’t happening until I tweaked the code somewhat. (Usually that somewhat irritating “helper” function split)
Here’s a classic example in Scheme of the obvious “simple” recursive version is tail-call… and the solution of splitting it into two functions. http://stackoverflow.com/questions/310974/what-is-tail-call-optimization
In C it’s a different beast because the language spec does not require a tail call convention. That is why I asked at the beginning if you meant specifically in C or tail calls in general.
For the scheme code, yes that is what you do. Are you pointing that out or are you saying that the non-tail-call implementation of
tailis difficult to determine if it is a tail call? In Scheme, especially, it should be pretty obvious that the first implementation is not a tail call.As I say, it’s been in gcc since year dot.
Yet unless people may focused attention to it, they write code that isn’t tail call. Even those people who understand TCO.
ie. It’s a monkey level problem, not a compiler level one.
The compiler could help, for example if you could annotate something as tail call and the compiler had a warning that kicks you if it isn’t.
The C language spec does not guarantee proper tail calls, so I would not depend on it at all. In languages which do guarantee it (Erlang, Haskell, Ocaml, Scheme, …) I have not found it to be a problem at all. On the scale of “what’s hard about programming”, determining if a program ends with a function call or not is pretty low compared to other sources of bugs, like determining if a loop condition is correct. In Erlang, one has no choice but to write code with tail calls, and it doesn’t seem to be a problem.