Tech Ideas

C++,Linux,Algorithm,Crypto,Lisp,etc

Church计数

my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
;Church计数

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))
(define (show-num n)((n (lambda (x) (+ 1 x))) 0))
(define (add a b) (lambda (f) (lambda (x) ((a f) ((b f) x)))))
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

(show-num zero)
(show-num one)
(show-num two)
(newline)
(show-num (add-1 zero))
(show-num (add-1 (add-1 zero)))
(show-num (add-1 (add-1 (add-1 zero))))
(show-num (add-1 (add-1 (add-1 (add-1 zero)))))

(newline)
(display "my add\n")
(show-num (add zero zero))
(show-num (add (add-1 zero) (add-1 zero)))
(show-num (add (add-1 zero) (add-1 (add-1 zero))))

(define (multi a b)
  (lambda (f)
    (lambda (x)
      ((a (b f) ) x))))

(define (expon a b)
  (lambda (f)
    (lambda (x)
      (((a b) f)  x))))

(show-num (multi two two))
(show-num (multi (add one two) two))

(show-num (expon two two))
(show-num (expon (expon two two) two))

 

Church计数,通过(lambda (f))把f作为参数,这样f就不会被求值,而f的执行次数就代表了数字。

lambda中的形参其值是未知的,所以不会被求值。

形参好比糖果的包装纸,要把一段代码包起来,把它放到一个匿名函数里就行了

比如有一个函数

(lambda (a b) (+ a b))

要把它包装起来,可以写成

(lambda (x) (lambda (a b) (+ a b)) )

要剥开糖纸,传个参数就行了。

Church计数就是这个思想。

show-num用来把Church计数方式的数字转换成普通数字。