On 6/15/2012 1:03 PM, Tomasz Rola wrote:
Last time I checked, Python didn't have linked lists - arrayed lists are
nice, but their elements can't be automatically GC-ed (or, this requires
very nontrivial GC algorithm), the easiest way I can think would be
replacing them with None manually. I'm not sure if del is
performance-nice.
Python does not come with a linked-list class, but one can easily use
tuples or lists with two items as linked-list cells. One can optionally
wrap such cell in a linked-list class. However, if array lists do the
job, which they usually do, using linked-lists will take more time and
space. The problem being discussed may be a case where they are useful
and make it easier to save space.
Also, around the same time, Python couldn't do tail-call,
Nonsense. A tail call is a call temporally followed by a return. In
CPython bytecode, it would be a call followed by return. In Python code,
it is a call spatially preceded by 'return'. Any "return f(whatever)", a
common operation is a tail call.
I presume you actually mean that CPython does not automatically convert
tail calls into local assignments and a jump to reuse the existing
execution frame instead of a new one. True. A Python interpreter could
easily detect all tail calls at either compilation or execution, but
such conversions would erase call history, leaving gaps in exception
tracebacks and make debugging harder. Depending on your viewpoint, such
conversion might be considered a semantic change.
Selectively converting recursive tail calls has specific problems that
have been discussed on other threads, and it would *still* erase the
call history that one might need to debug. If you do branching
recursion, as with a tree, and there is an unexpected exception, you
most likely really do want to see the complete call path leading up to
the exception. In addition, it is a feature that non-terminating
recursions such as "def forever(): return forever()" get stopped.
In any case, a properly written linear tail-recursive function is,
usually, easily converted to an explicit while loop. So if you want
within-frame looping, write it explicitly. To illustrate one general
pattern:
def tail_rec(a, b=start): # use default arg to avoid nesting
if should_loop(a, b):
return tail_rec(A(a,b), B(a,b))
else:
return term(a, b)
def while_equiv(a, b=start):
while should_loop(a, b):
a, b = A(a,b), B(a,b)
else:
return term(a, b)
In practice, should_loop, A, and B will usually be in-line expressions
rather than calls. There may be additional statements after if, else,
and while headers. In while_equiv, move b=start into the body. Else is
typically omitted from the while version, but I prefer it in the
recursive version.
One downside of the space saving is that the history of a,b values is
invisible unless one add a debug print statement. Another is that the
forever function becomes
def forever():
while True: pass
and Python will never stop it without intervention.
Even more cool, with lazy evaluation (like in Haskell) one can generate
lists on a fly and process them like they were statically allocated.
Python iterators can do lazy evaluation. All the builtin classes come
with a corresponding iterator.
Yes, you could also run it in a loop or simulate lazy-eval manually (with
yield)
There is nothing simulated about yield. Python mostly does what you tell
it to do. You just have to learn how to tell it to do what you want.
--
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
