如何在 Racket 中应用 lambda 演算规则？

Question

我正在尝试测试我使用 Racket 编写的一些 lambda 演算函数，但在测试用例方面运气不佳。例如给定一个定义

; successor function
(define my_succ (λ (one)
                 (λ (two)
                   (λ (three)
                     (two ((one two) three))))))

我正在尝试将其应用于 1 2 3，希望 2 的后继者成为 3

(((my_succ 1) 2) 3)

逻辑是因为 my_succ 是一个接受一个 arg 并将其传递给另一个接受一个 arg 的函数的函数，该函数将它传递给接受一个 arg 的第三个函数。但是我得到

application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 1
  arguments.:

我尝试了谷歌搜索，发现了很多规则的代码，但没有应用这些规则的例子。我应该如何调用上面的后继函数来测试它？

Answer 1

您正在混合两种完全不同的东西：Racket 中的 lambda 术语和函数。

在 Racket 中你可以有匿名函数，可以用 λ 符号来写（比如 (λ(x) (+ x 1)) 那 returns 一个整数的后继，所以 ((λ(x) (+ x 1)) 1) returns 2),
在 Pure Lambda Calculus 中，您只有 lambda 项，它们以类似的表示法编写，并且可以解释为函数。

在第二个域中，您没有像 0, 1, 2, ... 这样的自然数，但是您有只有个 lambda 项，并且这样表示数字。例如，如果您使用所谓的 Church numerals，则表示（在技术术语 encode 中）数字 0 与 lambda 项 λf.λx.x , 1 与 λf.λx.f x, 2 与 λf.λx.f (f x) 等等。

因此，函数 successor（对于用此编码表示的数字）对应于一个术语，在 Racket 表示法中，它是您编写的函数，但您不能将其应用于数字，例如 0, 1, 等等，但仅限于其他 lambda 表达式，也就是说你可以这样写：

(define zero (λ(f) (λ (x) x)))   ; this correspond to λf.λx.x

(successor zero)

Racket中的结果是一个过程（它会被打印为：#<procedure>），但是如果你尝试测试你的结果是否正确，将它与1的功能编码进行比较，你会发现一些奇怪的事情。事实上：

(equal? (successor zero) (λ(f) (λ(x) (f x))))

产生 #f，因为如果你比较 Racket 中的两个过程，你总是得到假（例如 (equal? (λ(x)x) (λ(x)x)) 产生 #f），除非你比较“相同”（在某种意义上“相同的存储单元”）值（(equal? zero zero) 给出 #t）。这是因为，为了正确比较两个函数，您应该比较无限组对（输入、输出）！

另一种可能性是将 lambda 项表示为 Racket 中的某种结构，因此您可以表示教会数字以及 "normal" lambda 项，并定义函数 apply（或更好reduce) 执行 lambda 归约。

Answer 2

您正在尝试应用柯里化。

(define my_succ
  (lambda(x)(
     lambda(y)(
       lambda(z)(
              (f x y z)))))

(define (add x y z)
  (+  x y z))

((( (my_succ add)1)2)3)

在 DR 球拍中的实现：

如何在 Racket 中应用 lambda 演算规则？

How to apply lambda calculus rules in Racket?

lambda-calculus

racket