и

1

l/fll + 1/Д2

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

(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. Права ли она? Почему?

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

Объясните в общем случае, почему эквивалентные алгебраические выражения могут давать разные результаты. Можете ли Вы представить себе пакет для работы с интервальной арифметикой, который бы не обладал этим недостатком, или такое невозможно? (Предупреждение: эта задача очень сложна.)

2.2 Иерархические данные и свойство замыкания

Как мы уже видели, пары служат элементарным «клеем», с помощью которого можно строить составные объекты данных. На рис.2.2 показан стандартный способ рисовать пару - в данном случае, пару, которая сформирована выражением (cons 1 2). В этом представлении, которое называется стрелочная диаграмма (box-and-pointer notation), каждый объект изображается в виде стрелки (pointer), указывающей на какую-нибудь ячейку. Ячейка, изображающая элементарный объект, содержит представление этого объекта. Например,

1

Рис. 2.2: Представление (cons 12) в виде стрелочной диаграммы.

1

2

(cons (cons 1 2) (cons 3 4))

1

2

3

(cons (cons 1

(cons 2 3))

4)

Рис. 2.3: Два способа соединить 1, 2, 3 и 4 с помощью пар.

ячейка, соответствующая числу, содержит числовую константу. Изображение пары состоит из двух ячеек, причем левая из них содержит (указатель на) car этой пары, а правая - ее cdr.

Мы уже видели, что cons способен соединять не только числа, но и пары. (Вы использовали это свойство, или, по крайней мере, должны были использовать, когда выполняли упражнения 2.2 и 2.3). Как следствие этого, пары являются универсальным материалом, из которого можно строить любые типы структур данных. На рис. 2.3 показаны два способа соединить числа 1, 2, 3 и 4 при помощи пар.

Возможность создавать пары, элементы которых сами являются парами, определяет значимость списковой структуры как средства представления данных. Мы называем эту возможность свойством замыкания (closure property) для cons. В общем случае, операция комбинирования объектов данных обладает свойством замыкания в том случае, если результаты соединения объектов с помощью этой операции сами могут соединяться этой же операцией.6 Замыкание - это ключ к выразительной силе для любого средства комбинирования, поскольку оно позволяет строить иерархические (hierarchical) структуры, то есть структуры, которые составлены из частей, которые сами составлены из частей, и так далее.

С самого начала главы 1 мы существенным образом использовали свойство

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

Рис. 2.4: Последовательность 1, 2, 3, 4, представленная в виде цепочки пар.

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

2.2.1 Представление последовательностей

Одна из полезных структур, которые можно построить с помощью пар - это последовательность (sequence), то есть упорядоченная совокупность объектов данных. Разумеется, существует много способов представления последовательностей при помощи пар. Один, особенно простой, показан на рисунке 2.4, где последовательность 1, 2, 3, 4 представлена как цепочка пар. В каждой паре car - это соответствующий член цепочки, а cdr - следующая пара цепочки. Cdr последней пары указывает на особое значение, не являющееся парой, которое на диаграммах изображается как диагональная линия, а в программах как значение переменной nil. Вся последовательность порождается несколькими вложенными операциями cons:

(cons 1

(cons 2

(cons 3

(cons 4 nil))))

Такая последовательность пар, порождаемая вложенными cons-ами, называется список (list). В Scheme имеется примитив, который называется list и помогает строить списки.8 Вышеуказанную последовательность можно было бы

7Идея, что средство комбинирования должно удовлетворять условию замыкания, очень проста. К сожалению, такие средства во многих популярных языках программирования либо не удовлетворяют этому условию, либо делают использование замыканий неудобным. В Фортране и Бейсике элементы данных обычно группируются путем создания массивов - но массивы, элементы которых сами являются массивами, строить нельзя. Паскаль и Си позволяют иметь структуры, члены которых являются структурами. Однако при этом требуется, чтобы программист напрямую работал с указателями и соблюдал ограничение, по которому каждое поле структуры может содержать только элементы заранее заданной формы. В отличие от Лиспа с его парами, в этих языках нет встроенного универсального клея, который позволял бы легко работать с составными данными единым способом. Это ограничение дало Алану Перлису повод сказать в предисловии к этой книге: «В Паскале обилие объявляемых структур данных ведет к специализации функций, которая сдерживает и наказывает случайное взаимодействие между ними. Лучше иметь 100 функций, которые работают с одной структурой данных, чем 10 функций, работающих с 10 структурами».

8 В этой книге термин список всегда означает цепочку пар, которая завершается маркером конца списка. Напротив, термин списковая структура (list structure) относится к любой структуре данных, составленной из пар, а не только к спискам.