TrampolineとCPSとPython

TrampolineとCPSについて調べたことの一応のメモ．
理論的な側面はともかくやりかたはなんとなく分かってきた気がする．

http://en.wikipedia.org/wiki/Continuation-passing_style
を参考にして書いてみた．

CPS

Direct style

import operator as op
def pyth(x, y):
    return pow(op.add(op.mul(x, x), op.mul(y, y)), 0.5)

pyth(3, 4) # => 5.0

Continuation passing style

def pyth_cps(x, y, k):
    def mul_cps(x, y, k):
        return k(x * y)
    def add_cps(x, y, k):
        return k(x + y)
    def pow_cps(x, y, k):
        return k(pow(x, y))
    return mul_cps(x, x, lambda x2: mul_cps(y, y, lambda y2: add_cps(x2, y2, lambda x2py2: pow_cps(x2py2, 0.5, k))))

pyth_cps(3, 4, lambda x: x) # => 5.0

もうちょっとPythonらしく（したつもり）．
継続渡し版演算子関数を展開してしまっている．
美しい...か？

def pyth_cps2(x, y, k):
    def k0(x2):
        def k1(y2):
            def k2(x2py2):
                return k(x2py2 ** 0.5)
            return k2(x2 + y2)
        return k1(y * y)
    return k0(x * x)

pyth_cps2(3, 4, lambda x: x) # => 5.0

Trampoline

これでいいのか？

def pyth_trampoline(x, y, k):
    def k0(x2):
        def k1(y2):
            def k2(x2py2):
                return lambda: k(x2py2 ** 0.5)
            return lambda: k2(x2 + y2)
        return lambda: k1(y * y)
    return lambda: k0(x * x)

pyth_trampoline(3, 4, lambda x: x)()()()() # => 5.0

次は再帰関数でやる．

def fact(n):
    if n:
        return n * fact(n - 1)
    else:
        return 1

def fact_cps(n, k):
    mul_cps = lambda x, y, k: k(x * y)
    sub_cps = lambda x, y ,k: k(x - y)
    def k0(b):
        if b:
            def k1(m):
                def k2(l):
                    return mul_cps(n * l, k)
                return fact_cps(m, k2)
            return sub_cps(n, 1, k1)
        else:
            return k(1)
    return k0(n)

def fact_trampoline(n, k):
    mul_trampoline = lambda x, y, k: lambda: k(x * y)
    sub_trampoline = lambda x, y ,k: lambda: k(x - y)
    def k0(b):
        if b:
            def k1(m):
                def k2(l):
                    return mul_trampoline(n, l, k)
                return fact_trampoline(m, k2)
            return sub_trampoline(n, 1, k1)
        else:
            return lambda: k(1)
    return lambda: k0(n)

def bounce(t):
    i = 1
    while callable(t):
        print 'loop:', i
        i += 1
        t = t()
    return t

>>> t = fact_trampoline(5, lambda x: x)
>>> bounce(t)
loop: 1
loop: 2
loop: 3
loop: 4
loop: 5
loop: 6
loop: 7
loop: 8
loop: 9
loop: 10
loop: 11
loop: 12
loop: 13
loop: 14
loop: 15
loop: 16
loop: 17
120