Self function

B

bearophileHUGS

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
 
E

Emile van Sebille

On 5/3/2009 3:39 PM (e-mail address removed) 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
 
S

Steve Howell

On 5/3/2009 3:39 PM (e-mail address removed) 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?
 
A

Arnaud Delobelle

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 boundf(*args, **kwargs):
.... return f(boundf, *args, **kwargs)
.... return boundf
.... .... def fac(self, n):
.... return 1 if n <= 1 else n * self(n - 1)
.... 120
 
C

Chris Rebert

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 boundf(*args, **kwargs):
...         return f(boundf, *args, **kwargs)
...     return boundf
...... def fac(self, n):
...     return 1 if n <= 1 else n * self(n - 1)
...120

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

Cheers,
Chris
 
B

bearophileHUGS

Arnaud Delobelle:
...     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
 
B

BJörn Lindqvist

2009/5/4 said:
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)

??
 
S

Steve Howell

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

bearophileHUGS

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
 
A

Arnaud Delobelle

Steve Howell:

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

bearophileHUGS

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
 
A

Aahz

Arnaud Delobelle:

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

Tim Wintle

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

bearophileHUGS

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
 
C

Chris Rebert

Aahz:

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
 
A

Arnaud Delobelle

Aahz:

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)
 
T

Terry Reedy

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

Carl Banks

Aahz:


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
 
B

bearophileHUGS

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
 
C

Carl Banks

Carl Banks:


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.

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]
I should use D when I have to use such algorithms, I know.

That's another idea.


Carl Banks
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top