# -*- Mode: Python -*-

# see http://dark.nightmare.com/rushing/factcps/ for this in C

# original
def fact (n):
    if n == 0:
        return 1
    else:
        return n * fact (n - 1)

# CPS conversion, assuming functions for ==, *, -
def minus_cps (a, b, k):
    return k (a - b)

def mul_cps (a, b, k):
    return k (a * b)

def eq_cps (a, b, k):
    return k (a == b)

def fact_cps (n, k):
    def k0 (b):
        def k1 (nm1):
            def k2 (f):
                return mul_cps (n, f, k)
            return fact_cps (nm1, k2)
        if b:
            return k (1)
        else:
            return minus_cps (n, 1, k1)
    return eq_cps (n, 0, k0)
        
def ident (x):
    return x

print fact_cps (5, ident)
print fact_cps (10, ident)

# CPS conversion of just the function call (i.e., assuming cps-safe primitives)

def fact_cps_1 (n, k):
    def k0 (f):
        return k (n * f)
    if n == 0:
        return k (1)
    else:
        return fact_cps_1 (n-1, k0)

print fact_cps_1 (5, ident)
print fact_cps_1 (10, ident)

# accumulator version (would be efficient if python had tail recursion optimization)

def facta (n, a):
    if n == 1:
        return a
    else:
        return facta (n-1, n*a)

# CPS of facta

def fact_cps_2 (n, a, k):
    if n == 1:
        return k (a)
    else:
        return fact_cps_2 (n-1, n*a, k)

print fact_cps_2 (5, 1, ident)
print fact_cps_2 (10, 1, ident)