先贴上 CS61A Homework 3 Recursion, Tree Recursion 中的最后一道思考题题面：
Q6: Anonymous Factorial
This question demonstrates that it's possible to write recursive functions without assigning them a name in the global frame.
The recursive factorial function can be written as a single expression by using a conditional expression.
>>> fact = lambda k: 1 if k == 1 else mul(k, fact(k - 1))
>>> fact(5)
120
However, this implementation relies on the fact (no pun intended) that fact has a name, to which we refer in the body of fact. To write a recursive function, we have always given it a name using a def or assignment statement so that we can refer to the function within its own body. In this question, your job is to define fact recursively without giving it a name!
Write an expression that computes n factorial using only call expressions, conditional expressions, and lambda expressions (no assignment or def statements).
Note: You are not allowed to use
make_anonymous_factorialin your return expression.
The sub and mul functions from the operator module are the only built-in functions required to solve this problem.
def make_anonymous_factorial():
"""Return the value of an expression that computes factorial.
>>> make_anonymous_factorial()(5)
120
>>> from construct_check import check
>>> # ban any assignments or recursion
>>> check(HW_SOURCE_FILE, 'make_anonymous_factorial',
... ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'FunctionDef', 'Recursion'])
True
"""
return 'YOUR_EXPRESSION_HERE'
答案代码
def make_anonymous_factorial():
return (lambda f: lambda k: f(f, k))(lambda f, k: k if k == 1 else mul(k, f(f, k - 1)))
思路
注意：对本文 python 代码的验证，别忘了 from operator import mul
我们以
fact = lambda k: 1 if k == 1 else mul(k, fact(k - 1))
作为基础进行修改
题目要求不能使用赋值和 def 定义，这意味着不能在全局框架中增加新的函数绑定，然而，必须使用递归实现，这意味着必须在函数中调用自身——如果要进行函数调用，则必须使用函数的名称，这是不可避免的。
通过上述分析，可以知道，为了在递归调用时能够指称函数，我们不得不使用由 lambda 函数绑定的形式参数，因此，一个基本的框架是：
lambda f: ...
这样一来，就能通过名称 f 来递归调用了！
让我们把这个框架与原先的基础代码（随意地，漫无目的地）结合起来：
lambda f: lambda k: 1 if k == 1 else mul(k, f(k - 1))
现在，这个表达式起到的作用是接受一个函数 f ，转换成这样一个函数：如果参数是 \(1\) ，则输出 \(1\)，否则输出 \(k * f (k - 1)\)
然而，这和目标有着很大的差距！如果要直接使用这个匿名高阶函数，无论将它应用于什么函数 h，都是不可行的：假设可行，由于 h 以一个整数 n 作为唯一参数， 且返回一个整数，我们会发现这个匿名高阶函数并未将其转化为一个递归过程，而是最多将 h(3) 转换为 h(2) 就停止了
我们考虑一个关于信息的小问题：可以观察到，我们辛辛苦苦用 lambda 函数绑定的名称 f， 在“递归”一次后就丢失了，那么显然不能继续递归了
如何不让这一信息丢失？当然是把这一信息作为参数代代相传！
因此，我们把 f 修改为一个双参数函数，多出来的一个参数是 f 本身，对代码略作修改（有两处地方需要同时修改）：
lambda f, k: 1 if k == 1 else mul(k, f(f, k - 1))
几乎快完成了！能够惊喜地发现，在解决信息传递问题的同时，顺带着也实现了递归！设想我们计算 \(f (f, 5)\)，结果是 \(5 * f (f, 4)\)，也就是 \(5 * 4 * f (f, 3)\) ... 这就成功了。
唯一的问题是：这个过程没办法开始，如果要这样开始第一次计算，就需要传入参数 f, n，而 f 此时还没有定义。
考虑希望达到的效果：输入 n， 输出 n 的阶乘。我们必须把输入缩减到一个变量，这既是为了避免计算过程无法开始的困难，也是业务本身的要求，因此，我们通过一个高阶函数来构造一个计算的入口：
(lambda f: lambda k: f(f, k))
将这个入口应用于核心函数：
(lambda f: lambda k: f(f, k))(lambda f, k: 1 if k == 1 else mul(k, f(f, k - 1)))
这就完成了整道题目！
继续前进（写于 2025.9.15）
python 的 lambda 表达式和 Untyped lambda calculus 的一个不同点是：python 支持多参数的 lambda 函数，然而，正如上文那样，使用多参数的 lambda 函数会导致不能科里化，妨碍化简为更简单的形式。
因此，将上面的答案改为使用单参数函数的版本：
(lambda f: lambda k: f(f)(k))(lambda f: lambda k: 1 if k == 1 else mul(k, f(f)(k - 1)))
现在可以用科里化进行化简：
(lambda f: f(f))(lambda f: lambda k: 1 if k == 1 else mul(k, f(f)(k - 1)))
回忆一下，我们是从 “把这个框架与原先的基础代码（随意地，漫无目的地）结合起来” 开始的：
g = lambda f: lambda k: 1 if k == 1 else mul(k, f(k - 1))
接下来，我们进行的只不过是一个机械的，可重复的过程：让 f 接受自己为参数。刚刚，我们手动进行了变更，得到了答案，那么能不能自动化呢？把转换过程视为一个应用过程，我们只需要下面这个将高阶函数 fix 应用于 g：
fix = lambda g: (lambda f: f(f)) (lambda f: g(f(f)))
如果进行一步 \(\beta\) 规约，那么可以得到 Y 组合子的常见形式：
fix = lambda g: (lambda f: g(f(f)))(lambda f: g(f(f)))
那么我们期望 fix(g)(4) 的结果是 \(24\)
但是，实际上爆栈了，怎么会事呢？
是因为 python 的求值策略是 call-by-value！在进行 \(\beta\) 规约前，必须先把右半部分规约到值（value）
等等，什么是值？需要补充一下 lambda-calculus 的基础知识：
在这里，abstraction 就是值，而 variable 和 application 不是
下面这段代码这是可求值到底的：
(lambda f: f(f))(lambda f: lambda k: 1 if k == 1 else mul(k, f(f)(k - 1)))(4)
求值过程：
G = (lambda f: lambda k: 1 if k == 1 else mul(k, f(f)(k - 1)))(lambda f: f(f))(G)(4)
= G(G)(4)
= (lambda k: 1 if k == 1 else mul(k, G(G)(k - 1)))(4)
= 1 if 4 == 1 else mul(4, G(G)(4 - 1)))
= mul(4, G(G)(3)))
= ...
= 4 * (3 * (2 * G(G)(1)))
= 4 * (3 * (2 * 1))
= 24
但下面的就不行了：
g = lambda f: lambda k: 1 if k == 1 else mul(k, f(k - 1))
H = (lambda f: g(f(f)))
fix = lambda g: H(H)fix(g)(4)
展开：
fix(g)(4)
= H(H)(4)
按照设计 fix 时的思考，H 就是 G，所以应该这样继续：
= G(G)(4)
= ...
= 24
但这需要先将 H，也就是 lambda f: g(f(f)) 规约到 G，这在 call-by-value 求值策略是不可行的，甚至在更宽松的 call-by-name 就不行，因为它试图在 abstraction 内部规约。
实际上会这样继续：
fix(g)(4)
= H(H)(4)
= (lambda f: g(f(f))) (lambda f: g(f(f)))(4)
= g((lambda f: g(f(f)))(lambda f: g(f(f))))(4)
= g(g((lambda f: g(f(f)))(lambda f: g(f(f)))))(4)
= g(g(g((lambda f: g(f(f)))(lambda f: g(f(f))))))(4)
= ...
这就是失败的原因！
最后，来看一看它在 call-by-name 求值策略中的表现：此时不能在 abstraction 内部规约，但是能在右边部分不是值时规约：
fix(g)(4)
= H(H)(4)
= g(H(H))(4)
= (lambda f: lambda k: 1 if k == 1 else mul(k, f(k - 1)))(H(H)(H(H)))(4)
= (lambda k: 1 if k == 1 else mul(k, (H(H)(H(H)))(k - 1)))(4)
= 1 if 4 == 1 else mul(4, (H(H)(H(H)))(4 - 1))
= mul(4, (H(H)(H(H)))(3))
= ...
= 24
Magic! 这个故事告诉我们，退一步海阔天空！
终点站
我们还能拯救美好的幻想吗？能否定义一个更好的 fix 来规避求值顺序问题？
问题的本质在于，项 f(f) 是 application，不是值，call-by-value 会试图规约这个部分来试图让它化简成值。只需要把它包装为 abstraction 即可！
为了保持含义不变，具体方法是将 f(f) 替换为 lambda x: f(f)(x)，这个技巧叫 \(\eta\) - 展开（eta-expansion）
g = lambda f: lambda k: 1 if k == 1 else mul(k, f(k - 1))
M = (lambda f: g(lambda x: f(f)(x)))
fix2 = lambda g: M(M)fix2(g)(4)
= M(M)(4)
= g(lambda x: M(M)(x))(4)
= (lambda f: lambda k: 1 if k == 1 else mul(k, f(k - 1)))(lambda x: M(M)(x))(4)
= (lambda k: 1 if k == 1 else mul(k, (lambda x: M(M)(x))(k - 1)))(4)
= mul(4, (lambda x: M(M)(x))(3))
= 4 * M(M)(3)
= ...
= 4 * (3 * (2 * M(M)(1)))
= 24
成功了！最后，fix2 就是 Z 组合子！
来看看 TAPL 中的 Z 组合子定义：
把函数的形式变量命名为 \(x\)，令人费解啊！
)
)
)
)
)
)
)
