重写教堂数字功能

Question

在SICP中，正数的教会数定义如下：

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
    (lambda (f) (lambda (x) (f (n f) x))))

以下是我'best attempt'为了自己的理解重写的，这里将显式参数传递给一个函数：

(define (church f x n)
  (cond
    ((= n 0) x)                       ; zero case: return x
    (else (f (church f x (- n 1)))))) ; otherwise f(f(f...(x))) n times

(church square 3 2)
81

然后重新定义 zero 我会：

(define (zero2 f)
  (lambda (x) (church f x 0)))

和add-one为：

(define (add-1 n f)
  (lambda (x) (church f x (+ n 1))))

或者，如果我们必须推迟 f 参数，那么添加一个 wrapper-lambda：

(define (add-1 n)
  (lambda (f) (lambda (x) (church f x (+ n 1)))))

我的理解正确吗？如果是这样，为什么 add-1 或 zero 过程顶部的语法如此复杂（注意：我猜它并没有那么复杂，我只是不完全理解它是什么正在做）。任何帮助将不胜感激！

Answer 1

您的版本预设了 cond、0、1、= 和 - 等原语的存在。所有这一切的目的是表明您可以从 lambda 开始实现这些原语。

Answer 2

lambda演算是Scheme的子集，不允许多于一个参数和lambda。使用 lambda 的组合，您可以构建任何结构：

(define false (lambda (true) (lambda (false) false)))
(define true (lambda (true) (lambda (false) true)))
(define if (lambda (pred) (lambda (consequence) (lambda (alternative) ((pred consequence) alternative)))))

您可能想知道为什么我允许 define，因为它不是 lambda。那么你不需要它。这只是为了方便，因为您可以尝试一下：

(((if true) 
  'result-true) 
 'result-false) 
; ==> result-true

而不是使用完全相等的版本：

((lambda (pred) 
  (lambda (consequence) 
     (lambda (alternative) 
       ((pred consequence) alternative)))) 
 (lambda (true) (lambda (false) true))
  'result-true 
     'result-false)

您的函数 church 不是 lambda 演算，因为它 return 不是教堂编号，而且它需要多个参数，这是一种违规行为。我已经看到了生成卡盘号的方案函数，但是任何卡盘号你都应该能够这样做以获得整数值：

((church-number add1) 0)

例如。零：

(((lambda (f) (lambda (x) x)) add1) 0) ; ==> 0

Answer 3

SICP defines the Church numerals for positive numbers as follows:
 (define zero (lambda (f) (lambda (x) x)))
 (define (add-1 n)
     (lambda (f) (lambda (x) (f (n f) x))))

不，不是。正确的定义是

(define zero  (lambda (f)  (lambda (x)  x)))
(define (add-1 n)
              (lambda (f)  (lambda (x)  (f  ((n f) x)))))

f是“后继步骤”，x是“零值”。

(f ((n f) x)) 意味着，用 f 和 x 做 ，无论 n 用 f 做什么和 x，然后再做一次 f 结果。

换句话说，用“后继步骤”函数变换“零值”比[=20=多次 ] 将对其进行改造。

现在，

> ((zero add1) 0)
0
> (((add-1 zero) add1) 0)
1
> (((add-1 (add-1 zero)) add1) 0)
2

等或者，

> (define plus1 (lambda (x) (cons '() x)))

> ((zero plus1) '(NIL))
'(NIL)
> (((add-1 zero) plus1) '(NIL))
'(() NIL)
> (((add-1 (add-1 zero)) plus1) '(NIL))
'(() () NIL)

希望您也能了解如何将丘奇数定义为二元函数：

(define zero  (lambda (f x)  x))
(define (add-1 n)
              (lambda (f x)  (f  (n f x))))

(define plus1 (lambda (x) (cons '() x)))

(zero add1 0)                    ;=> 0
((add-1 zero) add1 0)            ;=> 1
((add-1 (add-1 zero)) add1 0)    ;=> 2

(zero plus1 '(NIL))                    ;=> '(NIL)
((add-1 zero) plus1 '(NIL))            ;=> '(() NIL)
((add-1 (add-1 zero)) plus1 '(NIL))    ;=> '(() () NIL)

产生与以前相同的结果。

重写教堂数字功能

Re-writing church numerals function

scheme

lisp

lambda-calculus

sicp