Possibly Pythonic Tail Call Optimization (TCO/TRE)
tjreedy at udel.edu
Wed Jul 15 03:36:13 CEST 2015
> I think I'm beginning to understand. Tail call elimination is
> necessary to cope with a system of programming that has deliberately
> excluded certain other options (eg mutables, in pure functional
Tail recursion is the functional way to write a while loop. To put is
another way, a while loop is within stackframe recursion. Ditto for for
loops, which are specialized while loops.
Recursion, first (or car), rest (or cdr), and linked lists
(non-mutational stacks with the top at the front) work together as a
tightly coordinated system. (rest ll) is equivalent to ll[1:] except
that rest does not mutate anything. When Python's ll.pop(0) (or ll.pop()
removes and returns (first ll), it does mutate ll. Since ll becomes
what was previously (rest ll), there is no need for a separate list.rest
Python's next(it) is also does the job of both first + rest. As with
pop(0), it removes the first item of it, mutates it so it represents the
rest of the items in the collection it represents, and then returns the
initial item. Again, there is no need for a separate rest(it) funciton.
The fundamental computational idea in both systems, beneath the
differing syntax and religious wars, is that we can process a collection
by processing one item at a time.
Terry Jan Reedy
More information about the Python-list