SICP по-русски

Мы уже сводили пары к процедурам и пары к числам в двух предыдущих упражнениях. Сейчас нам предстоит задача для истинных интеллектуальных гурманов: мы будем представлять числа как процедуры.

Имея определения zero и add-1 из условия упражнения

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

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x))))) ,

вычислим one как подстановку (add-1 zero):

(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)))

В этом вычислении активно используется редукция lambda-выражений. Таким образом получили следующее определение для one:

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

Аналогичным образом вычислим two как подстановку (add-1 one):

(add-1 one)
(add-1 (lambda (f) (lambda (x) (f x))))
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) (f x))) f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) (f x)) x))))
(lambda (f) (lambda (x) (f (f x))))

В результате получили определение для two:

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

Обобщая полученный результат, можно сказать, что натуральное число n представляется как процедура, принимающая как аргумент функцию одной переменной и применяющая эту функцию повторно к самой себе n раз. В случае с one (которой соответствует n=1) функция f применяется единожды. В случае с two (которой соответствует n=2) функция f применяется дважды и получаем (f (f x)). Случай с zero (n=0) вырожден и функция f вообще не применяется, то есть можно сказать, что в этом случае функция f применяется ноль раз.

Таким образом выражение ((n f) x) вычисляет f⁽ⁿ⁾(x). Под f⁽ⁿ⁾(x) я подразумеваю сокращенную запись для f(f(…f(x)…)), где f вызывается n раз.

Переходя к вычислению суммы двух “чисел” (на деле это не числа, а объекты, которые ведут себя как числа относительно элементарных арифметических операций) сформулируем, как же должен представляться результат сложения m и n. По введенному раньше определению, это будет процедура, принимающая как аргумент функцию одной переменной и применяющая эту функцию повторно к самой себе m+n раз.

Итак, ((n f) x) вычисляет f⁽ⁿ⁾(x). Аналогично выражение ((m f) t) вычисляет f^(m)(t).

Тогда, обозначив f⁽ⁿ⁾(x) через t, получаем, что ((m f) ((n f) x)) вычисляет f^(m)(f⁽ⁿ⁾(t)) = f^(m+n)(t), то есть как раз тот результ, который нам нужен для суммы. Оформляя полученное в виде процедуры суммирования, получим следующее:

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

Красивый и компактный ответ. Мне это упражнение показалось весьма интересным.