Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 20
Текст из файла (страница 20)
Поскольку сам метод Ньютона был выражен как процесс поиска неподвижной точки, на самом деле мы увидели два способа вычислить квадратный корень какнеподвижную точку. Каждый из этих методов получает некоторую функцию и находитнеподвижную точку для некоторой трансформации этой функции. Эту общую идею мыможем выразить как процедуру:(define (fixed-point-of-transform g transform guess)(fixed-point (transform g) guess))Эта очень общая процедура принимает в качестве аргументов процедуру g, которая вычисляет некоторую функцию, процедуру, которая трансформирует g, и начальное приближение.
Возвращаемое значение есть неподвижная точка трансформированной функции.С помощью такой абстракции можно переформулировать процедуру вычисления квадратного корня из этого раздела (ту, где мы ищем неподвижную точку версии y 7→ x/y,заторможенной усреднением) как частный случай общего метода:(define (sqrt x)(fixed-point-of-transform (lambda (y) (/ x y))average-damp1.0))Подобным образом, вторую процедуру нахождения квадратного корня из этого раздела(пример применения метода Ньютона, который находит неподвижную точку Ньютоновапреобразования y 7→ y 2 − x) можно представить так:(define (sqrt x)(fixed-point-of-transform (lambda (y) (- (square y) x))newton-transform1.0))Мы начали раздел 1.3 с наблюдения, что составные процедуры являются важныммеханизмом абстракции, поскольку они позволяют выражать общие методы вычисления в виде явных элементов нашего языка программирования. Теперь мы увидели, как63 При поиске квадратных корней метод Ньютона быстро сходится к правильному решению, начиная с любойточки.1.3.
Формулирование абстракций с помощью процедур высших порядков87процедуры высших порядков позволяют нам манипулировать этими общими методами исоздавать еще более глубокие абстракции.Как программисты, мы должны быть готовы распознавать возможности поиска абстракций, лежащих в основе наших программ, строить нашу работу на таких абстракциях и обобщать их, создавая еще более мощные абстракции. Это не значит, что программы всегда нужно писать на возможно более глубоком уровне абстракции: опытныепрограммисты умеют выбирать тот уровень, который лучше всего подходит к их задаче. Однако важно быть готовыми мыслить в терминах этих абстракций и быть готовымприменить их в новых контекстах. Важность процедур высшего порядка состоит в том,что они позволяют нам явно представлять эти абстракции в качестве элементов нашегоязыка программирования, так что мы можем обращаться с ними так же, как и с другимиэлементами вычисления.В общем случае языки программирования накладывают ограничения на способы, спомощью которых можно манипулировать элементами вычисления.
Говорят, что элементы, на которые накладывается наименьшее число ограничений, имеют статус элементоввычисления первого класса (first-class) или полноправных. Вот некоторые из их «прав ипривилегий»64:• Их можно называть с помощью переменных.• Их можно передавать в процедуры в качестве аргументов.• Их можно возвращать из процедур в виде результата.• Их можно включать в структуры данных65 .Лисп, в отличие от других распространенных языков программирования, дает процедурам полноправный статус. Это может быть проблемой для эффективной реализации,но зато получаемый выигрыш в выразительной силе огромен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)64 Понятием полноправного статуса элементов языка программирования мы обязаны британскому специалисту по информатике Кристоферу Стрейчи (1916-1975).65 Примеры этого мы увидим после того, как введем понятие структур данных в главе 2.66 Основная цена, которую реализации приходится платить за придание процедурам статуса полноправныхобъектов, состоит в том, что, поскольку мы разрешаем возвращать процедуры как значения, нам нужно оставлять память для хранения свободных переменных процедуры даже тогда, когда она не выполняется. В реализации Scheme, которую мы рассмотрим в разделе 4.1, эти переменные хранятся в окружении процедуры.Глава 1.
Построение абстракций с помощью процедур88Упражнение 1.42.Пусть f и g — две одноаргументные функции. По определению, композиция (composition) f иg есть функция x 7→ f (g(x)). Определите процедуру compose которая реализует композицию.Например, если inc — процедура, добавляющая к своему аргументу 1,((compose square inc) 6)49Упражнение 1.43.Если f есть численная функция, а n — положительное целое число, то мы можем построитьn-кратное применение f , которое определяется как функция, значение которой в точке x равноf (f (.
. . (f (x)) . . .)). Например, если f есть функция x 7→ x + 1, то n-кратным применением fбудет функция x 7→ x + n. Если f есть операция возведения в квадрат, то n-кратное применениеf есть функция, которая возводит свой аргумент в 2n -ю степень. Напишите процедуру, котораяпринимает в качестве ввода процедуру, вычисляющую 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). Напишите процедуру smooth,которая в качестве ввода принимает процедуру, вычисляющую f , и возвращает процедуру, вычисляющую сглаженную версию f .
Иногда бывает удобно проводить повторное сглаживание (тоесть сглаживать сглаженную функцию и т.д.), получая n-кратно сглаженную функцию (n-foldsmoothed function). Покажите, как породить n-кратно сглаженную функцию с помощью smooth иrepeated из упражнения 1.43.Упражнение 1.45.В разделе 1.3.3 мы видели, что попытка вычисления квадратных корней путем наивного поиска неподвижной точки y 7→ x/y не сходится, и что это можно исправить путем торможенияусреднением. Тот же самый метод работает для нахождения кубического корня как неподвижнойточки y 7→ x/y 2 , заторможенной усреднением.
К сожалению, этот процесс не работает для корней четвертой степени — однажды примененного торможения усреднением недостаточно, чтобызаставить сходиться процесс поиска неподвижной точки y 7→ x/y 3 . С другой стороны, если мыприменим торможение усреднением дважды (т.е. применим торможение усреднением к результатуторможения усреднением от y 7→ x/y 3 ), то поиск неподвижной точки начнет сходиться. Проделайте эксперименты, чтобы понять, сколько торможений усреднением нужно, чтобы вычислитькорень n-ой степени как неподвижную точку на основе многократного торможения усреднениемфункции y 7→ x/y n−1 . Используя свои результаты для того, напишите простую процедуру вычислениякорней n-ой степени с помощью процедур fixed-point, average-damp и repeated изупражнения 1.43.
Считайте, что все арифметические операции, какие Вам понадобятся, присутствуют в языке как примитивы.1.3. Формулирование абстракций с помощью процедур высших порядков89Упражнение 1.46.Некоторые из вычислительных методов, описанных в этой главе, являются примерами чрезвычайнообщей вычислительной стратегии, называемой пошаговое улучшение (iterative improvement). Пошаговое улучшение состоит в следующем: чтобы что-то вычислить, нужно взять какое-то начальное значение, проверить, достаточно ли оно хорошо, чтобы служить ответом, и если нет, то улучшить это значение и продолжить процесс с новым значением.
Напишите процедуру iterativeimprove, которая принимает в качестве аргументов две процедуры: проверку, достаточно ли хорошо значение, и метод улучшения значения. Iterative-improve должна возвращать процедуру,которая принимает начальное значение в качестве аргумента и улучшает его, пока оно не станетдостаточно хорошим. Перепишите процедуру sqrt из раздела 1.1.7 и процедуру fixed-pointиз раздела 1.3.3 в терминах iterative-improve.ГЛАВА 2ПОСТРОЕНИЕАБСТРАКЦИЙ С ПОМОЩЬЮДАННЫХТеперь мы подходим к решающему шагув математической абстракции: мызабываем, что обозначают наши символы....[Математик] не должен стоять наместе: есть много операций, которые онможет производить с этими символами,не обращая внимания на те вещи,которые они обозначают.Герман Вейль.«Математический способ мышления»В главе 1 мы сконцентрировали внимание на вычислительных процессах и ролипроцедур в проектировании программ.
Мы рассмотрели, как использовать простейшиеданные (числа) и простейшие операции (арифметические), как сочетать процедуры иполучать составные процедуры с помощью композиции, условных выражений и использования параметров, а также как строить абстрактные процедуры при помощи define.Мы убедились, что процедуру можно рассматривать как схему локального развитияпроцесса; мы классифицировали некоторые общие схемы процессов, воплощенные в процедурах, строили о них умозаключения и производили их простейший алгоритмическийанализ.
Кроме того, мы увидели, что процедуры высших порядков увеличивают выразительную силу нашего языка, позволяя оперировать общими методами вычисления, аследовательно, и проводить рассуждения в их терминах. Это во многом и составляетсущность программирования.В этой главе мы будем рассматривать более сложные данные. Все процедуры главы 1работают с простыми численными данными, а простых численных данных часто бываетнедостаточно для тех задач, которые мы хотим решать с помощью вычислений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
