Структура и интерпретация компьютерных программ

Предисловие 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
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
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. Реализация ашЬ-интерпретатора 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