Абельсон Х., Сассман Д.Д. Структура и интерпретация компьютерных программ

Подождите немного. Документ загружается.

2.1. Введение в абстракцию данных

101

Эта идея ярко иллюстрируется тем, что мы могли бы реализовать cons, car и cdr без

использования каких-либо структур данных, а только при помощи одних процедур. Вот

эти определения:

(define (cons x y)

(define (dispatch m)

(cond ((= m 0) x)

((= m 1) y)

(else (error "Аргумент не 0 или 1 -- CONS" m))))

dispatch)

(define (car z) (z 0))

(define (cdr z) (z 1))

Такое использование процедур совершенно не соответствует нашему интуитивному по-

нятию о том, как должны выглядеть данные. Однако для того, чтобы показать, что это

закон ный способ представления пар, требуется только проверить, что эти процедуры

удовлетворяют вышеуказанному условию.

Тонкость здесь состоит в том, чтобы заметить, что значение, возвращаемое cons,

есть процедура, — а именно процедура dispatch, определенная внутри cons, которая

принимает один аргумент и возвращает либо x, либо y в зависимости от того, равен ли

ее аргумент 0 или 1. Соответственно, (car z) определяется как применение z к 0. Сле-

довательно, если z есть процедура, полученная из (cons x y), то z, примененная к 0,

вернет x. Таким образом , мы показали, что (car (cons x y)) возвращает x, как нам

и хо телось. Подобным образом (cdr (cons x y)) при меняет процедуру, возвращае-

мую (cons x y), к 1, что дает нам y. С ледовательно, эта процедурная реализация пар

закон на, и если мы обращаемся к парам только с помощью cons, car и cdr, то мы не

сможем отличить эту ре ализацию от такой, которая использует «настоящие» структуры

дан ных.

Демонстрировать процедурную реализацию имеет смысл не для того, чтобы пока-

зать, как работает наш язык (Scheme, и вообще Лисп-системы, реал изуют пары напря-

мую из соображений эффективности), а в том, чтобы показать, что он мог бы работать

и так. Пр оцедурная реализация, хотя она и выглядит трюком, — совершенно адекват-

ный способ представления пар, поскольку она удовлетворяет единственному условию,

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

собность работать с процедурами как с объектами автоматически дает нам возможность

представлять составные данные. Сейчас это может показаться курьезом, но в нашем про-

граммистском репертуаре процедурные представления данных будут играть центральную

роль. Такой стиль программирования часто называют передачей сообщений (message

passing), и в главе 3, при рассмотрении вопросов моделирования, он будет нашим основ-

ным инструментом.

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

Вот еще одно процедурное представление для пар. Проверьте для этого представления, что при

любых двух объектах x и y (car (cons x y)) возвращает x.

(define (cons x y)

(lambda (m) (m x y)))

102

Глава 2. Построение абстракций с помощ ью данных

(define (car z)

(z (lambda (p q) p)))

Каково соответствующее определение cdr? (Подсказка: Чтобы проверить, что это работает, ис-

пользуйте подстановочную модель из раздела 1 .1.5.)

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

Покажите, что можно представлять пары неотрицательных целых чисел, используя только числа

и арифметические операции, если представлять пару a и b как произведение 2

. Дайте соответ-

ствующие определения процедур cons, car и cdr.

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

Если представление пар как процедур было для Вас еще недостаточно сумасшедшим, то заметьте,

что в языке, который способен манипулировать процедурами, мы можем обойтись и без чисел (по

крайней мере, пока речь идет о неотрицательных числах), определив 0 и операцию прибавления 1

так:

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)

(lambda (f) (lambda (x) (f ((n f) x)))))

Такое представление известно как числа Чёрча (Church numerals), по имени е го изобретателя,

Алонсо Чёрча, того самого логика, который придумал λ-исчисление.

Определите one (единицу) и two (двойку) напрямую (не через zero и add-1). (Подсказ-

ка: вычислите (add-1 zero) с помощью подстановки.) Дайте прямое определение процедуры

сложения + (не в терминах повторяющегося применения add-1).

2.1.4. Расширенный пример: интервальная арифметика

Лиза П. Хакер проектирует систему, которая помогала бы в решении технических

задач. Одна из возможностей, которые она хочет реализовать в своей сис теме, — способ-

ность работать с неточными величинами (например, измеренные параметры физических

устройств), обладающими известной погрешностью, так что когда с такими приблизи-

тельными величинами производятся вычисления, результаты также представляют собой

числа с известной погрешностью.

Инженеры-электрики будут с помощью Лизиной системы вычислять электрические

величины. Иногда им требуется вычислить сопротивление R

параллельного соединения

двух резисторов R

и R

по ф ормуле

1/R

+ 1/R

Обычно сопротивления резисторов известны только с некоторой точностью, которую

гарантирует их производитель. Например, покупая ре зистор с надписью «6.8 Ом с по-

грешностью 10%», Вы знаете только то, что сопротивление резистора находится между

6.8 −0.68 = 6.12 и 6.8 + 0.68 = 7.48 Ом. Так что если резистор в 6.8 Ом с погрешностью

10% подключен параллельно резистору в 4.7 Ом с погрешностью 5%, то сопротивле-

ние этой комбинации может быть примерно от 2.58 О м (если оба резистора находятся

2.1. Введение в абстракцию данных

103

на нижней границе интервала допустимых значений) до 2.97 Ом (если оба резистора

находятся на верхней границе).

Идея Лизы состоит в том, чтобы реализовать «интервальну ю арифметику» как набор

арифметических операций над «интервалами» (объектами, которые представляют диа-

пазоны возможных значений неточной величины). Результатом сложения, вычитания,

умножения или деления двух интервалов также будет интервал, который представляет

диапазон возможных значений результата.

Лиза постулирует существование абстрактного объекта, называемого «интервал», у

которого есть два конца: верхняя и нижняя границы. Кроме того, она предполагае т,

что имея два конца интервала, мы можем сконструировать его при помощи конструк-

тора make-interval. Сначала Лиза пишет процедуру сложения двух интервалов. Она

рассуждает так: минимальное возможное значение суммы равно сумме нижних границ

интервалов, а максимальное возможное значение сумме верхних границ интервалов.

(define (add-interval x y)

(make-interval (+ (lower-bound x) (lower-bound y))

(+ (upper-bound x) (upper-bound y))))

Кроме того, она вычисляет произведение двух ин тервалов путем нахождения миниму-

ма и максимума произведени й кон цов интервалов и использования в качестве границ

интервала-результата. (min и max — примитивы, которые находят минимум и максимум

при любом количестве аргументов.)

(define (mul-interval x y)

(let ((p1 (* (lower-bound x) (lower-bound y)))

(p2 (* (lower-bound x) (upper-bound y)))

(p3 (* (upper-bound x) (lower-bound y)))

(p4 (* (upper-bound x) (upper-bound y))))

(make-interval (min p1 p2 p3 p4)

(max p1 p2 p3 p4))))

При делении двух интервалов Лиза умножает первый из них на интервал, обратный вто-

рому. Замети м , что границами обратного интервала являются числа, обратные верхней

и нижней границе исходного интервала, именно в таком порядке.

(define (div-interval x y)

(mul-interval x

(make-interval (/ 1.0 (upper-bound y))

(/ 1.0 (lower-bound y)))))

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

Программа Лизы неполна, поскольку она не определила, как реализуется абстракция интервала.

Вот определение конструктора интервала:

(define (make-interval a b) (cons a b))

Завершите реализацию, определив селекторы upper-bound и lower-bound.

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

Рассуждая в духе Лизы, опишите, как можно вычислить разность двух интервалов. Напиш ите

соответствующую процедуру вычитания, называемую sub-interval.

104

Глава 2. Построение абстракций с помощ ью данных

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

Радиус (width) интервала определяется как половина расстояния между его верхней и нижней гра-

ницами. Радиус является мерой неопределенности числа, которое обозначает интервал. Есть такие

математические операции, для которых радиус результата зависит только от радиусов интервалов-

аргументов, а есть такие, для которых радиус результата не является функцией радиусов аргу-

ментов. Покажите, что радиус суммы (или разности) двух интервалов зависит только от радиусов

интервалов, которые складываются (или вычитаются). Приведите примеры, которые показывают,

что для умножения или деления это не так.

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

Бен Битобор, системный программист-эксперт, смотрит через плечо Лизы и замечает: неясно, что

должно означать деление на интервал, пересекающий ноль. Модифицируйте код Лизы так, чтобы

программа проверяла это условие и сообщала об ошибке, если оно возникает.

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

Проходя мимо, Бен делает туманное замечание: «Если проверять знаки концов интервалов, можно

разбить mul-interval на девять случаев, из которых только в одном требуется более двух

умножений». Перепишите эту процедуру в соответствии с предложением Бена.

Отладив программу, Лиза показывает ее потенциальному пользователю, а тот жалу-

ется, что она решает не ту задачу. Ему нужна программа, которая работала бы с числами,

представлен ными в виде срединного значения и аддитивной погрешности; например, ему

хочется работать с интервалам и вида 3.5±0.15, а не [3.3 5, 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.

Покажите, что, если предположить, что погрешность составляет малую долю величины интервала,

то погрешность в процентах произведения двух интервалов можно получить из погрешности в

процентах исходных интервалов по простой приближенной формуле. Задачу можно упрос тить,

если предположить, что все числа положительные.

После долгой работы Лиза П. Хакер сдает систему пользователям. Несколько лет

спустя, ужезабыв об этом, она получает жалобу от разгневанного пользователя Дайко

Поправича. Оказывается, Дайко заметил, ч то формулу для парал лельных ре зисторов

можно записать двумя алгебраически эквивалентными способами:

+ R

1/R

+ 1/R

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

лельн ых резисторов своим способом:

(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.1 2).

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

Ева Лу Атор, другой пользователь Лизиной программы, тоже заметила, что алгебраически эквива-

лентные, но различные выражения могут давать разные р езультаты. Она говорит, что формула для

вычисления интервалов, которая использует Лизину систему, будет давать более узкие границы

погрешности, если ее удастся записать так, чтобы ни одна переменная, представляющая неточ-

ную величину, не повторялась. Таким образом, говорит она, par2 «лучше» как программа для

параллельных резисторов, чем par1. Права ли она? Почему?

106

Глава 2. Построение абстракций с помощ ью данных

Рис. 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. В общем случае, опе-

рация комбинирования объектов данных обладает свойством замыкания в том случае,

если результаты соединени я объектов с помощью этой операции с ам и могут соединяться

этой же операцией

. Замыкание — это ключ к выразительной силе для любого средства

комбинирования, поскольку оно позволяет строить иерархические (hierarchical) струк-

туры, то есть структуры, которые составлены из частей, которые сами составлены из

частей, и так далее.

Такое употребление слова «замыкание» происходит из абстрактной алгебры. Алгебраисты говорят, что

множество замкнуто относительно операци и, если применение операции к элементам этого множества дает ре-

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

на Лиспе, словом «замыкание» обозначается еще и совершенно другое понятие: замыканием называют способ

представления процедур, имеющих свободные переменные. В этом втором смысле мы слово «замыкание» в

книге не используем.

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

107

1 32

(cons (cons 1 2) (cons (cons 1

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

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

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

кания при работе с процедурами, поскольку все программы, кроме самых простых,

опираются на то, что элементы комбинации сами могут быть комбинациями. В этом

разделе мы рассмотрим, какое значение замыкание имеет для составных данных. Мы

опишем несколько распр остраненных методов использования пар для представления по-

следовательностей и деревьев, а также построим графический язык, который наглядно

иллюстрируе т замыкание

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

Одна из полезных структур, которые можно построить с помощью пар — это по-

следовательность (sequence), то есть упорядоченная совокупность объектов данных.

Разумеется, существует много способов представлен ия последовательностей при помо-

щи пар. Один, особенно простой, показан на рисунке 2.4, где последовательность 1, 2,

3, 4 представлена как цепочка пар. В каждой паре car — это соответствующий член

цепочки, а cdr — следующая пара цепочки. Cdr последней пары указывает на особое

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

линия, а в программах как значение переменной nil. Вся последовательность порожда-

ется несколькими вложенными операциями cons:

Идея, что средство комбинирования должно удовлетворять условию замыкания, очень проста. К сожале-

нию, такие средства во многих популярных языках программирования либо не удовлетворяют этому условию,

либо делают использование замыканий неудобным. В Фортране и Бейсике элементы данных обычно группи-

руются путем создания массивов — но массивы, элементы которых сами являются массивами, строить нельзя.

Паскаль и Си позволяют иметь структуры, члены которых являются структурами. Однако при этом требует-

ся, чтобы программист напрямую работал с указателями и соблюдал ограничен ие, по которому каждое поле

структуры может содержать только элементы заранее заданной формы. В отличие от Лиспа с его парами, в

этих языках нет встроенного универсального клея, который позволял бы легко работать с составными данными

единым способом. Это ограни чение дало Алану Перлису повод сказать в предисловии к этой книге: «В Паска-

ле обилие объявляемых структур данных ведет к специализации функций, которая сдерживает и наказывает

случайное взаимодействие между ними. Лучше иметь 100 функций, которые работаю т с одной структурой

данных, чем 10 функций, работающих с 10 структурами».

108

Глава 2. Построение абстракций с помощ ью данных

1 2 3 4

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

(cons 1

(cons 2

(cons 3

(cons 4 nil))))

Так ая последовательность пар, порождаемая вложенными cons-ами, называется спи-

сок (list). В Scheme имеется примитив, который называется list и помогает стро -

ить списки

. Вышеуказ анную последовательно сть можно было бы получить с помощью

(list 1 2 3 4). В общем случае

(list ha

i ha

i ... ha

эквивалентно

(cons ha

i (consha

i (cons ... (cons ha

i nil) ... )))

По традиции, Лисп-сис темы печатают списки в виде последовательности их элементов,

заключенной в скобки. Таким образом, объект данных с рисунка 2.4 выводится как (1

2 3 4):

(define one-through-four (list 1 2 3 4))

one-through-four

(1 2 3 4)

Внимание: не путайте выражение (list 1 2 3 4) со списком (1 2 3 4), который

является результатом вычисления этого выражения. Попытка вычислить выражение (1

2 3 4) приведет к сообщению об ошибке, когда интерпретатор попробует применить

процедуру 1 к аргументам 1, 2, 3 и 4.

Мы можем считать, что процедура car выбирает первый элемент из списка, а cdr

возвращает подсписок, состоящий из всех элементов, кроме первого. Вложенные при-

менения car и cdr могут выбрать второй, третий и последующие элементы списка

В этой книге термин список всегда означает цепочку пар, которая завершается маркером конца списка.

Напротив, термин списковая структура (list structure) относится к любой структуре данных, составленной

из пар, а не только к спискам.

Поскольку записывать вложенные применения car и cdr громоздко, в диалектах Лиспа существуют

сокращения — например,

(cadr hаргi) = (car (cdr hаргi))

У всех таких процедур имена начинаются с c, а кончаются на r. Каждое a между ними означает операцию

car, а каждое d операцию cdr, и они применяются в том же порядке, в каком идут внутри имени. Имена

car и cdr сохраняются, поскольку простые их комбинации вроде cadr нетрудно произнести.

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

109

Конструктор cons порождает список, подобный исходному, но с дополнительным эле-

ментом в начале.

(car one-through-four)

(cdr one-through-four)

(2 3 4)

(car (cdr one-through-four))

(cons 10 one-through-four)

(10 1 2 3 4)

(cons 5 one-through-four)

(5 1 2 3 4)

Значение nil, которым завершается цепочка пар, можно рассматривать как последова-

тельность без элементов, пустой список (empty list). Слово nil произошло от стяжения

латинского nihil, что значит «ничто»

Операции со списками

Использованию пар для представления последовател ьностей элементов в виде спис -

ков сопутствуют общепринятые методы программирования, которые, работая со списка-

ми, последовательно их « у cdrивают». Например, процедура list-ref берет в качестве

аргументов список и число n и возвращает n-й элемент списка. Обычно элементы списка

нумеруют, начиная с 0. Метод вычисления list-ref следующий:

• Если n = 0, list-ref долж на вернуть car списка.

• В ос тальных случаях list-ref должна вернуть (n −1)-й элемент от cdr списка.

(define (list-ref items n)

(if (= n 0)

(car items)

(list-ref (cdr items) (- n 1))))

(define squares (list 1 4 9 16 25))

(list-ref squares 3)

Удивительно, сколько энергии при стандартизации диалектов Лиспа было потрачено на споры буквально

ни о чем: должно ли слово nil быть обычным именем? Должно ли значение nil являться символом? Должно

ли оно являться списком? Парой? В Scheme nil — обычное имя, и в этом разделе мы используем его как

переменную, значение которой — маркер конца списка (так же, как true — это обычная переменная, значе-

ние которой истина). Другие диалекты Лиспа, включая Common Lisp, рассматривают nil как специальный

символ. Авторы этой книги пережили слишком много скандалов со стандартизацией языков и хотели бы не

возвращаться к этим вопросам. Как только в разделе 2.3 мы введем кавычку, мы станем обозначать пустой

список в виде ’(), а от переменной nil полностью избавимся.

110

Глава 2. Построение абстракций с помощ ью данных

Часто мы проcdrиваем весь список. Чтобы помочь нам с этим, Scheme включает элемен-

тарную процедуру null?, которая определяе т, является л и ее аргумент пустым списком.

Процедура length, которая возвращает ч исло элементов в списке, иллюстрирует эту

характерную схему использования операций над списками:

(define (length items)

(if (null? items)

(+ 1 (length (cdr items)))))

(define odds (list 1 3 5 7))

(length odds)

Процедура length реализует простую рекурсивную схему. Шаг редукции таков:

• Длина любого списка равняется 1 плюс длина cdr этого списка

Этот шаг последовательно применяется, пока мы не достигнем базового случая:

• Длина пустого списка равна 0.

Мы можем вычислить length и в итеративном стиле:

(define (length items)

(define (length-iter a count)

(if (null? a)

count

(length-iter (cdr a) (+ 1 count))))

(length-iter items 0))

Еще один распространенный программистский прием состоит в том, что бы «с consить»

результат по ходу уcdrивания списка, как это делает процедура append, которая берет

в качестве аргументов два списка и составляет из их элементов один общий список:

(append squares odds)

(1 4 9 16 25 1 3 5 7)

(append odds squares)

(1 3 5 7 1 4 9 16 25)

Append также реализуется по рекурсивной схеме. Чтобы соединить списки list1 и

list2, нужно сделать следующее:

• Если список list1 пуст, то р езультатом является просто list2.

• В противном случае, нужно соединить cdr от list1 с list2, а к результату

прибавить car от list1 с помощью cons:

(define (append list1 list2)

(if (null? list1)

list2

(cons (car list1) (append (cdr list1) list2))))