SICP по-русски

Это просто замечательнейшее упражнение! Сейчас объясню, почему оно мне так понравилось, но начнем с простого, то есть с определения процедуры smooth. Здесь все достаточно легко:

(define (smooth f dx)
  (define (average x y z) (/ (+ x y z) 3))
  (lambda (x) (average (f (- x dx))
                       (f x)
                       (f (+ x dx)))))

А вот теперь часть похитрее - многократное сглаживание. Приведу первое решение, которое пришло мне в голову:

(define (smooth-n f dx n)
  (repeated (smooth f dx) n))

Оно хорошо краткостью своей записи, но неверно по сути. Правильное же решение записывается следующим образом:

(define (smooth-n f dx n)
  ((repeated (lambda (g) (smooth g dx)) n) f))

В чем разница (помимо более длинной записи)? Давайте разберемся.

Может показаться, что эти две записи эквивалентны, но это не так. Отличие в вызове процедуры smooth:

(smooth f dx) против (lambda (g) (smooth g dx))

Я хочу подчеркнуть, что (smooth f dx) - это процедура, которая принимает число и возвращает число. А вот (lambda (g) (smooth g dx)) - это процедура, которая принимает процедуру одного числового аргумента и возвращает также процедуру одного числового аргумента. Прочувствуйте отличие:

• число на входе и число на выходе;
• процедура на входе и процедура на выходе.

Прочитаем первый вариант реализации: применяем однократно сглаженную функцию f последовательно n раз к своему же результату (то есть функцию f’(f’(…f’(x)…)), где f’ - это сглаженная f); получаем функцию числового аргумента. То, что надо? Не похоже…

Второй вариант реализации smooth-n читается таким образом: к функции f применяем преобразование, получающееся в результате применения сглаживания n раз; в результате получаем функцию числового аргумента. Оно? Оно!

Это может показаться не очень простым в понимании. Рекомендую в таком случае попробовать вычислить

((smooth-n square 0.5 2) 1.0)

вручную и программно двумя способами и осознать, почему результаты двух описанных выше процедур smooth-n различны. И добро пожаловать в комментарии.