Proper tail recursion

Discussion in 'Python' started by Christopher T King, Jul 6, 2004.

  1. Is it feasable, and/or desirable to have Python optimize tail-recursive
    calls, similar to Scheme and gcc -O2? i.e. effectively compile this:

    def foo(n):
    return foo(n-1)

    into this:

    def foo(n):
    goto foo(n-1)

    This would naturally only be enabled in optimized bytecode.

    On an unrelated, Scheme-ish note, is there any way for a generator to
    access itself? i.e. I want to be able to write this:

    def gen():
    yield get_current_continuation(),someothergenerator()

    Thanks,
    Chris
     
    Christopher T King, Jul 6, 2004
    #1
    1. Advertising

  2. Christopher T King

    Duncan Booth Guest

    Christopher T King <> wrote in
    news:p:

    > Is it feasable, and/or desirable to have Python optimize tail-recursive
    > calls, similar to Scheme and gcc -O2? i.e. effectively compile this:
    >
    > def foo(n):
    > return foo(n-1)
    >
    > into this:
    >
    > def foo(n):
    > goto foo(n-1)
    >
    > This would naturally only be enabled in optimized bytecode.
    >
    > On an unrelated, Scheme-ish note, is there any way for a generator to
    > access itself? i.e. I want to be able to write this:
    >
    > def gen():
    > yield get_current_continuation(),someothergenerator()
    >
    > Thanks,
    > Chris
    >
    >


    Just because a function looks recursive to you, doesn't mean it actually is
    recursive when it gets called.

    How do you propose to handle this?

    def foo(n):
    return foo(n-1)

    def baz(n):
    return 0

    bar = foo
    foo = baz
    bar(3)

    One solution might be to provide a keyword which refers to the currently
    executing function: this would be useful not only for recursion but also to
    access attributes on the function. These help with methods and generators
    which as you noted find it hard to reference themselves.

    However, I don't believe there is at present any easy way to get hold of
    the current executing function or generator object.
     
    Duncan Booth, Jul 6, 2004
    #2
    1. Advertising

  3. Duncan Booth <> wrote:

    > Christopher T King <> wrote in
    > news:p:


    >> Is it feasable, and/or desirable to have Python optimize tail-recursive
    >> calls, similar to Scheme and gcc -O2? i.e. effectively compile this:


    > Just because a function looks recursive to you, doesn't mean it actually is
    > recursive when it gets called.


    > How do you propose to handle this?


    > def foo(n):
    > return foo(n-1)


    > def baz(n):
    > return 0


    > bar = foo
    > foo = baz
    > bar(3)


    Instead of doing tail recursion elimination, one could implement
    general tail call optimization. It shouldn't be too difficult to
    make the compiler recognize tail calls, i.e

    return spam(params)

    outside any try statement. It could then generate the byte code
    TAIL_CALL instead of CALL_FUNCTION. TAIL_CALL would throw away
    the current stack frame before calling spam().

    This doesn't give you the performance improvement of not making a
    function call, but at least it makes a tail recursive function
    run in constant space.

    Of course, some care needs to be taken to ensure that the current
    stack frame isn't thrown away if the called function is a local
    function accessing the namespace of the calling function. I.e,
    in the case

    def parrot(x):
    def spam(n):
    return n + y
    y = x*x
    return spam(5)

    the call to 'return spam(5)' must make sure that 'y' is
    accessible to spam(). That might need a runtime check in many
    cases. (In the common case of there being no local functions at
    all in the caller, it can be determined statically, of course.)
    Hmm, there is an attribute 'func_closure' on function objects,
    that at a quick glance seems to be None if it doesn't access the
    surrounding namespace.


    > However, I don't believe there is at present any easy way to get hold of
    > the current executing function or generator object.


    Raising and catching an exception, and digging through the
    traceback object might give you enough information to do
    that. But it's not very pretty, and I'm not sure that it
    is portable between C-Python, Jython, PyPy, Psyco, and any
    other Python compiler/interpreter.


    --
    Thomas Bellman, Lysator Computer Club, Linköping University, Sweden
    "The one who says it cannot be done should ! bellman @ lysator.liu.se
    never interrupt the one who is doing it." ! Make Love -- Nicht Wahr!
     
    Thomas Bellman, Jul 6, 2004
    #3
  4. On Tue, 6 Jul 2004, Thomas Bellman wrote:

    > Duncan Booth <> wrote:
    >
    > > Just because a function looks recursive to you, doesn't mean it actually is
    > > recursive when it gets called.

    >
    > > How do you propose to handle this?

    >
    > > def foo(n):
    > > return foo(n-1)

    >
    > > def baz(n):
    > > return 0

    >
    > > bar = foo
    > > foo = baz
    > > bar(3)

    >
    > Instead of doing tail recursion elimination, one could implement
    > general tail call optimization. It shouldn't be too difficult to
    > make the compiler recognize tail calls, i.e
    >
    > return spam(params)
    >
    > outside any try statement. It could then generate the byte code
    > TAIL_CALL instead of CALL_FUNCTION. TAIL_CALL would throw away
    > the current stack frame before calling spam().
    >
    > This doesn't give you the performance improvement of not making a
    > function call, but at least it makes a tail recursive function
    > run in constant space.


    What he said. :) I don't mean to optimize recursive functions into loops,
    but simply to replace normal calls at the end of functions with tail
    calls.

    > Of course, some care needs to be taken to ensure that the current
    > stack frame isn't thrown away if the called function is a local
    > function accessing the namespace of the calling function.
    > [snip]


    I'm just guessing here (my knowledge of the internals isn't too great),
    but in the case of closures, isn't it okay to throw away the stack space,
    since any variables needed are kept in the function's func_closure
    attribute? To modify your example:

    def parrot(x):
    def spam(n):
    return n + y
    y = x*x
    return spam

    print parrot(3)(5)

    This returns 28, as expected, and is (roughly) functionally no different
    from a tail-callified version of your parrot() function.

    > > However, I don't believe there is at present any easy way to get hold of
    > > the current executing function or generator object.

    >
    > Raising and catching an exception, and digging through the
    > traceback object might give you enough information to do
    > that. But it's not very pretty, and I'm not sure that it
    > is portable between C-Python, Jython, PyPy, Psyco, and any
    > other Python compiler/interpreter.


    I don't need it that badly ;) -- it just would have made a neat
    generaliztion in my code, rather than special-casing a yield of 'None' to
    refer to the generator that yielded it.
     
    Christopher T King, Jul 6, 2004
    #4
  5. Christopher T King

    Duncan Booth Guest

    Thomas Bellman <> wrote in
    news:ccekq2$8kp$:

    > Instead of doing tail recursion elimination, one could implement
    > general tail call optimization. It shouldn't be too difficult to
    > make the compiler recognize tail calls, i.e
    >
    > return spam(params)
    >
    > outside any try statement. It could then generate the byte code
    > TAIL_CALL instead of CALL_FUNCTION. TAIL_CALL would throw away
    > the current stack frame before calling spam().
    >


    That ought to be doable. The main disadvantages I can see are that stack
    backtraces will be incomplete (which could be confusing), and unbounded
    recursion won't be caught (which may or may not matter).

    > This doesn't give you the performance improvement of not making a
    > function call, but at least it makes a tail recursive function
    > run in constant space.
    >
    > Of course, some care needs to be taken to ensure that the current
    > stack frame isn't thrown away if the called function is a local
    > function accessing the namespace of the calling function. I.e,
    > in the case
    >
    > def parrot(x):
    > def spam(n):
    > return n + y
    > y = x*x
    > return spam(5)
    >
    > the call to 'return spam(5)' must make sure that 'y' is
    > accessible to spam().


    No it doesn't. References to 'y' in parrot are handled indirectly by
    storing the value in a cell object. The stack frame only holds a reference
    to the cell object. So long as the cell still has another reference the
    value remains valid.

    >> However, I don't believe there is at present any easy way to get hold
    >> of the current executing function or generator object.

    >
    > Raising and catching an exception, and digging through the
    > traceback object might give you enough information to do
    > that. But it's not very pretty, and I'm not sure that it
    > is portable between C-Python, Jython, PyPy, Psyco, and any
    > other Python compiler/interpreter.
    >

    I'm pretty sure that there is nothing useful in the traceback object. You
    can find out which instruction was executing, but this doesn't help in
    identifying the function since several functions could share the same code
    (an active generator being an obvious example where this happens).
     
    Duncan Booth, Jul 7, 2004
    #5
  6. Poking around in ceval.c, I discovered the PREDICT macros, and plan to
    make a preliminary implementation of tail calls using a similar test (use
    tail code call for any CALL_FUNCTION followed by a RETURN_VALUE). But I
    was just wondering, is there any reason why LOAD_CONST and friends don't
    check for a following RETURN_VALUE to avoid the push/loop/pop cycle and
    rather simply return the value?
     
    Christopher T King, Jul 8, 2004
    #6
  7. On Wed, 7 Jul 2004, Christopher T King wrote:

    > Poking around in ceval.c, I discovered the PREDICT macros, and plan to
    > make a preliminary implementation of tail calls using a similar test (use


    I take that back. The intertwinement of C functions and Python calls on
    the stack makes this nearly impossible -- there's no easy way to pop both
    the C and Python stacks before calling the next function (it could be
    partially done popping only the Python stack, though). Methinks tail calls
    will have to wait for Stackless.
     
    Christopher T King, Jul 8, 2004
    #7
  8. Christopher T King

    Chris King Guest

    Christopher T King wrote:
    > I take that back. The intertwinement of C functions and Python calls on
    > the stack makes this nearly impossible -- there's no easy way to pop both
    > the C and Python stacks before calling the next function (it could be
    > partially done popping only the Python stack, though). Methinks tail calls
    > will have to wait for Stackless.


    Here I am, replying to myself again :)

    I'm trying a new implementation, making good use of a loop around the
    entirety of PyEval_EvalFrame(). Unfortunately, my changes cause the
    interpreter to segfault after a couple of tail calls. A debugger shows
    that 0xffffffff is getting stuck into a pool->freeblock in
    PyObject_Free(), and then is subsequently dereferenced in
    PyObject_Malloc() (causing the segfault).

    Could this be caused by my code Py_DECREFing an object too many times,
    but leaving a pointer to it somewhere? (My changes don't explicitly set
    anything to 0xffffffff or -1.) Or am I just in way over my head? :p
     
    Chris King, Jul 10, 2004
    #8
  9. Christopher T King

    Tim Peters Guest

    [Chris King]
    > I'm trying a new implementation, making good use of a loop around the
    > entirety of PyEval_EvalFrame(). Unfortunately, my changes cause the
    > interpreter to segfault after a couple of tail calls. A debugger shows
    > that 0xffffffff is getting stuck into a pool->freeblock in
    > PyObject_Free(), and then is subsequently dereferenced in
    > PyObject_Malloc() (causing the segfault).
    >
    > Could this be caused by my code Py_DECREFing an object too many times,
    > but leaving a pointer to it somewhere? (My changes don't explicitly set
    > anything to 0xffffffff or -1.) Or am I just in way over my head? :p


    WHen fiddling with Python internals, build Python in debug mode. That
    enables many checks that will save you weeks of debugging. For
    example, if you decref an object too many times, the expansion of the
    Py_DECREF macro in a debug build will catch that and complain the
    instant the refcount goes negative. In a debug build pymalloc also
    pads both ends of allocated regions with special byte patterns,
    initializes newly allocated memory with another special byte pattern,
    and overwrites newly freed memory with a third special byte pattern.
    That's very effective at catching many kinds of problems too. Read
    Misc/SpecialBuilds.txt.

    And yes, of course you're in way over your head. But that's how you
    learn to swim, so enjoy it <wink>.
     
    Tim Peters, Jul 10, 2004
    #9
  10. Christopher T King

    Chris King Guest

    Tim Peters wrote:
    > WHen fiddling with Python internals, build Python in debug mode. That
    > enables many checks that will save you weeks of debugging.


    Thanks! I found the bug -- I was just forgetting to reset the stack
    after a call_function.

    I have a preliminary implementation ready, the patch is against 2.4a1:
    http://users.wpi.edu/~squirrel/temp/tailcall.diff.gz

    This patch only works for simple functions (i.e. those that can be
    handled by fast_function), but extension to other function types should
    be trivial. I haven't fully tested this with regards to exception
    handling and whatnot, so I want to stick with a simple case for now.

    The patch works roughly as follows:
    1. When a CALL_FUNCTION opcode is encountered, check if the following
    opcode is RETURN_VALUE. If so, execute the tail call code.
    2. The tail call code calls a modified version of call_function that
    sets up and returns a frame object for the function to be called (if
    possible), rather than recursively calling PyEval_EvalFrame. This frame
    is stored in a temporary variable, and a RETURN_VALUE is simulated to
    exit the loop.
    3. After cleaning up the current frame, PyEval_EvalFrame loops back up
    to the top, now using the temporarily stored frame as the current frame.

    Of course, instead of a loop, gcc's tail-call optimization feature could
    be used, but this would be non-portable to other compilers.

    An example of the patch in action:

    # Note default arguments aren't supported in the current patch
    def fact2(n,v):
    if n:
    return fact2(n-1,v*n)
    else:
    return v

    def fact(n):
    return fact2(n,1)

    Without the patch:
    >>> fact(10000)

    RuntimeError: maximum recursion depth exceeded

    With the patch:
    >>> fact(10000)

    <really really huge number>

    Any feedback would be greatly appreciated!
     
    Chris King, Jul 10, 2004
    #10
  11. Christopher T King

    JanC Guest

    Chris King <> schreef:

    > Any feedback would be greatly appreciated!


    If you didn't already do so, post this on the Python development mailing
    list to get feedback.

    --
    JanC

    "Be strict when sending and tolerant when receiving."
    RFC 1958 - Architectural Principles of the Internet - section 3.9
     
    JanC, Jul 13, 2004
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kay Schluehr

    New tail recursion decorator

    Kay Schluehr, May 10, 2006, in forum: Python
    Replies:
    19
    Views:
    532
    Michele Simionato
    May 15, 2006
  2. Ray Wesley Kinserlow Jr.

    g++ and tail recursion

    Ray Wesley Kinserlow Jr., Mar 5, 2006, in forum: C++
    Replies:
    0
    Views:
    441
    Ray Wesley Kinserlow Jr.
    Mar 5, 2006
  3. shailesh

    does CCS supports tail recursion?

    shailesh, Aug 5, 2007, in forum: C Programming
    Replies:
    16
    Views:
    635
    jacob navia
    Aug 6, 2007
  4. Muzammil

    is it tail recursion

    Muzammil, Nov 3, 2008, in forum: C++
    Replies:
    26
    Views:
    1,221
  5. Terry Michaels

    Tail Call Optimization (Tail Recursion)

    Terry Michaels, Apr 18, 2011, in forum: Ruby
    Replies:
    16
    Views:
    329
    Robert Klemme
    Apr 20, 2011
Loading...

Share This Page