Recur->Iter

.gitignore

.*.swp
*.pyc

README.md

Rewrite recursion into iteration

There are mainly two ways to do this:

• Use an explicit stack to store local variables and return addresses.
• Do a CPS against your function and then do a trampolining transformation.

In both ways, constructing a control flow graph from your function would be very useful to aid thinking...

fibo.py

def fibo(n):
    if n < 2:
        return n
    return fibo(n - 1) + fibo(n - 2)

# Step 1: mark retaddr

def fibo_entry(n):
    if n < 2:
        return n
    a = fibo(n - 1)
    # ret1
    b = fibo(n - 2)
    # ret2
    return a + b

print(fibo(10))

fibo2.py

# Step 2: eliminate local variables using stack

def fibo_entry(n, stack):
    if n < 2:
        return n
    stack.append(n)
    # [n]
    a = fibo_entry(n - 1, stack)
    return fibo_ret1(a, stack)

def fibo_ret1(a, stack):
    # [n]
    n = stack[-1]
    stack.append(a)
    # [n, a] <- Top
    # ret1
    b = fibo_entry(n - 2, stack)
    return fibo_ret2(b, stack)

def fibo_ret2(b, stack):
    # [n, a]
    a = stack.pop()
    n = stack.pop()
    # ret2
    return a + b

print(fibo_entry(10, []))

fibo3.py

# Step 3: eliminate recursive calls by pushing retaddrs to the stack

def fibo_entry(n, stack):
    if n < 2:
        # [retaddr] <- 
        return n
    stack.append(n)
    stack.append(fibo_ret1)
    a = fibo_entry(n - 1, stack)
    # return fibo_ret1(a, stack)

def fibo_ret1(a, stack):
    # [n]
    n = stack[-1]
    stack.append(a)
    stack.append(fibo_ret2)
    # [n, a, fibo_ret2] <- Top
    b = fibo_entry(n - 2, stack)
    # return fibo_ret2(b, stack)

def fibo_ret2(b, stack):
    # [n, a]
    a = stack.pop()
    n = stack.pop()
    # ret2
    return a + b

print(fibo_entry(10, []))

fibo_k.py

# Rewrite function calls using continuation

def fibo(n, k):
    if n < 2:
        k(n)
        return

    # def fibo1_ret(a):
    #     def fibo2_ret(b):
    #         k(a + b)
    #     fibo(n - 2, fibo2_ret)
    # fibo(n - 1, fibo1_ret)

    fibo(n - 1, lambda a:
            fibo(n - 2, lambda b:
                k(a + b)))

    # a = fibo(n - 1)
    # b = fibo(n - 2)
    # return a + b

fibo(10, print)

fibo_kiter.py

# Rewrite calls (f(args...)) into returns (f, args...), and repeatedly
# call the results in an outer loop

def fibo(n, k):
    if n < 2:
        return (k, (n,))

    def fibo1_ret(a):
        def fibo2_ret(b):
            return (k, (a + b,))
        return (fibo, (n - 2, fibo2_ret))
    return (fibo, (n - 1, fibo1_ret))

f, args = fibo(10, print)
while True:
    result = f(*args)
    if result is None:
        break
    else:
        f, args = result

tree.py

class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


t0 = Tree(1, Tree(2), Tree(3, Tree(4)))

# Step 0

def print_tree(t):
    if not t:
        return

    print(t.value)
    print_tree(t.left)
    print_tree(t.right)
    return

# Step 1: split by return addresses

def print_tree_entry(t):
    if not t:
        return

    print(t.value)
    print_tree_entry(t.left)
    print_tree_ret1(t)

def print_tree_ret1(t):
    # ret1
    print_tree_entry(t.right)
    print_tree_ret2()

def print_tree_ret2():
    # ret2
    pass

# print_tree_entry(t0)

tree2.py

from tree import t0

# Step 2: add a stack to save local variables

def print_tree_entry(t, stack):
    if not t:
        return

    print(t.value)
    stack.append(t)
    print_tree_entry(t.left, stack)
    print_tree_ret1(stack)
    return

def print_tree_ret1(stack):
    # ret1
    t = stack[-1]
    print_tree_entry(t.right, stack)
    print_tree_ret2(stack)

def print_tree_ret2(stack):
    # ret2
    stack.pop()
    pass

print_tree_entry(t0, [])

tree3.py

from tree import t0

# Step 3: kill recursion: for each of the consecutive two calls f() and g(),
# push g to the stack, and then do f.
# At each return site, try pop a return address from the stack and jump to it.

def print_tree_entry(t, stack):
    if not t:
        if not stack:
            return
        # [t, ret_addr] <- Top
        ret_addr = stack.pop()
        # [t] <- Top
        ret_addr(stack)
        return

    print(t.value)
    stack.append(t)

    stack.append(print_tree_ret1)
    # [t, ret_addr] <- Top
    print_tree_entry(t.left, stack)
    # print_tree_ret1(stack)

def print_tree_ret1(stack):
    # [t] <- Top
    # ret1
    t = stack[-1]

    stack.append(print_tree_ret2)
    print_tree_entry(t.right, stack)
    # print_tree_ret2(stack)

def print_tree_ret2(stack):
    # [t] <- Top
    # ret2
    stack.pop()

    if not stack:
        return
    # [t, ret_addr] <- Top
    ret_addr = stack.pop()
    # [t] <- Top
    ret_addr(stack)

print_tree_entry(t0, [])