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 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

#93800

On Tue, Jul 14, 2015 at 3:41 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Tail-call optimization has nothing to do with converting algorithms into
> iterations. It's a prosaic trick of dropping an unneeded stack frame
> before making a function 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.
>
> Nobody is making that claim.

Actually, that claim was made - that Python's stack would overflow if
you didn't optimize tail calls away. I don't feel like digging up
through the history to find out who first made the claim, but it was
made in this thread.

ChrisA

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

#93804

Chris Angelico <rosuav@gmail.com>:

> On Tue, Jul 14, 2015 at 3:41 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> Tail-call optimization has nothing to do with converting algorithms into
>> iterations. It's a prosaic trick of dropping an unneeded stack frame
>> before making a function 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.
>>
>> Nobody is making that claim.
>
> Actually, that claim was made - that Python's stack would overflow if
> you didn't optimize tail calls away. I don't feel like digging up
> through the history to find out who first made the claim, but it was
> made in this thread.

Nobody is making the claim that optimizing tail calls *always* saves you
from stack overflows.

Optimizing tail calls *sometimes* saves you from stack overflows.


Marko

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

#93783

On Tue, Jul 14, 2015 at 3:15 PM, Paul Rubin <no.email@nospam.invalid> wrote:
> 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.

Hmm, maybe, but I'm not sure that the transition to another state is a
goto with arguments. What triggers the transition? Is it a linear
protocol? Is it a nested protocol that completes some operation and
returns to a base state? How are these transitions recognized, and why
is that needing a "goto with arguments" to express it?

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

I use list comprehensions, but that's not the same thing as using
functional programming. What that means is that there's nothing that
we can't learn from. I'm glad functional languages exist, where people
try to make everything have no side effects and be deterministic; it's
a good discipline, and worth being aware of even when your language
doesn't enforce it. But just because functional languages like to say
"take this array and multiply every element by 4" and I like using
that same feature, that doesn't mean that I want to do everything in a
functional style.

Here's an alternative way of expressing that thought.

Do you write code such that each line does one simple thing? That's a
nice assembly language practice that's been adapted into Python.

Assembly languages tend to enforce a "one line, one operation" rule.
Python programmers often adhere to that (you don't generally see a
bunch of stuff separated by semicolons, and even "for line in lines:
print(line)" is frowned upon - add a newline!), but that doesn't mean
we want all the other trappings of assembly languages.

ChrisA

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

#93786

On Mon, Jul 13, 2015 at 11:25 PM, Chris Angelico <rosuav@gmail.com> wrote:
> (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.)

Another point in favor of an explicit tail-call keyword. Then one
couldn't make that mistake.

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

#93787

Ian Kelly <ian.g.kelly@gmail.com>:

> On Mon, Jul 13, 2015 at 11:25 PM, Chris Angelico <rosuav@gmail.com> wrote:
>> (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.)
>
> Another point in favor of an explicit tail-call keyword. Then one
> couldn't make that mistake.

How about "return"?


Marko

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

#93789

Marko Rauhamaa wrote:
> Ian Kelly <ian.g.kelly@gmail.com>:
> 
>>Another point in favor of an explicit tail-call keyword. Then one
>>couldn't make that mistake.
> 
> How about "return"?

How about "goto"? :-)

That's not entirely an unserious suggestion -- if you
really believe that a "goto with arguments" is a good
feature for a language to have, you shouldn't be
afraid to spell it as such.

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

-- 
Greg

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

#93790

Gregory Ewing <greg.ewing@canterbury.ac.nz>:

> Marko Rauhamaa wrote:
>> How about "return"?
>
> How about "goto"? :-)
>
> That's not entirely an unserious suggestion -- if you
> really believe that a "goto with arguments" is a good
> feature for a language to have, you shouldn't be
> afraid to spell it as such.
>
>   def quicksort(array, start, end):
>      midp = partition(array, start, end)
>      if midp <= (start+end)//2:
>         quicksort(array, start, midp)
>         goto quicksort(array, midp+1, end)
>      else:
>         quicksort(array, midp+1, end)
>         goto quicksort(array, start, midp)

This works already now:

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

It might even be tail-call optimized by Python. Only you can't count on
it because the language spec doesn't guarantee it.


Marko

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

#93845

Marko Rauhamaa wrote:

> It might even be tail-call optimized by Python. Only you can't count on
> it because the language spec doesn't guarantee it.

The language spec might permit it, but the BDFL has
explicitly expressed a dislike for the idea of implicit
tail call removal, so it's unlikely to ever happen
in CPython.

-- 
Greg

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

#93848

Gregory Ewing <greg.ewing@canterbury.ac.nz>:

> Marko Rauhamaa wrote:

>> It might even be tail-call optimized by Python. Only you can't count
>> on it because the language spec doesn't guarantee it.
>
> The language spec might permit it, but the BDFL has explicitly
> expressed a dislike for the idea of implicit tail call removal, so
> it's unlikely to ever happen in CPython.

Permitting wouldn't be enough.

The other problem for tail call elimination is the requirement that
functions return None by default. Smooth tail call elimination would
require that Python leave the default return value unspecified.


Marko

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

#93861

On Wednesday, July 15, 2015 at 2:44:55 AM UTC-4, Marko Rauhamaa wrote:
> Gregory Ewing <greg.ewing@canterbury.ac.nz>:
> 
> > Marko Rauhamaa wrote:
> 
> >> It might even be tail-call optimized by Python. Only you can't count
> >> on it because the language spec doesn't guarantee it.
> >
> > The language spec might permit it, but the BDFL has explicitly
> > expressed a dislike for the idea of implicit tail call removal, so
> > it's unlikely to ever happen in CPython.
> 
> Permitting wouldn't be enough.
> 
> The other problem for tail call elimination is the requirement that
> functions return None by default. Smooth tail call elimination would
> require that Python leave the default return value unspecified.

I don't understand this, can you explain more? Are you saying that the
Python specification shouldn't specify what x becomes?:

    def who_knows():
        pass

    x = who_knows()

--Ned.

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

#93862

Ned Batchelder <ned@nedbatchelder.com>:

> On Wednesday, July 15, 2015 at 2:44:55 AM UTC-4, Marko Rauhamaa wrote:
>> The other problem for tail call elimination is the requirement that
>> functions return None by default. Smooth tail call elimination would
>> require that Python leave the default return value unspecified.
>
> I don't understand this, can you explain more? Are you saying that the
> Python specification shouldn't specify what x becomes?:
>
>     def who_knows():
>         pass
>
>     x = who_knows()

Yes, that's what I'm saying. The implementation would be free to assign
any value whatsoever to x.


Marko

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

#93864

On 07/15/2015 12:55 PM, Marko Rauhamaa wrote:
> Ned Batchelder <ned@nedbatchelder.com>:
>
>> On Wednesday, July 15, 2015 at 2:44:55 AM UTC-4, Marko Rauhamaa wrote:
>>> The other problem for tail call elimination is the requirement that
>>> functions return None by default. Smooth tail call elimination would
>>> require that Python leave the default return value unspecified.
>> I don't understand this, can you explain more? Are you saying that the
>> Python specification shouldn't specify what x becomes?:
>>
>>     def who_knows():
>>         pass
>>
>>     x = who_knows()
> Yes, that's what I'm saying. The implementation would be free to assign
> any value whatsoever to x.

And can you explain why this would be needed foor smooth tail call elimination?

-- 
Antoon Pardon.

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

#93865

On Wednesday, July 15, 2015 at 6:56:10 AM UTC-4, Marko Rauhamaa wrote:
> Ned Batchelder <ned@nedbatchelder.com>:
> 
> > On Wednesday, July 15, 2015 at 2:44:55 AM UTC-4, Marko Rauhamaa wrote:
> >> The other problem for tail call elimination is the requirement that
> >> functions return None by default. Smooth tail call elimination would
> >> require that Python leave the default return value unspecified.
> >
> > I don't understand this, can you explain more? Are you saying that the
> > Python specification shouldn't specify what x becomes?:
> >
> >     def who_knows():
> >         pass
> >
> >     x = who_knows()
> 
> Yes, that's what I'm saying. The implementation would be free to assign
> any value whatsoever to x.

I don't understand why that is helpful for TCE?  Can you explain?  How does
specifying None make "smooth TCE" difficult?

--Ned.

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

#93867

Ned Batchelder <ned@nedbatchelder.com>:

> On Wednesday, July 15, 2015 at 6:56:10 AM UTC-4, Marko Rauhamaa wrote:
>> Ned Batchelder <ned@nedbatchelder.com>:
>> > I don't understand this, can you explain more? Are you saying that the
>> > Python specification shouldn't specify what x becomes?:
>> >
>> >     def who_knows():
>> >         pass
>> >
>> >     x = who_knows()
>> 
>> Yes, that's what I'm saying. The implementation would be free to assign
>> any value whatsoever to x.
>
> I don't understand why that is helpful for TCE?  Can you explain?  How does
> specifying None make "smooth TCE" difficult?

As Chris already pointed out, tail procedure calls can't be eliminated
otherwise. An example:

   def some_func():
       do_stuff()
       more_stuff()

Now, for Python to replace the call to "more_stuff()" with a simple
jump, there can't be an implicit "return None" following it. Instead,
"some_func()" must be allowed to return whatever "more_stuff()" returns.

You could require the programmer to write:

   def some_func():
       do_stuff()
       return more_stuff()

but that's not good style. In fact, it is not good style to write code
that omits "return None" when None needs to be returned. IOW, the
unspecifiedness of procedure return values is already the unwritten
assumption in good Python code.


Marko

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

#93986

On Wednesday, July 15, 2015 at 4:54:51 PM UTC+5:30, Marko Rauhamaa wrote:
> Ned Batchelder:
> 
> > On Wednesday, July 15, 2015 at 6:56:10 AM UTC-4, Marko Rauhamaa wrote:
> >> Ned Batchelder :
> >> > I don't understand this, can you explain more? Are you saying that the
> >> > Python specification shouldn't specify what x becomes?:
> >> >
> >> >     def who_knows():
> >> >         pass
> >> >
> >> >     x = who_knows()
> >> 
> >> Yes, that's what I'm saying. The implementation would be free to assign
> >> any value whatsoever to x.
> >
> > I don't understand why that is helpful for TCE?  Can you explain?  How does
> > specifying None make "smooth TCE" difficult?
> 
> As Chris already pointed out, tail procedure calls can't be eliminated
> otherwise. An example:
> 
>    def some_func():
>        do_stuff()
>        more_stuff()
> 
> Now, for Python to replace the call to "more_stuff()" with a simple
> jump, there can't be an implicit "return None" following it. Instead,
> "some_func()" must be allowed to return whatever "more_stuff()" returns.
> 
> You could require the programmer to write:
> 
>    def some_func():
>        do_stuff()
>        return more_stuff()
> 
> but that's not good style. In fact, it is not good style to write code
> that omits "return None" when None needs to be returned. IOW, the
> unspecifiedness of procedure return values is already the unwritten
> assumption in good Python code.
 
An interesting insight.
For sometime now I am seeing that C's void-return's are a mess-up of Pascal procedures.
And python's None-returns are a mess-up of C's void-return:
http://blog.languager.org/2015/06/functional-programming-moving-target.html

This was mostly from pedagogic data of observing student confusions
Now you are giving a new take on why None-return could be a language-design
anti-pattern. So thanks for that.

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

#93793

On 14/07/2015 07:29, Gregory Ewing wrote:
> Marko Rauhamaa wrote:
>> Ian Kelly <ian.g.kelly@gmail.com>:
>>
>>> Another point in favor of an explicit tail-call keyword. Then one
>>> couldn't make that mistake.
>>
>> How about "return"?
>
> How about "goto"? :-)
>

Why not "goto"?  It's use is scattered throughout the cpython code, and 
to my knowledge there's no paper that says *NEVER* use it.

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

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

#93795

On Mon, Jul 13, 2015 at 11:57 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Ian Kelly <ian.g.kelly@gmail.com>:
>
>> On Mon, Jul 13, 2015 at 11:25 PM, Chris Angelico <rosuav@gmail.com> wrote:
>>> (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.)
>>
>> Another point in favor of an explicit tail-call keyword. Then one
>> couldn't make that mistake.
>
> How about "return"?

I think you miss my point entirely. "return" doesn't mean tail-call
optimize; it just means to return the result. This is what led to the
confusion responsible for the bug that Chris pointed out in the first
place. With a keyword that explicitly means "perform tail-call
optimization *and* return", the association of the keyword with the
optimization is much clearer, and the programmer is much less likely
to mistakenly omit it.

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

#93797

Ian Kelly <ian.g.kelly@gmail.com>:

> On Mon, Jul 13, 2015 at 11:57 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> How about "return"?
>
> I think you miss my point entirely. "return" doesn't mean tail-call
> optimize;

Why not?

> it just means to return the result.

Same difference.

> This is what led to the confusion responsible for the bug that Chris
> pointed out in the first place. With a keyword that explicitly means
> "perform tail-call optimization *and* return",

That could well be the explicit definition of the "return" statement in
Python without changing the behavior of any working Python program
today.

> the association of the keyword with the optimization is much clearer,
> and the programmer is much less likely to mistakenly omit it.

The programmer shouldn't be controlling tail call optimizations.


Marko

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

#93808

On Tue, Jul 14, 2015 at 2:33 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Ian Kelly <ian.g.kelly@gmail.com>:
>
>> On Mon, Jul 13, 2015 at 11:57 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>>> How about "return"?
>>
>> I think you miss my point entirely. "return" doesn't mean tail-call
>> optimize;
>
> Why not?
>
>> it just means to return the result.
>
> Same difference.
>
>> This is what led to the confusion responsible for the bug that Chris
>> pointed out in the first place. With a keyword that explicitly means
>> "perform tail-call optimization *and* return",
>
> That could well be the explicit definition of the "return" statement in
> Python without changing the behavior of any working Python program
> today.

To the compiler. It won't be viewed that way be the programmer,
however. So they'll forget that the "return" is necessary to the
optimization and just write quicksort() instead of return quicksort().

>> the association of the keyword with the optimization is much clearer,
>> and the programmer is much less likely to mistakenly omit it.
>
> The programmer shouldn't be controlling tail call optimizations.

The programmer controls it regardless.

    return foo()  # TCO

    result = foo()  # No TCO
    return result  # No TCO

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

#93818

Ian Kelly <ian.g.kelly@gmail.com>:

> On Tue, Jul 14, 2015 at 2:33 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> The programmer shouldn't be controlling tail call optimizations.
>
> The programmer controls it regardless.
>
>     return foo()  # TCO
>
>     result = foo()  # No TCO
>     return result  # No TCO

Not necessarily. Compile this function with gcc ("gcc -S -O2 atoi.c"):

========================================================================
int atoi(const char *str, int n)
{
    if (str && *str)
        n = atoi(str + 1, n * 10 + *str - '0');
    return n;
}
========================================================================
(Example modified from <URL: http://stackoverflow.com/questions/34125/wh
ich-if-any-c-compilers-do-tail-recursion-optimization#220660>.)

You'll see that the generated code is tail-call-optimized.


Marko

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

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

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

csiph-web