1.3.4 Процедуры как возвращаемые значения

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

Эту идею можно проиллюстрировать примером с поиском неподвижной точки, обсуждаемым в конце раздела 1.3.3. Мы сформулировали новую версию процедуры вычисления квадратного корня как поиск неподвижной точки, начав с наблюдения, что л/х есть неподвижная точка функции у i-> х/у. Затем мы использовали торможение усреднением, чтобы заставить приближения сходиться. Торможение усреднением само по себе является полезным приемом. А именно, получив функцию f, мы возвращаем функцию, значение которой в точке х есть среднее арифметическое между x и f(x).

Идею торможения усреднением мы можем выразить при помощи следующей процедуры:

(define (average-damp f)

(lambda (x) (average x (f x))))

Average-damp - это процедура, принимающая в качестве аргумента процедуру f и возвращающая в качестве значения процедуру (полученную с помощью lambda), которая, будучи применена к числу x, возвращает среднее между x и (f x) . Например, применение average-damp к процедуре square получает процедуру, значением которой для некоторого числа x будет среднее между x и x2. Применение этой процедуры к числу 10 возвращает среднее между 10 и 100, то есть 55:59

((average-damp square) 10)

55

Используя average-damp, мы можем переформулировать процедуру вычисления квадратного корня следующим образом:

(define (sqrt x)

(fixed-point (average-damp (lambda (y) (/ x y)))

1.0))

Обратите внимание, как такая формулировка делает явными три идеи нашего метода: поиск неподвижной точки, торможение усреднением и функцию y - x/y. Полезно сравнить такую формулировку метода поиска квадратного корня с исходной версией, представленной в разделе 1.1.7. Вспомните, что обе процедуры выражают один и тот же процесс, и посмотрите, насколько яснее становится его идея, когда мы выражаем процесс в терминах этих абстракций. В общем случае существует много способов сформулировать процесс в виде процедуры. Опытные программисты знают, как выбрать те формулировки процедур, которые наиболее ясно выражают их мысли, и где полезные элементы

59Заметьте, что здесь мы имеем комбинацию, оператор которой сам по себе комбинация. В упражнении 1.4 уже была продемонстрирована возможность таких комбинаций, но то был всего лишь игрушечный пример. Здесь мы начинаем чувствовать настоящую потребность в выражениях такого рода - когда нам нужно применить процедуру, полученную в качестве значения из процедуры высшего порядка.

процесса показаны в виде отдельных сущностей, которые можно использовать в других приложениях. Чтобы привести простой пример такого нового использования, заметим, что кубический корень x является неподвижной точкой функции y - x/y2, так что мы можем немедленно обобщить нашу процедуру поиска квадратного корня так, чтобы она извлекала кубические корни:60

(define (cube-root x)

(fixed-point (average-damp (lambda (y) (/ x (square y))))

1.0))

Метод Ньютона

Когда в разделе 1.1.7 мы впервые представили процедуру извлечения квадратного корня, мы упомянули, что это лишь частный случай метода Ньютона (Newthons method). Если x - g(x) есть дифференцируемая функция, то решение уравнения g(x) = 0 есть неподвижная точка функции x - f (x), где

а Dg(x) есть производная g, вычисленная в точке x. Метод Ньютона состоит в том, чтобы применить описанный способ поиска неподвижной точки и аппроксимировать решение уравнения путем поиска неподвижной точки функции f .61 Для многих функций g при достаточно хорошем начальном значении x метод Ньютона очень быстро приводит к решению уравнения g(x) = 0.62

Чтобы реализовать метод Ньютона в виде процедуры, сначала нужно выразить понятие производной. Заметим, что «взятие производной», подобно торможению усреднением, трансформирует одну функцию в другую. Например, производная функции x - x3 есть функция x - 3x2. В общем случае, если g есть функция, а dx - маленькое число, то производная Dg функции g есть функция, значение которой в каждой точке x описывается формулой (при dx, стремящемся к нулю)

Таким образом, мы можем выразить понятие производной (взяв dx равным, например, 0.00001) в виде процедуры

(define (deriv g) (lambda (x)

(/ (- (g (+ x dx)) (g x))

dx)))

дополненной определением

(define dx 0.00001)

60См. дальнейшее обобщение в упражнении 1.45

61 Вводные курсы анализа обычно описывают метод Ньютона через последовательность приближений i„+i = xn - g(xn)/Dg(xn). Наличие языка, на котором мы можем говорить о процессах,

а также использование идеи неподвижных точек, упрощают описание этого метода.

62Метод Ньютона не всегда приводит к решению, но можно показать, что в удачных случаях каждая итерация удваивает точность приближения в терминах количества цифр после запятой. Для таких случаев метод Ньютона сходится гораздо быстрее, чем метод половинного деления.

f(x)

Dg(x)

Dg(x)

g(x + dx) - g(x) dx

Подобно average-damp, deriv является процедурой, которая берет процедуру в качестве аргумента и возвращает процедуру как значение. Например, чтобы найти приближенное значение производной x - x3 в точке 5 (точное значение производной равно 75), можно вычислить

(define (cube x) (* x x x))

((deriv cube) 5) 75.00014999664018

С помощью deriv мы можем выразить метод Ньютона как процесс поиска неподвижной точки:

(define (newton-transform g) (lambda (x)

(- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)

(fixed-point (newton-transform g) guess))

Процедура newton-transform выражает формулу, приведенную в начале этого раздела, а newtons-method легко определяется с ее помощью. В качестве аргументов она принимает процедуру, вычисляющую функцию, чей ноль мы хотим найти, а также начальное значение приближения. Например, чтобы найти квадратный корень x, мы можем с помощью метода Ньютона найти ноль функции y - y2 - x, начиная со значения 1.63 Это дает нам еще одну форму процедуры вычисления квадратного корня:

(define (sqrt x)

(newtons-method (lambda (y) (- (square y) x))

1.0))

Абстракции и процедуры как полноправные объекты

Мы видели два способа представить вычисление квадратного корня как частный случай более общего метода; один раз это был поиск неподвижной точки, другой - метод Ньютона. Поскольку сам метод Ньютона был выражен как процесс поиска неподвижной точки, на самом деле мы увидели два способа вычислить квадратный корень как неподвижную точку. Каждый из этих методов получает некоторую функцию и находит неподвижную точку для некоторой трансформации этой функции. Эту общую идею мы можем выразить как

процедуру:

(define (fixed-point-of-transform g transform guess) (fixed-point (transform g) guess))

Эта очень общая процедура принимает в качестве аргументов процедуру g, которая вычисляет некоторую функцию, процедуру, которая трансформирует g, и начальное приближение. Возвращаемое значение есть неподвижная точка трансформированной функции.

63 При поиске квадратных корней метод Ньютона быстро сходится к правильному решению, начиная с любой точки.