A new module for performing tail-call elimination

[Steven D'Aprano]

On Thu, 16 Jul 2015 08:41 pm, Antoon Pardon wrote:

> On 07/16/2015 10:07 AM, Steven D'Aprano wrote:
>> On Wednesday 15 July 2015 19:29, Antoon Pardon wrote:
>>
>>> Suppose I start with the following:
>>>
>>> def even(n):
>>>     True if n == 0 else odd(n - 1)
>>>
>>> def odd(n):
>>>     False if n == 0 else even(n - 1)
>> Well, both of those always return None, so can be optimized to:
>>
>> even = odd = lambda x: None
>>
>> :-)
>>
>> Fixing the obvious mistake (failing to return anything) leads to the next
>> mistake. When all you have is a hammer, everything looks like a nail.
>>
>> def even(n):
>>     return n%2 == 0
>>
>> def odd(n):
>>     return n%2 != 0
>>
>>
>> are faster, easier to understand, and don't turn into an infinite loop if
>> you pass a negative integer.
> 
> Nice of you to illustrate how being pedantic about something, can
> make a response useless with regard to the intended original question.

Just because your intention in giving that code was X, doesn't mean that
others cannot use that code to also do Y.

Your example of a mutually recursive pair of functions is perfectly fine as
a toy example to demonstrate a point. But the fact that people can only
come up with toy examples to demonstrate the uses of unbounded recursion is
telling. That's *my* point. It's orthogonal to your point.


> Sure your implementation for solving this particular problem is better
> if the purpose is to actually solve this problem. But it is useless as
> an illustration for the question I'm asking, which was about how to
> use a particular module.

True. But my comment doesn't stop the OP from answering your question. A
single post can lead to multiple replies you know :-)


>> The point is, people keep insisting that there are a vast number of
>> algorithms which are best expressed using recursion and which require TCO
>> to be practical, and yet when asked for examples they either can't give
>> any examples at all, or they give examples that are not well-suited to
>> recursion. Or, at best, examples which are equally good when written
>> either using recursion or iteration.
> 
> So what did you expect? That I should give a real world example here with
> lots of details that would only detract from the information I'm looking
> for, just so that your curiosity would be satisfied?

A non-toy example would be nice. There are non-toy examples of recursion
which are still simple enough to express in a few lines, like the usual
recursive algorithm for inorder traversal of a binary tree:

def inorder(node):
    if node is not None:
        inorder(node.left)
        visit(node.data)
        inorder(node.right)


If you can't come up with a non-toy example of mutual recursion, then
something which is *obviously* useless is better than something
useful-looking but actually a poor example of recursion.

To go back to the "if all you have is a hammer, everything looks like a
nail" analogy: if I want to demonstrate a hammer, I can pick an actual
useful task ("watch me build a chicken coop with a hammer, nails and
timber"); or I can pick something obviously pointless to demonstrate the
technique ("watch me nail this piece of wood to this other piece of wood");
but what I shouldn't do is demonstrate something *bad* ("watch me remove
the battery from my iPhone by wacking it repeatedly with a hammer").

def spam(s):
    return s if len(s) > 50 else eggs(s + "spam")

def eggs(s):
    return s if len(s) > 50 else spam("eggs" + s)



> I'm not here to satisfy your or anyone else's curiosity. 

Fair enough.

What are you here for? When you complain that Python doesn't have TCO, is
your intent to persuade people that it should, with the ultimate aim to
changing Python so that it gains TCO? If not, then what?



-- 
Steven