Stackless Python 1.0 + Continuations 0.6

[Darrell]

"""
Great job Christian.
It sure can speed up deep recursive functions.

I'd like to see what others have figured out about how to use
Stackless.

What are the chances this will make it into python 1.6 ?

The following is excerpts from the Stackless distribution.
With some comments and mods to help me understand.
Let me know if I'm way off or if this should have been an attachment.
"""
import continuation, time

get_caller  = continuation.caller

def nS2(n):
    """
    Not limited by stack depth.
    """
        # Causes a GP if no parms passed.
        # If given a 1 cont would point up on in the call stack/chain ?
    cont=get_caller(0)
        # I feel an ignorant statement coming on.
        # Using "cont" instead of "call" is an optimization.
        # cont assumes that when called it doesn't have to
        # return to it's caller. So a deep recursion doesn't have
        # to keep a stack to return to each level. The final return
        # at some depth, is the final returned value.
    call=cont.call
        # Each call to cont arrives at this point.
        # And k is assigned to the current value of n with update(n)
        # If you had used n it would always be the original value.
    k=cont.update(n)
    if k:
        # This won't return so "print msg" is never called
        # if "call(k-1" had been used it would have printed the msg.
        cont(k-1)
        msg="""
        This isn't printed when cont is used. Using cont
        doesn't experience stack depth limits.

        This is printed when call is used.
        Using call runs slower and has the same limits
        as a normal recursive function.
        """
        print msg
    else:
        del cont.link
    return k

def s1(n):
    """
    Limited by stack depth
    """
    if n:
        n=s1(n-1)
    return n


def timer(n,func):
    t1=time.time()
    for x in range(1000):
        func(n)
    print time.time()-t1

if 0:
    """
    Stackless is much faster for the right recursive function
    """
    timer(100,nS2)
    timer(100,s1)


# ======================================================================
#         coroutine
# ======================================================================
"""
This was hard to understand.
"""

class coroutine:

    current = None
    caller_of_this = continuation.caller

    def __init__ (self, f, *a, **kw):
        self.state = lambda v,f=f,a=a,kw=kw: apply (f, a, kw)
        self.caller = None

    def resume (self, value=None):
        caller = coroutine.current
        caller.state = self.caller_of_this()
        self.caller=caller.state
        self.caller = caller
        coroutine.current = self
            # If you tracing this call will runaway.
        self.state (value)

    def kill (self):
        self.__dict__.clear()


def resume_caller (value):
    me = coroutine.current
    me.caller.resume (value)

def resume_main (value):
    _main.resume (value)

_main = coroutine (None)
coroutine.current = _main

if __name__ == '__main__':
    # counter/generator

    def counter (start=0, step=1):
        n = start
        while 1:
            print 'A:',n
            resume_caller (n)
            n = n + step
            print 'B:', n


    """
    It's surprising that cc.resume() returns a value.
    Guess it's related to the lambda in the __init__ ??
    Need an experiment.
    Prints:
    A: 0
    0
    B: 1
    A: 1
    1
    B: 2
    A: 2
    2

    The second resume takes us back to the "print 'B:'"
    Then back to the "print A:"
    It's as though the counter functions are in separate threads.
    And resume or resume_caller is a blocking message pass.
    """
    cc = coroutine(counter)
    print cc.resume()
    print cc.resume()
    print cc.resume()


        # same-fringe
    def _tree_walker (t):
        if type(t) is type([]):
            for x in t:
                _tree_walker (x)
        else:
            """
            Passes control back to same_fringe
            tree_walker and _tree_walker are in the same pseudo thread.
            """
            resume_caller (t)

    def tree_walker (t):
        _tree_walker (t)
        print 'Returns None causing the caller to exit'
        resume_caller (None)
        print 'Never prints'

    def same_fringe (t1, t2):
        co1 = coroutine (tree_walker, t1)
        co2 = coroutine (tree_walker, t2)
        while 1:
            leaf1 = co1.resume()
            leaf2 = co2.resume()
            """
            tree_walker searches finds a result and calls resume_caller(t)
            which passes back the result. It's printed then cox.resume()
            continues the search. tree_walker is waiting to continue the
            search.
            """
            print 'leaf1: %s leaf2: %s' % (leaf1, leaf2)
            if leaf1 == leaf2:
                if leaf1 is None:
                    return 1
            else:
                return 0

    print same_fringe (
    [0,1,[2,3],[4,[5,[6]],7,[[[[8]]]],9]],
    [[[0,1],2,[3,[4],[5]],[[6],[7]],8],9]
    )