4 ms·

Why is there even an argument about this? Not being able to make a recursive call without potentially blowing the stack is a major drawback in any language. I

by drblast 15y ago

raganwald 15y ago
Why is there even an argument about this? Not being able to make a recursive call without potentially blowing the stack is a major drawback in any language. I'd venture to say it's a "bug.” You aren’t going to like Python: I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool. http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi... (I’m not advocating this view, just pointing out that there are programmers who appear in all other respects to be reasonable, intelligent, contributing members of computing society who actually feel that TCO is a bug, that 1000 calls ought to be enough for anybody, and so forth.)
- drblast 15y ago
  I don't like this in a lot of languages. But it's not a showstopper, just an annoyance to be aware of. That said, there should be no reason not to have your new modern programming language support tail calls. It's short-sighted, and can negatively affect more than just the trivial recursive case. So, new programming language inventors, if you're reading this, support tail call optimization and proper tail recursion from the beginning. Your language will be better for it.
  - bascule 15y ago
    > there should be no reason not to have your new modern programming language support tail calls There's many valid reasons not to support TCO. The first one that comes to mind: it makes generating stack traces more difficult. Another reason: the JVM doesn't natively support TCO. This means to implement it you'll either need to use a trampoline (e.g. Erjang) or convert recursion to iteration (e.g. Clojure) The latter isn't too difficult, but when tail recursion merely provides an alternate syntax for iteration, and mutual tail recall recursion isn't supported, is there really as much of a point if your language is something like Ruby and already provides multiple means of iteration?
    - gioele 15y ago
      > There's many valid reasons not to support TCO. The first one that comes to mind: it makes generating stack traces more difficult. > Another reason: the JVM doesn't natively support TCO. This means to implement it you'll either need to use a trampoline (e.g. Erjang) or convert recursion to iteration (e.g. Clojure) So you avoid a 35 years old functionality that makes many procedures smaller, faster and more understandable just to make the compilers simpler? Isn't this one of the usual tradeoffs where you (should) prefer having the compiler doing the boring and dirty job of converting a recursion to a loop, with all the bookkeeping of maintaining the state and making it thread-safe, simplifying the life of the application programmer at the expenses of the compiler programmer?
    - anonymoushn 15y ago
      Clojure doesn't really implement tail calls - if you need tail calls for several mutually recursive functions it becomes nontrivial to express because the looping constructs just won't do that for you.
- ken 15y ago
  drblast didn't say TCO was fundamental (just that it's an incredibly useful optimization and there's no reason to omit it), and Guido didn't say TCO is a bug (but that recursion shouldn't be the "basis of all programming"). There are two extremes here, but there is also a huge middle ground, where TCO is implemented but recursion is not the basis for all computation. Some of my favorite compilers do that.
anamax 15y ago
> Not being able to make a recursive call without potentially blowing the stack is a major drawback in any language. I'd venture to say it's a "bug." Recursive calls can blow the stack even with TCO.... I like TCO, but it lends itself to "infinite loops" that aren't as easy to figure out because they're not "local". > And TCO is so handy in so many instances that it's silly not to have it. "So handy" is even more true of lisp macros but .... > And you gain performance. It depends. If you're not doing a lot of interprocedural analysis, you can easily lose performance by writing "TCO-style".
rbehrends 15y ago
That is a bit misleading. Not every recursive function is tail-recursive, and making it tail-recursive will often throw away the benefits of recursion. Take, for example, a simple factorial implementation in OCaml (ignore for the sake of this example that int will overflow for reasonably large values of x, I don't want to complicate the example by using big_int): let rec fact x = if x <= 1 then 1 else x * fact (x-1);; This implementation is not tail-recursive, so tail-call optimization will not help. Now, you can make the function tail-recursive by rewriting it to use a helper function with an accumulator: let fact x = let rec f x a = if x <= 1 then a else f (x-1) * (x-a) in f x 1;; This implementation is tail-recursive; however, this happens at the loss of readability. Furthermore, any such accumulator-based implementation can trivially be converted into a (non-recursive) loop, which is in fact exactly what the compiler will do. Now, if you look at the Hamster library code that inspired the post, you will see the following in hamster/list.rb: def map(&block) return self unless block_given? Stream.new do next self if empty? Sequence.new(yield(head), tail.map(&block)) end end That's not tail-recursive, either, and the author would experience the self-same problems if ruby actually optimized tail calls. He'd have to rewrite his implementation for that. (If you look at OCaml's List.map, you will notice that it is not tail-recursive, either, and you will have to chain List.rev_map and List.rev to get a tail-recursive map.) In short: tail-call optimization is no silver bullet that protects against stack overflow. It's not uncommon for programmers to assume that code is tail-recursive when it, in fact, isn't (which is one reason why Scala, for example, has the @tailrec annotation to let the programmer verify that a function is actually tail-recursive). That does not mean that tail-call optimization is useless even in a procedural or object-oriented language. For example, if you have a language with formal function/procedure/method arguments that cannot be assigned to (that includes not only functional languages, but also Eiffel or Scala, and affects also the implicit self/this argument in any object-oriented language), then the only way to let the garbage collector free objects referenced by these arguments is to drop references to them via a tail call.
- Flow 15y ago
  I think that plain recursive calls that can be TCO'd are not what is interesting about TCO for OO languages... OO without TCO and lambda have a hole in the choices you have to encapsulate and abstract.

by drblast 15y ago

raganwald 15y ago

Why is there even an argument about this? Not being able to make a recursive call without potentially blowing the stack is a major drawback in any language. I'd venture to say it's a "bug.” You aren’t going to like Python: I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool. http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi... (I’m not advocating this view, just pointing out that there are programmers who appear in all other respects to be reasonable, intelligent, contributing members of computing society who actually feel that TCO is a bug, that 1000 calls ought to be enough for anybody, and so forth.)

drblast 15y ago
I don't like this in a lot of languages. But it's not a showstopper, just an annoyance to be aware of. That said, there should be no reason not to have your new modern programming language support tail calls. It's short-sighted, and can negatively affect more than just the trivial recursive case. So, new programming language inventors, if you're reading this, support tail call optimization and proper tail recursion from the beginning. Your language will be better for it.
- bascule 15y ago
  > there should be no reason not to have your new modern programming language support tail calls There's many valid reasons not to support TCO. The first one that comes to mind: it makes generating stack traces more difficult. Another reason: the JVM doesn't natively support TCO. This means to implement it you'll either need to use a trampoline (e.g. Erjang) or convert recursion to iteration (e.g. Clojure) The latter isn't too difficult, but when tail recursion merely provides an alternate syntax for iteration, and mutual tail recall recursion isn't supported, is there really as much of a point if your language is something like Ruby and already provides multiple means of iteration?
  - gioele 15y ago
    > There's many valid reasons not to support TCO. The first one that comes to mind: it makes generating stack traces more difficult. > Another reason: the JVM doesn't natively support TCO. This means to implement it you'll either need to use a trampoline (e.g. Erjang) or convert recursion to iteration (e.g. Clojure) So you avoid a 35 years old functionality that makes many procedures smaller, faster and more understandable just to make the compilers simpler? Isn't this one of the usual tradeoffs where you (should) prefer having the compiler doing the boring and dirty job of converting a recursion to a loop, with all the bookkeeping of maintaining the state and making it thread-safe, simplifying the life of the application programmer at the expenses of the compiler programmer?
  - anonymoushn 15y ago
    Clojure doesn't really implement tail calls - if you need tail calls for several mutually recursive functions it becomes nontrivial to express because the looping constructs just won't do that for you.
ken 15y ago
drblast didn't say TCO was fundamental (just that it's an incredibly useful optimization and there's no reason to omit it), and Guido didn't say TCO is a bug (but that recursion shouldn't be the "basis of all programming"). There are two extremes here, but there is also a huge middle ground, where TCO is implemented but recursion is not the basis for all computation. Some of my favorite compilers do that.

anamax 15y ago

> Not being able to make a recursive call without potentially blowing the stack is a major drawback in any language. I'd venture to say it's a "bug." Recursive calls can blow the stack even with TCO.... I like TCO, but it lends itself to "infinite loops" that aren't as easy to figure out because they're not "local". > And TCO is so handy in so many instances that it's silly not to have it. "So handy" is even more true of lisp macros but .... > And you gain performance. It depends. If you're not doing a lot of interprocedural analysis, you can easily lose performance by writing "TCO-style".

rbehrends 15y ago

That is a bit misleading. Not every recursive function is tail-recursive, and making it tail-recursive will often throw away the benefits of recursion. Take, for example, a simple factorial implementation in OCaml (ignore for the sake of this example that int will overflow for reasonably large values of x, I don't want to complicate the example by using big_int): let rec fact x = if x <= 1 then 1 else x * fact (x-1);; This implementation is not tail-recursive, so tail-call optimization will not help. Now, you can make the function tail-recursive by rewriting it to use a helper function with an accumulator: let fact x = let rec f x a = if x <= 1 then a else f (x-1) * (x-a) in f x 1;; This implementation is tail-recursive; however, this happens at the loss of readability. Furthermore, any such accumulator-based implementation can trivially be converted into a (non-recursive) loop, which is in fact exactly what the compiler will do. Now, if you look at the Hamster library code that inspired the post, you will see the following in hamster/list.rb: def map(&block) return self unless block_given? Stream.new do next self if empty? Sequence.new(yield(head), tail.map(&block)) end end That's not tail-recursive, either, and the author would experience the self-same problems if ruby actually optimized tail calls. He'd have to rewrite his implementation for that. (If you look at OCaml's List.map, you will notice that it is not tail-recursive, either, and you will have to chain List.rev_map and List.rev to get a tail-recursive map.) In short: tail-call optimization is no silver bullet that protects against stack overflow. It's not uncommon for programmers to assume that code is tail-recursive when it, in fact, isn't (which is one reason why Scala, for example, has the @tailrec annotation to let the programmer verify that a function is actually tail-recursive). That does not mean that tail-call optimization is useless even in a procedural or object-oriented language. For example, if you have a language with formal function/procedure/method arguments that cannot be assigned to (that includes not only functional languages, but also Eiffel or Scala, and affects also the implicit self/this argument in any object-oriented language), then the only way to let the garbage collector free objects referenced by these arguments is to drop references to them via a tail call.

Flow 15y ago
I think that plain recursive calls that can be TCO'd are not what is interesting about TCO for OO languages... OO without TCO and lambda have a hole in the choices you have to encapsulate and abstract.