4 ms·

My issue was more about his opposition to recursion than the preference for iteration. That being said, this is one of the better explanations/arguments for wh

My issue was more about his opposition to recursion than the preference for iteration. That being said, this is one of the better explanations/arguments for why iterations are more 'Pythonic' that I've heard. Thanks!

Veedrac 12y ago
Guido is not opposed to recursion per-se, just on basing programming around it. As he says, > TRE only addresses recursion that can easily be replaced by a loop and Python already has a very nice tool for that purpose. I have no doubt that he's fine with many other uses of recursion.
Veedrac 12y ago
Guido is not opposed to recursion per-se, just on basing programming around it. As he says, > TRE only addresses recursion that can easily be replaced by a loop and Python already has a very nice tool for that purpose. I have no doubt that he's fine with many other uses of recursion.
beagle3 12y ago
His opposition to recursion is well founded on the "principle of least surprise" that also underlies Python. Consider, e.g. def len1(list, acc=0): if not list: return acc else: return len1(list[1:],acc+1) def len2(list, acc=0): if not list: return acc else: return len2(list[1:],acc+1) + 0 First one is using only tail calls, and with proper TRE will run on any sized list. The second one will blow up the stack, despite being equivalent in almost every sense, especially in those senses (of "ease of proof") touted as the main reason to use tail recursion in the first place. And while this toy examples is easy to reason about, real world examples require more experience to understand - and Python was always intended at non CS people (and is hugely successful in that mission). Personally, I think the whole discussion is misguided. TRE should be explicit, not some kind of implicit optimization - that is, no TRE/TCO unless you explicity use e.g. a "chain" return keyword: def len3(list, acc=0): if not list: return acc else: chain len1(list[1:],acc+1) This way, a compiler could warn you about a syntax error should you rely on TRE and it is impossible or not available; Same thing could (and should) be done in scheme/lisp etc; It's easy to shoot yourself in the foot with macros and tailcalls in scheme. "chain" might not be the right keyword for this, but I haven't found a better one ("tail-return", "return-only", "continue-with" don't seem any better"; maybe reuse "pass"? e.g. "return pass len1(..)" or "pass return len1(...)"
- jdpage 12y ago
  Tcl added this relatively recently. They use the "tailcall" command, which immediately replaces the stack frame of the current function with one for the new function. If I recall correctly, it doesn't do any checks for whether or not the call is actually a tail-call, so if you do something like return [expr [tailcall foo] + 1] the return and expr simply never get executed, producing incorrect results (which I guess is slightly better than a potential stack overflow, since even the most basic of tests will pick up on the missing +1).
- anon4 12y ago
  I'd use "return from" for tail recursion, to be analogous to "yield from" for iterators. It doesn't add new keywords and "return from foo(...)" seems to me to explain what it does well.
- nostrademons 12y ago
  Actually, if you have a compiler with both TRE and constant folding, len2 will run on any sized list, if the optimizer runs constant folding before TRE or interleaves them. Which I guess is your point, that your program's behavior becomes unreasonably dependent on implementation details. However, I'll point out that this problem occurs in many situations already. In GC languages, a single allocation can trigger a GC that will lock up the CPU for 50-100ms; this is a particular problem with Javascript animations. In non-GC languages (like Python, Objective-C, or C++), you can get release cascades where the destruction of one object causes the reference counts on many others to go to zero, which causes the same problem. A single blocking call will make your server sit idly. Using a library function with O(N) behavior (like, say, string concatenation in many languages) in a loop will make your algorithm accidentally quadratic. Practically speaking, the way we deal with these performance gotchas is to instrument the code heavily, profile, and measure the working system as a whole. I've got some sympathy for the "languages shouldn't have dangerous gotchas" viewpoint, but I think that most of the time it ultimately results in premature micro-optimizations.
  - beagle3 12y ago
    > Which I guess is your point, that your program's behavior becomes unreasonably dependent on implementation details. Exactly. > Practically speaking, the way we deal with these performance gotchas is to instrument the code heavily, profile, and measure the working system as a whole. Yes, but that's the wrong way to deal with it. Especially with today's giant memories, you might run testing on a 512GB machine with a billion element list, not realize there's no TRE and it will fail on a machine with "only" 64GB of memory that is perfectly capable of running the same computation if TRE/TCO was done (but wasn't). I want simple-to-remember-and-use semantics, and implicitly relying on tail recursion semantics does not provide it. O() guarantees are enough (and should be properly documented) - I don't need deterministic time or space guarantees beyond order-of-magnitude precision. If you need deterministic timing in the 100ms range, most programming languages are not for you. If you need them within 10ms, most operating systems aren't. And if you need them within 100us, most CPUs aren't. Summing up my 23 years of Python experience, noticeable pauses due to release cascades are extremely uncommon (unlike Javascript / Java pauses) - unlike Java/Javascript, with the exception of free() and a few minor loops, everything that runs is of _your_ making, which makes it easier to reason about and control. And back to the subject: My "chain" (or whatever) suggestion above, which I (and others) have made numerous times is basically a static-vs-dynamic typing assertion about how a subroutine uses the call stack at that point: "need it later", "don't need it later". Even for a dynamic language like Python, it makes sense to make this static because it cannot change with argument types. The incoming call stack can either be dropped at a location, or not, independent of inputs. I am surprised it is often countered (as you did here) with "yes, but we can test it so it's not a big deal". It's not a big deal, but it is also comes at basically no cost, AND makes a requirement self-describing and easily verifiable by a static compiler.

Veedrac 12y ago

Guido is not opposed to recursion per-se, just on basing programming around it. As he says, > TRE only addresses recursion that can easily be replaced by a loop and Python already has a very nice tool for that purpose. I have no doubt that he's fine with many other uses of recursion.

Veedrac 12y ago

beagle3 12y ago

His opposition to recursion is well founded on the "principle of least surprise" that also underlies Python. Consider, e.g. def len1(list, acc=0): if not list: return acc else: return len1(list[1:],acc+1) def len2(list, acc=0): if not list: return acc else: return len2(list[1:],acc+1) + 0 First one is using only tail calls, and with proper TRE will run on any sized list. The second one will blow up the stack, despite being equivalent in almost every sense, especially in those senses (of "ease of proof") touted as the main reason to use tail recursion in the first place. And while this toy examples is easy to reason about, real world examples require more experience to understand - and Python was always intended at non CS people (and is hugely successful in that mission). Personally, I think the whole discussion is misguided. TRE should be explicit, not some kind of implicit optimization - that is, no TRE/TCO unless you explicity use e.g. a "chain" return keyword: def len3(list, acc=0): if not list: return acc else: chain len1(list[1:],acc+1) This way, a compiler could warn you about a syntax error should you rely on TRE and it is impossible or not available; Same thing could (and should) be done in scheme/lisp etc; It's easy to shoot yourself in the foot with macros and tailcalls in scheme. "chain" might not be the right keyword for this, but I haven't found a better one ("tail-return", "return-only", "continue-with" don't seem any better"; maybe reuse "pass"? e.g. "return pass len1(..)" or "pass return len1(...)"

jdpage 12y ago
Tcl added this relatively recently. They use the "tailcall" command, which immediately replaces the stack frame of the current function with one for the new function. If I recall correctly, it doesn't do any checks for whether or not the call is actually a tail-call, so if you do something like return [expr [tailcall foo] + 1] the return and expr simply never get executed, producing incorrect results (which I guess is slightly better than a potential stack overflow, since even the most basic of tests will pick up on the missing +1).
anon4 12y ago
I'd use "return from" for tail recursion, to be analogous to "yield from" for iterators. It doesn't add new keywords and "return from foo(...)" seems to me to explain what it does well.
nostrademons 12y ago
Actually, if you have a compiler with both TRE and constant folding, len2 will run on any sized list, if the optimizer runs constant folding before TRE or interleaves them. Which I guess is your point, that your program's behavior becomes unreasonably dependent on implementation details. However, I'll point out that this problem occurs in many situations already. In GC languages, a single allocation can trigger a GC that will lock up the CPU for 50-100ms; this is a particular problem with Javascript animations. In non-GC languages (like Python, Objective-C, or C++), you can get release cascades where the destruction of one object causes the reference counts on many others to go to zero, which causes the same problem. A single blocking call will make your server sit idly. Using a library function with O(N) behavior (like, say, string concatenation in many languages) in a loop will make your algorithm accidentally quadratic. Practically speaking, the way we deal with these performance gotchas is to instrument the code heavily, profile, and measure the working system as a whole. I've got some sympathy for the "languages shouldn't have dangerous gotchas" viewpoint, but I think that most of the time it ultimately results in premature micro-optimizations.
- beagle3 12y ago
  > Which I guess is your point, that your program's behavior becomes unreasonably dependent on implementation details. Exactly. > Practically speaking, the way we deal with these performance gotchas is to instrument the code heavily, profile, and measure the working system as a whole. Yes, but that's the wrong way to deal with it. Especially with today's giant memories, you might run testing on a 512GB machine with a billion element list, not realize there's no TRE and it will fail on a machine with "only" 64GB of memory that is perfectly capable of running the same computation if TRE/TCO was done (but wasn't). I want simple-to-remember-and-use semantics, and implicitly relying on tail recursion semantics does not provide it. O() guarantees are enough (and should be properly documented) - I don't need deterministic time or space guarantees beyond order-of-magnitude precision. If you need deterministic timing in the 100ms range, most programming languages are not for you. If you need them within 10ms, most operating systems aren't. And if you need them within 100us, most CPUs aren't. Summing up my 23 years of Python experience, noticeable pauses due to release cascades are extremely uncommon (unlike Javascript / Java pauses) - unlike Java/Javascript, with the exception of free() and a few minor loops, everything that runs is of _your_ making, which makes it easier to reason about and control. And back to the subject: My "chain" (or whatever) suggestion above, which I (and others) have made numerous times is basically a static-vs-dynamic typing assertion about how a subroutine uses the call stack at that point: "need it later", "don't need it later". Even for a dynamic language like Python, it makes sense to make this static because it cannot change with argument types. The incoming call stack can either be dropped at a location, or not, independent of inputs. I am surprised it is often countered (as you did here) with "yes, but we can test it so it's not a big deal". It's not a big deal, but it is also comes at basically no cost, AND makes a requirement self-describing and easily verifiable by a static compiler.