Абельсон Х., Сассман Д.Д. Структура и интерпретация компьютерных программ
Подождите немного. Документ загружается.
Harold Abelson
and Gerald Jay Sussman
with Julie Sussman
Structure and Interpretation
of Computer Programs
The MIT Press
Cambridge, Massatchusetts London, England
The McGraw-Hill Companies, Inc.
New York St.Louis San Francisco Montreal Toronto
Харольд Абельсон
Джеральд Джей Сассман
при участии Джули Сассман
Структура и интерпретация
компьютерных программ
Добросвет, 2006
3
Эта книга посвящается, с уважением и любовью, духу, который живет внутри
компьютера.
“Мне кажется, чрезвычайно важно, чтобы мы, занимаясь информатикой, по-
лучали радость от общения с компьютером. С самого начала это было гро-
мадным удовольствием. Конечно, время от времени встревали заказчики , и
через какое-то время мы стали серьезно относиться к их жалобам. Нам стало
казаться, что мы вправду отвечаем за то, чтобы эти машины использовались
успешно и безошибоч но. Я не думаю, что это так. Я считаю, что мы отвечаем
за то, чтобы их тренировать, указывать им новые направления и поддержи-
вать уют в доме. Я надеюсь, что информатика никогда не перестанет быть
радостью. Я надеюсь, что мы не превратимся в миссионеров. Не надо чув-
ствовать себя продавцом Библий. Таких в мире и так достаточно. То, что Вы
знаете о программировании, могут выучить и другие. Не думайте, что в ва-
ших руках ключ к успешной работе с компьютерами. Что у Вас, как я думаю
и надеюсь, есть — это разум: способность увидеть в машине больше, чем Вы
видели, когда Вас впервые к ней подвели, увидеть, что Вы способны сделать
ее б
´
oльшим.”
Алан Дж. Перлис (1 апреля 1922 – 7 февраля 1990)
Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Предисловие ко вт орому изданию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Предисловие к первому изданию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Благодарности .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1. По строение абстракций с помощью процедур ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.1. Элементы программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.1.1. Выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.1.2. Имена и окружение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.1.3. Вычисление комбинаций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.1.4. Составные процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.1.5. Подстановоч ная модель применения процедуры . . . . . . . . . . . . . . . . . . . . 33
1.1.6. Условные выражения и предикаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.1.7. Пример: вычисление квадратного корня методом Ньютона . . . . . . . . . . 40
1.1.8. Процедуры как абстракции типа «черный ящик» . . . . . . . . . . . . . . . . . . . 43
1.2. Процедуры и порождаемые ими процессы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
1.2.1. Линейные рекурсия и итерация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.2.2. Древовидная рекурсия. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.2.3. Порядки роста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
1.2.4. Возведение в степень . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
1.2.5. Нахождение наибольшего общего дели те ля . . . . . . . . . . . . . . . . . . . . . . . . 62
1.2.6. Пример: проверка на простоту . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
1.3. Формулирование абстракций с помощью процедур высших порядков . . . . . . 69
1.3.1. Процедуры в качестве аргументов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
1.3.2. Построение процедур с помощью lambda . . . . . . . . . . . . . . . . . . . . . . . . . 74
1.3.3. Процедуры как обобщен ные методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
1.3.4. Процедуры как возвращаемые значения . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2. По строение абстракций с помощью данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
2.1. Введение в абстракци ю данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
2.1.1. Пример: арифметические операции над рациональными числами . . . . 93
2.1.2. Барьеры абстракции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5
6
Оглавление
2.1.3. Что значит слово « данные»? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2.1.4. Расшир енный пример: интервальная арифметика . . . . . . . . . . . . . . . . . . . 102
2.2. Иерархические данные и свойство замыкан ия . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
2.2.1. Представление последовательностей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
2.2.2. Иерархические структуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
2.2.3. Последовательности как стандартные интерфейсы . . . . . . . . . . . . . . . . . . 120
2.2.4. Пример: язык описания изображений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
2.3. Символьные данные. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
2.3.1. Кавычки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
2.3.2. Пример: символьное ди фференцирование . . . . . . . . . . . . . . . . . . . . . . . . . . 149
2.3.3. Пример: представление множес тв . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
2.3.4. Пример: деревья кодирования по Хаффману . . . . . . . . . . . . . . . . . . . . . . . 163
2.4. Множественные предс тавления для абстрактных данных . . . . . . . . . . . . . . . . . . 170
2.4.1. Представления комплексных чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
2.4.2. Помеченные данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
2.4.3. Программирование, управляемое данными, и аддитивность . . . . . . . . . 179
2.5. Системы с обобщенными операциями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
2.5.1. Обобщенные арифметические операции . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
2.5.2. Сочетание данных различн ых типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
2.5.3. Пример: символьная алгебра . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
3. Модульность, объекты и состояние . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
3.1. Присваивание и внутреннее состоя ние объектов . . . . . . . . . . . . . . . . . . . . . . . . . . 212
3.1.1. Внутренние переменные состояния . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
3.1.2. Преимущества присваивания. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
3.1.3. Издержки, связанные с введением присваивания . . . . . . . . . . . . . . . . . . . 221
3.2. Модель вычислений с окружениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
3.2.1. Правила вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
3.2.2. Применение простых процедур . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
3.2.3. Кадры как хранилище внутреннего состояни я . . . . . . . . . . . . . . . . . . . . . . 234
3.2.4. Внутренние опреде ления. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
3.3. Моделирование при помощи изменяемых данн ых . . . . . . . . . . . . . . . . . . . . . . . . . 241
3.3.1. Изменяемая списковая структура. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
3.3.2. Представление очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
3.3.3. Представление таблиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
3.3.4. Имитация цифровых схем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
3.3.5. Распространение ограничений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
3.4. Параллелизм: время имеет значение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
3.4.1. Природа времен и в параллельных системах . . . . . . . . . . . . . . . . . . . . . . . . 284
3.4.2. Механизмы управления параллелизмом . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
3.5. Потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
3.5.1. Потоки как задержанные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
3.5.2. Бесконечные потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
3.5.3. Использование парадигмы потоков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
3.5.4. Потоки и задержанное вычисление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
Оглавление
7
3.5.5. Модульность функционал ьных программ
и модульность объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
4. Метаязыковая абстракция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
4.1. Метацикл ический интерпретатор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
4.1.1. Ядро интерпре татора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
4.1.2. Представление выражений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
4.1.3. Структуры данных интерпре татора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
4.1.4. Выполнение интерпретатора как программы. . . . . . . . . . . . . . . . . . . . . . . . 354
4.1.5. Данные как программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
4.1.6. Внутренние опреде ления. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
4.1.7. Отделение синтаксического анализа от выполнения . . . . . . . . . . . . . . . . 365
4.2. Scheme с вариациями: ленивый интерпретатор . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
4.2.1. Нормальный порядок вычислен ий и аппликативный порядок вычис-
лений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
4.2.2. Интерпретатор с ленивым вычислением . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
4.2.3. Потоки как лени вые списки. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
4.3. Scheme с вариациями —
недетерминистское вычисление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
4.3.1. Amb и search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
4.3.2. Примеры недетерминистских программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
4.3.3. Реализация amb-интерпретатора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
4.4. Логиче ское программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
4.4.1. Дедуктивный поиск информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
4.4.2. Как действует система обработки запросов . . . . . . . . . . . . . . . . . . . . . . . . 417
4.4.3. Является ли логическое программирование математической логикой? 425
4.4.4. Реализация запросной системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
5. Вычисления на регистровых машинах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
5.1. Проектирование регистровых машин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
5.1.1. Язык для описания регистровых машин . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
5.1.2. Абстракция в проектировании машин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
5.1.3. Подпрограммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
5.1.4. Реализация рекурсии с помощью стека . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
5.1.5. Обзор системы команд . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
5.2. Программа моделирования регистровых машин . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
5.2.1. Модель машины . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
5.2.2. Ассемблер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
5.2.3. Порождение исполнительных процедур для команд . . . . . . . . . . . . . . . . . 480
5.2.4. Отслеживание производительности машины . . . . . . . . . . . . . . . . . . . . . . . 486
5.3. Выделение памяти и сборка мусора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
5.3.1. Память как векторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
5.3.2. Иллюзия бесконечной памяти . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
5.4. Вычислитель с явным управлением . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
5.4.1. Ядро вычислителя с явным управлением . . . . . . . . . . . . . . . . . . . . . . . . . . 502
5.4.2. Вычисление последовате льностей и хвостовая рекурсия . . . . . . . . . . . . 507
5.4.3. Условные выражения, присваивания и определения . . . . . . . . . . . . . . . . . 510
5.4.4. Запуск вычислителя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
5.5. Компиляция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
5.5.1. Структура компилятора. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
5.5.2. Компиляция выражений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
5.5.3. Компиляция комбинаций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
5.5.4. Сочетание последовательностей команд . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
5.5.5. Пример скомпил ированного кода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
5.5.6. Лексическая адресация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
5.5.7. Связь скомпилированного кода с вычислителем . . . . . . . . . . . . . . . . . . . . 551
Литература. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566
Предисловие
Программированием зани маются учителя, генералы, диетологи, психологи и родите-
ли. Программированию подвергаются армии, ученики и некоторые виды о бществ. При
решении крупных задач приходится применять последовательно множество программ,
б
´
ольшая часть которых возникает прямо в пр оцессе решен ия. Эти программы изобилу-
ют деталями, относящимися к той конкретной задаче, которую они решают. Если же
Вы хотите оценить программирование как интеллектуальную деятельность особого ро-
да, то Вам следует обратиться к программированию компьютеров; читайте и пишите
компьютерные программы — много программ. Не так уж важно, что будет в них напи-
сано и как они будут примен яться. Важно то, насколько хорошо они работают и как
гладко с тыкуются с другими программами при создании еще более крупных программ.
Программист должен равно стремиться и к совершенству в деталях, и к соразмерности
сложного целого. В книге, которую Вы держите в руках, словом «программирование» мы
будем обозначать прежде всего создание, выполнение и изучение программ, написанных
на одном из диалектов языка Лисп и предназначенных для выполнения на цифровом
компьютере. Использование Лиспа не ограничивает нас в том, чт
´
о мы можем описать в
наших программах, — лишь в способе их выражения.
Продвигаясь по материалу этой книги, мы будем встречаться с тремя группами яв-
лений: человеческ ий разум, совокупности компьютерных программ и компьютер. Всякая
компьютерная программа — это порожденная человеческим разумом модель реального
либо умозрительного процесса. Эти процессы, возникающие из нашего опыта и мысли,
многочисленны, сложны в деталях, и мы всегда понимаем их лишь частично. Редко
бывает так, что компьютерные программы отображают их к нашему окончательному
удовлетворению. Таким образом, хотя наши програм м ы представляют собой тщатель-
но сработанные дискретные совокупности символов, мозаики переплетенных функций ,
они непрерывно развиваются: мы изменяем их по мере того, как наше восприятие мо-
дели приобретает все большую глубину, расширяется и обобщается, до тех пор, пока
модель не достигнет, наконец, метастабильного состояния в рамках следующей модели,
над которой нам предстоит биться. Радостное возбуждение, сопутствующее компьютер-
ному программированию, происходит из постоянного раскрытия в голове и в компьютере
все новых выраженных в виде программ механизмов и из взрыва восприятия, который
они порождают. Искусство выражает наши мечты. Компьютер исполняет их под видом
программ!
При всей своей мощности, компьютер требователен и придирчив. Ему нужны верные
программы, и то, что мы хотим ему сказать, должно быть выражено точно в каждой
мелочи. Как и при всякой другой работе с символами, мы убеждаемся в правильности
10
Предисловие
программ через доказательство. Самому Лиспу мож но сопоставить семантику (между
прочим, тоже модель), и если функцию программ ы можно выразить, скажем, в терми-
нах исчисления предикатов, то логические методы позволят нам вывести формальное
доказательство ее корректности. К сожалению, когда программы становятся больши-
ми и сложными, что с ними всегда и происходит, адекватность, непротиворечивость и
корректность самих спецификаций становится предметом сомнений, так что большие
программы редко сопровождаются полными формальными доказательствами корректно-
сти. Поскольку большие программы вырас тают из малых, нам необходимо обзавестись
арсеналом программных структур, в правильности которых мы можем быть уверены —
их можно назвать идиомами — и научиться объединя ть их в структуры большего разме-
ра с помощью организационных методов, ценность которых также доказана. Эти методы
подробно обсуждаются в книге, и их понимание существенно для участия в прометеев-
ском предприятии под названием «программирование». Для у мения создавать большие,
значительные программы нет лучшего помощника, чем свободное владение мощными
организационными методами. И наоборот: затраты, связанные с написанием больших
программ, побуждают нас изобретать новые методы уменьшения веса функций и дета-
лей, входящих в эти программы.
В отли чие от программ, компьютеры должны повиноваться законам физики. Если мы
хотим, чтобы они работали быстро — по нескольку наносекунд на смену состояния, —
электроны в их цепях не должны проходить большие расстояния (более полуметра).
При этом тесно сконцентрированные в пространстве приборы излучают тепло, которое
нужно куда-то отводить: так развилось изысканное инженерное искусство, призванное
находить равновесие между обилием функций и плотностью расположения устройств.
Так или иначе, аппаратура всегда работае т ниже того уровня , на котором мы бы хо-
тели программировать. Процессы, посредством которых наши программы на Лиспе пе-
реводятся в «машинные» программы, сами являются абс трактными моделями, которые
мы воплощаем в программах. Их изучен ие и реализация многое дают для понимания
организационных методов, направленных на програм м ирование произвольных моделей.
Разумеется, так можно смоделировать и сам компьютер. Подумайте об этом: поведение
мельчайшего переключателя моделируется квантовой механикой, которая описывается
дифференциальными уравнениями, точное поведение которых фиксируется в численных
приближениях, представленных в виде ком пьютерных программ, которые выполняются
на компьютере, составленном из ... — и так без конца!
Раздельное выделение трех групп явлений — не просто вопрос тактического удоб-
ства. Хотя эти группы и остаются, как говорится, в голове, но, проводя это разделение,
мы позволяем потоку символов между тремя группами двигаться быстрее. В челове че-
ском опыте с этим потоком по богатству, живости и обилию возможностей сравнится
разве что сама эволюция жизни. Отношения между разу мом человека, программами и
компьютером в лучшем случае метастабильны. Компьютерам никогда не хватает мощ-
ности и быстродействия . Каждый новый прорыв в технологии производства аппаратуры
ведет к появлению более масштабных программных пр оектов, новых организ ационных
принципов и к о богащению абстрактных моделей. Пусть каждый читатель время от вре-
мени спрашивает себя: «А зачем, к чему все это?» — только не слишком часто, чтобы
удовольствие от программирования не сменилось горечью философского тупика.