С помощью такой абстракции можно переформулировать процедуру вычисления квадратного корня из этого раздела (ту, где мы ищем неподвижную точку версии y - x/y, заторможенной усреднением) как частный случай общего метода:

(define (sqrt x)

(fixed-point-of-transform (lambda (y) (/ x y))

average-damp

1.0))

Подобным образом, вторую процедуру нахождения квадратного корня из этого раздела (пример применения метода Ньютона, который находит неподвижную точку Ньютонова преобразования y - y2 - x) можно представить так:

(define (sqrt x)

(fixed-point-of-transform (lambda (y) (- (square y) x))

newton-transform

1.0))

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

Как программисты, мы должны быть готовы распознавать возможности поиска абстракций, лежащих в основе наших программ, строить нашу работу на таких абстракциях и обобщать их, создавая еще более мощные абстракции. Это не значит, что программы всегда нужно писать на возможно более глубоком уровне абстракции: опытные программисты умеют выбирать тот уровень, который лучше всего подходит к их задаче. Однако важно быть готовыми мыслить в терминах этих абстракций и быть готовым применить их в новых контекстах. Важность процедур высшего порядка состоит в том, что они позволяют нам явно представлять эти абстракции в качестве элементов нашего языка программирования, так что мы можем обращаться с ними так же, как и с другими элементами вычисления.

В общем случае языки программирования накладывают ограничения на способы, с помощью которых можно манипулировать элементами вычисления. Говорят, что элементы, на которые накладывается наименьшее число ограничений, имеют статус элементов вычисления первого класса (first-class) или полноправных. Вот некоторые из их «прав и привилегий»:64

•Их можно называть с помощью переменных.

•Их можно передавать в процедуры в качестве аргументов.

•Их можно возвращать из процедур в виде результата.

•Их можно включать в структуры данных.65

64Понятием полноправного статуса элементов языка программирования мы обязаны британскому специалисту по информатике Кристоферу Стрейчи (1916-1975). 65Примеры этого мы увидим после того, как введем понятие структур данных в главе 2.

Лисп, в отличие от других распространенных языков программирования, дает процедурам полноправный статус. Это может быть проблемой для эффективной реализации, но зато получаемый выигрыш в выразительной силе огромен.66

Упражнение 1.40.

Определите процедуру cubic, которую можно было бы использовать совместно с процедурой newtons-method в выражениях вида

(newtons-method (cubic a b c) 1)

для приближенного вычисления нулей кубических уравнений x3 + ax2 + bx + c. Упражнение 1.41.

Определите процедуру double, которая принимает как аргумент процедуру с одним аргументом и возвращает процедуру, которая применяет исходную процедуру дважды. Например, если процедура inc добавляет к своему аргументу 1, то (double inc) должна быть процедурой, которая добавляет 2. Скажите, какое значение возвращает

(((double (double double)) inc) 5)

Упражнение 1.42.

Пусть f и g - две одноаргументные функции. По определению, композиция (composition) f и g есть функция x - f (g(x)). Определите процедуру compose которая реализует композицию. Например, если inc - процедура, добавляющая к своему аргументу

1,

((compose square inc) 6)

49

Упражнение 1.43.

Если f есть численная функция, а n - положительное целое число, то мы можем построить n-кратное применение f, которое определяется как функция, значение которой в точке x равно f (f (... (f (x))...)). Например, если f есть функция x - x + 1, то n-кратным применением f будет функция x - x + n. Если f есть операция возведения в квадрат, то n-кратное применение f есть функция, которая возводит свой аргумент в 2п-ю степень. Напишите процедуру, которая принимает в качестве ввода процедуру, вычисляющую f, и положительное целое n, и возвращает процедуру, вычисляющую n-кратное применение f. Требуется, чтобы Вашу процедуру можно было использовать в таких контекстах:

((repeated square 2) 5)

625

Подсказка: может оказаться удобно использовать compose из упражнения 1.42 Упражнение 1.44.

Идея сглаживания (smoothing a function) играет важную роль в обработке сигналов. Если f - функция, а dx - некоторое малое число, то сглаженная версия f есть функция, значение которой в точке x есть среднее между f(x - dx), f (x) и f (x + dx).

66Основная цена, которую реализации приходится платить за придание процедурам статуса полноправных объектов, состоит в том, что, поскольку мы разрешаем возвращать процедуры как значения, нам нужно оставлять память для хранения свободных переменных процедуры даже тогда, когда она не выполняется. В реализации Scheme, которую мы рассмотрим в разделе 4.1, эти переменные хранятся в окружении процедуры.

Напишите процедуру smooth, которая в качестве ввода принимает процедуру, вычисляющую f, и возвращает процедуру, вычисляющую сглаженную версию f. Иногда бывает удобно проводить повторное сглаживание (то есть сглаживать сглаженную функцию и т.д.), получая n-кратно сглаженную функцию (n-fold smoothed function). Покажите, как породить n-кратно сглаженную функцию с помощью smooth и repeated из упражнения 1.43.

Упражнение 1.45.

В разделе 1.3.3 мы видели, что попытка вычисления квадратных корней путем наивного поиска неподвижной точки y н-► x/y не сходится, и что это можно исправить путем торможения усреднением. Тот же самый метод работает для нахождения кубического корня как неподвижной точки y н x/y2, заторможенной усреднением. К сожалению, этот процесс не работает для корней четвертой степени - однажды примененного торможения усреднением недостаточно, чтобы заставить сходиться процесс поиска неподвижной точки y н x/y3. С другой стороны, если мы применим торможение усреднением дважды (т.е. применим торможение усреднением к результату торможения усреднением от y н x/y3), то поиск неподвижной точки начнет сходиться. Проделайте эксперименты, чтобы понять, сколько торможений усреднением нужно, чтобы вычислить корень n-ой степени как неподвижную точку на основе многократного торможения усреднением функции y н x/yn-1. Используя свои результаты для того, напишите простую процедуру вычисления корней n-ой степени с помощью процедур fixed-point, average-damp и repeated из упражнения 1.43. Считайте, что все арифметические операции, какие Вам понадобятся, присутствуют в языке как примитивы.

Упражнение 1.46.

Некоторые из вычислительных методов, описанных в этой главе, являются примерами чрезвычайно общей вычислительной стратегии, называемой пошаговое улучшение (iterative improvement). Пошаговое улучшение состоит в следующем: чтобы что-то вычислить, нужно взять какое-то начальное значение, проверить, достаточно ли оно хорошо, чтобы служить ответом, и если нет, то улучшить это значение и продолжить процесс с новым значением. Напишите процедуру iterative-improve, которая принимает в качестве аргументов две процедуры: проверку, достаточно ли хорошо значение, и метод улучшения значения. Iterative-improve должна возвращать процедуру, которая принимает начальное значение в качестве аргумента и улучшает его, пока оно не станет достаточно хорошим. Перепишите процедуру sqrt из раздела 1.1.7 и процедуру fixed-point из раздела 1.3.3 в терминах iterative-improve.