Self function

[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 D'Aprano]

"(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".

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?

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 D'Aprano]

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/[email protected]/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

.... def spam(n):
.... if n < 0: return __this__(-n).upper()
.... return ' '.join([__this__.__name__] * n)
....'SPAM SPAM SPAM'

 

[Carl Banks]

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]

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

 

[Carl Banks]

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.

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.

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.

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.

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]

(e-mail address removed) wrote:

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/[email protected]/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

... def spam(n):
...     if n < 0: return __this__(-n).upper()
...     return ' '.join([__this__.__name__] * n)
...>>> tasty_meat_like_product = spam
'SPAM SPAM SPAM'

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

 

[CTO]

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]

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

 

[Carl Banks]

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.hinderer]

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]

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.

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.

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

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.


[...]

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

 

[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!
</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__).

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]

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]

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

 

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