关于延续式Haskell阶乘代码的追踪逻辑是否正确？

背景与代码 #

我正在学习延续性（continuations）的概念，认为追踪延续式的经典阶乘代码是理解该概念的有效方法，现确认自己的理解是否正确。

Haskell代码如下：

fact :: Integer -> (Integer -> Integer) -> Integer
fact 0 k = k 1
fact n k = fact (n-1) (\v -> k (n*v))

-- 调用示例: fact 5 id
-- 结果: 120

我的代码追踪过程 #

我认为能完成追踪是理解延续性的基础，以下是我的追踪步骤：

fact 5 id --> 
fact 4 (\v -> id (5*v)) --> 
fact 3 (\v -> (\v -> id (5*v)) (4*v)) --> 
fact 2 (\v -> (\v -> (\v -> id (5*v)) (4*v)) (3*v)) --> 
fact 1 (\v -> (\v -> (\v -> (\v -> id (5*v)) (4*v)) (3*v)) (2*v)) --> 
fact 0 (\v -> (\v -> (\v -> (\v -> (\v -> id (5*v)) (4*v)) (3*v)) (2*v)) (1*v)) --> 
(\v -> (\v -> (\v -> (\v -> (\v -> id (5*v)) (4*v)) (3*v)) (2*v)) (1*v)) 1

疑问 #

1. 这样的追踪是否符合预期？我对延续性的基础理解是否有误？
2. 我知道这些v有些混淆，但我假设内层的v会遮蔽外层的v，这个理解是否正确？

解答 #

• 你的追踪完全符合预期，对延续性的基础理解也没问题
  这个延续传递风格（CPS）的阶乘，核心就是把每一步要执行的乘法逻辑"打包"成延续函数，递归时只传递这个"待完成的操作"，直到触发n=0的基准情况时，把初始值1传入最内层的延续，随后逐层展开执行所有打包的乘法操作，最终得到结果120。你的追踪准确还原了这个流程，说明你已经抓住了延续性的核心——延续就是当前计算完成后，后续需要执行的剩余逻辑。

• 内层v遮蔽外层v的理解是正确的
  Haskell采用词法作用域，每个\v -> ...中的v都是当前匿名函数的局部绑定变量，内层的v会覆盖外层同名变量的作用域，因此每个v只在自己的函数范围内有效，不会和外层的v混淆。不过为了追踪时更清晰，建议给不同层级的参数起不同的名字（比如v1、v2、v3），这样能更直观地对应每一层递归的结果：

  fact 5 id --> 
  fact 4 (\v1 -> id (5*v1)) --> 
  fact 3 (\v2 -> (\v1 -> id (5*v1)) (4*v2)) --> 
  fact 2 (\v3 -> (\v2 -> (\v1 -> id (5*v1)) (4*v2)) (3*v3)) --> 
  ...
  

内容的提问来源于stack exchange，提问作者kesarling