...

Tail Recursion -------------- from Me (my brain)

Have proper tail recursion in Python. Would require identifying where a direct function call is returned (could keep it simple and just do it where CALL_FUNCTION and RETURN bytecodes are in a row). Also have to deal with exception catching since that requires the frame to stay alive to handle the exception.

But getting it to work well could help with memory and performance. Don't know if it has been done for a language that had exception handling.

How is this different from stackless?

AFAIK Stackless only curtails the *C* stack, not the chain of Python frames on the heap. But I have a problem with tail recursion. It's generally requested by new converts from the Scheme/Lisp or functional programming world, and it usually means they haven't figured out yet how to write code without using recursion for everything yet. IOW I'm doubtful on how much of a difference it would make for real Python programs (which, simplifying a bit, tend to use loops instead of recursion). And also note that even if an exception is not caught, you'd like to see all stack frames listed when the traceback is printed or when the debugger is invoked. --Guido van Rossum (home page: http://www.python.org/~guido/)

Guido van Rossum wrote:

...

...

Tail Recursion ...

AFAIK Stackless only curtails the *C* stack, not the chain of Python frames on the heap.

Yup.

But I have a problem with tail recursion. It's generally requested by new converts from the Scheme/Lisp or functional programming world, and it usually means they haven't figured out yet how to write code without using recursion for everything yet. IOW I'm doubtful on how much of a difference it would make for real Python programs (which, simplifying a bit, tend to use loops instead of recursion). And also note that even if an exception is not caught, you'd like to see all stack frames listed when the traceback is printed or when the debugger is invoked.

Same here. I'm not for automatic tail recursion detection. A very simple approach, also pretty easy to implement would be a "jump" property, which would be added to a function. It would simply allow to run a different (or the same) function than the current one without returning. def sort3(a, b, c): if a>b: return sort3.jump(b, a, c) if b>c: return sort3.jump(a, c, b) return a, b, c -- Christian Tismer :^) <mailto:tismer@tismer.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/

I mostly agree with everything Guido has said. It probably should only be used when -OO is switched on. And yes, iterative solutions tend to be easier to grasp.

Not always. For example, suppose you want to find out how many (decimal) digits are in a (non-negative) integer. Yes, you could convert it to a string and see how long the string is, but suppose you want to do it directly. Then it is easy to solve the problem recursively by making use of two facts: 1) Non-negative integers less than 10 have one digit. 2) If x > 10, x//10 has one fewer digit than x. These two facts yield the following recursive solution: def numdigits(n): assert n >= 0 and n%1 == 0 if n < 10: return 1 return 1 + numdigits(n//10) An iterative version of this function might look like this: def numdigits(n): assert n >= 0 and n%1 == 0: length = 1 while n >= 10: length += 1 n //= 10 return length Although these two functions are pretty clearly equivalent, I find the recursive one much easier to understand. Moreover, I don't know how to write an interative version that is as easy to understand as the recursive version. Think, for example, how you might go about proving the iterative version correct.

Easy to understand, but it's not tail-recursive, so isn't an example of what was suggested for Brett to investigate. I think a tail-recursive version is more obscure than your iterative one:

def numdigits(n): def inner(n, lensofar): if n < 10: return lensofar else: return inner(n//10, lensofar+1) return inner(n, 1)

Ah. I will agree with you that wholly tail-recursive programs are usually no easier to understand than their iterative counterparts. On the other hand, there are partially tail-recursive functions that I find easier to understand, such as def traverse(t, f): if nonempty(t): traverse(t.left, f) traverse(t.right, f) Here, the second call to traverse is tail-recursive; the first isn't. Of course it could be rewritten this way def traverse(t, f): while nonempty(t): traverse(t.left, f) t = t.right but I think that this rewrite makes the code harder to follow and would prefer that the compiler do it for me.

A different approach makes iteration much more natural: the number of digits in n (>= 0) is the least i >= 1 such that 10**i > n. Then iterative code is an obvious search loop:

i = 1 while 10**i <= n: i += 1 return i

Play strength-reduction tricks to get exponentiation out of the loop, and it's (just) a teensy bit less obvous.

This code relies on 10**i being exact. Is that guaranteed?

[Andrew Koenig]

Ah. I will agree with you that wholly tail-recursive programs are usually no easier to understand than their iterative counterparts.

Good! That's why I've never been keen to "do something" about tail recursion in Python -- the "one obvious way" to write a loop in Python is with a loop <wink>.

On the other hand, there are partially tail-recursive functions that I find easier to understand, such as

def traverse(t, f): if nonempty(t): traverse(t.left, f) traverse(t.right, f)

Here, the second call to traverse is tail-recursive; the first isn't.

Of course it could be rewritten this way

def traverse(t, f): while nonempty(t): traverse(t.left, f) t = t.right

but I think that this rewrite makes the code harder to follow

I agree. Worse still is writing it iteratively with an explicit stack. Note that PEP 255 has both spellings for a tree-walking generator, and the fully iterative spelling is much harder to understand.

would prefer that the compiler do it for me.

I don't in Python: if I coded a call, I want Python to make a call. WYSIWYG contributes greatly to the debuggability of large Python programs in practice.

...

i = 1 while 10**i <= n: i += 1 return i

This code relies on 10**i being exact.

Also on + being exact, and the other code in this thread depended on // being exact.

Is that guaranteed?

+ - * // % ** pow and divmod on integers in Python will either deliver an exact result or raise an exception (like MemoryError if malloc() can't find enough space to hold an intermediate result).

+ - * // % ** pow and divmod on integers in Python will either deliver an exact result or raise an exception (like MemoryError if malloc() can't find enough space to hold an intermediate result).

Except for ** if the exponent is negative. --Guido van Rossum (home page: http://www.python.org/~guido/)

For example, suppose you want to find out how many (decimal) digits are in a (non-negative) integer. Yes, you could convert it to a string and see how long the string is, but suppose you want to do it directly. Then it is easy to solve the problem recursively by making use of two facts:

1) Non-negative integers less than 10 have one digit.

2) If x > 10, x//10 has one fewer digit than x.

These two facts yield the following recursive solution:

def numdigits(n): assert n >= 0 and n%1 == 0 if n < 10: return 1 return 1 + numdigits(n//10)

An iterative version of this function might look like this:

def numdigits(n): assert n >= 0 and n%1 == 0: length = 1 while n >= 10: length += 1 n //= 10 return length

Although these two functions are pretty clearly equivalent, I find the recursive one much easier to understand. Moreover, I don't know how to write an interative version that is as easy to understand as the recursive version. Think, for example, how you might go about proving the iterative version correct.

Hm. The iterative version looks totally fine to me. I wonder if it all depends on the (recursive) definition with which you started. --Guido van Rossum (home page: http://www.python.org/~guido/)

...

Tail Recursion -------------- from Me (my brain)

Have proper tail recursion in Python. Would require identifying where a direct function call is returned (could keep it simple and just do it where CALL_FUNCTION and RETURN bytecodes are in a row). Also have to deal with exception catching since that requires the frame to stay alive to handle the exception.

But getting it to work well could help with memory and performance. Don't know if it has been done for a language that had exception handling.

How is this different from stackless?

AFAIK Stackless only curtails the *C* stack, not the chain of Python frames on the heap. But I have a problem with tail recursion. It's generally requested by new converts from the Scheme/Lisp or functional programming world, and it usually means they haven't figured out yet how to write code without using recursion for everything yet. IOW I'm doubtful on how much of a difference it would make for real Python programs (which, simplifying a bit, tend to use loops instead of recursion). And also note that even if an exception is not caught, you'd like to see all stack frames listed when the traceback is printed or when the debugger is invoked. --Guido van Rossum (home page: http://www.python.org/~guido/)

Guido van Rossum wrote:

...

...

Tail Recursion ...

AFAIK Stackless only curtails the *C* stack, not the chain of Python frames on the heap.

Yup.

But I have a problem with tail recursion. It's generally requested by new converts from the Scheme/Lisp or functional programming world, and it usually means they haven't figured out yet how to write code without using recursion for everything yet. IOW I'm doubtful on how much of a difference it would make for real Python programs (which, simplifying a bit, tend to use loops instead of recursion). And also note that even if an exception is not caught, you'd like to see all stack frames listed when the traceback is printed or when the debugger is invoked.

Same here. I'm not for automatic tail recursion detection. A very simple approach, also pretty easy to implement would be a "jump" property, which would be added to a function. It would simply allow to run a different (or the same) function than the current one without returning. def sort3(a, b, c): if a>b: return sort3.jump(b, a, c) if b>c: return sort3.jump(a, c, b) return a, b, c -- Christian Tismer :^) <mailto:tismer@tismer.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/

I mostly agree with everything Guido has said. It probably should only be used when -OO is switched on. And yes, iterative solutions tend to be easier to grasp.

Not always. For example, suppose you want to find out how many (decimal) digits are in a (non-negative) integer. Yes, you could convert it to a string and see how long the string is, but suppose you want to do it directly. Then it is easy to solve the problem recursively by making use of two facts: 1) Non-negative integers less than 10 have one digit. 2) If x > 10, x//10 has one fewer digit than x. These two facts yield the following recursive solution: def numdigits(n): assert n >= 0 and n%1 == 0 if n < 10: return 1 return 1 + numdigits(n//10) An iterative version of this function might look like this: def numdigits(n): assert n >= 0 and n%1 == 0: length = 1 while n >= 10: length += 1 n //= 10 return length Although these two functions are pretty clearly equivalent, I find the recursive one much easier to understand. Moreover, I don't know how to write an interative version that is as easy to understand as the recursive version. Think, for example, how you might go about proving the iterative version correct.

Easy to understand, but it's not tail-recursive, so isn't an example of what was suggested for Brett to investigate. I think a tail-recursive version is more obscure than your iterative one:

def numdigits(n): def inner(n, lensofar): if n < 10: return lensofar else: return inner(n//10, lensofar+1) return inner(n, 1)

Ah. I will agree with you that wholly tail-recursive programs are usually no easier to understand than their iterative counterparts. On the other hand, there are partially tail-recursive functions that I find easier to understand, such as def traverse(t, f): if nonempty(t): traverse(t.left, f) traverse(t.right, f) Here, the second call to traverse is tail-recursive; the first isn't. Of course it could be rewritten this way def traverse(t, f): while nonempty(t): traverse(t.left, f) t = t.right but I think that this rewrite makes the code harder to follow and would prefer that the compiler do it for me.

A different approach makes iteration much more natural: the number of digits in n (>= 0) is the least i >= 1 such that 10**i > n. Then iterative code is an obvious search loop:

i = 1 while 10**i <= n: i += 1 return i

Play strength-reduction tricks to get exponentiation out of the loop, and it's (just) a teensy bit less obvous.

This code relies on 10**i being exact. Is that guaranteed?

[Andrew Koenig]

Ah. I will agree with you that wholly tail-recursive programs are usually no easier to understand than their iterative counterparts.

Good! That's why I've never been keen to "do something" about tail recursion in Python -- the "one obvious way" to write a loop in Python is with a loop <wink>.

On the other hand, there are partially tail-recursive functions that I find easier to understand, such as

def traverse(t, f): if nonempty(t): traverse(t.left, f) traverse(t.right, f)

Here, the second call to traverse is tail-recursive; the first isn't.

Of course it could be rewritten this way

def traverse(t, f): while nonempty(t): traverse(t.left, f) t = t.right

but I think that this rewrite makes the code harder to follow

I agree. Worse still is writing it iteratively with an explicit stack. Note that PEP 255 has both spellings for a tree-walking generator, and the fully iterative spelling is much harder to understand.

would prefer that the compiler do it for me.

I don't in Python: if I coded a call, I want Python to make a call. WYSIWYG contributes greatly to the debuggability of large Python programs in practice.

...

i = 1 while 10**i <= n: i += 1 return i

This code relies on 10**i being exact.

Also on + being exact, and the other code in this thread depended on // being exact.

Is that guaranteed?

+ - * // % ** pow and divmod on integers in Python will either deliver an exact result or raise an exception (like MemoryError if malloc() can't find enough space to hold an intermediate result).

+ - * // % ** pow and divmod on integers in Python will either deliver an exact result or raise an exception (like MemoryError if malloc() can't find enough space to hold an intermediate result).

Except for ** if the exponent is negative. --Guido van Rossum (home page: http://www.python.org/~guido/)

For example, suppose you want to find out how many (decimal) digits are in a (non-negative) integer. Yes, you could convert it to a string and see how long the string is, but suppose you want to do it directly. Then it is easy to solve the problem recursively by making use of two facts:

1) Non-negative integers less than 10 have one digit.

2) If x > 10, x//10 has one fewer digit than x.

These two facts yield the following recursive solution:

def numdigits(n): assert n >= 0 and n%1 == 0 if n < 10: return 1 return 1 + numdigits(n//10)

An iterative version of this function might look like this:

def numdigits(n): assert n >= 0 and n%1 == 0: length = 1 while n >= 10: length += 1 n //= 10 return length

Although these two functions are pretty clearly equivalent, I find the recursive one much easier to understand. Moreover, I don't know how to write an interative version that is as easy to understand as the recursive version. Think, for example, how you might go about proving the iterative version correct.

Hm. The iterative version looks totally fine to me. I wonder if it all depends on the (recursive) definition with which you started. --Guido van Rossum (home page: http://www.python.org/~guido/)