Python 3.10.0中Lambda实现λ演算NOT运算符的替换失效问题

你在Python 3.10.0里基于λ演算实现NOT逻辑运算符时，遇到了字面量替换后断言失败的问题，核心原因在于Python对lambda函数的相等性判断规则，和λ演算里的逻辑等价不是一回事。

正确实现的逻辑解析 #

正确代码中：

TRUE  = lambda a: lambda b: a
FALSE = lambda a: lambda b: b
NOT = lambda a: a(FALSE)(TRUE)
assert NOT(FALSE) == TRUE

执行NOT(FALSE)时，实际是调用FALSE(FALSE)(TRUE)。根据λ演算定义，FALSE的行为是返回传入的第二个参数，所以这里直接返回全局变量TRUE的引用——和断言右边的TRUE是同一个对象，因此==判断成立，断言通过。

替换字面量后的问题根源 #

修改后的代码：

NOT1 = lambda a: a(FALSE)(lambda a: lambda b: a)
assert NOT1(FALSE) == TRUE

执行NOT1(FALSE)时，同样是FALSE(FALSE)(lambda a: lambda b: a)，FALSE返回第二个参数，但这个参数是新创建的匿名lambda函数——它的逻辑和TRUE完全一致，但在Python中是一个全新的对象，内存地址和全局变量TRUE不同。

Python中==判断lambda对象时，只会检查两个对象是否指向同一个内存引用，不会判断它们的逻辑是否等价。所以新创建的lambda a: lambda b: a和全局的TRUE引用不同，==结果为False，导致断言失败。

核心结论 #

λ演算里的“等价”指的是β归约后的逻辑等价，但Python的==运算符对函数对象只做引用相等检查。你替换字面量后，相当于生成了一个逻辑相同但引用不同的新lambda，自然过不了断言。

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