Self function

Discussion in 'Python' started by bearophileHUGS@lycos.com, May 3, 2009.

  1. Guest

    Sometimes I rename recursive functions, or I duplicate&modify them,
    and they stop working because inside them there's one or more copy of
    their old name.
    This happens to me more than one time every year.
    So I have written this:

    from inspect import getframeinfo, currentframe

    def SOMEVERYUGLYNAME(n):
    if n <= 1:
    return 1
    else:
    self_name = getframeinfo(currentframe()).function
    #self_name = getframeinfo(currentframe())[2] # older python

    # only if it's a global function
    #return n * globals()[self_name](n - 1)
    return n * eval(self_name + "(%d)" % (n - 1))
    assert SOMEVERYUGLYNAME(6) == 2*3*4*5*6

    Are there nicer ways to do that? I don't know.
    If there aren't, then a way may be added.
    An idea-syntax:

    def fact(n):
    return 1 if n <= 1 else n * inspect.self(n - 1)

    Or even a lambda, because you don't need the name anymore to call the
    function:

    fact = lambda n: 1 if n <= 1 else n * self(n - 1)

    (If you have two or more recursive functions that call each other this
    idea can't be used, but I think such situations are uncommon enough to
    not deserve help from the language).

    Bye,
    bearophile
     
    , May 3, 2009
    #1
    1. Advertising

  2. On 5/3/2009 3:39 PM said...
    > Sometimes I rename recursive functions, or I duplicate&modify them,
    > and they stop working because inside them there's one or more copy of
    > their old name.
    > This happens to me more than one time every year.
    > So I have written this:
    >
    > from inspect import getframeinfo, currentframe
    >
    > def SOMEVERYUGLYNAME(n):
    > if n <= 1:
    > return 1
    > else:
    > self_name = getframeinfo(currentframe()).function
    > #self_name = getframeinfo(currentframe())[2] # older python
    >
    > # only if it's a global function
    > #return n * globals()[self_name](n - 1)
    > return n * eval(self_name + "(%d)" % (n - 1))
    > assert SOMEVERYUGLYNAME(6) == 2*3*4*5*6
    >
    > Are there nicer ways to do that?


    I've sometimes used classes like:


    class SOMEVERYUGLYNAME:
    def __call__(self,n):
    if n<=1:
    return 1
    else:
    return n*self.__class__()(n-1)

    assert SOMEVERYUGLYNAME()(6) == 2*3*4*5*6


    It's probably nicer (for some definition of nice), but I wouldn't say
    it's nice.

    Emile
     
    Emile van Sebille, May 4, 2009
    #2
    1. Advertising

  3. Steve Howell Guest

    On May 3, 5:21 pm, Emile van Sebille <> wrote:
    > On 5/3/2009 3:39 PM said...
    >
    >
    >
    > > Sometimes I rename recursive functions, or I duplicate&modify them,
    > > and they stop working because inside them there's one or more copy of
    > > their old name.
    > > This happens to me more than one time every year.
    > > So I have written this:

    >
    > > from inspect import getframeinfo, currentframe

    >
    > > def SOMEVERYUGLYNAME(n):
    > >     if n <= 1:
    > >         return 1
    > >     else:
    > >         self_name = getframeinfo(currentframe()).function
    > >         #self_name = getframeinfo(currentframe())[2] # older python

    >
    > >         # only if it's a global function
    > >         #return n * globals()[self_name](n - 1)
    > >         return n * eval(self_name + "(%d)" % (n - 1))
    > > assert SOMEVERYUGLYNAME(6) == 2*3*4*5*6

    >
    > > Are there nicer ways to do that?

    >
    > I've sometimes used classes like:
    >
    > class SOMEVERYUGLYNAME:
    >      def __call__(self,n):
    >          if n<=1:
    >              return 1
    >          else:
    >              return n*self.__class__()(n-1)
    >
    > assert SOMEVERYUGLYNAME()(6) == 2*3*4*5*6
    >
    > It's probably nicer (for some definition of nice), but I wouldn't say
    > it's nice.
    >


    Some of that could probably abstracted into a decorator maybe?
     
    Steve Howell, May 4, 2009
    #3
  4. writes:

    > Sometimes I rename recursive functions, or I duplicate&modify them,
    > and they stop working because inside them there's one or more copy of
    > their old name.
    > This happens to me more than one time every year.
    > So I have written this:
    >
    > from inspect import getframeinfo, currentframe
    >
    > def SOMEVERYUGLYNAME(n):
    > if n <= 1:
    > return 1
    > else:
    > self_name = getframeinfo(currentframe()).function
    > #self_name = getframeinfo(currentframe())[2] # older python
    >
    > # only if it's a global function
    > #return n * globals()[self_name](n - 1)
    > return n * eval(self_name + "(%d)" % (n - 1))
    > assert SOMEVERYUGLYNAME(6) == 2*3*4*5*6
    >
    > Are there nicer ways to do that? I don't know.
    > If there aren't, then a way may be added.
    > An idea-syntax:
    >
    > def fact(n):
    > return 1 if n <= 1 else n * inspect.self(n - 1)
    >
    > Or even a lambda, because you don't need the name anymore to call the
    > function:
    >
    > fact = lambda n: 1 if n <= 1 else n * self(n - 1)
    >
    > (If you have two or more recursive functions that call each other this
    > idea can't be used, but I think such situations are uncommon enough to
    > not deserve help from the language).
    >
    > Bye,
    > bearophile


    Here's an idea:

    >>> def bindfunc(f):

    .... def boundf(*args, **kwargs):
    .... return f(boundf, *args, **kwargs)
    .... return boundf
    ....
    >>> @bindfunc

    .... def fac(self, n):
    .... return 1 if n <= 1 else n * self(n - 1)
    ....
    >>> fac(5)

    120
    >>> fac = bindfunc(lambda f, n: 1 if n <= 1 else n*f(n - 1))
    >>> fac(5)

    120

    --
    Arnaud
     
    Arnaud Delobelle, May 4, 2009
    #4
  5. Chris Rebert Guest

    On Sun, May 3, 2009 at 11:29 PM, Arnaud Delobelle
    <> wrote:
    > writes:
    >
    >> Sometimes I rename recursive functions, or I duplicate&modify them,
    >> and they stop working because inside them there's one or more copy of
    >> their old name.
    >> This happens to me more than one time every year.
    >> So I have written this:
    >>
    >> from inspect import getframeinfo, currentframe
    >>
    >> def SOMEVERYUGLYNAME(n):
    >>     if n <= 1:
    >>         return 1
    >>     else:
    >>         self_name = getframeinfo(currentframe()).function
    >>         #self_name = getframeinfo(currentframe())[2] # older python
    >>
    >>         # only if it's a global function
    >>         #return n * globals()[self_name](n - 1)
    >>         return n * eval(self_name + "(%d)" % (n - 1))
    >> assert SOMEVERYUGLYNAME(6) == 2*3*4*5*6
    >>
    >> Are there nicer ways to do that? I don't know.
    >> If there aren't, then a way may be added.
    >> An idea-syntax:
    >>
    >> def fact(n):
    >>     return 1 if n <= 1 else n * inspect.self(n - 1)
    >>
    >> Or even a lambda, because you don't need the name anymore to call the
    >> function:
    >>
    >> fact = lambda n: 1 if n <= 1 else n * self(n - 1)
    >>
    >> (If you have two or more recursive functions that call each other this
    >> idea can't be used, but I think such situations are uncommon enough to
    >> not deserve help from the language).
    >>
    >> Bye,
    >> bearophile

    >
    > Here's an idea:
    >
    >>>> def bindfunc(f):

    > ...     def boundf(*args, **kwargs):
    > ...         return f(boundf, *args, **kwargs)
    > ...     return boundf
    > ...
    >>>> @bindfunc

    > ... def fac(self, n):
    > ...     return 1 if n <= 1 else n * self(n - 1)
    > ...
    >>>> fac(5)

    > 120
    >>>> fac = bindfunc(lambda f, n: 1 if n <= 1 else n*f(n - 1))
    >>>> fac(5)

    > 120


    Why am I reminded of the Y-Combinator...?

    Cheers,
    Chris
    --
    http://blog.rebertia.com
     
    Chris Rebert, May 4, 2009
    #5
  6. Guest

    Arnaud Delobelle:
    > >>> def bindfunc(f):

    > ...     def boundf(*args, **kwargs):
    > ...         return f(boundf, *args, **kwargs)
    > ...     return boundf


    > ...>>> @bindfunc
    > ... def fac(self, n):
    > ...     return 1 if n <= 1 else n * self(n - 1)
    > ...>>> fac(5)
    > 120


    This is cute, now I have two names to take care of.
    Thank you to all the people that have answered.
    Another possible syntax:

    def fact(n):
    return 1 if n <= 1 else n * return(n - 1)

    But I guess most people don't see this problem as important&common
    enough to justify changing the language.

    Bye,
    bearophile
     
    , May 4, 2009
    #6
  7. 2009/5/4 <>:
    > An idea-syntax:
    >
    > def fact(n):
    >    return 1 if n <= 1 else n * inspect.self(n - 1)
    >
    > Or even a lambda, because you don't need the name anymore to call the
    > function:
    >
    > fact = lambda n: 1 if n <= 1 else n * self(n - 1)


    How would it work with methods?

    class Foo:
    def fac(self, n):
    return 1 if n <= 1 else n * self.self(n-1)

    ??


    --
    mvh Björn
     
    BJörn Lindqvist, May 4, 2009
    #7
  8. Steve Howell Guest

    On May 3, 3:39 pm, wrote:
    > Sometimes I rename recursive functions, or I duplicate&modify them,
    > and they stop working because inside them there's one or more copy of
    > their old name.
    > This happens to me more than one time every year.
    > So I have written this:
    >
    > from inspect import getframeinfo, currentframe
    >
    > def SOMEVERYUGLYNAME(n):
    >     if n <= 1:
    >         return 1
    >     else:
    >         self_name = getframeinfo(currentframe()).function
    >         #self_name = getframeinfo(currentframe())[2] # older python
    >
    >         # only if it's a global function
    >         #return n * globals()[self_name](n - 1)
    >         return n * eval(self_name + "(%d)" % (n - 1))
    > assert SOMEVERYUGLYNAME(6) == 2*3*4*5*6
    >
    > Are there nicer ways to do that? I don't know.
    > If there aren't, then a way may be added.
    > An idea-syntax:
    >
    > def fact(n):
    >     return 1 if n <= 1 else n * inspect.self(n - 1)
    >
    > Or even a lambda, because you don't need the name anymore to call the
    > function:
    >
    > fact = lambda n: 1 if n <= 1 else n * self(n - 1)
    >
    > (If you have two or more recursive functions that call each other this
    > idea can't be used, but I think such situations are uncommon enough to
    > not deserve help from the language).
    >


    One very simple thing that you can do is assign the current function
    name to a local var at the very top to make it a little more obvious.

    I agree that there are lots of recursive patterns where python itself
    does not provide much sugar. A pattern that comes up for me
    occasionally is two methods with almost identical names, where one
    function is the public interface and then another method that does
    most of the recursion.
     
    Steve Howell, May 4, 2009
    #8
  9. Guest

    Steve Howell:
    >two methods with almost identical names, where one function is the public interface and then another method that does most of the recursion.<


    Thanks Guido & Walter both Python and D support nested functions, so
    in such situations I put the recursive function inside the "public
    interface" function/method.

    Recursion is a high-level way to represent certain kinds of algorithms
    in a short and readable way (when data structures are nested, the most
    natural algorithms that work on them are recursive). But in Python
    function calls are slow, the maximum level of nested calls is limited
    (and it can't grow too much), so this has sometimes forced me to
    manually convert recursive functions into iterative ones with a stack.
    This is silly for a supposed high-level language. The bad support for
    recursivity is one of the few faults of Python.

    Bye,
    bearophile
     
    , May 4, 2009
    #9
  10. writes:

    > Steve Howell:
    >>two methods with almost identical names, where one function is the
    >>public interface and then another method that does most of the
    >>recursion.<

    >
    > Thanks Guido & Walter both Python and D support nested functions, so
    > in such situations I put the recursive function inside the "public
    > interface" function/method.


    Yes, this is a common idiom for me:

    def public_function(a, b):
    def rec():
    ...
    return rec()

    E.g, to continue with the factorial toy example (of course for this
    particular example and in this particular language, a loop would be more
    appropriate):

    def fac(n):
    def rec(n, acc):
    if n <= 1:
    return acc
    else:
    return rec(n - 1, n*acc)
    return rec(n, 1)

    This is tail recursive, but Python does not optimise tail-calls so there
    is not much point.

    > Recursion is a high-level way to represent certain kinds of algorithms
    > in a short and readable way (when data structures are nested, the most
    > natural algorithms that work on them are recursive). But in Python
    > function calls are slow, the maximum level of nested calls is limited
    > (and it can't grow too much), so this has sometimes forced me to
    > manually convert recursive functions into iterative ones with a stack.
    > This is silly for a supposed high-level language. The bad support for
    > recursivity is one of the few faults of Python.


    Bearophile, there is a thread on python-ideas about tail-call
    optimization at the moment.

    --
    Arnaud
     
    Arnaud Delobelle, May 4, 2009
    #10
  11. Guest

    Arnaud Delobelle:
    > def fac(n):
    >     def rec(n, acc):
    >         if n <= 1:
    >             return acc
    >         else:
    >             return rec(n - 1, n*acc)
    >     return rec(n, 1)


    Right, that's another way to partially solve the problem I was talking
    about. (Unfortunately the performance in Python is significantly
    lower. I can use that in D).


    > Bearophile, there is a thread on python-ideas about tail-call
    > optimization at the moment.


    Someday I'll have to start following those mailing lists...
    But I am not interested in such optimization. It's not going to help
    me significantly. Most times I use recursion, I think it can't be
    optimized away by simple means (think about a visit to a binary tree).

    Bye,
    bearophile
     
    , May 4, 2009
    #11
  12. Aahz Guest

    In article <>,
    <> wrote:
    >Arnaud Delobelle:
    >>
    >> Bearophile, there is a thread on python-ideas about tail-call
    >> optimization at the moment.

    >
    >Someday I'll have to start following those mailing lists...
    >But I am not interested in such optimization. It's not going to help
    >me significantly. Most times I use recursion, I think it can't be
    >optimized away by simple means (think about a visit to a binary tree).


    When have you ever had a binary tree a thousand levels deep? Consider
    how big 2**1000 is...
    --
    Aahz () <*> http://www.pythoncraft.com/

    "It is easier to optimize correct code than to correct optimized code."
    --Bill Harlan
     
    Aahz, May 4, 2009
    #12
  13. Tim Wintle Guest

    On Mon, 2009-05-04 at 19:51 +0100, Arnaud Delobelle wrote:
    >
    > Bearophile, there is a thread on python-ideas about tail-call
    > optimization at the moment.


    Oooh - haven't noticed that (and don't have time to follow it), but has
    anyone seen the results I got a week or so ago from briefly playing with
    a couple of simple optimisations:

    <http://www.teamrubber.com/blog/python-tail-optimisation-using-byteplay/>

    I was amazed how much you could improve performance by not jumping all
    over the stack



    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.6 (GNU/Linux)

    iD8DBQBJ/08EOtrPP2cBxvQRAu0lAJ9geaAhv7UjLUC1UnoSXGprfypUGACgsCe3
    DxSM4581KRK7L3I8+6Ng01o=
    =jTwM
    -----END PGP SIGNATURE-----
     
    Tim Wintle, May 4, 2009
    #13
  14. Guest

    Aahz:
    > When have you ever had a binary tree a thousand levels deep?


    Yesterday.


    >Consider how big 2**1000 is...<


    You are thinking just about complete binary trees.
    But consider that a topology like a single linked list (every node has
    1 child, and they are chained) is a true binary tree still.

    Bye,
    bearophile
     
    , May 4, 2009
    #14
  15. Chris Rebert Guest

    On Mon, May 4, 2009 at 1:25 PM, <> wrote:
    > Aahz:
    >> When have you ever had a binary tree a thousand levels deep?

    >
    > Yesterday.
    >
    >
    >>Consider how big 2**1000 is...<

    >
    > You are thinking just about complete binary trees.
    > But consider that a topology like a single linked list (every node has
    > 1 child, and they are chained) is a true binary tree still.


    And who in their right mind would not use a *self-balancing* binary
    tree in that situation?

    Cheers,
    Chris
    --
    http://blog.rebertia.com
     
    Chris Rebert, May 4, 2009
    #15
  16. writes:

    > Aahz:
    >> When have you ever had a binary tree a thousand levels deep?

    >
    > Yesterday.
    >
    >
    >>Consider how big 2**1000 is...<

    >
    > You are thinking just about complete binary trees.
    > But consider that a topology like a single linked list (every node has
    > 1 child, and they are chained) is a true binary tree still.


    In that case the following would not grow the stack, given tail-call
    optimization:

    def visit(node):
    print 'visiting', node
    if node.right is None:
    return visit(node.left)
    if node.left is not None:
    visit(node.left)
    return visit(node.right)

    --
    Arnaud
     
    Arnaud Delobelle, May 4, 2009
    #16
  17. Terry Reedy Guest

    wrote:

    > Another possible syntax:
    >
    > def fact(n):
    > return 1 if n <= 1 else n * return(n - 1)
    >
    > But I guess most people don't see this problem as important&common
    > enough to justify changing the language.


    Actually, I would like a way to refer to the current function from
    inside a function. but I would like support in the language, so that
    the compiler patched the code after the function object is created to
    directly refer to the function object (or can the code object call the
    code object?) without any name lookup at all. [An possible objection to
    doing this is that the code might no longer be valid if used to make
    another function object, but I think this is so rare at to hardly worry
    about.] Your initial post seemed to be about a hackish work around that
    looked to me to make as much trouble as it saves. So I did not respond.
     
    Terry Reedy, May 4, 2009
    #17
  18. Carl Banks Guest

    On May 4, 1:25 pm, wrote:
    > Aahz:
    >
    > > When have you ever had a binary tree a thousand levels deep?

    >
    > Yesterday.
    >
    > >Consider how big 2**1000 is...<

    >
    > You are thinking just about complete binary trees.
    > But consider that a topology like a single linked list (every node has
    > 1 child, and they are chained) is a true binary tree still.


    1. Singly-linked lists can and should be handled with iteration. All
    recursion does it make what you're doing a lot less readable for
    almost all programmers.

    2. You should be using a Python list anyway.


    Carl Banks
     
    Carl Banks, May 4, 2009
    #18
  19. Guest

    Carl Banks:

    >1. Singly-linked lists can and should be handled with iteration.<


    I was talking about a binary tree with list-like topology, of course.


    >All recursion does it make what you're doing a lot less readable for almost all programmers.<


    I can't agree. If the data structure is recursive (like a tree, or
    even sometimes graphs, etc) a recursive algorithm is shorter, more
    readable and more natural.

    An example, a postorder recursive visit:

    def postorder_scan(root):
    if root is not None:
    if root.left is not None:
    for n in postorder_scan(root.left):
    yield n
    if root.right is not None:
    for n in postorder_scan(root.right):
    yield n
    yield root

    Try to write that in an iterative way, not adding any new field to the
    nodes, and you will see.
    And even if you add a "visited" new boolean field to nodes, the
    resulting code isn't as nice as the recursive one yet.


    > 2. You should be using a Python list anyway.


    I should use D when I have to use such algorithms, I know.

    Bye,
    bearophile
     
    , May 5, 2009
    #19
  20. Carl Banks Guest

    On May 4, 4:06 pm, wrote:
    > Carl Banks:
    >
    > >1. Singly-linked lists can and should be handled with iteration.<

    >
    > I was talking about a binary tree with list-like topology, of course.


    "(every node has 1 child, and they are chained)"

    That's a singly-linked list, not a tree. It's a degenerate tree at
    best.


    > >All recursion does it make what you're doing a lot less readable for almost all programmers.<

    >
    > I can't agree.


    If every child has one node you don't need recursion.


    > If the data structure is recursive (like a tree, or
    > even sometimes graphs, etc) a recursive algorithm is shorter, more
    > readable and more natural.


    Because that's a tree, not a linked-list.

    Which is germane because Python's recursion limit is the thing you're
    complaining about here, and you don't normally hit that limit with
    real trees because they rarely go 1000 deep.

    Singly-linked lists don't count because you don't need recursion for
    them.


    [snip strawman example]
    > > 2. You should be using a Python list anyway.

    >
    > I should use D when I have to use such algorithms, I know.


    That's another idea.


    Carl Banks
     
    Carl Banks, May 5, 2009
    #20
    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. Ralf W. Grosse-Kunstleve
    Replies:
    16
    Views:
    620
    Lonnie Princehouse
    Jul 11, 2005
  2. Ralf W. Grosse-Kunstleve
    Replies:
    18
    Views:
    619
    Bengt Richter
    Jul 11, 2005
  3. Ralf W. Grosse-Kunstleve
    Replies:
    2
    Views:
    427
    Dan Sommers
    Jul 12, 2005
  4. falcon
    Replies:
    0
    Views:
    401
    falcon
    Jul 31, 2005
  5. Bart Kastermans
    Replies:
    6
    Views:
    423
    Bart Kastermans
    Jul 13, 2008
Loading...

Share This Page