Tail recursion to while iteration in 2 easy steps

[Alain Ketterlin]

No, but you can't prevent a lot of bad moves in python. What you just
did there is a total bonehead ("strange"?) of an idea.

I think allowing rebinding of function names is extremely strange, even
though it's easier to implement. I tend to agree with you on the quality
of the idea, but optimization has to take this into account (and give
up, usually).

-- Alain.

 

[Ian Kelly]

You misunderstood me. As usually implemented tail call recursion doesn't
require verifying that the function is calling itself, but in Python the
function could be rebound so a check would be a necessary protection
against this unlikely situation. Consider this Python:

@some_decorator
def fact(n, acc=1):
if n <= 1:
return acc
return fact(n-1, n*acc)

Is that tail recursion or not?

You cannot tell whether or not that is tail recursion unless you know the
definition of 'some_decorator' and even then the answer may vary from run
to run.

There is no doubt that it's a tail call. Whether it is recursion is
irrelevant to optimizing it. The reason we talk about "tail call
recursion" specifically is because the recursive case is the one that
makes the optimization worthwhile, not because the recursion is
necessary to perform the optimization.

It is possible that fact is recursive but that some_decorator adds
additional stack frames that are not tail calls and not optimizable.
If this were the case, then the recursion would still eventually hit
the stack limit, but there would still be benefit in optimizing the
"fact" frames, as it would increase the allowable depth before the
stack limit is reached. So I see no reason to check the identity of
the called function before optimizing the tail call.

 

[Ian Kelly]

There is no doubt that it's a tail call. Whether it is recursion is
irrelevant to optimizing it. The reason we talk about "tail call
recursion" specifically is because the recursive case is the one that
makes the optimization worthwhile, not because the recursion is
necessary to perform the optimization.

It is possible that fact is recursive but that some_decorator adds
additional stack frames that are not tail calls and not optimizable.
If this were the case, then the recursion would still eventually hit
the stack limit, but there would still be benefit in optimizing the
"fact" frames, as it would increase the allowable depth before the
stack limit is reached. So I see no reason to check the identity of
the called function before optimizing the tail call.

On the other hand, if you start optimizing every tail call and not
just the recursive functions, then I can see where that could start to
get problematic for debugging -- as arbitrary functions get removed
from the stack traces just because they happened to end in tail calls.

 

[Steven D'Aprano]

I think allowing rebinding of function names is extremely strange,

It's not, it's quite common. Functions in Python are first-class values,
and we can do things like this:

from somelibrary import somethingwithalonglongname as shortname

def inorder(tree, op=print):
# Walk the tree in infix order, doing op to each node.
process(tree.left, op)
op(tree.payload)
process(tree.right, op)

_len = len
def len(obj):
do_something_first()
return _len(obj)


Now, the first two aren't the same sort of function-rebinding that you're
talking about, or that were shown in your post, but the third is. What is
unusual though is rebinding a function from within itself:

def func(arg):
global func
do_this(arg)
def func(arg):
do_that(arg)


but it's legal and it sometimes can be useful, although it counts as
"clever code", possibly "too clever".

 

[rusi]

I am interested in studying more this 'whole spectrum of optimizations'
Any further pointers?

Mmm… Bummer…

There was a book having these -- at least 5-6 different optimizations of which tail-call was the most obvious. Maybe author was McGettrick dont remember for sure... Probably 20 years now!

I'll try and re-remember them and post.

 

[Jussi Piitulainen]

You misunderstood me. As usually implemented tail call recursion
doesn't require verifying that the function is calling itself, but
in Python the function could be rebound so a check would be a
necessary protection against this unlikely situation. Consider this
Python:

@some_decorator
def fact(n, acc=1):
if n <= 1:
return acc
return fact(n-1, n*acc)

Is that tail recursion or not?

You cannot tell whether or not that is tail recursion unless you
know the definition of 'some_decorator' and even then the answer may
vary from run to run.

Ignoring the decorator, fact(n-1, n*acc) is in a tail position because
it follows the keyword return. It doesn't matter what function fact is
at the time: the remaining action in the caller is to return.

Tail positions, with respect to enclosing code, are defined
syntactically.

 

[Terry Reedy]

On the other hand, if you start optimizing every tail call and not
just the recursive functions, then I can see where that could start to
get problematic for debugging -- as arbitrary functions get removed
from the stack traces just because they happened to end in tail calls.

The idea of CPython space-optimizing tail calls when the call is made
has been suggested on python-ideas. Guido verified that it is
technically possible with the current bytecode interpreter but rejected
it because it would arbitrarily mess up stack traces.

 

[Terry Reedy]

I think allowing rebinding of function names is extremely strange,

Steven already countered the 'is extremely strange' part by showing that
such rebinding is common, generally useful, and only occasionally dodgy
and a candidate for being blocked.

I want to consider here what it would mean to concretely implement the
abstract notion 'disallow rebinding of function names' and show what
would be behind calling the idea 'not feasible'.

1. A 'name' is not a 'function name' unless the name is bound, at
runtime, to a 'function'.

2. A 'function' in Python is not just one class but any callable object
-- with with a __call__ methods. That comprises an unbounded set.

3. Python does not mandate how namespaces are implemented. CPython uses
both dicts and, for function local namespaces, internal C arrays. So
'names' in code can become either string keys for dicts or integer
indexes for arrays.

4. Rebinding can be explicit ('='), implicit ('import', 'class', 'def'),
*or hidden* (globals('a') = 1; ob.__dict__('a') = 1). The 'hidden'
methods are intentional as they are sometimes needed*. In CPython,
these forms remain different in the byte code, but it could be
otherwise. The point is that is may or may not be possible for the
interpreter to even recognize a 'rebinding' in order to apply any
rebinding blocking rule.

* There is no trick (that I know of) for hidden rebinding of function
locals and nonlocals (short of using ctypes), but I am not sure that
this is a language guarantee. However, I an sure that the absence is
intentional.

even though it's easier to implement.

No kidding.

 

[Antoon Pardon]

Op 04-10-13 23:14, Terry Reedy schreef:

The idea of CPython space-optimizing tail calls when the call is made
has been suggested on python-ideas. Guido verified that it is
technically possible with the current bytecode interpreter but rejected
it because it would arbitrarily mess up stack traces.

What does this mean?

Does it mean that a naive implementation would arbitrarily mess up
stack traces and he wasn't interested in investigating more
sophisticated implementations?

Does it mean he just didn't like the idea a stack trace wouldn't be a
100% represenatation of the active call history?

Does it mean he investigated more sphisticated implementations but found
them to have serious short comings that couldn't be remedied easily?

 

[Alain Ketterlin]

Steven already countered the 'is extremely strange' part by showing
that such rebinding is common, generally useful, and only occasionally
dodgy and a candidate for being blocked.

I was talking about rebinding a "function name", not about rebinding a
name to a function. Steve's message was pretty clear on this: iirc, his
first two cases were "binding a new name to an existing callable", the
last case (rebinding len) was in line with what I meant (except his code
"saved" the original function).

My example was: the code of "fact" contains a call to "fact", which is
not guaranteed to be bound to the function it appears in. And this
prevents any kind of optimization.

I want to consider here what it would mean to concretely implement the
abstract notion 'disallow rebinding of function names' and show what
would be behind calling the idea 'not feasible'.

Again, I'm more concerned about the function than about the name.

And the fact that "disallow rebinding of function names" is not feasible
in Python is a design choice, not an essential characteristic of every
programming language.

That's fine. My point was: you can't at the same time have full
dynamicity *and* procedural optimizations (like tail call opt).
Everybody should be clear about the trade-off.

1. A 'name' is not a 'function name' unless the name is bound, at
runtime, to a 'function'.

2. A 'function' in Python is not just one class but any callable
object -- with with a __call__ methods. That comprises an unbounded
set.

Right. Then when you do:

def myfunc(...): ...

myfunc is bound to an callable object. In my example, I was doing the
equivalent to rebinding myfunc, losing the last reference to that piece
of code:

myfunc = somethingelse

BTW, does the original callable object have a ref counter? Is it garbage
collected in that case? If not, would it be considered a bug?

3. Python does not mandate how namespaces are implemented. CPython
uses both dicts and, for function local namespaces, internal C arrays.
So 'names' in code can become either string keys for dicts or integer
indexes for arrays.

Well, yes, but that's an implementation detail, no?

4. Rebinding can be explicit ('='), implicit ('import', 'class',
def'), *or hidden* (globals('a') = 1; ob.__dict__('a') = 1). The
hidden' methods are intentional as they are sometimes needed*. In
CPython, these forms remain different in the byte code, but it could
be otherwise. The point is that is may or may not be possible for the
interpreter to even recognize a 'rebinding' in order to apply any
rebinding blocking rule.

Sure (that's exactly why I said it is easier to implement). If you were
to disallow rebinding of global function names, you would need a proper
notion of global scope and various categories of names, something almost
all compiled languages have.

* There is no trick (that I know of) for hidden rebinding of function
locals and nonlocals (short of using ctypes), but I am not sure that
this is a language guarantee. However, I an sure that the absence is
intentional.


No kidding.

(See above).

-- Alain.

 

[Antoon Pardon]

Op 07-10-13 19:15, Alain Ketterlin schreef:

Again, I'm more concerned about the function than about the name.

And the fact that "disallow rebinding of function names" is not feasible
in Python is a design choice, not an essential characteristic of every
programming language.

That's fine. My point was: you can't at the same time have full
dynamicity *and* procedural optimizations (like tail call opt).
Everybody should be clear about the trade-off.

Your wrong. Full dynamics is not in contradiction with tail call
optimisation. Scheme has already done it for years. You can rebind
names to other functions in scheme and scheme still has working
tail call optimisatiosn.

 

[Terry Reedy]

Well, yes, but that's an implementation detail, no?

That is why I switched from 'Python' to 'CPython'. But I note the
following: in 2.x, 'from mod import *' in a function meant that the
compile time mapping of name to index could not be used and that a
fallback to dict was necessary. So another implementation might take the
easier path and always use a dict for function locals. In 3.x, such
import are limited to module scope so that functions can always use an
array and indexes for function locals. So other implementations can take
the hint and do the same without needing a dict fallback.

In other words, 3.x changed the language to facilitate the
implementation detail.

 

[random832]

That's fine. My point was: you can't at the same time have full
dynamicity *and* procedural optimizations (like tail call opt).
Everybody should be clear about the trade-off.

Let's be clear about what optimizations we are talking about. Tail call
optimization, itself, doesn't care _what_ is being called. It can just
as easily mean "erase its own stack frame and replace it with that of
another function" as "reassign the arguments and jump to the top of this
function". Some people have introduced the idea of _further_
optimizations, transforming "near" tail recursion (i.e. return self()+1)
into tail recursion, and _that_ depends on knowing the identity of the
function (though arguably that could be accounted for at the cost of
including dead code for the path that assumes it may have been changed),
but tail call optimization itself does not.

 

[random832]

What does this mean?

Does it mean that a naive implementation would arbitrarily mess up
stack traces and he wasn't interested in investigating more
sophisticated implementations?

Does it mean he just didn't like the idea a stack trace wouldn't be a
100% represenatation of the active call history?

Does it mean he investigated more sphisticated implementations but found
them to have serious short comings that couldn't be remedied easily?

The entire point of tail call optimization requires not keeping the
intervening stack frames around, in _any_ form, so as to allow
arbitrarily deep recursion without ever having the possibility of a
stack overflow. An implementation which reduced but did not eliminate
the space used per call would not be worthwhile because it would not
enable the recursive functional programming patterns that mandatory tail
call optimization allows.

You could require that an "optimizable tail call" be made explicit.
Actually, I suspect it might be possible to do this now, by abusing
exception handling as a control flow mechanism.

 

[MRAB]

Op 07-10-13 19:15, Alain Ketterlin schreef:

Your wrong. Full dynamics is not in contradiction with tail call
optimisation. Scheme has already done it for years. You can rebind
names to other functions in scheme and scheme still has working tail
call optimisatiosn.

Consider this code:

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

It compiles to this:
2 0 LOAD_FAST 0 (n)
3 LOAD_CONST 1 (1)
6 COMPARE_OP 1 (<=)
9 POP_JUMP_IF_FALSE 16

3 12 LOAD_FAST 1 (acc)
15 RETURN_VALUE

4 >> 16 LOAD_GLOBAL 0 (fact)
19 LOAD_FAST 0 (n)
22 LOAD_CONST 1 (1)
25 BINARY_SUBTRACT
26 LOAD_FAST 0 (n)
29 LOAD_FAST 1 (acc)
32 BINARY_MULTIPLY
33 CALL_FUNCTION 2 (2 positional, 0 keyword pair)
36 RETURN_VALUE

I think that CALL_FUNCTION immediately followed by RETURN_VALUE could
be tail-call optimised by dropping the caller's stack frame provided
that (like in this case) the callee doesn't refer to any name in the
callers stack frame (nonlocal).

You could also consider replacing the caller's stack frame with a
smaller pseudo-frame, perhaps compressing multiple pseudo-frames or
repeated sequences of pseudo-frames into a single pseudo-frame, so that
it could still generate the same traceback as before (or an compressed
traceback like what was discussed on python-ideas in the threads
"Compressing excepthook output" and "Idea: Compressing the stack on the
fly").

 

[Piet van Oostrum]

BTW, does the original callable object have a ref counter? Is it garbage
collected in that case? If not, would it be considered a bug?

In CPython ALL objects have ref counters.

 

[Mark Janssen]

That's fine. My point was: you can't at the same time have full

Your wrong. Full dynamics is not in contradiction with tail call
optimisation. Scheme has already done it for years. You can rebind
names to other functions in scheme and scheme still has working
tail call optimisatiosn.

Yeah, and this is where two models of computation have been conflated,
creating magical effects, confusing everybody. I challenge you to get
down to the machine code in scheme and formally describe how it's
doing both.

 

[Steven D'Aprano]

I challenge you to get
down to the machine code in scheme and formally describe how it's doing
both.

For which machine?

Or are you assuming that there's only one machine code that runs on all
computing devices?


Frankly, asking somebody to *formally* describe a machine code
implementation strikes me as confused. Normally formal descriptions are
given in terms of abstract operations, often high level operations,
sometimes *very* high level, and rarely in terms of low-level "flip this
bit, copy this byte" machine code operations. I'm not sure how one would
be expected to generate a formal description of a machine code
implementation.

But even putting that aside, even if somebody wrote such a description,
it would be reductionism gone mad. What possible light on the problem
would be shined by a long, long list of machine code operations, even if
written using assembly mnemonics?

Far more useful would be a high-level description of Scheme's programming
model. If names can be rebound on the fly, how does Scheme even tell
whether something is a recursive call or not?

def foo(arg):
do stuff here
foo(arg-1) # how does Scheme know that this is the same foo?

 

[Mark Janssen]

For which machine?

Right, I should stop assuming a modern implementation of vonNeumann
architecture (even though that, too, is ambiguous) since I'm talking
about theory, but yet it is relevant. My demarcation point for
arguments between "the scheme way" and other procedural languages
(which, apart from Pascal variants, I blithely all "the C way") gets
down to differing models of computation which shouldn't get conflated,
even though everyone thinks and lumps it all as "computation". They
simply can't get *practically* translated between one and the other,
even though they are *theoretically* translated between each other all
the time. Humans, of course know how to translate, but that doesn't
count from the pov of computer *science*.

Frankly, asking somebody to *formally* describe a machine code
implementation strikes me as confused. Normally formal descriptions are
given in terms of abstract operations, often high level operations,
sometimes *very* high level, and rarely in terms of low-level "flip this
bit, copy this byte" machine code operations. I'm not sure how one would
be expected to generate a formal description of a machine code
implementation.

It's like this: there *should* be one-to-one mappings between the
various high-level constructs to the machine code, varying only
between different chips (that is the purpose of the compiler after
all), yet for some operations, in languages like scheme, well... I
cannot say what happens... hence my challenge.

But even putting that aside, even if somebody wrote such a description,
it would be reductionism gone mad. What possible light on the problem
would be shined by a long, long list of machine code operations, even if
written using assembly mnemonics?

Only that you've got a consistent, stable (and therefore,
formalizable) translation from your language to the machine. That's
all. Everything else is magic. Do you know that the Warren
Abstraction Engine used to power the predicate logic in Prolog into
machien code for a VonNeumann machine is so complex, no one has
understood it (or perhaps even verified it)? One hardly knows where
these things originate. But here it gets into dark arts best not
entered into too deeply. It will turn you mad, like that guy in the
movie "pi".

 

[Mark Janssen]

Only that you've got a consistent, stable (and therefore,

formalizable) translation from your language to the machine. That's
all. Everything else is magic. Do you know that the Warren
Abstraction Engine used to power the predicate logic in Prolog into
machien code for a VonNeumann machine is so complex, no one has
understood it (or perhaps even verified it)?

Sorry, I mean the Warren Abstraction Machine (or WAM). I refer you to
www.cvc.uab.es/shared/teach/a25002/wambook.pdf.

Now, one can easily argue that I've gone too far to say "no one has
understood it" (obviously), so it's very little tongue-in-cheek, but
really, when one tries to pretend that one model of computation can be
substituted for another (arguing *for* the Church-Turing thesis), they
are getting into troubling territory (it is only a thesis,
remember)....