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

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

Re: Possibly Pythonic Tail Call Optimization (TCO/TRE)

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

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 00:05 +1000
    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Steven D'Aprano <steve@pearwood.info> - 2015-07-14 13:20 +1000
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-14 09:26 +0200
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-14 02:34 -0600
        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Grant Edwards <invalid@invalid.invalid> - 2015-07-14 14:03 +0000
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-14 12:43 +0200
    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Paul Rubin <no.email@nospam.invalid> - 2015-07-13 22:15 -0700
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 15:25 +1000
        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Paul Rubin <no.email@nospam.invalid> - 2015-07-13 22:41 -0700
          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 21:43 +1000
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 15:28 +0300
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 22:55 +1000
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 16:38 +0300
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 23:43 +1000
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 20:29 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Steven D'Aprano <steve@pearwood.info> - 2015-07-15 03:48 +1000
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-15 10:28 +0200
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-14 16:02 +0200
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 00:07 +1000
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 20:31 +0300
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-14 20:41 -0400
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-15 11:10 +0200
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-16 10:43 +1200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 09:31 +0200
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-17 10:41 +1200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-16 21:45 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 15:56 +0200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 00:00 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 16:32 +0200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 02:43 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Joonas Liik <liik.joonas@gmail.com> - 2015-07-16 19:50 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 03:03 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ethan Furman <ethan@stoneleaf.us> - 2015-07-16 10:04 -0700
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Joonas Liik <liik.joonas@gmail.com> - 2015-07-16 20:34 +0300
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Steven D'Aprano <steve@pearwood.info> - 2015-07-17 04:58 +1000
                          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Joonas Liik <liik.joonas@gmail.com> - 2015-07-16 22:14 +0300
                            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-17 11:41 +1200
                          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ethan Furman <ethan@stoneleaf.us> - 2015-07-16 12:52 -0700
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 03:49 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Joonas Liik <liik.joonas@gmail.com> - 2015-07-16 21:23 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 04:29 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-16 16:19 -0400
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-17 12:48 +0200
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-19 10:57 +1200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 21:05 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-17 13:43 +0200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 21:49 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-17 14:54 +0200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 23:12 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-17 16:27 -0400
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-15 21:13 +1200
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-15 12:55 +0300
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-15 12:22 +0100
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-16 10:34 +1200
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-16 00:34 +0100
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) MRAB <python@mrabarnett.plus.com> - 2015-07-15 13:00 +0100
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 22:13 +1000
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-16 10:34 +1200
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 22:22 +1000
        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 08:41 +0300
          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 21:33 +1000
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 15:08 +0300
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 15:31 +1000
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-13 23:46 -0600
        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 08:57 +0300
          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-14 18:29 +1200
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 10:05 +0300
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-15 17:52 +1200
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-15 09:44 +0300
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ned Batchelder <ned@nedbatchelder.com> - 2015-07-15 03:45 -0700
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-15 13:55 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-15 13:04 +0200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ned Batchelder <ned@nedbatchelder.com> - 2015-07-15 04:12 -0700
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-15 14:24 +0300
                          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Rustom Mody <rustompmody@gmail.com> - 2015-07-16 21:28 -0700
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-14 08:47 +0100
          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-14 02:13 -0600
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 11:33 +0300
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-14 07:15 -0600
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 20:27 +0300
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-15 08:28 -0600
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-15 17:55 +0300
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Steven D'Aprano <steve@pearwood.info> - 2015-07-15 03:34 +1000
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 20:43 +0300
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 03:52 +1000
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Steven D'Aprano <steve@pearwood.info> - 2015-07-15 04:06 +1000
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 21:37 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 04:55 +1000
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 22:12 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-14 21:36 -0400
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-14 21:01 -0400
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 13:05 +1000
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Paul Rubin <no.email@nospam.invalid> - 2015-07-14 10:54 -0700
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-14 20:23 -0400

Page 1 of 5  [1] 2 3 4 5  Next page →

#93760 — Re: Possibly Pythonic Tail Call Optimization (TCO/TRE)

On Mon, Jul 13, 2015 at 11:55 PM, Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
> On 07/13/2015 02:34 PM, Chris Angelico wrote:
>>
>>>> Warping your code around a recursive solution
>>>> to make it into a perfect tail call usually means making it look a lot
>>>> less impressive; for instance,
>>> And sometimes your problem is very easily solved by a number of functions
>>> that tail call each other but in python you will need to warp your code
>>> around an iterative solution, in order to avoid the stack limit.
>> Example, please? In all my Python programming, I've never hit the
>> stack limit outside of deliberate playing around (or accidental
>> infinite recursion, which means it's doing its job).
>
> I have had to process text coming from a network connection. The data
> was mosly unstructered text with some lines that could be used as markers
> to proceed through some kind of state machine that indicated how the
> following lines needed to be processed. That was easiest written by having
> a function for each "state" that would process the next lines until
> a marker line was encountered and then call the function corresponding
> with the next state. However since a connection could stay active for
> days, sooner or later a stack limit would occur if done the natural
> recursive way.

I'm not sure why the transition to another state has to be recursive.
With most network protocols, you'll end up returning to some kind of
"base state" - maybe there's a header line that says that you're
entering some new mode, which strongly suggests a subroutine call, but
then at the end of that mode, you would return to the normal position
of looking for another header. Alternatively, if the only way you know
you're at the end of one mode is by discovering the beginning of the
next, it's common to be able to have a single primary loop that
dispatches lines appropriately - when it gets the next header, it
sends the entire previous block to its appropriate function, and then
carries on looking for lines of text.

Maybe this is something where previous experience makes you more
comfortable with a particular style, which will mean that functional
idioms will never feel more comfortable to me than iterative ones do,
and vice versa for you. If that's the case, then I'll stick with
Python and Pike, and you can happily use Lisp and Haskell, and neither
of us need be a problem to the other. But honestly, I'm not seeing
anything that requires infinite recursion in your description. And
I've worked with a lot of networking protocols in my time.

>>> It seems warping your code is only seen as a problem when going in the
>>> functional direction. Going into the iterative direction may take all
>>> the warping that is needed, without comment.
>> That's because I've never seen code that warps more for iteration than
>> it does for programming in general. Again, example please?
>
> And since when is your experience the measure stick for what other people
> encounter as problems?

That's why I said "example please?". My experience has not a single
time come across this. If you want to make an assertion that iterative
code requires equivalent warping to tail-recursive code, I want to see
an example of it. Is that difficult?

ChrisA

[toc] | [next] | [standalone]

#93772

On Tue, 14 Jul 2015 12:05 am, Chris Angelico wrote:

> If you want to make an assertion that iterative
> code requires equivalent warping to tail-recursive code, I want to see
> an example of it. Is that difficult?

Of course it is. If it wasn't difficult, people would post examples instead
of getting all defensive about being asked for examples.


-- 
Steven

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

#93791

On 07/14/2015 05:20 AM, Steven D'Aprano wrote:
> On Tue, 14 Jul 2015 12:05 am, Chris Angelico wrote:
>
>> If you want to make an assertion that iterative
>> code requires equivalent warping to tail-recursive code, I want to see
>> an example of it. Is that difficult?
> Of course it is. If it wasn't difficult, people would post examples instead
> of getting all defensive about being asked for examples.

Shrug! I have seen this game played before. It has been played since before
python had an if-expression. It always goes as follows. Some one mentions
a feature python doesn't has and that could be useful. The python status-quo
people will argue that it is unnecessary. Any example that will be given
to illustrate the advantage will be nit picked appart for any possible flaw,
while mostly ignoring the flaws in the status quo.

Before python had an if-expression, examples were asked too and they
convinced
noone. It wasn't until a core developer was bitten by an elusive bug, caused
by using the then advised "and or" combination, that python got an
if-expression
and that an if-expression was considered useful by the python community
in general.

I expect any example given, to be used as a contest by those reading,
for finding
the least warped alternative and then using that to dismiss the example.

So I really don't feel compelled to search through my code in the hope
of finding
an example that would persuade someone.

-- 
Antoon Pardon

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

#93798

On Tue, Jul 14, 2015 at 1:26 AM, Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
> On 07/14/2015 05:20 AM, Steven D'Aprano wrote:
>> On Tue, 14 Jul 2015 12:05 am, Chris Angelico wrote:
>>
>>> If you want to make an assertion that iterative
>>> code requires equivalent warping to tail-recursive code, I want to see
>>> an example of it. Is that difficult?
>> Of course it is. If it wasn't difficult, people would post examples instead
>> of getting all defensive about being asked for examples.
>
> Shrug! I have seen this game played before. It has been played since before
> python had an if-expression. It always goes as follows. Some one mentions
> a feature python doesn't has and that could be useful. The python status-quo
> people will argue that it is unnecessary. Any example that will be given
> to illustrate the advantage will be nit picked appart for any possible flaw,
> while mostly ignoring the flaws in the status quo.
>
> Before python had an if-expression, examples were asked too and they
> convinced
> noone. It wasn't until a core developer was bitten by an elusive bug, caused
> by using the then advised "and or" combination, that python got an
> if-expression
> and that an if-expression was considered useful by the python community
> in general.
>
> I expect any example given, to be used as a contest by those reading,
> for finding
> the least warped alternative and then using that to dismiss the example.
>
> So I really don't feel compelled to search through my code in the hope
> of finding
> an example that would persuade someone.

And yet, Python somehow manages to gain new features with each release.

The reason why most proposals get rejected is because most proposals
are bad. If every idea that came along just got accepted, we'd have a
disastrous hodge-podge of a language.

In the case of TCO, Guido rejected the feature six years ago and
hasn't shown any sign of changing his mind. He considered the
arguments for it, and he decided that for Python, the benefits don't
outweigh the drawbacks. Maybe his mind could still be changed, but
it's going to take somebody to make a very convincing case for the
feature, and if you're not even willing to put forth some examples
then you don't have a case at all.

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

#93812

On 2015-07-14, Ian Kelly <ian.g.kelly@gmail.com> wrote:

> And yet, Python somehow manages to gain new features with each release.
>
> The reason why most proposals get rejected is because most proposals
> are bad. If every idea that came along just got accepted, we'd have a
> disastrous hodge-podge of a language.

And PHP already has that niche nailed down.

-- 
Grant Edwards               grant.b.edwards        Yow! World War III?
                                  at               No thanks!
                              gmail.com            

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

#93799

On 07/14/2015 10:34 AM, Ian Kelly wrote:
> On Tue, Jul 14, 2015 at 1:26 AM, Antoon Pardon
> <antoon.pardon@rece.vub.ac.be> wrote:
>> I expect any example given, to be used as a contest by those reading,
>> for finding
>> the least warped alternative and then using that to dismiss the example.
>>
>> So I really don't feel compelled to search through my code in the hope
>> of finding
>> an example that would persuade someone.
> And yet, Python somehow manages to gain new features with each release.

Sure, but what happens in this list, has an insignificant role in
driving that process.

> The reason why most proposals get rejected is because most proposals
> are bad. If every idea that came along just got accepted, we'd have a
> disastrous hodge-podge of a language.

But I'm not proposing TCO to be accepted. I was just pointing out
a reason for preferring it in particular circumstances and only
because some people here suggested there could be no such reasons.

> In the case of TCO, Guido rejected the feature six years ago and
> hasn't shown any sign of changing his mind. He considered the
> arguments for it, and he decided that for Python, the benefits don't
> outweigh the drawbacks. Maybe his mind could still be changed, but
> it's going to take somebody to make a very convincing case for the
> feature, and if you're not even willing to put forth some examples
> then you don't have a case at all.

Indeed I am not trying to make a case. I was just protesting the
sugestion that there are no circumstances in which having TCO could
be an advantage. That me suggesting such circumstances do exist
gets turned into me trying to make a case for including TCO into
the language is one important reason why I am not inclined to search
for examples. Because all I would try to do is illustrate how TCO
would be an advantage in that case en how it would probably be received
is as if I would try and present that example as a compelling case for
introducing TCO into python.

For what it is worth, in general I find both the warping necessary for
turning iterative code into tail-recursive code and vice versa not
that big a deal. I just find that the solutions for my problems are
sometimes more easily expressed one way and sometimes the other way
and I would prefer I didn't need to warp.

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

#93780

Chris Angelico <rosuav@gmail.com> writes:
> I'm not sure why the transition to another state has to be recursive.

It's not recursive: it's more like a goto with arguments, and a tail
call expresses it nicely.

> Maybe this is something where previous experience makes you more
> comfortable with a particular style, which will mean that functional
> idioms will never feel more comfortable to me than iterative ones do,
> and vice versa for you. If that's the case, then I'll stick with
> Python and Pike, and you can happily use Lisp and Haskell, and neither
> of us need be a problem to the other. 

Do you also use explicit loops instead of list comprehensions?  They are
another nice functional idiom adapted into Python.

> That's why I said "example please?". My experience has not a single
> time come across this. If you want to make an assertion that iterative
> code requires equivalent warping to tail-recursive code, I want to see
> an example of it. Is that difficult?

It's difficult given how subjective the concept of warping is.  What's
straightforward to someone else sounds likely to look warped to you and
vice versa.  But how does this look:

  def quicksort(array, start, end):
     midp = partition(array, start, end)
     if midp <= (start+end)//2:
        quicksort(array, start, midp)
        quicksort(array, midp+1, end)
     else:
        quicksort(array, midp+1, end)
        quicksort(array, start, midp)

I assume you know how quicksort and its partition step work.  The idea
is you partition the array around the pivot element (midp is the index
of that element), then recursively sort the two partitions, doing the
smaller partition as a recursive call and the larger one as a tail call,
so that you use O(log n) stack depth instead of potentially O(n).

So the idea is that the second quicksort call in each branch of the if
is a tail call.  Yes you could code that as a loop but from my
perspective the way I wrote it above looks more natural.

Of course it's also possible that I've totally derped this and the
example is no good for some reason I've missed so far ;-).

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

#93782

On Tue, Jul 14, 2015 at 3:15 PM, Paul Rubin <no.email@nospam.invalid> wrote:
> It's difficult given how subjective the concept of warping is.  What's
> straightforward to someone else sounds likely to look warped to you and
> vice versa.  But how does this look:
>
>   def quicksort(array, start, end):
>      midp = partition(array, start, end)
>      if midp <= (start+end)//2:
>         quicksort(array, start, midp)
>         quicksort(array, midp+1, end)
>      else:
>         quicksort(array, midp+1, end)
>         quicksort(array, start, midp)
>
> I assume you know how quicksort and its partition step work.  The idea
> is you partition the array around the pivot element (midp is the index
> of that element), then recursively sort the two partitions, doing the
> smaller partition as a recursive call and the larger one as a tail call,
> so that you use O(log n) stack depth instead of potentially O(n).
>
> So the idea is that the second quicksort call in each branch of the if
> is a tail call.  Yes you could code that as a loop but from my
> perspective the way I wrote it above looks more natural.
>
> Of course it's also possible that I've totally derped this and the
> example is no good for some reason I've missed so far ;-).

That's a prime example of recursion... but not of recursion that can
be tail-call optimized into iteration. It's an example of forking
recursion, where one call can result in multiple calls (same with tree
traversal); it calls itself to sort the first part and the last part,
and while you might be able to turn the second call into a goto, you
still need stack space to maintain the first call. The claim that TCO
means you don't need stack space for all those levels of recursion
doesn't work if you still need stack space for all those levels of
recursion *before* you get to the tail call.

(Also, side point: Python can't actually optimize the above function,
because it actually means "call quicksort, then discard its return
value and return None". A true tail call has to return the result of
the recursive call, and Python lacks a way to say "this function will
always return None". But that's trivial.)

ChrisA

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

#93784

Chris Angelico <rosuav@gmail.com> writes:
> That's a prime example of recursion... but not of recursion that can
> be tail-call optimized into iteration. It's an example of forking
> recursion, where one call can result in multiple calls (same with tree
> traversal); it calls itself to sort the first part and the last part,
> and while you might be able to turn the second call into a goto, you
> still need stack space to maintain the first call. The claim that TCO
> means you don't need stack space for all those levels of recursion
> doesn't work if you still need stack space for all those levels of
> recursion *before* you get to the tail call.

You partition the array into two parts, one of which has at most N/2
elements.  You push that smaller one onto the stack and recurse, so at
the next recursive level you push at most an N/4 part, then N/8 and so
on.  In that way the total recursion depth is O(log N).  If N=1e6 you
enter 20 levels of recursion which is no big deal.

If you also push the larger part on the stack, it can have size as high
as N-1, so you can end up pushing N-1, N-2, N-3, etc.  If N=1e6 you
overflow the stack when you've barely gotten started.

So it's important in that example that both of the recursive calls
involving the larger partition are both tail calls.  It's fine that the
first call pushes stuff on the stack.  It's vital that the second call
be turned into a goto.

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

#93801

On Tue, Jul 14, 2015 at 3:41 PM, Paul Rubin <no.email@nospam.invalid> wrote:
> Chris Angelico <rosuav@gmail.com> writes:
>> That's a prime example of recursion... but not of recursion that can
>> be tail-call optimized into iteration. It's an example of forking
>> recursion, where one call can result in multiple calls (same with tree
>> traversal); it calls itself to sort the first part and the last part,
>> and while you might be able to turn the second call into a goto, you
>> still need stack space to maintain the first call. The claim that TCO
>> means you don't need stack space for all those levels of recursion
>> doesn't work if you still need stack space for all those levels of
>> recursion *before* you get to the tail call.
>
> You partition the array into two parts, one of which has at most N/2
> elements.  You push that smaller one onto the stack and recurse, so at
> the next recursive level you push at most an N/4 part, then N/8 and so
> on.  In that way the total recursion depth is O(log N).  If N=1e6 you
> enter 20 levels of recursion which is no big deal.
>
> If you also push the larger part on the stack, it can have size as high
> as N-1, so you can end up pushing N-1, N-2, N-3, etc.  If N=1e6 you
> overflow the stack when you've barely gotten started.

Ah, good point. So this is a way of forcing the recursion to be capped
at log N, preventing the worst-case time from also carrying worst-case
stack usage. Fair enough. Okay! Great! We have one example where TCO
can be helpful, because it means your two calls look identical. Well,
nearly identical... since one of them has to be "return
quicksort(...)" but the other has to be just "quicksort(...)". So in
order to make sure it's a true optimizable tail call, they end up
having to look different. Plus there's the whole traceback problem.

I'm still interested in the explicit "replace current stack frame with
this call" operation. Calling it "goto" seems wrong, as most languages
with goto restrict it to _within_ a function, whereas this would be
_across_ functions:

int fail_and_bail_demo(int arg, char *whatever)
{
    int ret = 1; /* failure */

    if (arg < 0) goto failure;

    int stuff_done = do_stuff(whatever);
    if (stuff_done < arg) goto failure;

    if (do_more_stuff(arg, whatever)) goto failure;

    ret = 0; /* If we get here, success! */

    failure:
    clean_up();
    return ret;
}

Contrast this proposal:

def func():
    pass

def setup_and_call():
    setup()
    transfer func, (), {}

The transfer of control has to be to the beginning of some other
function. So I'd rather it _not_ be called goto, but rather something
more evoking the notion of "hand control over to that function over
there, pretending that I've already returned". It's very much like the
Unix exec* family of functions, but Python already uses the name
'exec' in a very different way.

Done explicitly like this, it avoids the problem of bad tracebacks,
because by definition you would use it only when you want the current
stack frame to be dropped. I wonder how hard it would be to hack this
into CPython... Anyone feel like tackling it?

ChrisA

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

#93805

Chris Angelico <rosuav@gmail.com>:

> Done explicitly like this, it avoids the problem of bad tracebacks,
> because by definition you would use it only when you want the current
> stack frame to be dropped. I wonder how hard it would be to hack this
> into CPython... Anyone feel like tackling it?

I would rather optimize by default and disable optimizations with
--debug or equivalent.


Marko

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

#93806

On Tue, Jul 14, 2015 at 10:28 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Chris Angelico <rosuav@gmail.com>:
>
>> Done explicitly like this, it avoids the problem of bad tracebacks,
>> because by definition you would use it only when you want the current
>> stack frame to be dropped. I wonder how hard it would be to hack this
>> into CPython... Anyone feel like tackling it?
>
> I would rather optimize by default and disable optimizations with
> --debug or equivalent.

That assumes that it's simply an optimization. This is a distinct
semantic change. Would you, for instance, want all of your arithmetic
to be rounded to integer because integers are faster - and then
disable this "optimization" with a flag that permits floating-point
arithmetic? Certainly not.

ChrisA

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

#93809

Chris Angelico <rosuav@gmail.com>:

> On Tue, Jul 14, 2015 at 10:28 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> I would rather optimize by default and disable optimizations with
>> --debug or equivalent.
>
> That assumes that it's simply an optimization. This is a distinct
> semantic change.

No, tail call optimization doesn't change the behavior of the program,
for the worse anyway.


Marko

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

#93810

On Tue, Jul 14, 2015 at 11:38 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Chris Angelico <rosuav@gmail.com>:
>
>> On Tue, Jul 14, 2015 at 10:28 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>>> I would rather optimize by default and disable optimizations with
>>> --debug or equivalent.
>>
>> That assumes that it's simply an optimization. This is a distinct
>> semantic change.
>
> No, tail call optimization doesn't change the behavior of the program,
> for the worse anyway.

It does, because you lose traceback records. That's pretty significant
when you come to try to debug something.

ChrisA

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

#93820

Chris Angelico <rosuav@gmail.com>:

> On Tue, Jul 14, 2015 at 11:38 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> No, tail call optimization doesn't change the behavior of the
>> program, for the worse anyway.
>
> It does, because you lose traceback records. That's pretty significant
> when you come to try to debug something.

Doesn't count. Optimization can do weird things to code and make
debugging challenging. That's why you usually tell the compiler not to
optimize the debug builds.


Marko

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

#93825

On Wed, 15 Jul 2015 03:29 am, Marko Rauhamaa wrote:

> Chris Angelico <rosuav@gmail.com>:
> 
>> On Tue, Jul 14, 2015 at 11:38 PM, Marko Rauhamaa <marko@pacujo.net>
>> wrote:
>>> No, tail call optimization doesn't change the behavior of the
>>> program, for the worse anyway.
>>
>> It does, because you lose traceback records. That's pretty significant
>> when you come to try to debug something.
> 
> Doesn't count. 

Says you.

> Optimization can do weird things to code and make 
> debugging challenging. That's why you usually tell the compiler not to
> optimize the debug builds.

Here's a real scenario for you to chew on: testing. Test suites should be
considered an application where the developer is the end user, and the
point of the application is to verify that the code passes tests, and if
they don't, present the user (i.e. the developer) with sufficient
information to debug the problem (i.e. full stack traces).

So how do you test your optimized code?

If you turn optimizations on globally, you're testing something which may or
may not have the same behaviour as the code you wrote. Compiler bugs exist,
so it is more important than ever to ensure that the post-optimization code
passes the test suite. But if it fails, you no longer get the stack traces
you need to debug the problem.

But if you turn optimizations off globally, you're not testing the optimized
code any longer.


-- 
Steven

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

#93853

On 07/14/2015 07:48 PM, Steven D'Aprano wrote:
> On Wed, 15 Jul 2015 03:29 am, Marko Rauhamaa wrote:
>
>> Chris Angelico <rosuav@gmail.com>:
>>
>>> On Tue, Jul 14, 2015 at 11:38 PM, Marko Rauhamaa <marko@pacujo.net>
>>> wrote:
>>>> No, tail call optimization doesn't change the behavior of the
>>>> program, for the worse anyway.
>>> It does, because you lose traceback records. That's pretty significant
>>> when you come to try to debug something.
>> Doesn't count. 
> Says you.
>
>> Optimization can do weird things to code and make 
>> debugging challenging. That's why you usually tell the compiler not to
>> optimize the debug builds.
> Here's a real scenario for you to chew on: testing. Test suites should be
> considered an application where the developer is the end user, and the
> point of the application is to verify that the code passes tests, and if
> they don't, present the user (i.e. the developer) with sufficient
> information to debug the problem (i.e. full stack traces).

The stack traces in Test suites are generally pretty useless. If the code
doesn't pass a test, the stack trace you get, is the one provoked by an
assert like statement in the test code. At that moment the call to the
code to be tested is already done. So the stack trace won't provide any
information about the code just tested.

> So how do you test your optimized code?
>
> If you turn optimizations on globally, you're testing something which may or
> may not have the same behaviour as the code you wrote. Compiler bugs exist,
> so it is more important than ever to ensure that the post-optimization code
> passes the test suite. But if it fails, you no longer get the stack traces
> you need to debug the problem.

You don't need those stack traces to debug the problem. The only thing useful
they generally contain is the line that failed. Traceback records of the moment
some subcalculation in some subcall went wrong are not available. So TCO will
not be a real burden here.

-- 
Antoon Pardon

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

#93811

On 07/14/2015 03:43 PM, Chris Angelico wrote:
> On Tue, Jul 14, 2015 at 11:38 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> Chris Angelico <rosuav@gmail.com>:
>>
>>> On Tue, Jul 14, 2015 at 10:28 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>>>> I would rather optimize by default and disable optimizations with
>>>> --debug or equivalent.
>>> That assumes that it's simply an optimization. This is a distinct
>>> semantic change.
>> No, tail call optimization doesn't change the behavior of the program,
>> for the worse anyway.
> It does, because you lose traceback records. That's pretty significant
> when you come to try to debug something.

I doubt it would be really significant. Not compared to writing it iteratively.
When you write it iteratively, you don't get to keep a traceback record per time
you go throught the loop. So the traceback records you loose in tale call elimination
would be the traceback records you wouldn't have anyway in the iterative version.

So how would this be significant?

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

#93814

On Wed, Jul 15, 2015 at 12:02 AM, Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
> On 07/14/2015 03:43 PM, Chris Angelico wrote:
>> On Tue, Jul 14, 2015 at 11:38 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>>> Chris Angelico <rosuav@gmail.com>:
>>>
>>>> On Tue, Jul 14, 2015 at 10:28 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>>>>> I would rather optimize by default and disable optimizations with
>>>>> --debug or equivalent.
>>>> That assumes that it's simply an optimization. This is a distinct
>>>> semantic change.
>>> No, tail call optimization doesn't change the behavior of the program,
>>> for the worse anyway.
>> It does, because you lose traceback records. That's pretty significant
>> when you come to try to debug something.
>
> I doubt it would be really significant. Not compared to writing it iteratively.
> When you write it iteratively, you don't get to keep a traceback record per time
> you go throught the loop. So the traceback records you loose in tale call elimination
> would be the traceback records you wouldn't have anyway in the iterative version.
>
> So how would this be significant?

You're proposing making _every_ instance of "return func(...)" into
this kind of thing. That's not always recursion, and it's certainly
not always clear what called what to get you there.

ChrisA

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

#93821

Chris Angelico <rosuav@gmail.com>:

> You're proposing making _every_ instance of "return func(...)" into
> this kind of thing.

Yes.

> That's not always recursion,

Correct.

> and it's certainly not always clear what called what to get you there.

Correct.


Marko

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

Page 1 of 5  [1] 2 3 4 5  Next page →

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

csiph-web