续延去泛化转换阶乘为迭代效果差，如何优化转换步骤？

我正在尝试对递归函数使用“defunctionalize the continuation（去函数化延续）”技术，以将其转换为优质的迭代版本，实现如下：

二叉树中序遍历转换示例 #

原始递归实现 #

-- original
function printTree(tree)
    if tree then
        printTree(tree.left)
        print(tree.content)
        printTree(tree.right)
    end
end
tree = { left = { content = 1 }, content = 2, right = { content = 3 } }
printTree(tree)

CPS尾递归改造 #

-- make tail-recursive with CPS
function printTree(tree, kont)
    if tree then
        printTree(tree.left, function()
            print(tree.content)
            printTree(tree.right, kont)
        end)
    else
        kont()
    end
end
tree = { left = { content = 1 }, content = 2, right = { content = 3 } }
printTree(tree, function() end)

延续去函数化 #

-- defunctionalize the continuation
function apply(kont)
    if kont then
        print(kont.tree.content)
        printTree(kont.tree.right, kont.next)
    end
end
function printTree(tree, kont)
    if tree then
        printTree(tree.left, { tree = tree, next = kont })
    else
        apply(kont)
    end
end
tree = { left = { content = 1 }, content = 2, right = { content = 3 } }
printTree(tree)

内联apply #

-- inline apply
function printTree(tree, kont)
    if tree then
        printTree(tree.left, { tree = tree, next = kont })
    elseif kont then
        print(kont.tree.content)
        printTree(kont.tree.right, kont.next)
    end
end
tree = { left = { content = 1 }, content = 2, right = { content = 3 } }
printTree(tree)

尾调用消除得到迭代版本 #

-- perform tail-call elimination
function printTree(tree, kont)
    while true do
        if tree then
            kont = { tree = tree, next = kont }
            tree = tree.left
        elseif kont then
            print(kont.tree.content)
            tree = kont.tree.right
            kont = kont.next
        else
            return
        end
    end
end
tree = { left = { content = 1 }, content = 2, right = { content = 3 } }
printTree(tree)

阶乘函数转换尝试 #

原始递归实现 #

-- original
function factorial(n)
    if n == 0 then
        return 1
    else
        return n * factorial(n - 1)
    end
end
print(factorial(6))

CPS尾递归改造 #

-- make tail-recursive with CPS
function factorial(n, kont)
    if n == 0 then
        return kont(1)
    else
        return factorial(n - 1, function(x)
            return kont(n * x)
        end)
    end
end
print(factorial(6, function(x) return x end))

延续去函数化 #

-- defunctionalize the continuation
function apply(kont, x)
    if kont then
        return apply(kont.next, kont.n * x)
    else
        return x
    end
end
function factorial(n, kont)
    if n == 0 then
        return apply(kont, 1)
    else
        return factorial(n - 1, { n = n, next = kont })
    end
end
print(factorial(6))

apply尾调用消除 #

-- perform tail-call elimination
function apply(kont, x)
    while kont do
        x = kont.n * x
        kont = kont.next
    end
    return x
end
function factorial(n, kont)
    if n == 0 then
        return apply(kont, 1)
    else
        return factorial(n - 1, { n = n, next = kont })
    end
end
print(factorial(6))

内联apply #

-- inline apply
function factorial(n, kont)
    if n == 0 then
        local x = 1
        while kont do
            x = kont.n * x
            kont = kont.next
        end
        return x
    else
        return factorial(n - 1, { n = n, next = kont })
    end
end
print(factorial(6))

尾调用消除得到双循环迭代实现 #

-- perform tail-call elimination
function factorial(n, kont)
    while n ~= 0 do
        kont = { n = n, next = kont }
        n = n - 1
    end
    local x = 1
    while kont do
        x = kont.n * x
        kont = kont.next
    end
    return x
end
print(factorial(6))

问题 #

最终得到的阶乘迭代实现使用了额外的栈结构和两次循环，效率不佳，期望得到如下更精简的实现：

function factorial(n)
    local x = 1
    while n ~= 0 do
        x = n * x
        n = n - 1
    end
    return x
end
print(factorial(6))

需要对现有转换步骤做哪些修改，才能通过机械化方式得到更接近预期的实现？

你已有的转换流程是标准正确的，只需要在尾调用消除得到双循环实现后，增加一步栈语义识别与化简的机械化优化步骤即可：

1. 首先识别当前实现的语义：第一个循环仅将n从大到小依次压入kont栈，第二个循环从栈顶到栈底依次弹出元素，与初始值1做乘法运算
2. 验证运算性质：乘法满足交换律和结合律，1 * n * (n-1) * ... * 1的运算结果和1 * 1 * 2 * ... * n完全一致，不需要严格遵循先压栈后弹出的执行顺序
3. 匹配化简规则：当同时满足以下两个条件时，可以直接省略栈存储，合并两次循环：
   • 第一次循环仅生成固定序列的元素存入栈，无其他逻辑
   • 第二次循环仅弹出栈中元素做满足结合律的二元运算，无其他逻辑
4. 执行化简：将压栈操作替换为直接运算，删除栈相关逻辑，得到最终的单循环实现。

内容的提问来源于stack exchange，提问作者Joseph Sible-Reinstate Monica