Харольд Абельсон, Джеральд Джей Сассман - Структура и интерпретация компьютерных программ (2004) бесплатно

Оглавление

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Предисловие ко второму изданию . . . . . . . . . . . . . . . . . . . . . ix
Предисловие к первому изданию . . . . . . . . . . . . . . . . . . . . . . xi
Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv
1 Построение абстракций с помощью процедур 1
1.1 Элементы программирования . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Имена и окружение . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 Вычисление комбинаций . . . . . . . . . . . . . . . . . . . 8
1.1.4 Составные процедуры . . . . . . . . . . . . . . . . . . . . . 10
1.1.5 Подстановочная модель применения процедуры . . . . . . 11
1.1.6 Условные выражения и предикаты . . . . . . . . . . . . . . 14
1.1.7 Пример: вычисление квадратного корня методом Ньютона 18
1.1.8 Процедуры как абстракции типа «черный ящик» . . . . . 22
1.2 Процедуры и порождаемые ими процессы . . . . . . . . . . . . . . 26
1.2.1 Линейные рекурсия и итерация . . . . . . . . . . . . . . . 27
1.2.2 Древовидная рекурсия . . . . . . . . . . . . . . . . . . . . 31
1.2.3 Порядки роста . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.2.4 Возведение в степень . . . . . . . . . . . . . . . . . . . . . 37
1.2.5 Нахождение наибольшего общего делителя . . . . . . . . 40
1.2.6 Пример: проверка на простоту . . . . . . . . . . . . . . . . 42
1.3 Формулирование абстракций с помощью процедур высших по-
рядков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
1.3.1 Процедуры в качестве аргументов . . . . . . . . . . . . . . 48
1.3.2 Построение процедур с помощью lambda . . . . . . . . . 52
1.3.3 Процедуры как обобщенные методы . . . . . . . . . . . . . 56
1.3.4 Процедуры как возвращаемые значения . . . . . . . . . . . 61
2 Построение абстракций с помощью данных 67
2.1 Введение в абстракцию данных . . . . . . . . . . . . . . . . . . . 70
2.1.1 Пример: арифметические операции над рациональными
числами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.1.2 Барьеры абстракции . . . . . . . . . . . . . . . . . . . . . . 74
2.1.3 Что значит слово «данные»? . . . . . . . . . . . . . . . . . 76
2.1.4 Расширенный пример: интервальная арифметика . . . . . 79
2.2 Иерархические данные и свойство замыкания . . . . . . . . . . . 82
2.2.1 Представление последовательностей . . . . . . . . . . . . . 84
2.2.2 Иерархические структуры . . . . . . . . . . . . . . . . . . . 91
2.2.3 Последовательности как стандартные интерфейсы . . . . . 96
2.2.4 Пример: язык описания изображений . . . . . . . . . . . . 107
2.3 Символьные данные . . . . . . . . . . . . . . . . . . . . . . . . . . 122
2.3.1 Кавычки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
2.3.2 Пример: символьное дифференцирование . . . . . . . . . . 125
2.3.3 Пример: представление множеств . . . . . . . . . . . . . . 130
2.3.4 Пример: деревья кодирования по Хаффману . . . . . . . . 139
2.4 Множественные представления для абстрактных данных . . . . . 145
2.4.1 Представления комплексных чисел . . . . . . . . . . . . . 147
2.4.2 Помеченные данные . . . . . . . . . . . . . . . . . . . . . . 150
2.4.3 Программирование, управляемое данными, и аддитивность 154
2.5 Системы с обобщенными операциями . . . . . . . . . . . . . . . . 161
2.5.1 Обобщенные арифметические операции . . . . . . . . . . . 162
2.5.2 Сочетание данных различных типов . . . . . . . . . . . . . 166
2.5.3 Пример: символьная алгебра . . . . . . . . . . . . . . . . . 173
3 Модульность, объекты и состояние 187
3.1 Присваивание и внутреннее состояние объектов . . . . . . . . . . 188
3.1.1 Внутренние переменные состояния . . . . . . . . . . . . . 189
3.1.2 Преимущества присваивания . . . . . . . . . . . . . . . . . 194
3.1.3 Издержки, связанные с введением присваивания . . . . . 197
3.2 Модель вычислений с окружениями . . . . . . . . . . . . . . . . . 203
3.2.1 Правила вычисления . . . . . . . . . . . . . . . . . . . . . 204
3.2.2 Применение простых процедур . . . . . . . . . . . . . . . . 207
3.2.3 Кадры как хранилище внутреннего состояния . . . . . . . 210
3.2.4 Внутренние определения . . . . . . . . . . . . . . . . . . . 214
3.3 Моделирование при помощи изменяемых данных . . . . . . . . . 217
3.3.1 Изменяемая списковая структура . . . . . . . . . . . . . . 217
3.3.2 Представление очередей. . . . . . . . . . . . . . . . . . . . 225
3.3.3 Представление таблиц . . . . . . . . . . . . . . . . . . . . . 230
3.3.4 Имитация цифровых схем . . . . . . . . . . . . . . . . . . 235
3.3.5 Распространение ограничений . . . . . . . . . . . . . . . . 246
3.4 Параллелизм: время имеет значение . . . . . . . . . . . . . . . . . 255
3.4.1 Природа времени в параллельных системах . . . . . . . . 257
3.4.2 Механизмы управления параллелизмом . . . . . . . . . . . 261
3.5 Потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
3.5.1 Потоки как задержанные списки . . . . . . . . . . . . . . . 273
3.5.2 Бесконечные потоки . . . . . . . . . . . . . . . . . . . . . . 280
3.5.3 Использование парадигмы потоков . . . . . . . . . . . . . 287
3.5.4 Потоки и задержанное вычисление . . . . . . . . . . . . . 297
3.5.5 Модульность функциональных программ и модульность
объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
4 Метаязыковая абстракция 307
4.1 Метациклический интерпретатор. . . . . . . . . . . . . . . . . . . 310
4.1.1 Ядро интерпретатора . . . . . . . . . . . . . . . . . . . . . 311
4.1.2 Представление выражений . . . . . . . . . . . . . . . . . . 315
4.1.3 Структуры данных интерпретатора . . . . . . . . . . . . . 322
4.1.4 Выполнение интерпретатора как программы . . . . . . . . 326
4.1.5 Данные как программы . . . . . . . . . . . . . . . . . . . . 329
4.1.6 Внутренние определения . . . . . . . . . . . . . . . . . . . 331
4.1.7 Отделение синтаксического анализа от выполнения . . . . 336
4.2 Scheme с вариациями: ленивый интерпретатор . . . . . . . . . . . 340
4.2.1 Нормальный порядок вычислений и аппликативный поря-
док вычислений . . . . . . . . . . . . . . . . . . . . . . . . 341
4.2.2 Интерпретатор с ленивым вычислением . . . . . . . . . . . 343
4.2.3 Потоки как ленивые списки . . . . . . . . . . . . . . . . . 349
4.3 Scheme с вариациями — недетерминистское вычисление . . . . . 352
4.3.1 Amb и search . . . . . . . . . . . . . . . . . . . . . . . . . 354
4.3.2 Примеры недетерминистских программ . . . . . . . . . . . 357
4.3.3 Реализация amb-интерпретатора . . . . . . . . . . . . . . . 364
4.4 Логическое программирование . . . . . . . . . . . . . . . . . . . . 374
4.4.1 Дедуктивный поиск информации. . . . . . . . . . . . . . . 377
4.4.2 Как действует система обработки запросов . . . . . . . . . 387
4.4.3 Является ли логическое программирование математиче-
ской логикой? . . . . . . . . . . . . . . . . . . . . . . . . . 394
4.4.4 Реализация запросной системы . . . . . . . . . . . . . . . 399
5 Вычисления на регистровых машинах 419
5.1 Проектирование регистровых машин . . . . . . . . . . . . . . . . 420
5.1.1 Язык для описания регистровых машин . . . . . . . . . . 423
5.1.2 Абстракция в проектировании машин . . . . . . . . . . . . 426
5.1.3 Подпрограммы . . . . . . . . . . . . . . . . . . . . . . . . . 428
5.1.4 Реализация рекурсии с помощью стека . . . . . . . . . . . 432
5.1.5 Обзор системы команд . . . . . . . . . . . . . . . . . . . . 440
5.2 Программа моделирования регистровых машин . . . . . . . . . . 441
5.2.1 Модель машины . . . . . . . . . . . . . . . . . . . . . . . . 442
5.2.2 Ассемблер. . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
5.2.3 Порождение исполнительных процедур для команд . . . . 449
5.2.4 Отслеживание производительности машины . . . . . . . . 455
5.3 Выделение памяти и сборка мусора . . . . . . . . . . . . . . . . . 458
5.3.1 Память как векторы . . . . . . . . . . . . . . . . . . . . . . 458
5.3.2 Иллюзия бесконечной памяти . . . . . . . . . . . . . . . . 463
5.4 Вычислитель с явным управлением . . . . . . . . . . . . . . . . . 469
5.4.1 Ядро вычислителя с явным управлением . . . . . . . . . . 470
5.4.2 Вычисление последовательностей и хвостовая рекурсия . 476
5.4.3 Условные выражения, присваивания и определения . . . . 478
5.4.4 Запуск вычислителя . . . . . . . . . . . . . . . . . . . . . . 480
5.5 Компиляция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
5.5.1 Структура компилятора . . . . . . . . . . . . . . . . . . . . 488
5.5.2 Компиляция выражений . . . . . . . . . . . . . . . . . . . . 493
5.5.3 Компиляция комбинаций . . . . . . . . . . . . . . . . . . . 498
5.5.4 Сочетание последовательностей команд . . . . . . . . . . . 504
5.5.5 Пример скомпилированного кода . . . . . . . . . . . . . . . 507
5.5.6 Лексическая адресация . . . . . . . . . . . . . . . . . . . . 515
5.5.7 Связь скомпилированного кода с вычислителем . . . . . . 518
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . 533