Exercise2-5 <---> Exercise2-7
Exercise 2.6.
In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
;; A better version of +church-numerals
;; which handles arbitrary arguments by using
;; the dotted-tail notation.
;; by Lenatis(lenatis@gmail.com)
(define (+church-numerals . args)
(define (+ m n)
(lambda (f)
(lambda (x)
((m f) ((n f) x)))))
(define (iter sum rest)
(if (null? rest)
sum
(iter (+ sum (car rest)) (cdr rest))))
(iter (lambda (f)
(lambda (x) x)) args))
This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the 
-calculus.
Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).
Ru: Если представление пар как процедур было для Вас еще недостаточно сумасшедшим, то заметьте, что в языке, который способен манипулировать процедурами, мы можем обойтись и без чисел (по крайней мере, пока речь идет о неотрицательных числах), определив 0 и операцию прибавления 1 так:
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
Такое представление известно как числа Чёрча (Church numerals), по имени его изобретателя, Алонсо Чёрча, того самого логика, который придумал -исчисление. Определите one (единицу) и two (двойку) напрямую (не через zero и add-1). (Подсказка: вычислите (add-1 zero) с помощью подстановки.) Дайте прямое определение процедуры сложения + (не в терминах повторяющегося применения add-1).
Scheme solution:
At first, let's illustrate evaluation of one as (add-1 zero) using substitution model:
one
= (add-1 zero)
= (add-1 (lambda (f) (lambda (x) x)))
= (lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
= (lambda (f) (lambda (x) (f ((lambda (x) x) x))))
= (lambda (f) (lambda (x) (f x)))
So, we've got that Church one is high-order procedure which applies its arguments procedure one time. In a similar manner, Church two will apply its function two times, etc. And our initial zero is applying function zero times, so it's no applying at all, thus zero f is simply identity function.
Our definitions of one and two:
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
Let's introduce helper inc function, which increments its argument:
(define (inc n) (+ n 1))
Then we can test one and two procedures by turning Church numerals into numbers using such method:
> ((one inc) 0)
1
> ((two inc) 0)
2
> ((zero inc) 0)
0
Sum of two Church numerals m and n is applying function (m + n) times. Using as an example definition of add-1 procedure, we can define add-m function in much the same way:
(define (add-church-numerals m n)
(lambda (f) (lambda (x) ((m f) ((n f) x)))))
Here we apply (m f) instead of f, and this causes adding m instead of 1 as in add-1 procedure.
Let's test our addition function:
> (((add-church-numerals one two) inc) 0)
3
> (((add-church-numerals two two) inc) 0)
4
> (((add-church-numerals two one) inc) 0)
3
Exercise2-5 <---> Exercise2-7