如何在 lambda 演算中编码

Question

我正在 Haskell 学习 lambda 演算，在此期间，我遇到了这个问题。

这些问题的答案是：

但我无法理解他们是如何得出答案的。就像 eq，我不明白他们是怎么得出这个结论的：λab.a b (b (λxy.y) (λxy.x)) 和nand一样。如果有人解释一下并帮助我理解这个问题，那就太好了。

谢谢。

Answer 1

让我们先用实际数据类型编写有问题的函数（但没有模式匹配：只有if/then/else）：

data Bool = False | True -- recall this definition
not  a   = if a then False else True
eq   a b = if a then (if b then True  else False)
                else (if b then False else True )
nand a b = if a then (if b then False else True )
                else (if b then True  else True )

如果您购买这些定义——非常简单，只是列出函数的真值表——那么我们就可以开始进行一些推理了。首先，我们可以稍微简化一下 eq 和 nand 函数的外部分支：

eq   a b = if a then b else not b
nand a b = if a then not b else True

现在我们基本上完成了。我们只是将每个 False 和 True 替换为它们的 if/then/else 行为，并替换每个 if/then /else 函数应用：

type Bool a = a -> a -> a
false a b = a -- `if False then a else b` becomes `false a b`
true  a b = b -- `if True  then a else b` becomes `true  a b`

not  a   = a false true   -- from `if a then False else True`
eq   a b = a b (not b)    -- from `if a then b else not b`
nand a b = a (not b) true -- from `if a then not b else True`

这些是您的解决方案中给出的定义，尽管公认的是 Haskell 语法而不是 lambda 演算语法。

Answer 2

我使用 Haskell 约定将 λ 写成 \。

从评论来看，您似乎在这部分遇到了问题：

eq = \a b. a b (b (\x y. y) (\x y. x))

所以我只关注这个。

我们对布尔值的编码是作为带有两个参数的函数。 True return 是第一个参数，False return 是第二个参数。第一段直接给出编码：

True = \x y. x
False = \x y. y

直到最后我们都将使用名称而不是 lambda 表达式。

我们知道 eq 应该有两个参数，即要比较的两个布尔值。（布尔值的编码本身有两个参数，但这是不同的——无论布尔值如何编码，eq 都应该有两个参数）所以我们知道它应该看起来像：

eq = \a b. _________________

在这一点上，我们几乎唯一能做的就是检查其中一个参数，以确定它是 True 还是 False。 eq 是对称的，所以我们问的是哪一个并不重要；让我们无缘无故地选择 a。根据编码，我们询问的方式是将两个参数传递给我们想要了解的事物。

eq = \a b. a ____ ____

我们还没有弄清楚 "holes" 中的内容。第一个洞是 return 如果 a 结果是 True，第二个洞是 return 如果结果是 False.

为了弄清楚如何填补这些漏洞，让我们写下我们试图定义的真相 table：

a     |   b   |  eq a b
------+-------+---------
True  | True  |  True
True  | False |  False
False | True  |  False
False | False |  True

请注意，在 a 为 True 的两行中，a == b 列与 b 列完全相同。所以当 a 是 True 时，我们只是 return b。所以我们可以填补其中一个漏洞：

eq = \a b. a b ____

现在注意 table 当 a 是 False 时，a == b 与 b 列相反，所以在这种情况下我们应该反转 b 和 return 它。

要反转 b，当 b 为 True 时，我们希望它为 False，反之亦然。在编码中，即：

b False True

这就是我们应该 return 当 a 是 False 时，所以我们填补另一个洞：

eq = \a b. a b (b False True)

现在我们只展开 False 和 True

的定义

eq = \a b. a b (b (\x y. y) (\x y. x))

给你了。

如何在 lambda 演算中编码

How to encode in lambda calculus

lambda

haskell

lambda-calculus

semantics