УДК 004.4
ББК 32.372
Х19
Х19 Хансон К., Сассман Д. Дж.
Проектирование гибких программ / пер. с англ. Ю. Бронникова. – М.:
ДМК Пресс, 2022. – 374 с.: ил.
ISBN 978-5-97060-955-2
Бывает так, что при написании программы вы попадаете в тупик.
Возможно, это потому, что вы, как оказалось, не учли некоторые особенности
исходной задачи. Однако до обидного часто дело в том, что на начальной
стадии проектирования вы приняли какое-то решение, выбрали
какую-то структуру данных или способ организации кода, который
затем оказался слишком ограниченным, а теперь его трудно заменить.
Эта книга служит мастер-классом по стратегиям организации программ,
которые позволяют сохранить гибкость. В каждой главе можно
видеть, как два эксперта демонстрируют тот или иной передовой метод,
шаг за шагом разрабатывая работающую подсистему, объясняют на ходу
стратегию своей работы и время от времени указывают на подводный
камень или способ обойти то или иное ограничение.
Издание предназначено для разработчиков, стремящихся создавать
адаптивные системы, которые можно менять с минимальными усилиями.
Copyright
Original English language edition published by The MIT Press, MA. Copyright ©
Права на издание получены при помощи агенства Александра Корженевского (Москва)
2021 Chris Hanson, Gerald Jay Sussman. Russian-language edition copyright © 2022 by DMK
Press. All rights reserved. The rights to the Russian-language edition obtained through Alexander
Korzhenevski Agency (Moscow)
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой
бы то ни было форме и какими бы то ни было средствами без письменного разрешения
владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность
технических ошибок все равно существует, издательство не может гарантировать
абсолютную точность и правильность приводимых сведений. В связи с этим издательство
не несет ответственности за возможные ошибки, связанные с использованием книги.
Права на издание получены при помощи агенства Александра Корженевского (Москва).
ISBN 978-0-26204-549-0 (англ.)
ISBN 978-5-97060-955-2 (рус.)
© 2021 Massachusetts Institute of Technology
© Оформление, перевод на русский язык,
издание, ДМК Пресс, 2022
Стр.3
Оглавление
Предисловие
9
Предисловие авторов
Благодарности
1 Гибкость в природе и в проектировании
11
15
17
1.1 Архитектура вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2 Гибкость через умные компоненты . . . . . . . . . . . . . . . . . . . . . 22
1.3 Избыточность и дублирование . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4 Исследовательское поведение . . . . . . . . . . . . . . . . . . . . . . . . 27
1.5 Цена гибкости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2 Специализированные языки
33
2.1 Комбинаторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.1 Комбинаторы функций . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.2 Комбинаторы и планы строения . . . . . . . . . . . . . . . . . . 45
2.2 Регулярные выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.2.1 Комбинаторный язык регулярных выражений . . . . . . . . . . 47
2.2.2 Реализация транслятора . . . . . . . . . . . . . . . . . . . . . . . 48
2.3 Обертки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.3.1 Обертки со специализацией . . . . . . . . . . . . . . . . . . . . . 55
2.3.2 Реализация оберток . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.3.3 Адаптеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.4 Абстракция предметной области . . . . . . . . . . . . . . . . . . . . . . 59
2.4.1 Монолитная реализация . . . . . . . . . . . . . . . . . . . . . . . 59
2.4.2 Абстрагирование предметной области . . . . . . . . . . . . . . . 64
2.5 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3 Вариации на арифметическую тему
71
3.1 Арифметика на комбинаторах . . . . . . . . . . . . . . . . . . . . . . . . 71
3.1.1 Простой интегратор ОДУ . . . . . . . . . . . . . . . . . . . . . . 72
3.1.2 Настройка арифметических операций . . . . . . . . . . . . . . . 74
3.1.3 Сочетание разных арифметик . . . . . . . . . . . . . . . . . . . . 76
3.1.4 Арифметика на функциях . . . . . . . . . . . . . . . . . . . . . . 81
3.1.5 Сложности с комбинаторами . . . . . . . . . . . . . . . . . . . . 84
3.2 Расширяемые полиморфные процедуры . . . . . . . . . . . . . . . . . . 87
5
Стр.6
6
Оглавление
3.2.1 Полиморфная арифметика . . . . . . . . . . . . . . . . . . . . . . 90
3.2.2 Структура зависит от порядка! . . . . . . . . . . . . . . . . . . . 93
3.2.3 Реализация полиморфных процедур . . . . . . . . . . . . . . . . 95
3.3 Пример: автоматическое дифференцирование . . . . . . . . . . . . . . . 101
3.3.1 Как работает автоматическое дифференцирование . . . . . . . . 102
3.3.2 Производные n-местных функций . . . . . . . . . . . . . . . . . 107
3.3.3 Технические детали . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.3.4 Функции-литералы от дифференциальных аргументов . . . . . 116
3.4 Эффективность полиморфных процедур . . . . . . . . . . . . . . . . . . 118
3.4.1 Префиксные графы . . . . . . . . . . . . . . . . . . . . . . . . . . 118
3.4.2 Кеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.5 Эффективные типы, определяемые пользователем . . . . . . . . . . . . 124
3.5.1 Предикаты как типы . . . . . . . . . . . . . . . . . . . . . . . . . 125
3.5.2 Отношения между предикатами . . . . . . . . . . . . . . . . . . 126
3.5.3 Предикаты как ключи для диспетчеризации . . . . . . . . . . . 127
3.5.4 Пример: игра-бродилка . . . . . . . . . . . . . . . . . . . . . . . . 129
3.6 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4 Сопоставление с образцом
145
4.1 Образцы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
4.2 Переписывание термов . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.2.1 Сегментные переменные в алгебре . . . . . . . . . . . . . . . . . 149
4.2.2 Реализация систем правил . . . . . . . . . . . . . . . . . . . . . . 151
4.2.3 Ремарка: волшебные макросы . . . . . . . . . . . . . . . . . . . . 153
4.2.4 Вызов, управляемый образцами . . . . . . . . . . . . . . . . . . . 154
4.3 Устройство сопоставителя . . . . . . . . . . . . . . . . . . . . . . . . . . 156
4.3.1 Компиляция образцов . . . . . . . . . . . . . . . . . . . . . . . . 161
4.3.2 Ограничения на переменные сопоставления . . . . . . . . . . . . 164
4.4 Унификация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
4.4.1 Как работает унификация . . . . . . . . . . . . . . . . . . . . . . 168
4.4.2 Приложение: вывод типов . . . . . . . . . . . . . . . . . . . . . . 175
4.4.3 Как работает вывод типов . . . . . . . . . . . . . . . . . . . . . . 177
4.4.4 Эксперимент: добавляем сегментные переменные . . . . . . . . 183
4.5 Сопоставление с образцом на графах . . . . . . . . . . . . . . . . . . . . 189
4.5.1 Списки как графы . . . . . . . . . . . . . . . . . . . . . . . . . . 189
4.5.2 Реализация графов . . . . . . . . . . . . . . . . . . . . . . . . . . 190
4.5.3 Сопоставление на графах . . . . . . . . . . . . . . . . . . . . . . 192
4.5.4 Шахматные доски и альтернативные перспективы для графов 194
4.5.5 Шахматные ходы . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
4.5.6 Реализация сопоставления на графах . . . . . . . . . . . . . . . 201
4.6 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
5 Вычисление
209
5.1 Полиморфный интерпретатор eval/apply . . . . . . . . . . . . . . . . . 210
5.1.1 eval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
5.1.2 apply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
5.2 Процедуры с нестрогими аргументами . . . . . . . . . . . . . . . . . . . 223
5.3 Компиляция в исполнительные процедуры . . . . . . . . . . . . . . . . 230
Стр.7
5.4 Исследовательское поведение . . . . . . . . . . . . . . . . . . . . . . . . 239
5.4.1 amb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
5.4.2 Реализация amb . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
5.5 Явная работа с нижележащими продолжениями . . . . . . . . . . . . . 247
5.5.1 Продолжения как нелокальные возвраты . . . . . . . . . . . . . 251
5.5.2 Нелокальная передача управления . . . . . . . . . . . . . . . . . 252
5.5.3 От продолжений к amb . . . . . . . . . . . . . . . . . . . . . . . . 254
5.6 Власть и ответственность . . . . . . . . . . . . . . . . . . . . . . . . . . 261
6 Слои
263
6.1 Использование слоевой структуры . . . . . . . . . . . . . . . . . . . . . 264
6.2 Реализация слоев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
6.2.1 Многослойные данные . . . . . . . . . . . . . . . . . . . . . . . . 266
6.2.2 Многослойные процедуры . . . . . . . . . . . . . . . . . . . . . . 268
6.3 Слоеная арифметика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
6.3.1 Арифметика единиц измерения . . . . . . . . . . . . . . . . . . . 272
6.4 Отслеживание зависимостей между значениями . . . . . . . . . . . . . 277
6.4.1 Слой поддержки . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
6.4.2 Хранение обоснований . . . . . . . . . . . . . . . . . . . . . . . . 282
6.5 Что обещает многослойность . . . . . . . . . . . . . . . . . . . . . . . . 283
7 Распространение информации
287
7.1 Пример: расстояния до звезд . . . . . . . . . . . . . . . . . . . . . . . . 289
7.2 Механизм распространения . . . . . . . . . . . . . . . . . . . . . . . . . 300
7.2.1 Ячейки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
7.2.2 Распространители . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
7.3 Альтернативные точки зрения . . . . . . . . . . . . . . . . . . . . . . . . 305
7.4 Слияние значений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
7.4.1 Слияние базовых значений . . . . . . . . . . . . . . . . . . . . . . 307
7.4.2 Слияние значений с поддержкой . . . . . . . . . . . . . . . . . . 308
7.4.3 Слияние множеств значений . . . . . . . . . . . . . . . . . . . . . 309
7.5 Поиск в возможных мирах . . . . . . . . . . . . . . . . . . . . . . . . . . 310
7.5.1 Перебор с возвратами, управляемый зависимостями . . . . . . . 313
7.5.2 Решение комбинаторных задач . . . . . . . . . . . . . . . . . . . 318
7.6 Распространители поддерживают дублирование . . . . . . . . . . . . . 322
8 Эпилог
A Программное обеспечение
B Scheme
Литература
Предметный указатель
325
329
331
347
357
B.1 Базовые конструкции Scheme . . . . . . . . . . . . . . . . . . . . . . . . 332
B.2 Более сложные конструкции . . . . . . . . . . . . . . . . . . . . . . . . . 344
Стр.8