"""A continuation-passing version of factorial, using trampolined
style.

We show several different versions of the factorial function, and end
up with a recursive factorial function that doesn't grow stack
context.
"""



def factorial(n):
    """Regular factorial."""
    if n == 0:
        return 1
    return n * factorial(n-1)



######################################################################

def identity(x):
    """Identity function to map x to itself."""
    return x


def c_factorial(n, cont = identity):
    """Continuation passing factorial."""
    if n == 0: 
        return cont(1)
    else:
        def c(result):
            return cont(n * result)
        return c_factorial(n-1, c)


######################################################################

def pogo(bouncer):
    """Applies a trampoline on a function."""
    while callable(bouncer):
        bouncer = bouncer()
    return bouncer


def bounce(f, *args):
    """Wraps f and args in a callable."""
    return lambda: f(*args)


def bc_factorial(n, k = identity):
    """Bouncing, continuation-passing factorial."""
    if n == 0:
        return bounce(k, 1)
    else:
        def c(result):
            return bounce(k, n * result)
        return bounce(bc_factorial, n-1, c)
    

def abc_factorial(n):
    """A bouncing, continuation factorial function."""
    return pogo(bc_factorial(n))



if __name__ == '__main__':
    print abc_factorial(1000)