Functional Programming and python

[Terry Reedy]

On 9/30/2013 5:02 PM, Tim Chase wrote:
> On 2013-09-30 19:04, Franck Ditter wrote:
>> two points make me crazy :
>> 1. Tail recursion is not optimized. We are in 2013, why ? This is
>> known technology (since 1960). And don't answer with "good
>> programmers don't use recursion",
>
> I seem to recall hearing that the primary reason it hadn't been
> implemented is because of Python's super-dynamism (to make up a
> word).

Right. A tail call is a call immediately followed by a return (in the 
byte code or equivalent). A recursive tail call is a tail call to the 
function containing the tail call. In Python, the function to be called 
in a call is not determined until the call is made. This is because the 
function expression is evaluated to a function object at runtime, not 
when the function is compiled.

It would be trivial to detect and somewhat optimize all tail calls in 
CPython. But the result would be to delete traceback info with *all* 
tail calls, not just for recursive tail calls.

Some functions have multiple recursive calls, as with divide and conquer 
algorithms and graph traversal. The last recursive call might or might 
not be a tail call. When it is, having calls omitted from the traceback 
might be undesireable. It might be disconcerting, for instance, if the 
number of calls in the traceback for a balanced binary tree algorithm 
did *not* match the level where the error took place.

> That a function could be a tail recursion in one call, but
> the calling the same name could then become rebound.  I'm making up
> the example, but I think it was something like this:
>
>    def kablooie(*args):
>      if not args:
>        def kablooie(*args):
>          woah()
>      do_something(args)
>      kablooie(args[1:])
>
> where tail recursion optimization would do weird things.

-- 
Terry Jan Reedy