基于Lambda演算的延续式阶乘：为何该定义属于延续实例？

首先得明确：延续传递风格（CPS）的核心是，函数不直接返回结果，而是把结果传递给一个专门的“延续”参数——这个参数代表了当前计算完成后要执行的后续逻辑。咱们就从这个角度拆解你给出的阶乘定义：

$$FACT_{cps} = Y \hspace{0.2cm} λf. λn, k.\hspace{0.2cm} \text{if} \hspace{0.2cm} n = 0 \hspace{0.2cm} \text{then} \hspace{0.2cm} k\ 1 \hspace{0.2cm} \text{else} \hspace{0.2cm} f\ (n − 1)\ (λv. k (n ∗ v))$$

这里的Y是不动点组合子，用来实现递归，咱们重点看后面的λ函数：它接受两个参数，n是要求阶乘的数，k就是延续——也就是拿到阶乘结果后要做的事情。

一步步看具体例子 #

• 当n=0时：直接执行k 1。这里没有返回1，而是把1传给了延续k，让k去处理这个结果（比如打印、或者继续参与其他计算）。这完全符合CPS的逻辑：结果交给延续，而非直接返回。
• 当n=1时：进入else分支，调用f(0)，同时传递了一个新的延续λv. k(1*v)。当f(0)执行完，会把1传给这个新延续，也就是计算1*1，再把结果传给原来的k。整个过程中，每一步的计算结果都没有直接返回，而是通过延续传递下去。
• 当n=2时：同样进入else分支，调用f(1)，延续是λv. k(2*v)。然后f(1)又会调用f(0)，同时传递延续λv'. (λv. k(2*v))(1*v')。当f(0)把1传给这个内层延续，会先计算1*1=1，再把这个值传给外层的λv. k(2*v)，最终计算2*1=2，再传给最初的k。

核心原因总结 #

这个阶乘定义完全符合延续传递风格的本质：

1. 函数的最终结果不是直接返回，而是传递给延续参数k；
2. 递归调用时，把“后续要做的乘法计算”打包成一个新的延续（比如λv. k(n*v)），传递给下一层递归，让下一层的计算结果能顺着延续链传递下去，完成整个阶乘的计算。

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