On 7/13/2015 7:22 AM, Jussi Piitulainen wrote:
Ian Burnette writes:
A post I did not receive, but want to comment on.
I've recently been playing around with Clojure, and I really like the
way they've overcome the JVM not supporting TRE. The way Clojure
solves this problem is to have a built in "recur" function that
signals to the Clojure compiler to convert the code to a loop in the
JVM.In python we could do something similar
Currently, the only means of affecting compilation of Python code are
future imports and global and nonlocal declarations. (Coding cookie
comments affect decoding of python code encoded as bytes, which happens
before interpretation of the code.) Functions are called while running,
after normal compilation. Python-coded functions are created during
runtime by executing def statements (although code object are created
during compilation).
A tre(code) function could be written today that converts a
tail-recursive body to a while body. It would be used as an alternate
'decorator' that works on the function text rather than the function
object. Example:
tre('''\
def dsum(n, a=0): return dsum(n-1, a+n) if n > 0 else a
'''
In pseudocode (minus error checks and raises) that would work for the
simple (and normal) case of exactly one tail_recursive call:
def tre(tail_rec_code):
split tail_rec_code into initial_part (header, docstring,
and initial comments and code before the alternation)
and recursive_alternation
if recursive_alternation is if-else expression,
convert to if-else statement
if tail-recursion is in else branch,
invert if condition and switch branch bodies
replace 'if' with 'while'
replace tail call with multiple assignment to parameters
(from signature)
modified_code = inital_part + modified_body
return exec(modified_code, globals())
In the replacement steps
if n > 1: return fac(n-1, acc*n)
would become
while n > 1: n, acc = n-1, acc*n
If the operations were done with strings, tre would work today and
indefinitely with any interpreter with standard string operations, exec
and globals (though in practice I would use re also). If operations
were done with ASTs, compile and the ast module (which is subject to
change) would be required.
>> by having a recur(*args,
**kwargs) function that removes its parent from the stack and then
runs the parent function again with the given arguments.
Ian here somewhat confusingly half switches from loop conversion, which
saves both space and time, to general tail call elimination, which saves
space possibly at the cost of more time and less useful or even useless
tracebacks. Which is to say, he switches from a tre-only implementation
to a general tco implementation but uses syntax limited to tre. As Jussi
notes, a general method should not be so limited.
If one only wants tre, for which traceback compression is often a plus
rather than a minus, then for automatic conversion, I think the time and
space efficient loop-conversion should be used.
If the recursion iterates through a collection, which is nearly always
the case, then a human might convert to a for loop instead of a while
loop. The idiomatic example below contains the input check usually left
out of toy recursion examples. (Doing the check just once would require
nesting the recursion within an outer function.)
def fact(n):
if n < 0 or not isinstance(n, int):
raise ValueError('non-negative integer required')
val = 1
for i in range(2, n+1):
val *= i
return val
For loops separate iterating through a collection, which in this case is
a range of integers, which has a known builtin solution, from processing
the items produced by the iteration. Recursion and the equivalent while
loops mix item processing with explicit next-item calculation, which is
generally collection-class specific. To write a generic function like
sum(iterable, start) with recursion, one must explicitly do everything
that for loop do, which is to call iter, next, and handle StopIteration.
Stack frames, and hence tre and tco, are implementation issues, not
language issues. Moreover, these are machine implementation issues, as
an intelligent human executing Python code should do 'the right thing'
anyway.
Guido himself has noted that it would be trivial for CPython to optimize
all tail calls. But he also noted the cost of sometimes useless
trackbacks and distraction from using iterables with for loops.
Optimizing specific tail calls is tricker. For one thing, calls to a
recursion-replacement function, such as recur, add a stack frame that
must also be popped. A CPython bytecode manimpuation solution was given
years ago as a recipe on the ActiveState Python Cookbook site. MacroPy
at pypi.python.org "provides a mechanism for user-defined functions
(macros) to perform transformations on the abstract syntax tree(AST) of
Python code at module import time". Among many included examples, it
has a tco decorator.
--
Terry Jan Reedy
--
https://mail.python.org/mailman/listinfo/python-list
