Проектирование гибких программ

Москва, 2022

Проектирование  
гибких программ 

Как не загнать себя в угол

Крис Хансон, Джеральд Джей Сассман

Software Design for Flexibility 

How to Avoid Programming Yourself into a Corner

Chris Hanson and Gerald Jay Sussman
foreword by Guy L. Steele Jr.

The MIT Press
Cambridge, Massachusetts
London, England

УДК  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 (англ.) 
 © 2021 Massachusetts Institute of Technology
ISBN 978-5-97060-955-2 (рус.)   
 © Оформление, перевод на русский язык, 

   издание, ДМК Пресс, 2022

Компьютер подобен скрипке.
Представьте себе новичка,
который сначала испытывает
проигрыватель, затем скрипку.
Скрипка, говорит он, звучит
ужасно. Именно этот аргумент
мы слышали от наших
гуманитариев и специалистов
по информатике. Компьютеры,
говорят они, хороши для
определенных целей, но они
недостаточно гибки. Так же и
со скрипкой, и с пишущей
машинкой, пока Вы не
научились их использовать.

Марвин Минский.
«Почему программирование —
хороший способ выражения
малопонятных и туманно
сформулированных идей»,
Проектирование и
планирование, 1967

Оглавление

Предисловие
9

Предисловие авторов
11

Благодарности
15

1
Гибкость в природе и в проектировании
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

Оглавление

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

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
Эпилог
325

A Программное обеспечение
329

B Scheme
331
B.1
Базовые конструкции Scheme . . . . . . . . . . . . . . . . . . . . . . . . 332

B.2
Более сложные конструкции . . . . . . . . . . . . . . . . . . . . . . . . . 344

Литература
347

Предметный указатель
357

Предисловие

Бывает так, что при написании программы вы попадаете в тупик. Возможно, это
потому, что вы, как оказалось, не учли некоторые особенности исходной задачи.
Однако до обидного часто дело в том, что на начальной стадии проектирования вы
приняли какое-то решение, выбрали какую-то структуру данных или способ организации кода, который затем оказался слишком ограниченным, а теперь его трудно
изменить.
Эта книга служит мастер-классом по стратегиям организации программ, которые позволяют сохранять гибкость. Все мы уже давно знаем, что, хотя для хранения
входных данных легко объявить массив фиксированного размера, такое программное решение может оказаться неприятно ограниченным и привести к тому, что нельзя станет обрабатывать строки больше какой-то длины или наборы записей свыше
некоторого фиксированного количества. Многие дыры в безопасности, особенно в
сетевом коде, случились потому, что программист выделял буфер фиксированного размера и забывал проверить, что обрабатываемые данные помещаются в этот
буфер. Динамически выделяемая память (получаемая от библиотеки вроде вызова malloc языка C или от автоматического сборщика мусора), будучи несколько
сложнее устроена, тем не менее даeт намного больше гибкости и, в качестве дополнительного преимущества, позволяет легче избегать ошибок (особенно если язык
программирования всегда проверяет обращения к массивам и убеждается, что индекс не выходит за границы). Это всего лишь простейший пример.
Некоторые ранние языки программирования, в сущности, закладывались на способ проектирования, отражающий стиль аппаратной организации, называемый Гарвардская архитектура: код программы находится здесь, данные — там, и задача
кода состоит в том, чтобы манипулировать данными. Однако такое жeсткое разделение между несмешиваемыми кодом и данными, как оказалось, слишком сильно
ограничивает организацию программ. Уже задолго до конца XX в. из опыта функциональных языков программирования (например, ML, Scheme и Haskell) и объектно
ориентированных языков (например, Simula, Smalltalk и C++) мы поняли, что у
стиля, позволяющего рассматривать данные как код, код как данные и связывать
небольшие блоки кода и относящихся к нему данных в единое целое, есть преимущества перед стилем, разделяющим код и данные как отдельные монолитные области.
Самый гибкий вид данных — структура-запись, которая может содержать не только «элементарные ячейки» вроде чисел и символов, но и ссылки на выполняемый
код, скажем, на функции. Самая мощная разновидность кода — такой, который
порождает другой код, объединeнный с точно определeнным количеством специально отобранных данных; такая связка уже не просто «указатель на функцию», но

9

Предисловие

замыкание (в функциональном языке) или объект (если язык объектно ориентированный).
Джерри Сассман и Крис Хансон используют свой более чем вековой совместный
опыт программирования и представляют набор методов, разработанных и проверенных за десятилетия преподавания в Массачусетском технологическом институте, которые позволяют ещe более расширить эту базовую стратегию достижения
гибкости. Используйте не просто функции, а полиморфные функции, открытые для
расширения так, как обычным функциям недоступно. Функции должны оставаться
маленькими. Часто лучший вариант возвращаемого значения для функции — другая функция (уточнeнная соответствующими данными). Будьте готовы относиться
к данным как к разновидности кода; иногда, если необходимо, это приводит к созданию специализированного встроенного языка внутри вашей программы. (Это один
из способов рассказать, откуда взялся язык Scheme: лисповский диалект MacLisp
не поддерживал достаточно общий вид замыкания функций, так что мы с Джерри просто написали на нeм встроенный вариант Lisp, где такие замыкания были.)
Будьте готовы заменить структуру данных структурой более общего вида, которая
включает исходную как частный случай и расширяет еe возможности. С помощью
автоматического распространения ограничений можно избежать преждевременного
решения, какие данные подаются на вход, а какие получаются на выходе.
Эта книга не является обзорной монографией или учебником — скажу повторно,
это мастер-класс. В каждой главе можно видеть, как два эксперта демонстрируют
тот или иной передовой метод, шаг за шагом разрабатывая работающую подсистему, объясняют на ходу стратегию своей работы и время от времени указывают на
подводный камень или способ обойти то или иное ограничение. Будьте готовы, когда вас попросят показать свою способность работать самостоятельно, расширить
структуру данных или дописать дополнительный код — а затем подключите своe
воображение и идите дальше, чем показали вам авторы. Идеи этой книги богаты и
глубоки; внимание как к словам, так и к программам будет вознаграждено.

Гай Стил
Лексингтон, Массачусетс.
Август 2020