# Defunctionalize the Continuation
http://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html

## 什麼是 Defunctionalization?
Turning functions into not-functions, into data structures。其實到處都是 Defunctionalization 的蹤跡

## 案例一：filtering

# filter(bool_func, iterable)
def is_odd(n: int) -> bool:
    return n % 2 == 1
def is_even(n: int) -> bool:
    return n % 2 == 0
def less_than_three(n: int) -> bool:
    return n < 3
    
arr = [1, 2, 3]
list(filter(is_odd, arr))    # [1, 3]
list(filter(is_even, arr))   # [2]

but，網站過濾器無法傳遞 function

so，we defunctionalize it：

class FilterSpec(Enum):
    IS_ODD = 1
    IS_EVEN = 2
    LESS_THAN_TRHEE = 3    # <-- limited
    
def apply(f: FilterSpec, arr):
    if f == FilterSpec.IS_ODD:
        return filter(is_odd, arr)
    elif f == FilterSpec.IS_EVEN:
        return filter(is_even, arr)
    elif f == FilterSpec.LESS_THAN_TRHEE:
        return filter(less_than_three, arr)

如果想要再彈性一點：

class FilterSpec:
    name = ''
    args = []

# more flexible
def less_than(upper_bound, n):
    return n < upper_bound
    
# more, more flexible
def and_(spec1, spec2, arr):
    return apply(spec1, arr) and apply(spec2, arr)
    
def apply(f: FilterSpec, arr):
    if f.name == 'is_odd':
        return filter(is_odd, arr)
    elif f.name == 'is_even':
        return filter(is_even, arr)
    elif f.name == 'less_than':
        upper_bound = f.args[0]
        return filter(
            partial(less_than, upper_bound), arr)
    elif f.name == 'and':
        spec1, spec2 = f.args
        return filter(
            partial(and_, spec1, spec2), arr)
    else:
        raise

Defunctionalized-Form
把 function 轉為資料結構
缺點：封閉，因為必須預先知道總共要支援哪些可能
優點：serializable

vs

Refunctionalized-Form
把資料結構還原回 function 邏輯
優點：開放，支援任何 function
缺點：無法序列化

## 案例二：Web Actions (HackerNews)
進入 [HackerNews](https://news.ycombinator.com/) 網站
--> 未登入狀態留言
--> 跳轉要求登入
--> 自動 post 完成

DevConsole 看端倪

## 案例三：將 recursive function 轉為 iterative

假設我們要 inorder traversal to print a binary tree

from dataclasses import dataclass

@dataclass
class Tree:
    value: int = None
    left: 'Tree' = None
    right: 'Tree' = None
    
def get_sample_tree():
    """
             4
            / \
           2   5
          / \
         1   3
    """
    root = Tree(
        4,
        left=Tree(
            2,
            left=Tree(1),
            right=Tree(3)),
        right=Tree(5)
    )
    return root

# inorder traversal
def recr_print(tree):
    if tree:
        recr_print(tree.left)
        print(tree.value)
        recr_print(tree.right)
        
def iter_print(tree):
    # how?

from typing import Callable

# step1: Continuation-Passing style
def recr_print_step1(tree, cont: Callable = None):
    if tree:
        recr_print_step1(tree.left, lambda: (
            print(tree.value),
            recr_print_step1(tree.right, cont)
        ))
    elif cont:
        cont()

# step2: Defunctionalize the Continuation

@dataclass
class Cont:
    tree: Tree = None
    next: 'Cont' = None
    
def run(cont):
    print(cont.tree.value)
    recr_print_step2(cont.tree.right, cont.next)
    
def recr_print_step2(tree, cont: Cont = None):
    if tree:
        recr_print_step2(tree.left, Cont(tree, cont))
    elif cont:
        run(cont)

# step3: inlining
def recr_print_step3_1(tree, cont: Cont = None):
    if tree:
        recr_print_step3_1(tree.left, Cont(tree, cont))
    elif cont:
        print(cont.tree.value)
        recr_print_step3_1(cont.tree.right, cont.next)

# step4: tail-call elimination
def iter_print(tree, cont: Cont = None):
    while True:
        if tree:
            cont = Cont(tree, cont)
            tree = tree.left
        elif cont:
            print(cont.tree.value)
            tree = cont.tree.right
            cont = cont.next
        else:
            return

# in the end, a lot like the normal iter-version
def iter_print_stack(tree):
    stack = []
    while True:
        if tree:
            stack.append((tree.value, tree.right))
            tree = tree.left
        elif stack:
            value, tree = stack.pop()
            print(value)
        else:
            return

## 其他案例：
Linux SIGIO