Church计数的简单实现

上午看到别人的一个实现，一时来了兴趣，就自己也实现了一个。

第一部分对curry-2的定义表明，任何多参数的函数都可以实现为单参数的。这样，在后面可以定义多參函数，更清晰些。

附带额外的boolean值和条件分支的定义，很容易看出来图灵完全性。

PS：其实，在上一篇的“一个简单的元循环解释器”博文给出了图灵完全的最小定义，只是看起来不明显。本文对church计数、boolean以及分支判断的实现，完全可以在那个解释器中实现，而无需扩展解释器，也说明了它确实是图灵完全的。

#lang racket

;; macro for easy testing
;; (test 'utname target-expr expectation)
(define-syntax test
  (syntax-rules (===)
    ((_ name expr === expect)
     (let ((val-expr expr) (val-expect expect))
       (if (equal? val-expr val-expect)
           (printf "Test ~a\tDone\n" name)
           (eprintf "Test ~a\tFailed: expecting ~a, got ~a\n"
                    val-expect
                    val-expr))))))

;; multi-argument functions
;; curry it into a set of single argument functions
(define (curry-2 f)
  (lambda (x)
    (lambda (y)
      (f x y))))

(test 'curry-add
      (((curry-2 +) 1) 2) === (+ 1 2))
(test 'curry-sub
      (((curry-2 -) 2) 1) === (- 2 1))

;; void value
;; for functions without arguments,
;; we use a single argument function with void as its argument.
(define void (lambda (x) x))

(define (no-arg f)
  (lambda (arg)
    (f)))

(test 'no-arg-current-error-port
      ((no-arg current-error-port) void) === (current-error-port))
(test 'no-arg-pi
      ((no-arg (lambda () pi)) void) === ((lambda () pi)))

;; use non-termination to signal error
(define (error . args)
  ((lambda (x) (x x)) (lambda (x) (x x))))

;; boolean encoded into a choosing lambda
;; bwt: yes multiple arguments function, remember the curry-2 trick?
(define true (lambda (on-true on-false) (on-true)))
(define false (lambda (on-true on-false) (on-false)))

;; if expression
(define iff (lambda (condition on-true on-false)
              (condition on-true on-false)))

(test 'boolean-if-true
      (iff true
          (lambda () 42)
          (lambda () 43))
      ===
      42)
(test 'boolean-if-false
      (iff false
           (lambda () 42)
           (lambda () 43))
      ===
      43)

;; church numbers
;; every number is a two argument lambda,
;; n applies the first argument n times on the second.
(define zero (lambda (f x) x))

;; define +1 operation
(define (add1 n)
  (lambda (f x)
    (f (n f x))))

(define one (add1 zero))
(define two (add1 one))

;; define add num num
(define (addd n1 n2)
  (lambda (f x)
    (n2 f (n1 f x))))

;; testing Church number
(define (inc x) (+ x 1)) ;; this is our f for counting applications
(test 'number-zero
      (zero inc 0) === 0)
(test 'number-one
      (one inc 0) === 1)
(test 'number-two
      (two inc 0) === 2)
(test 'number-add
     ((addd two (add1 two)) inc 0) === 5)

;; from the number with add-operation and conditional branch, we can define any thing.