Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 25
Текст из файла (страница 25)
Перепишите эту процедуру в соответствии с предложением Бена.Отладив программу, Лиза показывает ее потенциальному пользователю, а тот жалуется, что она решает не ту задачу. Ему нужна программа, которая работала бы с числами,представленными в виде срединного значения и аддитивной погрешности; например, емухочется работать с интервалами вида 3.5 ± 0.15, а не [3.35, 3.65]. Лиза возвращается к работе и исправляет этот недочет, добавив дополнительный конструктор и дополнительныеселекторы:(define (make-center-width c w)(make-interval (- c w) (+ c w)))(define (center i)(/ (+ (lower-bound i) (upper-bound i)) 2))(define (width i)(/ (- (upper-bound i) (lower-bound i)) 2))К сожалению, большая часть Лизиных пользователей — инженеры. В реальных технических задачах речь обычно идет об измерениях с небольшой погрешностью, котораяизмеряется как отношение радиуса интервала к его средней точке.
Инженеры обычно указывают в параметрах устройств погрешность в процентах, как в спецификацияхрезисторов, которые мы привели в пример выше.Упражнение 2.12.Определите конструктор make-center-percent, который принимает среднее значение и погрешность в процентах и выдает требуемый интервал. Нужно также определить селектор percent,который для данного интервала выдает погрешность в процентах. Селектор center остается темже, что приведен выше.2.1. Введение в абстракцию данных105Упражнение 2.13.Покажите, что, если предположить, что погрешность составляет малую долю величины интервала,то погрешность в процентах произведения двух интервалов можно получить из погрешности впроцентах исходных интервалов по простой приближенной формуле.
Задачу можно упростить,если предположить, что все числа положительные.После долгой работы Лиза П. Хакер сдает систему пользователям. Несколько летспустя, ужезабыв об этом, она получает жалобу от разгневанного пользователя ДайкоПоправича. Оказывается, Дайко заметил, что формулу для параллельных резисторовможно записать двумя алгебраически эквивалентными способами:R1 R2R1 + R2и11/R1 + 1/R2Он написал следующие две программы, каждая из которых считает формулу для параллельных резисторов своим способом:(define (par1 r1 r2)(div-interval (mul-interval r1 r2)(add-interval r1 r2)))(define (par2 r1 r2)(let ((one (make-interval 1 1)))(div-interval one(add-interval (div-interval one r1)(div-interval one r2)))))Дайко утверждает, что для двух способов вычисления Лизина программа дает различныерезультаты.
Это серьезное нарекание.Упражнение 2.14.Покажите, что Дайко прав. Исследуйте поведение системы на различных арифметических выражениях. Создайте несколько интервалов A и B и вычислите с их помощью выражения A/A и A/B.Наибольшую пользу Вы получите, если будете использовать интервалы, радиус которых составляет малую часть от среднего значения. Исследуйте результаты вычислений в форме центр/проценты(см. упражнение 2.12).Упражнение 2.15.Ева Лу Атор, другой пользователь Лизиной программы, тоже заметила, что алгебраически эквивалентные, но различные выражения могут давать разные результаты. Она говорит, что формула длявычисления интервалов, которая использует Лизину систему, будет давать более узкие границыпогрешности, если ее удастся записать так, чтобы ни одна переменная, представляющая неточную величину, не повторялась. Таким образом, говорит она, par2 «лучше» как программа дляпараллельных резисторов, чем par1.
Права ли она? Почему?106Глава 2. Построение абстракций с помощью данных21Рис. 2.2. Представление (cons 1 2) в виде стрелочной диаграммы.Упражнение 2.16.Объясните в общем случае, почему эквивалентные алгебраические выражения могут давать разныерезультаты. Можете ли Вы представить себе пакет для работы с интервальной арифметикой,который бы не обладал этим недостатком, или такое невозможно? (Предупреждение: эта задачаочень сложна.)2.2.
Иерархические данные и свойство замыканияКак мы уже видели, пары служат элементарным «клеем», с помощью которого можностроить составные объекты данных. На рис. 2.2 показан стандартный способ рисоватьпару — в данном случае, пару, которая сформирована выражением (cons 1 2). В этомпредставлении, которое называется стрелочная диаграмма (box-and-pointer notation),каждый объект изображается в виде стрелки (pointer), указывающей на какую-нибудьячейку. Ячейка, изображающая элементарный объект, содержит представление этогообъекта. Например, ячейка, соответствующая числу, содержит числовую константу.Изображение пары состоит из двух ячеек, причем левая из них содержит (указательна) car этой пары, а правая — ее cdr.Мы уже видели, что cons способен соединять не только числа, но и пары.
(Выиспользовали это свойство, или, по крайней мере, должны были использовать, когдавыполняли упражнения 2.2 и 2.3). Как следствие этого, пары являются универсальнымматериалом, из которого можно строить любые типы структур данных. На рис. 2.3 показаны два способа соединить числа 1, 2, 3 и 4 при помощи пар.Возможность создавать пары, элементы которых сами являются парами, определяетзначимость списковой структуры как средства представления данных. Мы называем этувозможность свойством замыкания (closure property) для cons. В общем случае, операция комбинирования объектов данных обладает свойством замыкания в том случае,если результаты соединения объектов с помощью этой операции сами могут соединятьсяэтой же операцией6.
Замыкание — это ключ к выразительной силе для любого средствакомбинирования, поскольку оно позволяет строить иерархические (hierarchical) структуры, то есть структуры, которые составлены из частей, которые сами составлены изчастей, и так далее.6 Такое употребление слова «замыкание» происходит из абстрактной алгебры. Алгебраисты говорят, чтомножество замкнуто относительно операции, если применение операции к элементам этого множества дает результат, который также является элементом множества. К сожалению, в сообществе программистов, пишущихна Лиспе, словом «замыкание» обозначается еще и совершенно другое понятие: замыканием называют способпредставления процедур, имеющих свободные переменные. В этом втором смысле мы слово «замыкание» вкниге не используем.2.2.
Иерархические данные и свойство замыкания107431412(cons (cons 1 2)(cons 3 4))23(cons (cons 1(cons 2 3))4)Рис. 2.3. Два способа соединить 1, 2, 3 и 4 с помощью пар.С самого начала главы 1 мы существенным образом использовали свойство замыкания при работе с процедурами, поскольку все программы, кроме самых простых,опираются на то, что элементы комбинации сами могут быть комбинациями. В этомразделе мы рассмотрим, какое значение замыкание имеет для составных данных.
Мыопишем несколько распространенных методов использования пар для представления последовательностей и деревьев, а также построим графический язык, который наглядноиллюстрирует замыкание7 .2.2.1. Представление последовательностейОдна из полезных структур, которые можно построить с помощью пар — это последовательность (sequence), то есть упорядоченная совокупность объектов данных.Разумеется, существует много способов представления последовательностей при помощи пар. Один, особенно простой, показан на рисунке 2.4, где последовательность 1, 2,3, 4 представлена как цепочка пар.
В каждой паре car — это соответствующий членцепочки, а cdr — следующая пара цепочки. Cdr последней пары указывает на особоезначение, не являющееся парой, которое на диаграммах изображается как диагональнаялиния, а в программах как значение переменной nil. Вся последовательность порождается несколькими вложенными операциями cons:7 Идея, что средство комбинирования должно удовлетворять условию замыкания, очень проста. К сожалению, такие средства во многих популярных языках программирования либо не удовлетворяют этому условию,либо делают использование замыканий неудобным.
В Фортране и Бейсике элементы данных обычно группируются путем создания массивов — но массивы, элементы которых сами являются массивами, строить нельзя.Паскаль и Си позволяют иметь структуры, члены которых являются структурами. Однако при этом требуется, чтобы программист напрямую работал с указателями и соблюдал ограничение, по которому каждое полеструктуры может содержать только элементы заранее заданной формы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
