lisp - Lambda 微积分和 CLISP 中的实现

Question

我对函数式编程、lisp 和 lambda 演算非常陌生。我正在尝试使用 Common Lisp Lambda Calc 样式实现 AND 运算符。

来自维基百科:

AND := λp.λq.p q p

到目前为止，这是我的代码:

(defvar TRUE #'(lambda(x)#'(lambda(y)x)))
(defvar FALSE #'(lambda(x)#'(lambda(y)y)))

(defun OPAND (p q)
    #'(lambda(f) 
        #'(lambda(p) #'(lambda(q) (funcall p (funcall q(funcall p))))))
)

我找到了这 2 个转换函数:

(defun church2int(numchurch)
    (funcall (funcall numchurch #'(lambda (x) (+ x 1))) 0)
)

(defun int2church(n)
    (cond
        ((= n 0) #'(lambda(f) #'(lambda(x)x)))
        (t #'(lambda(f) #'(lambda(x) (funcall f
            (funcall(funcall(int2church (- n 1))f)x))))))

)

如果我这样做:

(church2int FALSE)

我有 0。如果我这样做:

(church2int TRUE)

我有

#<FUNCTION :LAMBDA (X) (+ X 1)>

我觉得还行。但是如果我这样做:

 (church2int (OPAND FALSE FALSE))

我有:

#<FUNCTION :LAMBDA (Q) (FUNCALL P (FUNCALL Q (FUNCALL P)))>

我应该有 0 的地方。我的代码有问题吗？还是我遗漏了什么？

谢谢

Answer 1

如果您想将 opand 定义为具有 2 个参数的函数，就像您尝试的那样，您需要这样做:

(defun OPAND (p q)
    (funcall (funcall p q) p) )

然后:

(opand false false)
#<FUNCTION :LAMBDA (X) #'(LAMBDA (Y) Y)> ;; which is FALSE

(opand true true)
#<FUNCTION :LAMBDA (X) #'(LAMBDA (Y) X)> ;; which is TRUE

这是我的实现，基于原始论文 http://www.utdallas.edu/~gupta/courses/apl/lambda.pdf , and 运算符 λxy.xyF

(defvar OPAND 
    #'(lambda(x) 
        #'(lambda(y) 
            (funcall (funcall x y) FALSE) ) ) )

如果你这样做

(funcall (funcall opand false) false)
#<FUNCTION :LAMBDA (X) #'(LAMBDA (Y) Y)> ;; which is FALSE

(funcall (funcall opand true) true)
#<FUNCTION :LAMBDA (X) #'(LAMBDA (Y) X)> ;; which is TRUE