Tail recursion, the naughty way.

[Jon Riehl]

Did you ever have a day when you've sat down to do one thing, and
suddenly you're working diligently on something else? I just did.

It bothered me that the interpreter from yesterday didn't do tail
calls, especially considering that's what I think Tyler really wanted.
I thought about it some after really reading the paper linked in that
LtU post I cited yesterday (http://lambda-the-ultimate.org/node/2374).
What I came up with was doing a few things:

1. Adding a 'tapp' form that indicates a tail call (not to be confused
with application of a type constructor...). The idea would be that
the front-end is responsible for tail call detection and transforming
an 'app' with a 'tapp'. I think of this as naughty because it uses
explicit annotation and special control flow in the interpreter,
instead of exposing something more general (like the register stuff in
Friedman's paper).

2. When we go to push an evaluation context for a tail call, we pop
all evaluation contexts up to and including the entry of the last
lambda body. I've added two special evaluation contexts to signal
this to the trampoline, MyCallContext, and MyTailCallContext. I use
inheritance to keep the top level of the evaluator looking nice, so it
just treats these as other evaluation contexts (the magic is all done
in push_context() and pop_context()).

3. In support of this, I've added a "call stack" that tracks the
context stack depth at the entry of each function call.

The result is attached, and here is some sample output that first
shows the output of the original test program, and second, shows the
output of the same program, but with annotated tail calls:

$ ./interp_play.py
788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000
Computed in 5995 steps, with a max call depth of 200.

788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000
Computed in 5596 steps, with a max call depth of 1.

Note that I've added a counter for the number of times we enter the
trampoline loop, and something to determine the maximum call stack.
We can clearly see the benefits of the tail recursion optimization
(both in time, roughly measured in steps, and size, roughly measured
in call stack size). You can see the call and context stacks grow and
shrink using the "-d" flag.

There was mention in Friedman's paper about making the interpreter
tail recursive itself, but apparently, I'll have to buy (or borrow) a
book to figure that out. Though, the LtU response seems to indicate
the next step would be to absorb the material presented in Olivier
Danvy's dissertation (http://www.daimi.au.dk/~danvy/DSc/), which looks
right up our alley. Who knows, maybe he's already at metaprogramming
nirvana, waiting for us?

Tail-recursively yours,
-Jon()

[Tyler Green]

Very cool, I looked at your source, learned a lot, but I will go back
over it at the end of the week to extract all the ideas. One quick
thing you may have oversimplified was symbol lookup -- My interpreters
always search through a list of frames(dicts) for variables since I
never do the lexical addressing optimization -- so I'm not sure if
your version will handle free variables correctly.
ex: (define (foo x) (map (lambda (y) (+ x y)) '(1 2 3 ))

I didn't look too closely at it so I might be wrong.

-Tyler

> --
> You received this message because you are subscribed to the Google Groups "mython" group.
> To post to this group, send email to myt...@googlegroups.com.
> To unsubscribe from this group, send email to mython+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/mython?hl=en.
>
>

[Jon Riehl]

I wouldn't be surprised if there are some bugs in there since
dictionaries are mutable, but I was also careful to make copies at
what I think are the correct points. If I wasn't lazy, I'd just code
that up real quick and look at the trace generated by the "-d" flag.

Glad you're digging this. See you in Atlanta.

Thanks,
-Jon

[sean jensen-grey]

Here are the other two tail recursive implementations in python I was
talking about.

# vim: sts=4 sw=4 ts=4 et
# PyCon 2010 Sean Jensen-Grey
# frameh4.py

import sys
import pdb

__doc__ = """

Shows manipulating the execution stack itself during runtime to
implement tail recursion.

Tail recursion enables the creation of compact state machines among
other things.

http://en.wikipedia.org/wiki/Tail_recursion

This is take (verbatim) from

http://code.activestate.com/recipes/496691/

"""

import sys

def tail_recursion_with_stack_inspection(g):
'''
Version of tail_recursion decorator using stack-frame
inspection.
'''
loc_vars ={"in_loop":False,"cnt":0}

def result(*args, **kwd):
if not loc_vars["in_loop"]:
loc_vars["in_loop"] = True
while 1:
tc = g(*args,**kwd)
try:
qual, args, kwd = tc
if qual == 'continue':
continue
except TypeError:
loc_vars["in_loop"] = False
return tc
else:
f = sys._getframe()
if f.f_back and f.f_back.f_back and \
f.f_back.f_back.f_code == f.f_code:
return ('continue',args, kwd)
return g(*args,**kwd)
return result

class tail_recursive(object):
"""
by George Sakkis http://code.activestate.com/recipes/users/2591466/
"""
def __init__(self, func):
self.func = func
self.firstcall = True
self.CONTINUE = object()

def __call__(self, *args, **kwd):
if self.firstcall:
func = self.func
CONTINUE = self.CONTINUE
self.firstcall = False
try:
while True:
result = func(*args, **kwd)
pass
if result is CONTINUE: # update arguments
args, kwd = self.argskwd
else: # last call
return result
finally:
self.firstcall = True
else: # return the arguments of the tail call
self.argskwd = args, kwd
return self.CONTINUE

def stack_death_factorial( n, acc=1):
if n == 0:
return acc
res = stack_death_factorial(n-1, n*acc)
return res

@tail_recursion_with_stack_inspection
def stack_inspection_factorial( n, acc=1):
if n == 0:
return acc
res = stack_inspection_factorial(n-1, n*acc)
return res

@tail_recursive
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
res = factorial(n-1, n*acc)
return res

factorial( 10)