Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #93763 > unrolled thread

A new module for performing tail-call elimination

Back to article view | Back to comp.lang.python

Contents

  A new module for performing tail-call elimination "Th. Baruchel" <baruchel@no.spam.gmx.dot.com> - 2015-07-13 15:44 +0000
    Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-15 11:29 +0200
      Re: A new module for performing tail-call elimination Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-07-16 18:07 +1000
        Re: A new module for performing tail-call elimination Robin Becker <robin@reportlab.com> - 2015-07-16 10:13 +0100
        Re: A new module for performing tail-call elimination Robin Becker <robin@reportlab.com> - 2015-07-16 10:28 +0100
          Re: A new module for performing tail-call elimination Marko Rauhamaa <marko@pacujo.net> - 2015-07-16 12:56 +0300
        Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 12:41 +0200
          Re: A new module for performing tail-call elimination Steven D'Aprano <steve@pearwood.info> - 2015-07-17 04:58 +1000
            Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-17 11:00 +0200
        Re: A new module for performing tail-call elimination Chris Angelico <rosuav@gmail.com> - 2015-07-16 21:11 +1000
        Re: A new module for performing tail-call elimination Jeremy Sanders <jeremy@jeremysanders.net> - 2015-07-16 13:29 +0200
        Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 15:35 +0200
        Re: A new module for performing tail-call elimination Chris Angelico <rosuav@gmail.com> - 2015-07-16 23:47 +1000
          Re: A new module for performing tail-call elimination Paul Rubin <no.email@nospam.invalid> - 2015-07-17 20:06 -0700
        Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 16:21 +0200
        Re: A new module for performing tail-call elimination Chris Angelico <rosuav@gmail.com> - 2015-07-17 00:27 +1000
        Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 17:14 +0200
        Re: A new module for performing tail-call elimination Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-16 10:17 -0600
        Re: A new module for performing tail-call elimination Ethan Furman <ethan@stoneleaf.us> - 2015-07-16 10:54 -0700
        Re: A new module for performing tail-call elimination Ethan Furman <ethan@stoneleaf.us> - 2015-07-16 11:02 -0700
        Re: A new module for performing tail-call elimination Terry Reedy <tjreedy@udel.edu> - 2015-07-16 15:45 -0400
        Re: A new module for performing tail-call elimination Ethan Furman <ethan@stoneleaf.us> - 2015-07-16 12:58 -0700
        Re: A new module for performing tail-call elimination Robin Becker <robin@reportlab.com> - 2015-07-17 09:57 +0100
      Re: A new module for performing tail-call elimination Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2015-07-16 13:23 +0200
    Re: A new module for performing tail-call elimination Terry Reedy <tjreedy@udel.edu> - 2015-07-15 17:19 -0400
    Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 09:45 +0200
    Re: A new module for performing tail-call elimination Terry Reedy <tjreedy@udel.edu> - 2015-07-16 15:34 -0400
      Re: A new module for performing tail-call elimination Marko Rauhamaa <marko@pacujo.net> - 2015-07-16 22:45 +0300
        Re: A new module for performing tail-call elimination Terry Reedy <tjreedy@udel.edu> - 2015-07-17 15:47 -0400
          Re: A new module for performing tail-call elimination Marko Rauhamaa <marko@pacujo.net> - 2015-07-17 23:55 +0300
            Re: A new module for performing tail-call elimination Terry Reedy <tjreedy@udel.edu> - 2015-07-17 20:40 -0400
              Re: A new module for performing tail-call elimination Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-19 10:39 +1200
            Re: A new module for performing tail-call elimination Chris Angelico <rosuav@gmail.com> - 2015-07-18 10:47 +1000
            Re: A new module for performing tail-call elimination Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-19 10:39 +1200
        Re: A new module for performing tail-call elimination Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-19 10:39 +1200
          Re: A new module for performing tail-call elimination Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-19 01:09 +0100
          Re: A new module for performing tail-call elimination MRAB <python@mrabarnett.plus.com> - 2015-07-19 01:19 +0100
          Re: A new module for performing tail-call elimination Marko Rauhamaa <marko@pacujo.net> - 2015-07-19 09:29 +0300
    Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-17 10:06 +0200

Page 1 of 2  [1] 2  Next page →

#93763 — A new module for performing tail-call elimination

Hi, after having spent much time thinking about tail-call elimination
in Python (see for instance http://baruchel.github.io/blog/ ), I finally
decided to write a module for that. You may find it at:

  https://github.com/baruchel/tco

Tail-call elimination is done for tail-recursion as well as for
continuation-passing style (cps) in a consistent syntax for both usages.

Any tail-recursive function having the suitable format for being
embeddable in the Y combinator can be used here with no change at all
(with the main difference that tail-calls will be eliminated), but other
continuations can also be added

The module is available under two forms: traditional python code and cython
compilable code (pre-compiled binaries are also released for the cython
version). Of course the Cython version is quicker and should be preferred
for serious work.

I must admit I haven't browsed much in order to know if similar projects
already exist; I was happy to do it for myself, but I want to share it now
in case other people are interested by it also.

Best regards,

-- 
Thomas Baruchel

[toc] | [next] | [standalone]

#93857

On 07/13/2015 05:44 PM, Th. Baruchel wrote:
> Hi, after having spent much time thinking about tail-call elimination
> in Python (see for instance http://baruchel.github.io/blog/ ), I finally
> decided to write a module for that. You may find it at:
>
>   https://github.com/baruchel/tco
>
> Tail-call elimination is done for tail-recursion as well as for
> continuation-passing style (cps) in a consistent syntax for both usages.
>
> Any tail-recursive function having the suitable format for being
> embeddable in the Y combinator can be used here with no change at all
> (with the main difference that tail-calls will be eliminated), but other
> continuations can also be added

Can you explain how you would do mutual recursive functions?

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)


How do I rewrite those with your module?

-- 
Antoon Pardon

[toc] | [prev] | [next] | [standalone]

#93914

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.


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.

I do believe that such examples surely must exist. But I'm yet to see one.



-- 
Steve

[toc] | [prev] | [next] | [standalone]

#93916

On 16/07/2015 09:07, Steven D'Aprano wrote:
.........
> 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
>
......
what about

 >>> def odd(n):
... 	return bool(n%2)
...
 >>> def even(n):
... 	return not odd(n)
...

not much more complex, but the logic for A(n) and not A(n) is only done once. 
Not really much to do with TCO though.
-- 
Robin Becker

[toc] | [prev] | [next] | [standalone]

#93918

..........
>
> 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.
>
> I do believe that such examples surely must exist. But I'm yet to see one.
....
I believe the classic answer is Ackermann's function

http://demonstrations.wolfram.com/RecursionInTheAckermannFunction/

which is said to be not "primitive recursive" ie cannot be unwound into loops; 
not sure whether that implies it has to be recursively defined or can perhaps be 
broken down some other way. For more eye-glazing

http://math.stackexchange.com/questions/75296/what-is-the-difference-between-total-recursive-and-primitive-recursive-functions
-- 
Robin Becker

[toc] | [prev] | [next] | [standalone]

#93919

Robin Becker <robin@reportlab.com>:

> which is said to be not "primitive recursive" ie cannot be unwound
> into loops; not sure whether that implies it has to be recursively
> defined or can perhaps be broken down some other way. For more
> eye-glazing

You only need a single while loop plus primitive recursion to implement
total recursion.


Marko

[toc] | [prev] | [next] | [standalone]

#93920

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.

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.

> 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?

I'm not here to satisfy your or anyone else's curiosity. Certainly not
when that curiosity often enough is just a pretext for donning the
role of judge or arbiter and where any simplification that was done
to make the example better understandable is siezed upon as a reason
to dismiss it, because one looks at it litterally, like you do above,
and is unable or unwilling to understand the spirit of the example.

-- 
Antoon Pardon

[toc] | [prev] | [next] | [standalone]

#93949

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

[toc] | [prev] | [next] | [standalone]

#93998

On 07/16/2015 08:58 PM, Steven D'Aprano wrote:
>> 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.

We know your point. You have repeated it often enough. There is no need
to keep bringing it up and certainly not where your point is irrelevant.

People are allowed to not care about your point. People may think it is
not worth the trouble trying to convince people who are skeptical and
may choose to discuss possible directions with people who are likewise 
intressed.

So why do you find it necessary to appear here and repeat your point,
that is already known, but is not cared about much and irrelevant here.


>> 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?

I don't complain that Python doesn't have TCO. I am intressed in the subject
and I'm willing to discuss the pro and cons, how it could be simulated, and
how good some arguments for or against it are. But I don't think any outcome
here will have much weight in getting it implemented and although I would
prefer having it, I can perfectly live without. So don't translate my
interest in the subject into a complaint about python not having it.

I'm also not interrested in convincing people who show a dislike for it.
If the toy examples here, don't ignite a spark of imagination about how
in some circumstance this could be useful for you, then I am not interessed
in showing you.

[toc] | [prev] | [next] | [standalone]

#93922

On Thu, Jul 16, 2015 at 8:41 PM, Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
>> 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.
>
> 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.

Once again, tail call optimization is used as a way to make something
more efficient that shouldn't need to be done at all.

"Bubble sort takes too long when I give it 1000 elements. How can I
make it faster?"

Before looking at code improvements or language improvements, it's
crucial to do algorithmic improvements. The recursive even() and odd()
functions are O(n), the modulo ones are O(1). Bubble sort is simply a
terrible way to sort long lists. Time spent optimizing bubble sort is
time utterly and totally wasted, because you'll get more benefit by
switching to quicksort, insertion sort, or a hybrid like Timsort. Time
spent eliminating tail call stack frames is equally useless if a small
algorithmic change can eliminate the recursion altogether.

That's why we need examples that *can't* be trivially reimplemented
some other way.

Unless, of course, *all* TCO examples, even real-world ones, could be
trivially reimplemented some other way, a theory which is gaining
currency...

ChrisA

[toc] | [prev] | [next] | [standalone]

#93924

Robin Becker wrote:

> I believe the classic answer is Ackermann's function
> 
> http://demonstrations.wolfram.com/RecursionInTheAckermannFunction/
> 
> which is said to be not "primitive recursive" ie cannot be unwound into
> loops; not sure whether that implies it has to be recursively defined or
> can perhaps be broken down some other way. For more eye-glazing

But am I right in thinking that TCO doesn't work for Ackermann's function, 
at least not as it's written down in the above page?

J.

[toc] | [prev] | [next] | [standalone]

#93926

On 07/16/2015 01:11 PM, Chris Angelico wrote:
> On Thu, Jul 16, 2015 at 8:41 PM, Antoon Pardon
> <antoon.pardon@rece.vub.ac.be> wrote:
>>> 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.
>>
>> 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.
> Once again, tail call optimization is used as a way to make something
> more efficient that shouldn't need to be done at all.

Once again, the intend of the example is ignored. The question was
not about how tail call optimization could be done on this specific
example. The question was about how it could be done generally and
this example was just used as a vehicle to get the question more
easily explained.
 

> "Bubble sort takes too long when I give it 1000 elements. How can I
> make it faster?"

But that is not a similar question. A similar question would have been
if someone would have trouble with making comparing items somehow
parametric is his function. So he writes a bubblesort to illustrate
that he somehow wants to specify on call time how items get compared.

And what happens is that lots of people start critisizing the bubble sort
and ignore the actual question, even though the question was not about
bubble sort. Bubble sort was just used as a vehicle to easily explain
the question. 

> Before looking at code improvements or language improvements, it's
> crucial to do algorithmic improvements.

But we were not looking at code improvements here. We were looking
at how to use a particular module. 

>  The recursive even() and odd()
> functions are O(n), the modulo ones are O(1). Bubble sort is simply a
> terrible way to sort long lists.

Which are all beside the point. The intent of the even and odd functions
was not to actually use them in production, but as a vehicle to ask someone
on how to use his module. For anyone in this context to seize upon the
particular implementation of those functions, is just making it clear
he completly missed the specific intend and used these examples to get
on his high horse.

>  Time spent optimizing bubble sort is
> time utterly and totally wasted, because you'll get more benefit by
> switching to quicksort, insertion sort, or a hybrid like Timsort. Time
> spent eliminating tail call stack frames is equally useless if a small
> algorithmic change can eliminate the recursion altogether.

That depends on the purpose. When the purpose is to learn something, it
may be usefull to spend time on code unfit for production, because such
code is often more comprehensible than code for which tco would be actually
useful. So here you are critisizing code meant to learn something, because
it isn't useful.

> That's why we need examples that *can't* be trivially reimplemented
> some other way.

These functions were not intented to provide such an example. I also
think that was rather clear. So critisizing them because they are not
is just disingenuous.

> Unless, of course, *all* TCO examples, even real-world ones, could be
> trivially reimplemented some other way, a theory which is gaining
> currency...

Of course they could be rather trivially reimplemented. They would
also become rather ugly and less easy to comprehend.

Here is one way to do the odd, even example.

def even(n):
    return odd_even('even', n)

def odd(n):
    return odd_even('odd', n)

def odd_even(fn, n):
    while fn is not None:
        if fn == 'even':
            fn, n = (None, True) if n == 0 else ('odd', n - 1)
        elif fn == 'odd':
            fn, n = (None, False) if n == 0 else ('even', n - 1)
        else:
            raise ValueError("Unknown state: %s" % fn)
    return n

Any collection of functions that tail calls each other can rather
trivially be turned into a state machine like the above. You can
just paste in the code of the individual functions and replace
the return call combo's with an assignment indicating which 'function'
is to be 'called' next and its arguments.
    
-- 
Antoon Pardon

[toc] | [prev] | [next] | [standalone]

#93927

On Thu, Jul 16, 2015 at 11:35 PM, Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
> Of course they could be rather trivially reimplemented. They would
> also become rather ugly and less easy to comprehend.
>
> Here is one way to do the odd, even example.
>
> def even(n):
>     return odd_even('even', n)
>
> def odd(n):
>     return odd_even('odd', n)
>
> def odd_even(fn, n):
>     while fn is not None:
>         if fn == 'even':
>             fn, n = (None, True) if n == 0 else ('odd', n - 1)
>         elif fn == 'odd':
>             fn, n = (None, False) if n == 0 else ('even', n - 1)
>         else:
>             raise ValueError("Unknown state: %s" % fn)
>     return n
>
> Any collection of functions that tail calls each other can rather
> trivially be turned into a state machine like the above. You can
> just paste in the code of the individual functions and replace
> the return call combo's with an assignment indicating which 'function'
> is to be 'called' next and its arguments.

That's not an algorithmic change, though. That's just a mechanical
change, and a poorly-written one. My point was that I have yet to see
anything that demands TCO and can't be algorithmically improved. The
best so far has been a quicksort that uses TCO to guarantee a maximum
on stack usage.

ChrisA

[toc] | [prev] | [next] | [standalone]

#94047

Chris Angelico <rosuav@gmail.com> writes:
> My point was that I have yet to see anything that demands TCO and
> can't be algorithmically improved.

I don't think anyone claimed you can't simulate TCO with updateable
variables and a while loop.  TCO just sometimes lets you write some
things in a cleaner (in proponnets' view) style.

> The best so far has been a quicksort that uses TCO to guarantee a
> maximum on stack usage.

I actually thought the state machine example was more convincing.  Doing
that without TCO would have required some kind of explicit control loop
and a messy dispatch mechanism instead of direct chaining from one state
to the next.

[toc] | [prev] | [next] | [standalone]

#93930

On 07/16/2015 03:47 PM, Chris Angelico wrote:
> On Thu, Jul 16, 2015 at 11:35 PM, Antoon Pardon
> <antoon.pardon@rece.vub.ac.be> wrote:
>> Any collection of functions that tail calls each other can rather
>> trivially be turned into a state machine like the above. You can
>> just paste in the code of the individual functions and replace
>> the return call combo's with an assignment indicating which 'function'
>> is to be 'called' next and its arguments.
> That's not an algorithmic change, though. That's just a mechanical
> change, and a poorly-written one.

What did you expect when you talked about all tco examples (including
real world ones) and the reimplementation being trivial?

> My point was that I have yet to see
> anything that demands TCO and can't be algorithmically improved.

And how is this point relevant? Why should I care about what you have
not seen? Will it give me new insights about my original question in
this thread?

-- 
Antoon Pardon

[toc] | [prev] | [next] | [standalone]

#93931

On Fri, Jul 17, 2015 at 12:21 AM, Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
>> My point was that I have yet to see
>> anything that demands TCO and can't be algorithmically improved.
>
> And how is this point relevant? Why should I care about what you have
> not seen? Will it give me new insights about my original question in
> this thread?

I guess you shouldn't care, because to you, functional programming is
an end in itself, XKCD 1270 style. You could alternatively show an
example, if there are any, but if you'd rather just live the
functional life, who am I to stop you?

Go ahead. Write LISP code that runs in the Python interpreter, and
then bemoan the stack limit. Meanwhile, I'll write Python code.

ChrisA

[toc] | [prev] | [next] | [standalone]

#93933

On 07/16/2015 04:27 PM, Chris Angelico wrote:
> On Fri, Jul 17, 2015 at 12:21 AM, Antoon Pardon
> <antoon.pardon@rece.vub.ac.be> wrote:
>>> My point was that I have yet to see
>>> anything that demands TCO and can't be algorithmically improved.
>> And how is this point relevant? Why should I care about what you have
>> not seen? Will it give me new insights about my original question in
>> this thread?
> I guess you shouldn't care, because to you, functional programming is
> an end in itself, XKCD 1270 style.

You are wrong and how is this relevant? I use the functional style
when I think it is more useful way in implementing things. And that
is in a minority of the cases. You not having seen anything that
demands TCO and can't be algorithmically improved, doesn't change
anything about that. You agreeing with me or not, doesn't change
anything about that either.

Please explain how it would make a difference for me, whether
or not you were given such an example?

> You could alternatively show an example, if there are any?

As far as I can see, such an example is not relevant in this
topic. It doesn't help in any way clarify on how the module
written by the topic starter is to be used.

You and steven just blundered into this topic, as if others
need to use examples that satisfy your curiosity instead
of examples helpful to get their own question accross. Behaving
as if this topic is about convincing either of you and getting
indignant when I don't accept that change in subject.

And you are still behaving here as if I should indulge you, as
if I somehow owe you such an example.

-- 
Antoon Pardon

[toc] | [prev] | [next] | [standalone]

#93934

On Thu, Jul 16, 2015 at 3:28 AM, Robin Becker <robin@reportlab.com> wrote:
> ..........
>>
>>
>> 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.
>>
>> I do believe that such examples surely must exist. But I'm yet to see one.
>
> ....
> I believe the classic answer is Ackermann's function
>
> http://demonstrations.wolfram.com/RecursionInTheAckermannFunction/
>
> which is said to be not "primitive recursive" ie cannot be unwound into
> loops; not sure whether that implies it has to be recursively defined or can
> perhaps be broken down some other way.

My recollection -- and it's been awhile since I've studied
computability theory so I may be distorting things here -- is that
primitive recursive functions can be computed using for loops, i.e.
loops where the number of iterations is bounded in advance, whereas
non-primitive recursive functions require while loops.

[toc] | [prev] | [next] | [standalone]

#93943

On 07/16/2015 01:07 AM, Steven D'Aprano wrote:

> 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.

You mean toy examples?

Toy examples serve useful purposes:

   - easy to understand
   - easy to write
   - esay to test as proof-of-concept (after all, if a routine can't handle
        a toy example, how is it going to handle real life?)

With responses like these I can understand Antoon's position that folks are not arguing in good faith.

--
~Ethan~

[toc] | [prev] | [next] | [standalone]

#93945

On 07/16/2015 06:35 AM, Antoon Pardon wrote:
> On 07/16/2015 01:11 PM, Chris Angelico wrote:

>> Unless, of course, *all* TCO examples, even real-world ones, could be
>> trivially reimplemented some other way, a theory which is gaining
>> currency...
>
> Of course they could be rather trivially reimplemented. They would
> also become rather ugly and less easy to comprehend.
>
> Here is one way to do the odd, even example.
>
> def even(n):
>      return odd_even('even', n)
>
> def odd(n):
>      return odd_even('odd', n)
>
> def odd_even(fn, n):
>      while fn is not None:
>          if fn == 'even':
>              fn, n = (None, True) if n == 0 else ('odd', n - 1)
>          elif fn == 'odd':
>              fn, n = (None, False) if n == 0 else ('even', n - 1)
>          else:
>              raise ValueError("Unknown state: %s" % fn)
>      return n

Wow -- definitely uglier and less easy to understand than the original (even if the original had had the error-checking).

--
~Ethan~

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web