Self function
bearoph...@lycos.com
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
Emile van Sebille
> 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
Steve Howell
> On 5/3/2009 3:39 PM bearophileH...@lycos.com said...
Some of that could probably abstracted into a decorator maybe?
Arnaud Delobelle
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
Chris Rebert
bearoph...@lycos.com
> >>> 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
BJörn Lindqvist
> 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
Steve Howell
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.
bearoph...@lycos.com
>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
Arnaud Delobelle
> 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
bearoph...@lycos.com
> 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
Aahz
<bearoph...@lycos.com> 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 (aa...@pythoncraft.com) <*> http://www.pythoncraft.com/
"It is easier to optimize correct code than to correct optimized code."
--Bill Harlan
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
bearoph...@lycos.com
> 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
Chris Rebert
And who in their right mind would not use a *self-balancing* binary
tree in that situation?
Arnaud Delobelle
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
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.
Scott David Daniels
> 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)
>
def visit(node):
while node is not None:
print 'visiting', node
if node.right is None:
else:
if node.left is not None:
visit(node.left)
Not so hard, really.
--Scott David Daniels
Scott....@Acm.Org
Carl Banks
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
bearoph...@lycos.com
>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
Carl Banks
> 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
Steven D'Aprano
> All
> recursion does it make what you're doing a lot less readable for almost
> all programmers.
What nonsense. There are many algorithms that are more understandable
written recursively than iteratively -- consult any good text book for
examples. There are algorithms that are naturally iterative, and
algorithms which are naturally recursive (and a few which are equally
simple either way), and forcing either one into the other form leads to
complicated and confusing code. This especially holds for mutually-
recursive functions, where re-writing them to be iterative is usually
very difficult.
Sometimes it's worth rewriting a recursive algorithm to be iterative for
the performance optimization, but that comes at the price of reduced
readability.
--
Steven
Steven D'Aprano
> On May 4, 4:06 pm, bearophileH...@lycos.com 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.
A singly-linked list is a degenerate tree. Not "at best", but "is".
>> >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.
And if one single node in the entire tree has two children, you do. What
are you suggesting, that Bearophile should write his tree-processing code
to only deal with the degenerate case?
>> 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.
And a linked list is a degenerate tree. If you have a non-self-balancing
tree, sometimes it will be degenerate, and your code needs to deal with
it.
> 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.
And if just ONE branch of the tree goes 1000 deep, even if the rest of
the tree is shallow, then you hit the default recursion limit.
> Singly-linked lists don't count because you don't need recursion for
> them.
If each node has two (or more) child fields, even if only one of those
children is non-empty, then your data structure is a degenerate tree and
does count.
> [snip strawman example]
It's not a strawman just because you don't like it. Dealing with
degenerate trees is a genuine issue, and avoiding degenerate trees is the
reason why people have developed more complicated structures like red-
black trees.
--
Steven
Steven D'Aprano
> bearoph...@lycos.com 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.
I don't know about avoiding name lookup, that smacks of deepest black
magic, and Python doesn't usually do that. It does however do parlour
tricks like `__name__` and `self`, suggests a solution.
I propose a small piece of sugar. When a function is entered, Python
creates an ordinary local name in the function's local namespace, and
binds the function itself to that name. Two possibilities for the name
are `this` or `__this__`, analogous to `self` in methods and `__name__`
in modules.
If there is any support for this, I propose to send the following (long)
post to python-ideas. Feedback, corrections and suggestions welcome.
* * *
Summary:
Most objects in Python don't need to know what name, or names (if any)
they are bound to. Functions are a conspicuous exception to that rule:
there are good reasons for a function to refer to itself, and the only
straightforward way to do so is by name. I propose that on calling a
function, Python should create a local name which refers to the function
itself, giving the programmer the ability to have a function refer to
itself without using its name.
There are (at least) four reasons for a function to refer to itself. In
no particular order:
(1) User-friendly messages (for logging, errors or other):
def parrot():
print "Error feeding cracker to function %r" % parrot
(2) Recursion:
def spam(n):
if n < 0: return spam(-n).upper()
return "spam "*n
(3) Introspection:
def spanish_inquisition():
print inspect.getmembers(spanish_inquisition)
(4) Storing data between function calls:
def cheeseshop():
if hasattr(cheeseshop, 'cheeses'):
print "We have many fine cheeses"
else:
print "I'm sorry, I have been wasting your time"
I call these self-reflective functions.
In some cases there are alternatives e.g. cheeseshop could be written as
a functor object, or some recursive functions can be re-written as
iteration. Nevertheless such self-reflective functions are acceptable to
many people, and consequently in moderately common use. How to have a
function refer to itself is a common question, e.g. for newbies:
http://www.mail-archive.com/tutor%40python.org/msg35114.html
and even more experienced programmers:
http://article.gmane.org/gmane.comp.python.general/622020
(An earlier draft of this proposal was sent to that thread.)
However, none of these functions are robust in the face of the function
being renamed, either at runtime or in the source code. In general, this
will fail for any of the above functions:
func = spam
del spam
func()
Self-reflective functions like these are (almost?) unique in Python in
that they require a known name to work correctly. You can rename a class,
instance or module and expect it to continue to work, but not so for such
functions. When editing source code, it is very easy to forget to change
all the references to the function name within the body of itself
function, even for small functions, and refactoring tools are overkill.
My proposal is for Python to automatically generate a local variable
named either `this` or `__this__` when entering a function. This will
allow any of the above functions to be re-written using the special name,
and become robust against name changes.
def spanish_inquisition():
print inspect.getmembers(__this__)
fang = spanish_inquisition
del spanish_inquisition
fang()
It will also allow lambda to use recursion:
lambda n: 0 if n <= 1 else __this__(n-1)
(This may count as a point against it, for those who dislike lambda.)
It is often useful to create two similar functions, or a variant of a
function, without duplicating the source code. E.g. you might want a
function that uses a cache, while still keeping around the version
without a cache:
cached_function = memoize(function)
Currently, this does not give the expected results for recursive
functions, nor does it give an error. It simply fails to behave as
expected. Re-writing function() to use __this__ for the recursive call
will solve that problem.
Q: Will `__this__` or `this` clash with existing variables?
I prefer `this` over `__this__`, for analogy with `self` inside methods.
However it is more likely that existing code already uses the name
`this`, since double-leading-and-trailing-underscore names are reserved
for use by Python. Because `this` is an ordinary local variable, if a
function assigns to it the function will work as expected. The only
meaningful clash I can think of will occur when a function refers to a
non-local name `this` without declaring it first. Another obvious clash
may be:
def function():
import this
...
Both of these are likely to be very rare.
Q: Will there be a performance penalty if every function defines the name
`__this__` on entry?
I don't expect so, but if it is found to be a problem, a slightly more
sophisticated strategy would be to only define `__this__` inside the
function if the body of the function refers to that variable. That will
allow the majority of functions which are not self-reflective to avoid
paying that (probably minuscule) cost.
Q: Is this really necessary?
This is sugar, a convenience for the programmer. None of the problems it
solves cannot be solved, or worked around, by other methods.
Nevertheless, that the question "how do I have my function refer to
itself?" keeps being asked over and over again suggests that the current
solutions are (1) not obvious to newbies, and (2) not entirely
satisfactory to more experienced programmers.
Here is a proof-of-concept pure Python implementation, using a decorator,
and abusing a global variable. This is NOT to imply that `__this__`
should be a global if this proposal goes ahead.
from functools import wraps
def make_this(func):
global __this__
__this__ = func
@wraps(func)
def f(*args, **kwargs):
return func(*args, **kwargs)
return f
>>> @make_this
... def spam(n):
... if n < 0: return __this__(-n).upper()
... return ' '.join([__this__.__name__] * n)
...
>>> tasty_meat_like_product = spam
>>> del spam
>>> tasty_meat_like_product(-3)
'SPAM SPAM SPAM'
--
Steven
Carl Banks
<ste...@REMOVE.THIS.cybersource.com.au> wrote:
> On Mon, 04 May 2009 15:51:15 -0700, Carl Banks wrote:
> > All
> > recursion does it make what you're doing a lot less readable for almost
> > all programmers.
>
> What nonsense.
It's not nonsense for a singly-linked list. I don't need to be taught
the benefit of recursion, but whenever interation is suitable for an
algorithm/data structure, as it is with singly-linked lists, then it
is the more readable and more preferrable choice, especially in
Python.
In Python the One Obvious Way is iteration when possible, recursion
when necessary.
Carl Banks
Chris Rebert
<ste...@remove.this.cybersource.com.au> wrote:
> On Mon, 04 May 2009 17:54:50 -0400, Terry Reedy wrote:
>
>> bearoph...@lycos.com 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.
>
> I don't know about avoiding name lookup, that smacks of deepest black
> magic, and Python doesn't usually do that. It does however do parlour
> tricks like `__name__` and `self`, suggests a solution.
>
> I propose a small piece of sugar. When a function is entered, Python
> creates an ordinary local name in the function's local namespace, and
> binds the function itself to that name. Two possibilities for the name
> are `this` or `__this__`, analogous to `self` in methods and `__name__`
> in modules.
>
> If there is any support for this, I propose to send the following (long)
> post to python-ideas. Feedback, corrections and suggestions welcome.
<snip entire excellent proposal text>
While I'm +0 on the proto-PEP, it doesn't currently address (or at
least rebut hard enough) the inevitable obvious naysayer argument
which will go along the lines of:
<devils_advocate>
Adding syntax is EVIL(tm) for it angers the Gods of Backwards
Compatibility, and this proposal is completely unnecessary because you
could instead just write:
def recursive(func):
"""We caved enough to allow this into functools."""
def wrapper(*args, **kwds):
return func(func, *args, **kwds)
return wrapper
#####
from functools import recursive
@recursive
def spam(this, number_of_thy_counting):
print " ".join([this.__name__.capitalize() + "!"]*number_of_thy_counting)
Which is not significantly more complex/longer/painful than learning
about __this__'s existence or typing the extra underscores and it
doesn't require any new syntax.
And the performance penalty for the proposed feature would actually be horrible!
And there would be much clashing with existing variable names, for
keywords are the Devil's work!
And your mother wears combat boots!
(etc...)
</devils_advocate>
You touch on this in "Is this really necessary?", but I think you're
going to prove more persuasively how drastically sweeter this syntax
sugar would be.
Cheers,
Chris
--
The Devil's Advocate-General
http://blog.rebertia.com
Carl Banks
<ste...@REMOVE.THIS.cybersource.com.au> wrote:
> On Mon, 04 May 2009 16:33:13 -0700, Carl Banks wrote:
> > On May 4, 4:06 pm, bearophileH...@lycos.com 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.
>
> A singly-linked list is a degenerate tree. Not "at best", but "is".
No, many implemenations of singly-linked lists aren't trees by any
definition. You are probably thinking of the bastardized list-tree
spawn they use in Lisp. But many implementations don't even bother
with a cons cell and just have the object itself refer to the next
object. That is not a tree.
But even singly-linked lists implemented with cons cells can be
handled, and are better handled, with interation.
> >> >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.
>
> And if one single node in the entire tree has two children, you do.
Then it't not a singly-linked list. It's a tree.
> What
> are you suggesting, that Bearophile should write his tree-processing code
> to only deal with the degenerate case?
I'm suggesting that Bearophile should write recursive code for his
trees and iterative code for his lists.
> >> 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.
>
> And a linked list is a degenerate tree. If you have a non-self-balancing
> tree, sometimes it will be degenerate, and your code needs to deal with
> it.
If you have a tree, then you use recursive code. If you have a list
you use iterative code.
> > 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.
>
> And if just ONE branch of the tree goes 1000 deep, even if the rest of
> the tree is shallow, then you hit the default recursion limit.
Yeah, well, see that's just the point here. Bearophile was asked if
any of his trees go 1000 deep, he said yes, his singly-linked lists
do. Well, I'm sorry, that's not going to convince me, because
bearophile should be using iteration for the singly-linked lists.
Bearophile might very well have real trees that are 1000 deep, but
that's not going to convince me either, because IMO real trees rarely
do that, and Python's recursion limit can be increased in the rare
cases they do.
Bearophile and you are welcome to try to convince me that there are
lots of real trees out there that can't be handled with iteration and
that do go 1000 deep, and that this is a common enough problem that
Python should drastically improve support for recursion. Until then I
will opine that it is adequate now for almost all purposes.
> > Singly-linked lists don't count because you don't need recursion for
> > them.
>
> If each node has two (or more) child fields, even if only one of those
> children is non-empty, then your data structure is a degenerate tree and
> does count.
If one of the fields is always empty, you don't need recursion to deal
with it.
> > [snip strawman example]
>
> It's not a strawman just because you don't like it.
No, it's a strawman because I said singly-linked lists don't need
recursion, and his counterexample was showing that recursion was
useful a tree. Which was true, but it wasn't answering my argument.
> Dealing with
> degenerate trees is a genuine issue, and avoiding degenerate trees is the
> reason why people have developed more complicated structures like red-
> black trees.
I'm not talking about degenerate trees. I'm talking about singly-
linked lists, which you DO NOT NEED, and SHOULD NOT USE, recursion to
deal with.
Carl Banks
Arnaud Delobelle
>
> - Show quoted text -
Are you aware of PEP 3130? http://www.python.org/dev/peps/pep-3130/
(BTW, it seems to me that your implementation breaks as soon as two
functions are decorated - not tested!)
--
Arnaud
CTO
<ste...@REMOVE.THIS.cybersource.com.au> wrote:
> On Mon, 04 May 2009 17:54:50 -0400, Terry Reedy wrote:
> > bearophileH...@lycos.com 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.
>
> I don't know about avoiding name lookup, that smacks of deepest black
> magic, and Python doesn't usually do that. It does however do parlour
> tricks like `__name__` and `self`, suggests a solution.
>
> I propose a small piece of sugar. When a function is entered, Python
> creates an ordinary local name in the function's local namespace, and
> binds the function itself to that name. Two possibilities for the name
> are `this` or `__this__`, analogous to `self` in methods and `__name__`
> in modules.
>
> If there is any support for this, I propose to send the following (long)
> post to python-ideas. Feedback, corrections and suggestions welcome.
[snip proposal]
I'm not all that in favor of this, but I think I've got another use
case
for you at http://code.activestate.com/recipes/576731/. The functions
written to use it would be a lot more standard looking at least.
Geremy Condra
Paul Rubin
> This happens to me more than one time every year.
> So I have written this:
> self_name = getframeinfo(currentframe()).function
ZOMG, you've got to be kidding. I'd expect Pylint to catch that sort
of error statically. If not, the best approach is probably to extend
Pylint to handle those cases. The frame crawling stuff just comes
across as madness to me.
Steven D'Aprano
> On May 4, 8:22 pm, Steven D'Aprano
> <ste...@REMOVE.THIS.cybersource.com.au> wrote:
>> On Mon, 04 May 2009 15:51:15 -0700, Carl Banks wrote:
>> > All
>> > recursion does it make what you're doing a lot less readable for
>> > almost all programmers.
>>
>> What nonsense.
>
> It's not nonsense for a singly-linked list.
def ivisit(node):
print node
while node and node.link is not None:
node = node.link
print node
def rvisit(node):
print node
if node and node.link is not None:
rvisit(node.link)
If there are programmers who find rvisit "a lot less readable" than
ivisit, then in my arrogant opinion they should consider a change of
profession.
> I don't need to be taught
> the benefit of recursion, but whenever interation is suitable for an
> algorithm/data structure, as it is with singly-linked lists, then it is
> the more readable and more preferrable choice, especially in Python.
Most (all?) recursive algorithms can be re-written as iteration. For many
recursive algorithms (but not all) the cost for doing so is to simulate
recursion yourself by managing your own stack. By making such an
absolutist claim, you're claiming that it is "more readable" and "more
preferable" to manage your own stack than to let the compiler do so.
That's clearly nonsense.
Whenever iteration gives a simpler and more readable algorithm than
recursion, then it should be preferred on account of being simpler and
more readable. That's not just a no-brainer, it's a tautology. "Whenever
iteration is simpler, it's simpler." But that's a far cry from what you
said: that recursion, as a general technique, is "a lot less readable"
for "almost all" programmers.
> In Python the One Obvious Way is iteration when possible, recursion when
> necessary.
There's nothing "obvious" about solving the 8 Queens problem using
iteration. Or walking a binary tree. Or generating all the permutations
of a list.
But don't just tell me that recursion isn't Pythonic. Tell Guido:
http://www.python.org/doc/essays/graphs.html
I quote:
"These [recursive] functions are about as simple as they get. Yet, they
are nearly optimal (for code written in Python)."
--
Steven
Steven D'Aprano
> Are you aware of PEP 3130? http://www.python.org/dev/peps/pep-3130/
I am now. Very disappointing.
> (BTW, it seems to me that your implementation breaks as soon as two
> functions are decorated - not tested!)
Of course it does! That's why I warned that I was "abusing a global
variable", and that it should not be read as meaning that I wanted
__this__ to be global. I want it to be local to the function.
If somebody can tell me how to inject a new local name into a function,
that would be far preferable to using global in the decorator.
--
Steven
Carl Banks
<ste...@REMOVE.THIS.cybersource.com.au> wrote:
> On Mon, 04 May 2009 23:09:25 -0700, Carl Banks wrote:
> > In Python the One Obvious Way is iteration when possible, recursion when
> > necessary.
>
> There's nothing "obvious" about solving the 8 Queens problem using
> iteration. Or walking a binary tree. Or generating all the permutations
> of a list.
*Sigh* Well, I'm out of this debate. Apparently it's not possible to
argue that recursivie algorithms should be avoided *sometimes* without
everyone citing cases that obviously aren't from those times (as if I
had been arguing that recursion should be avoided all the time).
Here's a parting thought for you to cite "counterexamples" of:
Iteration should be used instead of recursion anywhere a tail-
recursive algorithm is possible. Recursion should be used only when
tail-recursion is not possible.
Carl Banks
wolfram....@googlemail.com
<ste...@REMOVE.THIS.cybersource.com.au> wrote:
> Self-reflective functions like these are (almost?) unique in Python in
> that they require a known name to work correctly. You can rename a class,
> instance or module and expect it to continue to work, but not so for such
> functions. When editing source code, it is very easy to forget to change
> all the references to the function name within the body of itself
> function, even for small functions, and refactoring tools are overkill.
It is easy to change all references of the function name, except for
those in the function body itself? That needs some explantation.
> It is often useful to create two similar functions, or a variant of a
> function, without duplicating the source code. E.g. you might want a
> function that uses a cache, while still keeping around the version
> without a cache:
>
> cached_function = memoize(function)
>
> Currently, this does not give the expected results for recursive
> functions, nor does it give an error. It simply fails to behave as
> expected. Re-writing function() to use __this__ for the recursive call
> will solve that problem.
Won't __this__ (inside function) still refer to function, not
cached_function?
> Here is a proof-of-concept pure Python implementation, using a decorator,
> and abusing a global variable. This is NOT to imply that `__this__`
> should be a global if this proposal goes ahead.
>
> from functools import wraps
> def make_this(func):
> global __this__
> __this__ = func
> @wraps(func)
> def f(*args, **kwargs):
> return func(*args, **kwargs)
> return f
This still has the memoizing problem.
Steven D'Aprano
> On May 4, 8:26 pm, Steven D'Aprano
> <ste...@REMOVE.THIS.cybersource.com.au> wrote:
>> On Mon, 04 May 2009 16:33:13 -0700, Carl Banks wrote:
>> > On May 4, 4:06 pm, bearophileH...@lycos.com 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.
>>
>> A singly-linked list is a degenerate tree. Not "at best", but "is".
>
> No, many implemenations of singly-linked lists aren't trees by any
> definition.
I would say not. Nodes with a single link field can't form a tree,
because you can't give it a left and right child. However trees can
degenerate into a singly-linked list, where each node has at least one
unused child. That is what both Bearophile and I are trying to tell you.
It's not that anyone sane thinks "I know, I'll use a binary tree to
implement a linked list" -- that would be stupid, and shame on you for
thinking that Bearophile is that stupid. But if you insert data into a
non-self-balancing tree, sometimes the tree will degenerate into a linked
list with extra, unused child links.
[...]
> But even singly-linked lists implemented with cons cells can be handled,
> and are better handled, with interation.
Can be, certainly.
Better? Maybe.
>> >> >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.
>>
>> And if one single node in the entire tree has two children, you do.
>
> Then it't not a singly-linked list. It's a tree.
It was already a tree. It's just that the entire tree happened to form
one long chain.
>> What
>> are you suggesting, that Bearophile should write his tree-processing
>> code to only deal with the degenerate case?
>
> I'm suggesting that Bearophile should write recursive code for his trees
> and iterative code for his lists.
But his tree-handling recursive code MUST and WILL operate on degenerate
trees that form chains (linked lists), unless he writes more complicated
code to avoid it (e.g. red-black trees). For simple trees, you don't have
the luxury of saying "Oh, my trees will never be degenerate, they'll
always be optimal, with the minimum depth possible." You get the trees
you're given, and sometimes they'll be one long branch with no, or very
fewer, off-shoots, and you'll have O(N) performance instead of O(log N).
And the clever thing?
Just write the recursive code, as normal, and it will magically handle
the degenerate case too.
>> >> 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.
>>
>> And a linked list is a degenerate tree. If you have a
>> non-self-balancing tree, sometimes it will be degenerate, and your code
>> needs to deal with it.
>
> If you have a tree, then you use recursive code. If you have a list you
> use iterative code.
I wish to retract my poorly worded comment "And a linked list is a
degenerate tree". That is incorrect. What I should have said is that a
degenerate tree behaves equivalently to a linked list, rather than "is".
>> > 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.
>>
>> And if just ONE branch of the tree goes 1000 deep, even if the rest of
>> the tree is shallow, then you hit the default recursion limit.
>
> Yeah, well, see that's just the point here. Bearophile was asked if any
> of his trees go 1000 deep, he said yes, his singly-linked lists do.
He certainly did not say anything of the sort.
> Well, I'm sorry, that's not going to convince me, because bearophile
> should be using iteration for the singly-linked lists.
What Bearophile actually wrote was:
"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." [Emphasis added.]
It should be obvious what he means. But if, by some chance, you
misunderstood what he said, he replied to your earlier post and explained
further:
"I was talking about a binary tree with list-like topology, of course."
If you don't understand what a binary-tree with a list-like topology is,
then I respectfully suggest that you are unqualified to have an opinion
in this discussion and you should come back when you've learned what a
binary-tree with a list-like topology actually is, and why your
suggestion that he use iteration on linked lists is, to quote Wolfgang
Pauli, Not Even Wrong.
> Bearophile might very well have real trees that are 1000 deep, but
> that's not going to convince me either, because IMO real trees rarely do
> that, and Python's recursion limit can be increased in the rare cases
> they do.
Are you saying that Bearophile's trees are imaginary? That's he's making
them up?
Personally, I don't think it's good to have a function fail just because
it has to recurse over a mere 1000 items. I think that's as poor as some
hypothetical language where you can't iterate over more than 1000 items,
and if you try, you have to catch the exception, increase the iteration
limit, and try again. People wouldn't stand for it.
Oh, I understand *why* Python has that limitation. It's just a black mark
on an otherwise wonderful language.
[...]
>> > Singly-linked lists don't count because you don't need recursion for
>> > them.
>>
>> If each node has two (or more) child fields, even if only one of those
>> children is non-empty, then your data structure is a degenerate tree
>> and does count.
>
> If one of the fields is always empty, you don't need recursion to deal
> with it.
That's just silly. How do you know that one of the fields is always empty
until you've walked the tree?
[...]
> I'm not talking about degenerate trees. I'm talking about singly-
> linked lists, which you DO NOT NEED, and SHOULD NOT USE, recursion to
> deal with.
Ah, then you are the one introducing the straw man, because Bearophile is
talking about trees.
--
Steven
Steven D'Aprano
> *Sigh* Well, I'm out of this debate. Apparently it's not possible to
> argue that recursivie algorithms should be avoided *sometimes* without
> everyone citing cases that obviously aren't from those times (as if I
> had been arguing that recursion should be avoided all the time).
You overstated your position, and then instead of gracefully admitting
that you overstated it, you're trying to weasel out of it by acting the
victim. If all you had said was that "sometimes" recursion should be
avoided, then who could argue against that? Scheme purists? Pah, this is
Python, we don't need no stinkin' mathematical purity!
Practicality beats purity is *precisely* why sometimes you need recursion
instead of forcing a complicated iterative solution onto a simple
recursive problem.
> Here's a parting thought for you to cite "counterexamples" of:
>
> Iteration should be used instead of recursion anywhere a tail- recursive
> algorithm is possible. Recursion should be used only when
> tail-recursion is not possible.
Or when the recursive algorithm is simpler than the iterative algorithm,
and you don't care about squeezing out every last tiny micro-optimization
into the code.
--
Steven
Luis Zarrabeitia
> <devils_advocate>
> Adding syntax is EVIL(tm) for it angers the Gods of Backwards
> Compatibility, and this proposal is completely unnecessary because you
> could instead just write:
> And there would be much clashing with existing variable names,
> for keywords are the Devil's work!
Heh. I liked the proposal (though I'm not 100% sold on the name __this__), and
one of the reasons I liked it was... it preempted the name-clashing argument.
Not a new keyword, just a variable that is injected on the local namespace,
so it would only clash with code that uses __this__ as a global (or that
expects to use an unbound __this__).
Btw, is there any way to inject a name into a function's namespace? Following
the python tradition, maybe we should try to create a more general solution!
K.
(P.S: there is one advantage on having it as a keyword, though: it would make
static analisis easier)
--
Luis Zarrabeitia (aka Kyrie)
Fac. de Matemática y Computación, UH.
http://profesores.matcom.uh.cu/~kyrie
Luis Zarrabeitia
> def ivisit(node):
> print node
> while node and node.link is not None:
> node = node.link
> print node
>
> def rvisit(node):
> print node
> if node and node.link is not None:
> rvisit(node.link)
>
>
> If there are programmers who find rvisit "a lot less readable" than
> ivisit, then in my arrogant opinion they should consider a change of
> profession.
/me smiles.
What if I happen to find rvisit _more_ readable than ivisit?
/me ducks.
[I'm not a lisp user, but I tend to think recursively anyway...]
Luis Zarrabeitia
> Iteration should be used instead of recursion anywhere a tail-
> recursive algorithm is possible. Recursion should be used only when
> tail-recursion is not possible.
Why?
Is it because most languages suck at recursion (specially python, as this
thread shows)? If that's the reason, I think you have it backwards... Turning
a tail-recursion into an iteration should be the compiler's job, not mine.
An algorithm, any algorithm, should be written in the way that is easier to
read, unless the language wont allow that easier implementation to be
efficient enough.
Programming languages suck, but that shouldn't mean that we can't hope to
improve them.
Arnaud Delobelle
> On Tuesday 05 May 2009 02:46:58 am Chris Rebert wrote:
>
> > <devils_advocate>
> > Adding syntax is EVIL(tm) for it angers the Gods of Backwards
> > Compatibility, and this proposal is completely unnecessary because you
> > could instead just write:
> [...]
> > And there would be much clashing with existing variable names,
> > for keywords are the Devil's work!
> > </devils_advocate>
>
> Heh. I liked the proposal (though I'm not 100% sold on the name __this__), and
> one of the reasons I liked it was... it preempted the name-clashing argument.
> Not a new keyword, just a variable that is injected on the local namespace,
> so it would only clash with code that uses __this__ as a global (or that
> expects to use an unbound __this__).
One issue with automatically binding a local variable to the current
function is with nested functions:
def foo()
def bar():
# How do I call foo() from here?
One solution would be
def foo()
def bar(foo=__this__):
foo()
I don't know, it does not convince me ATM.
--
Arnaud
Paul Rubin
> def rvisit(node):
> print node
> if node and node.link is not None:
> rvisit(node.link)
Less redundant (remember the extra "recursion" doesn't cost anything
if the compiler is sane enough to turn it into a jump):
def rvisit(node):
print node
if node:
rvisit(node.link)
Steve Howell
<ste...@REMOVE.THIS.cybersource.com.au> wrote:
>
> I propose a small piece of sugar. When a function is entered, Python
> creates an ordinary local name in the function's local namespace, and
> binds the function itself to that name. Two possibilities for the name
> are `this` or `__this__`, analogous to `self` in methods and `__name__`
> in modules.
>
> If there is any support for this, I propose to send the following (long)
> post to python-ideas. Feedback, corrections and suggestions welcome.
>
I totally support this proposal. I've definitely wasted time in the
past trying to invent my own workarounds for the use cases you
describe.
Obviously, there will be some bikeshed debates on __this__ vs.
__name__ vs. __func__, etc. I don't have an opinion there, just want
*something* handy for introspection, DRYness, etc.
A more interesting question is whether __this__ would just always be
there (that's my vote), or if you should have to apply a special
decorator to get it (which I oppose, but I can see some merits).
Aaron Brady
Here is how to get the function into the function as an argument, and
still permit recursive calls onto it.
>>> def auto( f ):
... def _inner( *ar, **kw ):
... return f( g, *ar, **kw )
... g= _inner
... return g
...
>>> @auto
... def f( self, n ):
... print( self, n )
... return 1 if n== 1 else n* self( n- 1 )
...
>>> f(7)
<function _inner at 0x00BA0D68> 7
<function _inner at 0x00BA0D68> 6
<function _inner at 0x00BA0D68> 5
<function _inner at 0x00BA0D68> 4
<function _inner at 0x00BA0D68> 3
<function _inner at 0x00BA0D68> 2
<function _inner at 0x00BA0D68> 1
5040
The function that is passed into the function is the decorated
function, not the original. The decorator function is also returned
from the decorator calls, so both the external caller and the internal
caller are calling the same function, '_inner' in the sample, which
then back-calls the original.
Please stay tuned for the post-graduate lecture. There will be time
for questions at the cookies-and-creme seminar afterward.
Duncan Booth
> Here is how to get the function into the function as an argument, and
> still permit recursive calls onto it.
>
>>>> def auto( f ):
> ... def _inner( *ar, **kw ):
> ... return f( g, *ar, **kw )
> ... g= _inner
> ... return g
> ...
>>>> @auto
> ... def f( self, n ):
> ... print( self, n )
> ... return 1 if n== 1 else n* self( n- 1 )
> ...
>>>> f(7)
><function _inner at 0x00BA0D68> 7
><function _inner at 0x00BA0D68> 6
><function _inner at 0x00BA0D68> 5
><function _inner at 0x00BA0D68> 4
><function _inner at 0x00BA0D68> 3
><function _inner at 0x00BA0D68> 2
><function _inner at 0x00BA0D68> 1
> 5040
>
It might be better to use some convention other than 'self' for the first
argument otherwise it will cause confusion when writing recursive methods:
>>> class C(object):
@auto
def meth(this, self, n):
print this, self, n
return 1 if n==1 else n*this(self, n-1)
>>> inst = C()
>>> inst.meth(5)
<function _inner at 0x0000000003680198> <__main__.C object at
0x000000000366C4E0> 5
<function _inner at 0x0000000003680198> <__main__.C object at
0x000000000366C4E0> 4
<function _inner at 0x0000000003680198> <__main__.C object at
0x000000000366C4E0> 3
<function _inner at 0x0000000003680198> <__main__.C object at
0x000000000366C4E0> 2
<function _inner at 0x0000000003680198> <__main__.C object at
0x000000000366C4E0> 1
120
bearoph...@lycos.com
> It is easy to change all references of the function name, except for
> those in the function body itself? That needs some explantation.
I can answer this. If I have a recursive function, I may want to
create a similar function, so I copy and paste it, to later modify the
copied version. Then to change its name I usually don't use a search &
rename of its name into its block of code because it's usually
useless. In non-recursive functions the name of the function is stated
only once, at the top.
Recursive functions violate the DRY principle, that's the root of the
problem.
The auto(f) decorator shown later by Aaron Brady seems the best
solution found so far, it's so nice that it even seems practically
usable.
Bye,
bearophile
bearoph...@lycos.com
> >>> def auto( f ):
>
> ... def _inner( *ar, **kw ):
> ... return f( g, *ar, **kw )
> ... g= _inner
> ... return g
Looks nice, I'll try to the following variant to see if it's usable:
def thisfunc(fun):
"""Decorator to inject a default name of a
function inside a function"""
def _inner(*args, **kwds):
return fun(g, *args, **kwds)
g = _inner
g.__name__ = fun.__name__
g.__dict__.update(fun.__dict__)
g.__doc__ = fun.__doc__
g.__module__ = fun.__module__
return g
@thisfunc
def SOMEVERYUGLYNAME(this, n):
return 1 if n <= 1 else n * this(n - 1)
assert SOMEVERYUGLYNAME(6) == 2*3*4*5*6
Bye,
bearophile
Aaron Brady
/Actually/, the 'g' variable was spurious. FWIW.
def auto( f ):
def _inner( *ar, **kw ):
return f( _inner, *ar, **kw )
return _inner
MRAB
Steven D'Aprano
> One issue with automatically binding a local variable to the current
> function is with nested functions:
>
> def foo()
> def bar():
> # How do I call foo() from here?
As foo(), just like you would call foo() from outside of foo(). __this__
would refer to bar() inside bar().
My proposal isn't meant to solve the general case "how do I call any
function anywhere without knowing its name?". I don't think there is a
general solution to that problem (although obviously you can do it in
special cases). My proposal is sugar for a fairly general problem "how
should a function refer to itself?", not an alternative mechanism for
referring to functions outside of the usual namespace lookup mechanism.
> One solution would be
>
> def foo()
> def bar(foo=__this__):
> foo()
That would be an option, if the programmer had some reason for wanting to
do this.
--
Steven
Rhodri James
> wolfram.hinde...:
>> It is easy to change all references of the function name, except for
>> those in the function body itself? That needs some explantation.
>
> I can answer this. If I have a recursive function, I may want to
> create a similar function, so I copy and paste it, to later modify the
> copied version. Then to change its name I usually don't use a search &
> rename of its name into its block of code because it's usually
> useless. In non-recursive functions the name of the function is stated
> only once, at the top.
I'm sorry, but while I'm mildly positive towards the proposal (and more
so towards Aaron's decorator), I don't buy this argument at all. What
is broken about your editor's global search-and-replace function that
makes it "usually useless" for making these name changes?
--
Rhodri James *-* Wildebeeste Herder to the Masses
Gabriel Genellina
<rho...@wildebst.demon.co.uk> escribi�:>> wolfram.hinde...:
>>> It is easy to change all references of the function name, except for
>>> those in the function body itself? That needs some explantation.
>>
>> I can answer this. If I have a recursive function, I may want to
>> create a similar function, so I copy and paste it, to later modify the
>> copied version. Then to change its name I usually don't use a search &
>> rename of its name into its block of code because it's usually
>> useless. In non-recursive functions the name of the function is stated
>> only once, at the top.
>
> I'm sorry, but while I'm mildly positive towards the proposal (and more
> so towards Aaron's decorator), I don't buy this argument at all. What
> is broken about your editor's global search-and-replace function that
> makes it "usually useless" for making these name changes?
It happened to me sometimes. If a module defines some functions, and it
doesn't *use* them, why should I use a global search-and-replace to rename
something? Modifying the "def" line should be enough - unless the function
happens to be recursive.
It's the DRY principle in action, the same argument as when decorators
where introduced: there should be no need to repeat the function name
again and again.
--
Gabriel Genellina
Arnaud Delobelle
> def auto( f ):
> def _inner( *ar, **kw ):
> return f( _inner, *ar, **kw )
> return _inner
Quoting myself near the start of this thread:
Here's an idea:
>>> def bindfunc(f):
... def boundf(*args, **kwargs):
... return f(boundf, *args, **kwargs)
... return boundf
--
Arnaud
Lie Ryan
> Btw, is there any way to inject a name into a function's namespace? Following
> the python tradition, maybe we should try to create a more general solution!
How about a mechanism to pass arguments that are optional to accept?
So (in the general case) the caller can call a function with certain
arguments, but unless the function explicitly accept it, the argument
will be discarded.
With this, the injecting a local would simply be a case of adding an "I
accept the argument" statement.
Sort of like this:
def func():
''' I reject '''
pass
func(@somearg='Feel free to accept this arg')
def func(@somearg):
''' I accept '''
print(somearg)
func(@somearg='Feel free to accept this arg')
Then on the case of injecting locals is simply by wrapping the function
with a function that will inject various argument to the function and
the function selectively choose which arguments they want to accept.
def needinfo(f):
# let's assume there is an inspect code here
func(@__name__=yournameis,
@__call__=yourfunction,
@__code__=yourcode,
@__yoursub__=youryo,
@__yourlim__=yoururso,
@__yourina__=yournisk,
@__yourlmes__=youridna,
@__yoursage__=yourpped
)
@needinfo
def func(@__name__, @__call__):
print 'Hi, my name is %s and to call me press %s' % (__name__,
__call__)
Does it sounds like a feature smell?
Aaron Brady
Yeah, but that was two days ago.
Aaron Brady
> Luis Zarrabeitia wrote:
> > Btw, is there any way to inject a name into a function's namespace? Following
> > the python tradition, maybe we should try to create a more general solution!
>
> How about a mechanism to pass arguments that are optional to accept?
>
> So (in the general case) the caller can call a function with certain
> arguments, but unless the function explicitly accept it, the argument
> will be discarded.
>
> With this, the injecting a local would simply be a case of adding an "I
> accept the argument" statement.
You could write a decorator to do that with the inspect module, or you
could just accept a keyword dict for extra as-desired args.
Rhodri James
<gags...@yahoo.com.ar> wrote:
> En Tue, 05 May 2009 22:35:08 -0300, Rhodri James
> <rho...@wildebst.demon.co.uk> escribió:
>> On Tue, 05 May 2009 21:43:16 +0100, <bearoph...@lycos.com> wrote:
>>> wolfram.hinde...:
>
>>>> It is easy to change all references of the function name, except for
>>>> those in the function body itself? That needs some explantation.
>>>
>>> I can answer this. If I have a recursive function, I may want to
>>> create a similar function, so I copy and paste it, to later modify the
>>> copied version. Then to change its name I usually don't use a search &
>>> rename of its name into its block of code because it's usually
>>> useless. In non-recursive functions the name of the function is stated
>>> only once, at the top.
>>
>> I'm sorry, but while I'm mildly positive towards the proposal (and more
>> so towards Aaron's decorator), I don't buy this argument at all. What
>> is broken about your editor's global search-and-replace function that
>> makes it "usually useless" for making these name changes?
>
> It happened to me sometimes. If a module defines some functions, and it
> doesn't *use* them, why should I use a global search-and-replace to
> rename something? Modifying the "def" line should be enough - unless the
> function happens to be recursive.
So the answer to my question would be "nothing"?
> It's the DRY principle in action, the same argument as when decorators
> where introduced: there should be no need to repeat the function name
> again and again.
Unless of course you're using it again and again, which you are.
Luis Alberto Zarrabeitia Gomez
Quoting Rhodri James <rho...@wildebst.demon.co.uk>:
> >> I'm sorry, but while I'm mildly positive towards the proposal (and more
> >> so towards Aaron's decorator), I don't buy this argument at all. What
> >> is broken about your editor's global search-and-replace function that
> >> makes it "usually useless" for making these name changes?
> >
> > It happened to me sometimes. If a module defines some functions, and it
> > doesn't *use* them, why should I use a global search-and-replace to
> > rename something? Modifying the "def" line should be enough - unless the
> > function happens to be recursive.
>
> So the answer to my question would be "nothing"?
Indeed, there is nothing broken with the search and replace feature of his
editor. When he is copying a non-recursive function, it is _useless_ to do a
search and replace. When he is copying a recursive function, it is _required_ to
do a search and replace.
So, the very same task requires you to either perform a task that will almost
always be useless (or even dangerous), or to read the source code to find out if
the function is recursive, so that you can use the search and replace only then.
(I know that the "problem" is present in almost all programming languages... but
that's not what is being discussed. Bearophile's concerns seem legitimate, and
you should not dismiss them so lightly just because there are ways to do more
work and hopefully avoid the problems. I'd say that the "problem" is even
aggravated in python, where the dynamic nature of the language makes it near to
impossible to build good refactoring tools)
--
Luis Zarrabeitia
Facultad de Matem�tica y Computaci�n, UH
http://profesores.matcom.uh.cu/~kyrie
--
Participe en Universidad 2010, del 8 al 12 de febrero de 2010
La Habana, Cuba
http://www.universidad2010.cu
Rhodri James
<ky...@uh.cu> wrote:
> Quoting Rhodri James <rho...@wildebst.demon.co.uk>:
>> So the answer to my question would be "nothing"?
>
> Indeed, there is nothing broken with the search and replace feature of
> his editor. When he is copying a non-recursive function, it is
> _useless_ to do a search and replace. When he is copying a recursive
> function, it is _required_ to do a search and replace.
On the contrary, it's merely not very useful for a non-recursive
function. It still changes the function's name, which was one of the
objectives. Seriously, the lack of effort in (say) doing a quick
incremental search for the function's name is a no-brainer.
> So, the very same task requires you to either perform a task that will
> almost always be useless (or even dangerous), or to read the source code
> to find out if the function is recursive, so that you can use the search
> and replace only then.
If you're copying code without reading it, you're going to get bitten
anyway some time. My sympathy is still limited.
> (I know that the "problem" is present in almost all programming
> languages... but that's not what is being discussed. Bearophile's
> concerns seem legitimate, and you should not dismiss them so lightly
> just because there are ways to do more work and hopefully avoid the
> problems. I'd say that the "problem" is even aggravated in python,
> where the dynamic nature of the language makes it near to
> impossible to build good refactoring tools)
As with that other great "problem" of python, the lack of private
class attributes, a tiny amount of self-discipline solves 90% of the
issues.
Steven D'Aprano
> On Wed, 06 May 2009 23:33:20 +0100, Luis Alberto Zarrabeitia Gomez
> <ky...@uh.cu> wrote:
>
>> Quoting Rhodri James <rho...@wildebst.demon.co.uk>:
>>> So the answer to my question would be "nothing"?
>>
>> Indeed, there is nothing broken with the search and replace feature of
>> his editor. When he is copying a non-recursive function, it is
>> _useless_ to do a search and replace. When he is copying a recursive
>> function, it is _required_ to do a search and replace.
>
> On the contrary, it's merely not very useful for a non-recursive
> function.
[...]
Whether search and replace is "not very useful" or "not useful at all",
it's still an inconvenience and a PITA. Calling up S&R to search through
a six line function is ridiculously overkill, but if you don't do it,
you'll surely be bitten.
But regardless, everyone is missing the most important point: why are you
copying and pasting code in the first place? That is surely very close to
the top of the list of Worst Ever Anti-Patterns, and it should be avoided
whenever possible.
In Python, we can avoid much copy-and-paste coding with decorators. Given
one function, we can create as many variants as we want, differing in pre-
processing of arguments and post-processing of results, by using
decorators. This is a powerful ability to have, but it's crippled for
many recursive functions, because recursive functions in Python don't
actually call themselves, they call whatever happens to be bound to their
name at runtime.
As Luis said, all(?) programming languages have this same weakness. Just
because it's a weakness shared by all languages, doesn't stop it from
being a weakness. My proposal will lesson (but not entirely eliminate)
this weakness.
--
Steven
Luis Alberto Zarrabeitia Gomez
Quoting Steven D'Aprano <ste...@REMOVE.THIS.cybersource.com.au>:
> But regardless, everyone is missing the most important point: why are you
> copying and pasting code in the first place? That is surely very close to
> the top of the list of Worst Ever Anti-Patterns, and it should be avoided
> whenever possible.
[btw, I took this long before jumping into this thread for this precise
reason... Copy/paste is an evil anti-pattern.
> In Python, we can avoid much copy-and-paste coding with decorators. Given
> one function, we can create as many variants as we want, differing in pre-
> processing of arguments and post-processing of results, by using
> decorators. This is a powerful ability to have, but it's crippled for
> many recursive functions, because recursive functions in Python don't
> actually call themselves, they call whatever happens to be bound to their
> name at runtime.
A bit offtopic: a while ago I think I saw a recipe for a decorator that, via
bytecode hacks, would bind otherwise global names to the local namespace of the
function. Can anyone remember it/point me to it? An @bind decorator that would
'localize' all the global names, including the still unexistent but already know
function name, would guarantee that at least recursion calls the same function
instead of "whatever happens to be bound to their name at runtime". If it wasn't
a hack, anyway.
Terry Reedy
I am writing a book (with Python package) on algorithms that has *lots*
of recursive functions. I have also discovered that changing names can
be a pain. So in the text, (but not code) I have tried the equivalent of
# real_name
def f(params):
... f(args)
(This also keeps lines short enough for side-by-side versions, when I
want to do that.)
> But regardless, everyone is missing the most important point: why are you
> copying and pasting code in the first place?
In my case, I will be discussing variations of algorithms. Copy and
edit minimizes fatigue and errors and maximizes parallelism.
That is surely very close to
> the top of the list of Worst Ever Anti-Patterns, and it should be avoided
> whenever possible.
Not if the alternative is re-typing ;-).
> In Python, we can avoid much copy-and-paste coding with decorators.
But not when the variation is in the guts of the code.
> because recursive functions in Python don't actually call themselves,
> they call whatever happens to be bound to their name at runtime.
I have mentioned that. Also, apparently non-recursive functions can
become recursive after the fact by being bound to another name used in
the function.
tjr
Francis Carr
recursion, including the most complete support for tail-call
optimization, constructs like "letrec" to define collections of
multiply-recursive functions (which get used very frequently -- by no
means is it an uncommon situation, as you suggest in your initial
post), and hardly any iterative loops. Yet -- scheme does not provide
out-of-the-box support for your proposed "let-a-function-implicitly-
refer-to-itself" idea. This suggests that the idea itself runs
counter to more important aspects of a programming language.
In the special case of a self-recursive function, you would like re-
naming "to just work". Out of morbid curiosity, I am compelled to
ask... why do you expect that re-naming anything --- a function, a
class, a module, a variable, anything --- in just one place but not
all the others should ever, under any circumstances, "just work" ?
bearoph...@lycos.com
I don't know who are you talking to, but I can give you few answers
anyway.
>collections of multiply-recursive functions (which get used very frequently -- by no means is it an uncommon situation, as you suggest in your initial post),<
They may be frequent in Scheme (because it's often used as an almost
pure language), but in Python code they are quite rare. I have used
two mutual recursive functions only once in non-toy Python code in two
or more years.
>Yet -- scheme does not provide out-of-the-box support for your proposed "let-a-function-implicitly- refer-to-itself" idea. This suggests that the idea itself runs counter to more important aspects of a programming language.<
I see. It's not a very implicit thing, because you have to call a
function anyway, it's just it has a fixed name, like __func__.
I think it doesn't runs counter to Python & D languages (I have asked
for a similar feature in D2 too, and the designers seem to have
accepted the idea, already suggested there by another person in the
past).
Bye,
bearophile
Arnaud Delobelle
> A bit offtopic: a while ago I think I saw a recipe for a decorator
> that, via bytecode hacks, would bind otherwise global names to the
> local namespace of the function. Can anyone remember it/point me to
> it? An @bind decorator that would 'localize' all the global names,
> including the still unexistent but already know function name, would
> guarantee that at least recursion calls the same function instead of
> "whatever happens to be bound to their name at runtime". If it wasn't
> a hack, anyway.
I remember a discussion on python-ideas, and I wrote this decorator at
the time:
def new_closure(vals):
args = ','.join('x%i' % i for i in range(len(vals)))
f = eval("lambda %s:lambda:(%s)" % (args, args))
return f(*vals).func_closure
def localize(f):
f_globals = dict((n, f.func_globals[n]) for n in f.func_code.co_names)
f_closure = ( f.func_closure and
new_closure([c.cell_contents for c in f.func_closure]) )
return type(f)(f.func_code, f_globals, f.func_name,
f.func_defaults, f_closure)
Unfortunately it fails for recursive functions:
>>> @localize
... def fac(n):
... return 1 if n <= 1 else n*fac(n - 1)
...
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "localize.py", line 7, in localize
f_globals = dict((n, f.func_globals[n]) for n in f.func_code.co_names)
File "localize.py", line 7, in <genexpr>
f_globals = dict((n, f.func_globals[n]) for n in f.func_code.co_names)
KeyError: 'fac'
It can be fixed, but not very easily precisely because the function is
recursive. I've hacked a quick way to do it below.
def reclocalize(f):
def wrapper(*args, **kwargs):
return recf(*args, **kwargs)
def getglobal(name):
return wrapper if name == f.__name__ else f.func_globals[name]
f_globals = dict((n, getglobal(n)) for n in f.func_code.co_names)
f_closure = ( f.func_closure and
new_closure([c.cell_contents for c in f.func_closure]) )
recf = type(f)(f.func_code, f_globals, f.func_name,
f.func_defaults, f_closure)
return wrapper
Now it works as intended:
>>> @reclocalize
... def fac(n):
... return 1 if n <= 1 else n*fac(n - 1)
...
>>> fac(10)
3628800
>>> foo = fac
>>> del fac
>>> foo(10)
3628800
--
Arnaud
Gabriel Genellina
<ky...@uh.cu> escribiￜ:
>
> Quoting Steven D'Aprano <ste...@REMOVE.THIS.cybersource.com.au>:
>
>> But regardless, everyone is missing the most important point: why are
>> you
>> copying and pasting code in the first place? That is surely very close
>> to
>> the top of the list of Worst Ever Anti-Patterns, and it should be
>> avoided
>> whenever possible.
>
> [btw, I took this long before jumping into this thread for this precise
> reason... Copy/paste is an evil anti-pattern.
>
>> In Python, we can avoid much copy-and-paste coding with decorators.
>> Given
>> one function, we can create as many variants as we want, differing in
>> pre-
>> processing of arguments and post-processing of results, by using
>> decorators. This is a powerful ability to have, but it's crippled for
>> many recursive functions, because recursive functions in Python don't
>> actually call themselves, they call whatever happens to be bound to
>> their
>> name at runtime.
>
> A bit offtopic: a while ago I think I saw a recipe for a decorator that,
> via
> bytecode hacks, would bind otherwise global names to the local namespace
> of the
> function. Can anyone remember it/point me to it? An @bind decorator that
> would
> 'localize' all the global names, including the still unexistent but
> already know
> function name, would guarantee that at least recursion calls the same
> function
> instead of "whatever happens to be bound to their name at runtime". If
> it wasn't
> a hack, anyway.
I could not find such thing, but here it is something similar (mostly a
proof-of-concept).
Basically, modifies the bytecode so global references become local ones,
and then injects a new argument whose default value is the desired value.
It can be used to make all references to the function name to refer to the
function itself; also, the __function__ variant can be implemented.
<code>
from opcode import HAVE_ARGUMENT, opmap
def iter_code(co):
"""Iterate over a code object."""
code = co.co_code
n = len(code)
i = 0
while i < n:
op = ord(code[i])
if op >= HAVE_ARGUMENT:
oparg = ord(code[i+1]) + ord(code[i+2])*256
yield code[i:i+3], op, oparg
i += 3
else:
yield code[i], op, None
i += 1
def replace_bytecode(code, iname_global, iname_local):
LOAD_GLOBAL = opmap['LOAD_GLOBAL']
LOAD_FAST = opmap['LOAD_FAST']
STORE_GLOBAL = opmap['STORE_GLOBAL']
STORE_FAST = opmap['STORE_FAST']
for codestr, op, oparg in iter_code(code):
if op==LOAD_GLOBAL and oparg==iname_global:
codestr = chr(LOAD_FAST) + chr(iname_local % 256) + chr(iname_local
// 256)
elif op==STORE_GLOBAL and oparg==iname_global:
codestr = chr(STORE_FAST) + chr(iname_local % 256) + chr(iname_local
// 256)
yield(codestr)
class GlobalToLocalWarning(RuntimeWarning): pass
def global_to_local(function, refname, value):
"""
Make all references to `refname` local instead of global.
Actually, transform
def function(a,b,c):
into
def function(a,b,c,refname=value)
"""
code = function.func_code
if refname not in code.co_names:
import warnings
warnings.warn(GlobalToLocalWarning('no reference to "%s" found in %s'
% (refname, function.func_name)), stacklevel=2)
return function
# insert refname just after the last argument
varnames = list(code.co_varnames)
varnames.insert(code.co_argcount, refname)
# new bytecode using LOAD_FAST instead of LOAD_GLOBAL
iname_global = code.co_names.index(refname) # LOAD_GLOBAL/STORE_GLOBAL
operand
iname_local = code.co_argcount # LOAD_FAST/STORE_FAST operand
rawcode = ''.join(replace_bytecode(code, iname_global, iname_local))
function.func_code = type(code)(
code.co_argcount + 1,
code.co_nlocals + 1,
code.co_stacksize,
code.co_flags,
rawcode,
code.co_consts,
code.co_names,
tuple(varnames),
code.co_filename,
code.co_name,
code.co_firstlineno,
code.co_lnotab
)
# the desired value is the default value of the new, fake argument
if function.func_defaults is None:
function.func_defaults = (value,)
else:
function.func_defaults += (value,)
return function
# decorator: function name refers to itself
def recursive3(function):
return global_to_local(function, function.func_name, function)
@recursive3
def fibo(n):
if n<=1: return 1
return fibo(n-1) + fibo(n-2)
# those "fibo" won't be global anymore
# decorator: name '__function__' refers to function
def recursive4(function):
return global_to_local(function, '__function__', function)
def factorial(n):
@recursive4
def _factorial(n, acc):
if n<=1: return acc
return __function__(n-1, n*acc)
return _factorial(n, 1)
print fibo, fibo.__name__, fibo.func_name, fibo.func_code.co_name
assert fibo(5)==8
F10=factorial(10)
assert F10==2*3*4*5*6*7*8*9*10
foo = fibo
bar = factorial
del fibo, factorial
assert foo(5)==8
assert bar(10)==F10
import inspect
assert inspect.getargspec(foo).defaults[0] is foo
</code>
--
Gabriel Genellina
Steven D'Aprano
> In the special case of a self-recursive function, you would like re-
> naming "to just work". Out of morbid curiosity, I am compelled to
> ask... why do you expect that re-naming anything --- a function, a
> class, a module, a variable, anything --- in just one place but not all
> the others should ever, under any circumstances, "just work" ?
Patching functions to do pre-processing or post-processing can be a
useful technique, (e.g. for tracing and debugging). This works for
regular functions, but not recursive functions.
>>> def listify(x):
... return [x]
...
>>> listify(42)
[42]
>>>
>>> _old_listify = listify
>>> def listify(x):
... print "Calling listify"
... return _old_listify(x)
...
>>> listify(42)
Calling listify
[42]
Note that the call to listify "just works" -- the patch runs once, the
original version of the function runs once, and we get the expected
results without any problems.
Now try the same technique on a recursive function, and it fails:
>>> def rec(x):
... if x > 0: return [x] + rec(x-1)
... else: return []
...
>>> rec(5)
[5, 4, 3, 2, 1]
>>>
>>> _old_rec = rec
>>> def rec(x):
... print "Calling rec"
... return _old_rec(x)
...
>>> rec(5)
Calling rec
Calling rec
Calling rec
Calling rec
Calling rec
Calling rec
[5, 4, 3, 2, 1]
Note too that if you're given an arbitrary function, there's no simple
way of telling whether it's recursive or not. Properly written "self-
reflective" functions using my proposed technique should be immune to
this problem.
--
Steven
George Sakkis
wrote:
> A bit offtopic: a while ago I think I saw a recipe for a decorator that, via
> bytecode hacks, would bind otherwise global names to the local namespace of the
> function. Can anyone remember it/point me to it?
Maybe you saw http://code.activestate.com/recipes/277940/ ?
George