2.6 Church计数: 不使用数字的计算法

church.scm

(define zero (lambda (f) (lambda (x) x)))

(define one (lambda (f) (lambda (x) (f x))))

(define two (lambda (f) (lambda (x) (f (f x)))))

(define three (lambda (f) (lambda (x) (f (f (f x))))))

(define (add m n)
    (lambda (f) (lambda (x) ((m f) ((n f) x))))
)

(define three-2 (add one two))

; 111
((three my-func) 10)
; 111
((three-2 my-func) 10)
; 1111
(((add two two) my-func) 10)

; 关键点: 代换求值 (add-1 zero)
(define (add-1 n)
    (lambda (f) (lambda (x) (f ((n f) x))))
)

(define (my-func x) (display 1))
(define (my-func-2 x) 
    (display 2)
    x
)

; 10. 即: 不会调用 my-func.
((zero my-func) 10)

; 211
(((add-1 my-func-2) my-func) 10)

; 1
(((add-1 zero) my-func) 10)

; 1
((one my-func) 10)

; 11, 说明  my-func 被调用了 2 次.
((two my-func) 10)

NB. 初始以为, 记录大数时, 可能会栈溢出. 但是.. 并不会...

; 即使不考虑尾递归后话, 也不会有过多的 调用栈, 也不会导致栈溢出. 因为每次实际函数栈, 只有一个.
(define (my-func-2 x) (+ x 1))

> (define (my-func-2 x) (+ x 1))
> (trace my-func-2)
(my-func-2)
> ((three my-func-2) 10)
|(my-func-2 10)
|11
|(my-func-2 11)
|12
|(my-func-2 12)
|13
13
>