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

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

Tail recursion to while iteration in 2 easy steps

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

Contents

  Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-01 17:30 -0400
    Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-01 22:16 -0700
      Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-02 10:23 +0200
        Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-02 06:29 -0700
      Re: Tail recursion to while iteration in 2 easy steps Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-03 22:57 +0530
        Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-04 03:52 -0700
    Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-02 10:17 +0200
      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-02 11:59 -0700
      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-02 14:05 -0700
        Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-04 11:49 +0200
          Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-04 10:51 +0000
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-04 18:32 -0400
            Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-07 19:15 +0200
              Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-07 19:57 +0200
                Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-08 10:56 +0200
                  Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 12:49 +0300
              Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-07 16:42 -0400
              Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-07 17:19 -0400
                Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-08 10:41 +0200
              Re: Tail recursion to while iteration in 2 easy steps MRAB <python@mrabarnett.plus.com> - 2013-10-07 22:39 +0100
              Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 18:03 -0400
              Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 15:47 -0700
                Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-07 23:50 +0000
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 17:24 -0700
                    Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 20:17 -0700
                      Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 10:46 +0530
                        Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 22:44 -0700
                          Re: Formal-ity and the Church-Turing thesis Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-10-08 07:43 +0100
                          Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 18:31 +0530
                            Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-08 06:33 -0700
                        Re: Formal-ity and the Church-Turing thesis Steven D'Aprano <steve@pearwood.info> - 2013-10-08 07:50 +0000
                          Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 18:16 +0530
                            Re: Formal-ity and the Church-Turing thesis Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-08 13:11 +0000
                              Re: Formal-ity and the Church-Turing thesis Robert Day <robertkday@gmail.com> - 2013-10-08 14:25 +0100
                              Re: Formal-ity and the Church-Turing thesis Chris Angelico <rosuav@gmail.com> - 2013-10-09 08:36 +1100
                      Re: Formal-ity and the Church-Turing thesis Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 22:19 -0700
                        Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 23:01 -0700
                          Re: Formal-ity and the Church-Turing thesis Mark Janssen <dreamingforward@gmail.com> - 2013-10-08 10:39 -0700
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 17:16 -0700
                    Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-08 02:36 +0000
                      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 20:27 -0700
                        Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve@pearwood.info> - 2013-10-08 09:22 +0000
                          Re: Tail recursion to while iteration in 2 easy steps Charles Hixson <charleshixsn@earthlink.net> - 2013-10-09 15:45 -0700
                  Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 22:46 -0400
                  Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 10:25 +0300
                  Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-08 11:18 +0200
                Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 22:45 -0400
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 20:34 -0700
      Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 18:17 -0400
        Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-03 01:24 +0000
          Re: Tail recursion to while iteration in 2 easy steps Dave Angel <davea@davea.name> - 2013-10-03 01:39 +0000
          Re: Tail recursion to while iteration in 2 easy steps MRAB <python@mrabarnett.plus.com> - 2013-10-03 02:46 +0100
            Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-03 02:34 +0000
              Re: Tail recursion to while iteration in 2 easy steps Chris Angelico <rosuav@gmail.com> - 2013-10-03 14:14 +1000
              Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-03 10:16 -0400
              Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-03 15:04 -0400
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 22:41 -0400
            Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-04 01:30 +0000
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 23:06 -0400
          Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-03 10:14 -0400
          Literal syntax for frozenset, frozendict (was: Tail recursion to while iteration in 2 easy steps) Ben Finney <ben+python@benfinney.id.au> - 2013-10-04 10:18 +1000
          Re: Literal syntax for frozenset, frozendict Ethan Furman <ethan@stoneleaf.us> - 2013-10-03 18:31 -0700
      Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-03 14:52 +0000
        Re: Tail recursion to while iteration in 2 easy steps Neil Cerutti <neilc@norwich.edu> - 2013-10-03 16:03 +0000
          Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-04 10:16 +0000
            Re: Tail recursion to while iteration in 2 easy steps Ian Kelly <ian.g.kelly@gmail.com> - 2013-10-04 04:41 -0600
            Re: Tail recursion to while iteration in 2 easy steps Ian Kelly <ian.g.kelly@gmail.com> - 2013-10-04 04:46 -0600
              Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-04 11:16 +0000
            Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-04 14:11 +0300
            Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-04 17:14 -0400
            Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-05 09:39 +0200
            Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-07 17:27 -0400
              Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 10:11 +0300
            Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-08 11:43 +0200

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

#55447 — Literal syntax for frozenset, frozendict (was: Tail recursion to while iteration in 2 easy steps)

random832@fastmail.us writes:

> Hey, while we're on the subject, can we talk about frozen(set|dict)
> literals again? I really don't understand why this discussion fizzles
> out whenever it's brought up on python-ideas.

Can you start us off by searching for previous threads discussing it,
and summarise the arguments here?

-- 
 \     “If you ever catch on fire, try to avoid seeing yourself in the |
  `\        mirror, because I bet that's what REALLY throws you into a |
_o__)                                             panic.” —Jack Handey |
Ben Finney

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

#55449 — Re: Literal syntax for frozenset, frozendict

On 10/03/2013 05:18 PM, Ben Finney wrote:
> random832@fastmail.us writes:
>
>> Hey, while we're on the subject, can we talk about frozen(set|dict)
>> literals again? I really don't understand why this discussion fizzles
>> out whenever it's brought up on python-ideas.
>
> Can you start us off by searching for previous threads discussing it,
> and summarise the arguments here?

And then start a new thread.  :)

--
~Ethan~

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

#55414

Alain Ketterlin <alain@dpt-info.u-strasbg.fr> wrote:

> Terry Reedy <tjreedy@udel.edu> writes:
> 
>> Part of the reason that Python does not do tail call optimization is
>> that turning tail recursion into while iteration is almost trivial,
>> once you know the secret of the two easy steps. Here it is.
>>
>> Assume that you have already done the work of turning a body recursive
>> ('not tail recursive') form like
>>
>> def fact(n): return 1 if n <= 1 else n * fact(n-1)
>>
>> into a tail recursion like
> [...]
> 
> How do know that either "<=" or "*" didn't rebind the name "fact" to
> something else? I think that's the main reason why python cannot apply
> any procedural optimization (even things like inlining are impossible,
> or possible only under very conservative assumption, that make it
> worthless).
> 

That isn't actually sufficient reason.

It isn't hard to imagine adding a TAIL_CALL opcode to the interpreter that 
checks whether the function to be called is the same as the current 
function and if it is just updates the arguments and jumps to the start of 
the code block. If the function doesn't match it would simply fall through 
to doing the same as the current CALL_FUNCTION opcode.

There is an issue that you would lose stack frames in any traceback. Also 
it means code for this modified Python wouldn't run on other non-modified 
interpreters, but it is at least theoretically possible without breaking 
Python's assumptions.

-- 
Duncan Booth http://kupuguy.blogspot.com

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

#55416

On 2013-10-03, Duncan Booth <duncan.booth@invalid.invalid> wrote:
>> How do know that either "<=" or "*" didn't rebind the name
>> "fact" to something else? I think that's the main reason why
>> python cannot apply any procedural optimization (even things
>> like inlining are impossible, or possible only under very
>> conservative assumption, that make it worthless).
>
> That isn't actually sufficient reason.
>
> It isn't hard to imagine adding a TAIL_CALL opcode to the
> interpreter that checks whether the function to be called is
> the same as the current function and if it is just updates the
> arguments and jumps to the start of the code block.

Tail call optimization doesn't involve verification that the
function is calling itself; you just have to verfify that the
call is in tail position.

The current frame would be removed from the stack frame and
replaced with the one that results from calling the function.

> There is an issue that you would lose stack frames in any
> traceback.

I don't think that's a major issue. Frames that got replaced
would quite uninteresting. 

> Also it means code for this modified Python wouldn't run on
> other non-modified interpreters, but it is at least
> theoretically possible without breaking Python's assumptions.

In any case it's so easy to implement yourself I'm not sure
there's any point.

-- 
Neil Cerutti

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

#55466

Neil Cerutti <neilc@norwich.edu> wrote:
> On 2013-10-03, Duncan Booth <duncan.booth@invalid.invalid> wrote:
>> It isn't hard to imagine adding a TAIL_CALL opcode to the
>> interpreter that checks whether the function to be called is
>> the same as the current function and if it is just updates the
>> arguments and jumps to the start of the code block.
> 
> Tail call optimization doesn't involve verification that the
> function is calling itself; you just have to verfify that the
> call is in tail position.

You misunderstood me. As usually implemented tail call recursion doesn't 
require verifying that the function is calling itself, but in Python the 
function could be rebound so a check would be a necessary protection 
against this unlikely situation. Consider this Python:

@some_decorator
def fact(n, acc=1):
   if n <= 1:
       return acc
   return fact(n-1, n*acc)

Is that tail recursion or not?

You cannot tell whether or not that is tail recursion unless you know the 
definition of 'some_decorator' and even then the answer may vary from run 
to run.

-- 
Duncan Booth http://kupuguy.blogspot.com

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

#55467

On Fri, Oct 4, 2013 at 4:16 AM, Duncan Booth
<duncan.booth@invalid.invalid> wrote:
> Neil Cerutti <neilc@norwich.edu> wrote:
>> On 2013-10-03, Duncan Booth <duncan.booth@invalid.invalid> wrote:
>>> It isn't hard to imagine adding a TAIL_CALL opcode to the
>>> interpreter that checks whether the function to be called is
>>> the same as the current function and if it is just updates the
>>> arguments and jumps to the start of the code block.
>>
>> Tail call optimization doesn't involve verification that the
>> function is calling itself; you just have to verfify that the
>> call is in tail position.
>
> You misunderstood me. As usually implemented tail call recursion doesn't
> require verifying that the function is calling itself, but in Python the
> function could be rebound so a check would be a necessary protection
> against this unlikely situation. Consider this Python:
>
> @some_decorator
> def fact(n, acc=1):
>    if n <= 1:
>        return acc
>    return fact(n-1, n*acc)
>
> Is that tail recursion or not?
>
> You cannot tell whether or not that is tail recursion unless you know the
> definition of 'some_decorator' and even then the answer may vary from run
> to run.

There is no doubt that it's a tail call.  Whether it is recursion is
irrelevant to optimizing it.  The reason we talk about "tail call
recursion" specifically is because the recursive case is the one that
makes the optimization worthwhile, not because the recursion is
necessary to perform the optimization.

It is possible that fact is recursive but that some_decorator adds
additional stack frames that are not tail calls and not optimizable.
If this were the case, then the recursion would still eventually hit
the stack limit, but there would still be benefit in optimizing the
"fact" frames, as it would increase the allowable depth before the
stack limit is reached.  So I see no reason to check the identity of
the called function before optimizing the tail call.

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

#55472

On Fri, Oct 4, 2013 at 4:41 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> There is no doubt that it's a tail call.  Whether it is recursion is
> irrelevant to optimizing it.  The reason we talk about "tail call
> recursion" specifically is because the recursive case is the one that
> makes the optimization worthwhile, not because the recursion is
> necessary to perform the optimization.
>
> It is possible that fact is recursive but that some_decorator adds
> additional stack frames that are not tail calls and not optimizable.
> If this were the case, then the recursion would still eventually hit
> the stack limit, but there would still be benefit in optimizing the
> "fact" frames, as it would increase the allowable depth before the
> stack limit is reached.  So I see no reason to check the identity of
> the called function before optimizing the tail call.

On the other hand, if you start optimizing every tail call and not
just the recursive functions, then I can see where that could start to
get problematic for debugging -- as arbitrary functions get removed
from the stack traces just because they happened to end in tail calls.

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

#55475

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

> On Fri, Oct 4, 2013 at 4:41 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
>> There is no doubt that it's a tail call.  Whether it is recursion is
>> irrelevant to optimizing it.  The reason we talk about "tail call
>> recursion" specifically is because the recursive case is the one that
>> makes the optimization worthwhile, not because the recursion is
>> necessary to perform the optimization.
>>
>> It is possible that fact is recursive but that some_decorator adds
>> additional stack frames that are not tail calls and not optimizable.
>> If this were the case, then the recursion would still eventually hit
>> the stack limit, but there would still be benefit in optimizing the
>> "fact" frames, as it would increase the allowable depth before the
>> stack limit is reached.  So I see no reason to check the identity of
>> the called function before optimizing the tail call.
> 
> On the other hand, if you start optimizing every tail call and not
> just the recursive functions, then I can see where that could start to
> get problematic for debugging -- as arbitrary functions get removed
> from the stack traces just because they happened to end in tail calls.

Quite so. Losing some stack frames in the traceback because tail recursion 
was optimised is probably no big deal. Losing arbitrary stack frames 
because of a more widespread tail call optimisation would not IMHO fit with 
the spirit of Python except possibly as an optional optimisation that was 
off by default.


-- 
Duncan Booth http://kupuguy.blogspot.com

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

#55473

Duncan Booth writes:

> Neil Cerutti wrote:
> > On 2013-10-03, Duncan Booth <duncan.booth@invalid.invalid> wrote:
> >> It isn't hard to imagine adding a TAIL_CALL opcode to the
> >> interpreter that checks whether the function to be called is
> >> the same as the current function and if it is just updates the
> >> arguments and jumps to the start of the code block.
> > 
> > Tail call optimization doesn't involve verification that the
> > function is calling itself; you just have to verfify that the
> > call is in tail position.
> 
> You misunderstood me. As usually implemented tail call recursion
> doesn't require verifying that the function is calling itself, but
> in Python the function could be rebound so a check would be a
> necessary protection against this unlikely situation. Consider this
> Python:
> 
> @some_decorator
> def fact(n, acc=1):
>    if n <= 1:
>        return acc
>    return fact(n-1, n*acc)
> 
> Is that tail recursion or not?
> 
> You cannot tell whether or not that is tail recursion unless you
> know the definition of 'some_decorator' and even then the answer may
> vary from run to run.

Ignoring the decorator, fact(n-1, n*acc) is in a tail position because
it follows the keyword return. It doesn't matter what function fact is
at the time: the remaining action in the caller is to return.

Tail positions, with respect to enclosing code, are defined
syntactically.

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

#56147

On 10/4/2013 6:46 AM, Ian Kelly wrote:

> On the other hand, if you start optimizing every tail call and not
> just the recursive functions, then I can see where that could start to
> get problematic for debugging -- as arbitrary functions get removed
> from the stack traces just because they happened to end in tail calls.

The idea of CPython space-optimizing tail calls when the call is made 
has been suggested on python-ideas. Guido verified that it is 
technically possible with the current bytecode interpreter but rejected 
it because it would arbitrarily mess up stack traces.

-- 
Terry Jan Reedy

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

#56172

Op 04-10-13 23:14, Terry Reedy schreef:
> On 10/4/2013 6:46 AM, Ian Kelly wrote:
>
>> On the other hand, if you start optimizing every tail call and not
>> just the recursive functions, then I can see where that could start to
>> get problematic for debugging -- as arbitrary functions get removed
>> from the stack traces just because they happened to end in tail calls.
>
> The idea of CPython space-optimizing tail calls when the call is made
> has been suggested on python-ideas. Guido verified that it is
> technically possible with the current bytecode interpreter but rejected
> it because it would arbitrarily mess up stack traces.

What does this mean?

Does it mean that a naive implementation would arbitrarily mess up
stack traces and he wasn't interested in investigating more
sophisticated implementations?

Does it mean he just didn't like the idea a stack trace wouldn't be a
100% represenatation of the active call history?

Does it mean he investigated more sphisticated implementations but found
them to have serious short comings that couldn't be remedied easily?

-- 
Antoon Pardon

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

#56331

On Sat, Oct 5, 2013, at 3:39, Antoon Pardon wrote:
> What does this mean?
> 
> Does it mean that a naive implementation would arbitrarily mess up
> stack traces and he wasn't interested in investigating more
> sophisticated implementations?
> 
> Does it mean he just didn't like the idea a stack trace wouldn't be a
> 100% represenatation of the active call history?
> 
> Does it mean he investigated more sphisticated implementations but found
> them to have serious short comings that couldn't be remedied easily?

The entire point of tail call optimization requires not keeping the
intervening stack frames around, in _any_ form, so as to allow
arbitrarily deep recursion without ever having the possibility of a
stack overflow. An implementation which reduced but did not eliminate
the space used per call would not be worthwhile because it would not
enable the recursive functional programming patterns that mandatory tail
call optimization allows.

You could require that an "optimizable tail call" be made explicit.
Actually, I suspect it might be possible to do this now, by abusing
exception handling as a control flow mechanism.

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

#56358

random832@fastmail.us writes:

> The entire point of tail call optimization requires not keeping the
> intervening stack frames around, in _any_ form, so as to allow
> arbitrarily deep recursion without ever having the possibility of a
> stack overflow. An implementation which reduced but did not
> eliminate the space used per call would not be worthwhile because it
> would not enable the recursive functional programming patterns that
> mandatory tail call optimization allows.
> 
> You could require that an "optimizable tail call" be made explicit.
> Actually, I suspect it might be possible to do this now, by abusing
> exception handling as a control flow mechanism.

Python code already marks many of the functionally relevant tail calls
with 'return'. It just wants to retain the trace.

Another keyword could be used to indicate that the programmer does not
want a stack frame retained. It's probably too much to suggest 'please
return', but how about 'goto return'?

A tail call is a 'goto that passes arguments', and I think 'goto' is a
keyword already.

(Actually I just wanted to suggest 'please return'. Not seriously.)

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

#56378

Op 07-10-13 23:27, random832@fastmail.us schreef:
> On Sat, Oct 5, 2013, at 3:39, Antoon Pardon wrote:
>> What does this mean?
>>
>> Does it mean that a naive implementation would arbitrarily mess up
>> stack traces and he wasn't interested in investigating more
>> sophisticated implementations?
>>
>> Does it mean he just didn't like the idea a stack trace wouldn't be a
>> 100% represenatation of the active call history?
>>
>> Does it mean he investigated more sphisticated implementations but found
>> them to have serious short comings that couldn't be remedied easily?
> 
> The entire point of tail call optimization requires not keeping the
> intervening stack frames around, in _any_ form, so as to allow
> arbitrarily deep recursion without ever having the possibility of a
> stack overflow. An implementation which reduced but did not eliminate
> the space used per call would not be worthwhile because it would not
> enable the recursive functional programming patterns that mandatory tail
> call optimization allows.

So? What about an implementation that would keep its stackframes
normally until it deteced recursion had occured. From then on it
would only keep what it already had plus the four top stackframes
(assuming it are all tail calls for the moment). This would allow
for a stacktrace of the last four calls and essentially doesn't need
any space per call from then on.

-- 
Antoon Pardon

[toc] | [prev] | [standalone]

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

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

csiph-web