我正在尝试"取消延续功能";一些递归函数的技巧，看看我能否得到一个好的迭代版本。遵循你从未听说过的最佳重构(在Lua中)，只是为了方便;这似乎主要是语言不可知论)，我这样做:
-- 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)
-- 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)
-- 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))
-- 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，但我不能这样做，因为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))
好了，现在我们似乎又回到了正轨。
-- 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))
好了，我们得到了factorial的一个完整的迭代实现，但它是一个相当糟糕的实现。我希望以这样的方式结束:
function factorial(n)
local x = 1
while n ~= 0 do
x = n * x
n = n - 1
end
return x
end
print(factorial(6))
是否对我所遵循的步骤进行了任何修改，以使我机械地最终得到一个看起来更像这个的函数?
首先，祝贺您正确地遵循了所有步骤。我看过很多人尝试去功能化练习，但我很少看到这种情况。
CPS、去功能化和尾部调用消除的三步过程并不是一个独立的配方，它不能在所有上下文中产生干净的代码而不进行修改。您在需要TCE apply函数本身时看到了这一点。(顺便说一下，如果您想在打印树时使用括号，这也是必要的，这使得该版本比我在博客文章中使用的示例要复杂得多。)
在这种情况下，需要一个额外的步骤来获得您想要的干净的阶乘函数。你写的函数计算5!作为5*(4*(3*(2*1)))，所以最后的延续是function(x) return 5*(4*(3*(2*x))) end。这涉及4次乘法，更一般地说，这种形式的延拓涉及无限次乘法。如果没有第二个循环，这是无法处理的....
…除非您注意到延续等同于function(x) return 120*x end。关键的性质是乘法的结合律。实际上，比较一下:假设我们定义了一个阶乘类似的非结合运算符，比如取幂而不是乘法。调用powerorial，这样powerorial(5)=5^(4^(3^(2^1)))。这样就不可能简化循环。
这里，您需要证明apply(kont, x)等于acc*x，其中acc等于kont中包含的部分阶乘。例如:对于去功能化的连续kont={n=3, next={n=4, next={n=5, next=nil}}}，证明apply(kont, x)等价于60*x。这是一个使用结合律的简单归纳证明。
各种形式的结合律是获得具有累加器的干净迭代函数的关键步骤，这一见解适用于许多问题，以至于Jeremy Gibbons写了一篇关于这个主题的论文，名为《连续传递风格、去功能化、累加和结合律》——以阶乘作为他的第一个例子!
这是程序的机械操作这一更大领域的一部分，这一主题在我们的高级软件设计课程中得到了更深入的实践。如果你想要更深入的了解，那么你也可以开始阅读关于程序操作和方程推理的论文，包括Jeremy Gibbons, Richard Bird, Zohar Manna和Bill Scherlis的作品。