SICP по-русски

Интересное упражнение. Да и вообще работа с функциями высших порядков - сплошное интеллектуальное удовольствие. Процедура double записывается очень просто:

(define (double f)
  (lambda (x) (f (f x))))

Ее запуск в простых случаях приводит ко вполне ожидаемым результатам:

> ((double square) 2)
16

> ((double inc) 5)
7

Что же выведет (((double (double double)) inc) 5)? В этом случае выводится число 21. Почему? Все достаточно просто.

Если вызов double вызывает функцию дважды, то запись (double double) означает функцию, которая принимает один аргумент - функцию одного параметра и вызывает ее четырежды. Тут неожиданностей нет. Более странным может показаться то, что ((double (double double)) вызывает свой аргумент не 8 раз, как могло бы показаться, а 16. Дело в том, что двойной вызов функции означает композицию функции с собой же, то есть функция-аргумент вызывается четыре раза по четырежды, то есть 16 раз. В итоге, инкрементируя число 5 шестнадцать раз, получаем 21.