如何在 DrRacket 中检查纯（无类型）lambda 演算中的空列表？

Question

我正在尝试在纯 lambda 演算中构建列表（实际上是伪装成列表的二叉树（以 [Root, [Left SubTree], [Right SubTree]] 的形式），但是为了这个特定问题的目的，我们可以讨论一般列表在 lambda 演算中）。

我将在这个问题中使用 lambda 演算的一些基本定义（用 Racket 语法表示）：

(define true (lambda (x) (lambda (y) x)))
(define false (lambda (x) (lambda (y) y)))
(define if (lambda (x) (lambda (y) (lambda (z) ((x y) z)))))

; I'm using Parigot Encodings to represent numbers
(define zero (lambda (s) (lambda (z) z)))
(define one (lambda (s) (lambda (z) ((s zero) z))))
(define two (lambda (s) (lambda (z) ((s one) ((s zero) z)))))

; Here are some converter functions for debugging/printing
(define (p->int n)
   ((n (lambda(x) add1)) 0))

(define (int->p i)
   (if (zero? i)
       (lambda (f) (lambda (x) x))
       (let ((m (int->p (- i 1))))
         (lambda (f) (lambda (x) ((m f) ((f m) x)))) )))

; Building blocks for Lists. A list consists of a single element Head,
; followed by the rest of the list (Tail). Lists are thus recursively
; defined. An empty list consists of only the element 'nil'
(define mkpair (lambda (a) (lambda (b) (lambda (c) ((c a) b)))))   
(define Head (lambda (p) (p true)))
(define Tail (lambda (p) (p false)))
(define nil false)

为了对此类列表进行操作，我需要检测列表何时为空（例如，在对表示为列表的二叉搜索树进行二分搜索时检测叶节点）。以下 link 将该函数作为 isempty = λl.l(λab.false)true，我在 Racket 中定义如下：

(define Null? (lambda (p) (p (lambda (x) (lambda (y) false)))true))

这似乎有效，如下所示：

(p->int (((if (Null? (Head ((mkpair nil) one)))) two) one))

换句话说，上面的应用程序检查列表的头部 [nil, one] 是否为空列表（仅包含 nil），如果是，则求值为 two，这当馈送到转换器函数 p->int 时，会产生 2。一切都很好，除了 Null? 函数似乎没有评估为 false，如下面的代码片段所示：

(p->int (((if (Null? (Tail ((mkpair nil) one)))) two) one))

在 Racket 中也计算为 2。

谁能指出我的错误，我希望这是我无法检测到的语法错误！

PS：以防万一我完全以错误的方式接近这个问题，我正在尝试在 Racket 中用纯 lambda 演算实现二叉搜索树。任何指向我最终目标的指示都将不胜感激 - 我已经列出了我采用的一种方法。

（有关我尝试模拟的函数的更多阅读，请参阅 this）。

Answer 1

问题实际上是isempty函数的错误转置。你应该写：

(define Null? (lambda (p) ((p (lambda (x) (lambda (y) false))) true)))

而不是：

(define Null? (lambda (p) (p (lambda (x) (lambda (y) false))) true))

因为 λl.l(λab.false)true 应解释为：

λl. ((l (λab.false)) true)

虽然你的解释在 lambda 演算中没有对应关系。

如何在 DrRacket 中检查纯（无类型）lambda 演算中的空列表？

How to check for empty list in pure (untyped) lambda calculus in DrRacket?

functional-programming

list

lambda-calculus

racket