6 ms·

The iterative version's magic can be explained by Tail Recursion Elimination. Python creator Guido's post on why he left it out of Python might be an interestin

by arocks 14y ago

The iterative version's magic can be explained by Tail Recursion Elimination. Python creator Guido's post on why he left it out of Python might be an interesting read: http://neopythonic.blogspot.in/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.in/2009/04/tail-recursion-elimin...

pmelendez 14y ago
This is so far my biggest disagreement with Guido and Python. Comments like "Third, I don't believe in recursion as the basis of all programming." and recursion "is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool." Makes me wonder how long he was exposed to Scheme. For me, programming in Scheme is a wonderful experience, way more pleasant that in Python. In Scheme is really clear what is an efficient or inefficient piece of code. Rather in Python, where I found myself going back and forward trying to figuring out what is happening behind the scenes to see if I can do it in a more efficient way. Don't get me wrong, I will take a slow Python against something faster like Java any day. But I have Scheme in the top of my preferences and that hasn't changed since 17 years ago when I was introduced to Scheme for first time.
- xradionut 14y ago
  I'm not missing Scheme-like recursion from Python that much since Guido borrowed features from Icon and other languages that helps me do much of the crap that used require nasty loops. (Love me some iterators!)
  - pi18n 14y ago
    Iterators are great! I think I prefer thinking in terms of recursion because it helps me break it into subproblems better. That doesn't invalidate anyone's preference for iterators or generators. And you Python devs have nice list comprehensions as well, so I don't doubt that you have no real need for recursion. But I will say it seems really weird to me to refuse tail-call recursion flat out. People even do it in C as an optimization (http://llvm.org/docs/Passes.html#tailcallelim-tail-call-elimination http://llvm.org/docs/Passes.html#tailcallelim-tail-call-elim...).
  - chongli 14y ago
    Maybe not, but perhaps you'll later run into something you are missing from the language and Guido (PBUH) won't add add it. With Lisp (incl. Scheme), you can add it yourself.
    - xradionut 14y ago
      I like Scheme, but I have this desire to be productive without reinventing the wheel or most of the automobile. If it's not in the core Python language, chances are it's a feature in one the almost infinite selection of third party modules. Or can be done in C and called from Python.
      - cygwin98 14y ago
        Maybe you should give Clojure a try, which is a pragmatic Lisp in my opinion. You don't have to reinvent the wheel most of the time since you have access to a vast array of Java libraries.
        takeoutweight 14y ago
        Unfortunately Clojure is one of the few lisps without proper tail calls. (I love Clojure I just thought I should point this out in the context of the discussion).
        chongli 14y ago
        >Unfortunately Clojure is one of the few lisps without proper tail calls. (I love Clojure I just thought I should point this out in the context of the discussion). Fortunately, thanks to Clojure being a Lisp, you can add it yourself: https://github.com/cjfrisz/clojure-tco https://github.com/cjfrisz/clojure-tco
        S4M 14y ago
        Thank you for posting this! I wanted for a long time to see a concrete example of adding a feature to a Lisp language, I will study that code.
  - deleted 14y ago
    [deleted]
- zem 14y ago
  this was amusing: https://twitter.com/gvanrossum/status/1838308947 https://twitter.com/gvanrossum/status/1838308947
- MostAwesomeDude 14y ago
  Uh, recursion doesn't have to be the basis of computation. It certainly can be, but it's not how you have to think of stuff. Iterative algorithms are perfectly cromulent.
bitwize 14y ago
Guido mentions that you can't get an accurate stack trace in the presence of tail-call optimization. That alone makes it an absolute no-go for just about ANY production code (where ease of debugging is orders of magnitude more important than ease of writing in the first place).
- pmelendez 14y ago
  I think you could chose a better analogy. In any production code I would rather prefer performance than debugging. Isn't that the point why C/C++ programmers have debug and release configurations? to turn off debugging features on a production code?
- klibertp 14y ago
  But it's not true. As someone said in the comments below Guido's post, providing meaningful stack traces in presence of TCO is possible, it just requires a little more bookkeeping on language part.
- raganwald 14y ago
  That makes it sound like a. you can never get an accurate stack trace, and 2. the stack traces you do get that are "inaccurate" are worthless. I can't speak to every optimizing interpreter or compiler, but in the few that I've used, TCO doesn't do anything to code that doesn't have tail calls, so lots of the code has "accurate" stack traces. And when it does perturb the stack trace, it does so in a very obvious way, it abbreviates the tail calls. Such stack traces no longer have a 1:1 mapping with the function "calls," but are still quite informative for debugging purposes. Not as informative as they would be if you turn TCO off just to debug that code, but informative enough that I rarely had to turn it off.
  - snprbob86 14y ago
    Never mind the fact that tail cails are just fundamentally loops, which don't generate any stack frames anyway! If you're application is complex enough that inspection won't reveal the source of the bug, then stack traces are almost strictly less useful than logging.

by arocks 14y ago

pmelendez 14y ago

This is so far my biggest disagreement with Guido and Python. Comments like "Third, I don't believe in recursion as the basis of all programming." and recursion "is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool." Makes me wonder how long he was exposed to Scheme. For me, programming in Scheme is a wonderful experience, way more pleasant that in Python. In Scheme is really clear what is an efficient or inefficient piece of code. Rather in Python, where I found myself going back and forward trying to figuring out what is happening behind the scenes to see if I can do it in a more efficient way. Don't get me wrong, I will take a slow Python against something faster like Java any day. But I have Scheme in the top of my preferences and that hasn't changed since 17 years ago when I was introduced to Scheme for first time.

xradionut 14y ago
I'm not missing Scheme-like recursion from Python that much since Guido borrowed features from Icon and other languages that helps me do much of the crap that used require nasty loops. (Love me some iterators!)
- pi18n 14y ago
  Iterators are great! I think I prefer thinking in terms of recursion because it helps me break it into subproblems better. That doesn't invalidate anyone's preference for iterators or generators. And you Python devs have nice list comprehensions as well, so I don't doubt that you have no real need for recursion. But I will say it seems really weird to me to refuse tail-call recursion flat out. People even do it in C as an optimization (http://llvm.org/docs/Passes.html#tailcallelim-tail-call-elimination http://llvm.org/docs/Passes.html#tailcallelim-tail-call-elim...).
- chongli 14y ago
  Maybe not, but perhaps you'll later run into something you are missing from the language and Guido (PBUH) won't add add it. With Lisp (incl. Scheme), you can add it yourself.
  - xradionut 14y ago
    I like Scheme, but I have this desire to be productive without reinventing the wheel or most of the automobile. If it's not in the core Python language, chances are it's a feature in one the almost infinite selection of third party modules. Or can be done in C and called from Python.
    - cygwin98 14y ago
      Maybe you should give Clojure a try, which is a pragmatic Lisp in my opinion. You don't have to reinvent the wheel most of the time since you have access to a vast array of Java libraries.
      - takeoutweight 14y ago
        Unfortunately Clojure is one of the few lisps without proper tail calls. (I love Clojure I just thought I should point this out in the context of the discussion).
      - chongli 14y ago
        >Unfortunately Clojure is one of the few lisps without proper tail calls. (I love Clojure I just thought I should point this out in the context of the discussion). Fortunately, thanks to Clojure being a Lisp, you can add it yourself: https://github.com/cjfrisz/clojure-tco https://github.com/cjfrisz/clojure-tco
        S4M 14y ago
        Thank you for posting this! I wanted for a long time to see a concrete example of adding a feature to a Lisp language, I will study that code.
- deleted 14y ago
  [deleted]
zem 14y ago
this was amusing: https://twitter.com/gvanrossum/status/1838308947 https://twitter.com/gvanrossum/status/1838308947
MostAwesomeDude 14y ago
Uh, recursion doesn't have to be the basis of computation. It certainly can be, but it's not how you have to think of stuff. Iterative algorithms are perfectly cromulent.

bitwize 14y ago

Guido mentions that you can't get an accurate stack trace in the presence of tail-call optimization. That alone makes it an absolute no-go for just about ANY production code (where ease of debugging is orders of magnitude more important than ease of writing in the first place).

pmelendez 14y ago
I think you could chose a better analogy. In any production code I would rather prefer performance than debugging. Isn't that the point why C/C++ programmers have debug and release configurations? to turn off debugging features on a production code?
klibertp 14y ago
But it's not true. As someone said in the comments below Guido's post, providing meaningful stack traces in presence of TCO is possible, it just requires a little more bookkeeping on language part.
raganwald 14y ago
That makes it sound like a. you can never get an accurate stack trace, and 2. the stack traces you do get that are "inaccurate" are worthless. I can't speak to every optimizing interpreter or compiler, but in the few that I've used, TCO doesn't do anything to code that doesn't have tail calls, so lots of the code has "accurate" stack traces. And when it does perturb the stack trace, it does so in a very obvious way, it abbreviates the tail calls. Such stack traces no longer have a 1:1 mapping with the function "calls," but are still quite informative for debugging purposes. Not as informative as they would be if you turn TCO off just to debug that code, but informative enough that I rarely had to turn it off.
- snprbob86 14y ago
  Never mind the fact that tail cails are just fundamentally loops, which don't generate any stack frames anyway! If you're application is complex enough that inspection won't reveal the source of the bug, then stack traces are almost strictly less useful than logging.