Нумералы Чёрча

(defvar combinator-0 project-2nd-of-2)

(defvar combinator-IsZero (lambda (n)
                            (funcall (funcall n project-3rd-of-3) combinator-T)))

(defvar combinator-Suc (lambda (x)
                         (lambda (y)
                           (lambda (z)
                             (funcall y (funcall (funcall x y) z))))))

Две служебные функции позволят переводить целые естественного вида в комбинаторное представление и обратно.

(defun make-church-numeral (n)
  ;; Перевести неотрицательное целое число Лисп
  ;; в комбинатор
  (if (zerop n)
      combinator-0
      (funcall combinator-Suc (make-church-numeral (1- n)))))

(defun dechurchify (numeral)
  ;; Преобразовать комбинаторное представление
  ;; в число Лисп
  (funcall (funcall numeral #'1+) 0))

(defvar combinator-1 (make-church-numeral 1))

;(dechurchify (make-church-numeral 50))

;(funcall combinator-IsZero combinator-0)
;(funcall combinator-IsZero combinator-1)

(defun IsZero (numeral)
  (funcall (funcall (funcall combinator-IsZero numeral)
                    t) 
           nil))
;(IsZero combinator-0)
;(IsZero combinator-1)

(defvar combinator-* (lambda (m)
                       (lambda (n)
                         (lambda (f)
                           (funcall m (funcall n f))))))

;(dechurchify (funcall (funcall combinator-* (make-church-numeral 45)) 
;                      (make-church-numeral 3)))

(defvar fact 
  (lambda (n)
    (funcall (funcall (funcall combinator-if (funcall combinator-IsZero n))
                      (lambda () combinator-1))
             (lambda () 
               (funcall (funcall combinator-* n) 
                        (fact (funcall combinator-pred n)))))))

;(dechurchify-numeral (fact (make-church-numeral 5)))

Проверять комбинаторы на равенство нет возможности, ибо в Лисп нет понятия равенства функций - оно трактуется как совпадение указателей.