Possibly Pythonic Tail Call Optimization (TCO/TRE)

Terry Reedy 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
> languages),

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 mailing list