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

Москва, 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

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

Всем нам приходилось тратить уйму лишнего времени за попытками уломать кусок
старого кода на выполнение задач, которые мы не представляли себе, когда его
исходно писали. Это ужасная трата времени и сил. К сожалению, на нас действует
множество сил, побуждающих нас писать программы, хорошо приспособленные к
конкретной узкой задаче, где почти нет многократно используемых частей. Однако
мы считаем, что так быть не должно.
Строить системы, приемлемо работающие в более широком классе ситуаций, чем
их создатели исходно имели в виду, трудно. Лучшие из таких систем способны к развитию: 
их можно приспособить к новым задачам ценой лишь небольших изменений.
Как мы можем проектировать системы, гибкие в этом смысле?
Было бы замечательно, если бы для добавления новой возможности к программе
нам нужно было бы только добавить немного кода, без изменения существующего
массива программы. Часто этого можно добиться, если использовать определeнные
организационные принципы при построении этого массива и включать в него соответствующие 
зацепки.
Многое о построении гибких, способных к развитию систем можно узнать из наблюдения 
за биологическими системами. Приeмы, исходно разработанные для поддержки 
символического искусственного интеллекта, можно рассматривать как способы 
увеличить гибкость и приспособляемость программ и других инженерных систем. 
Напротив, многие практики, принятые в информатике, активно препятствуют
построению систем, которые легко перестроить для использования в новых условиях.

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

Эта книга

Эта книга появилась в процессе преподавания компьютерного программирования в
Массачусетском технологическом институте (MIT). Мы начали вести этот курс много 
лет назад, желая показать старшекурсникам и аспирантам методы и технологии,
полезные при решении основных задач в области искусственного интеллекта, таких
как символическая математика и системы, основанные на правилах. Мы хотели,

11

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

чтобы студенты были способны строить эти системы гибко, чтобы их можно было
легко сочетать при построении ещe более мощных программ. Кроме того, мы хотели
обучить студентов рассуждать о зависимостях — как их отслеживать, использовать
для объяснения поведения и как с их помощью управлять перебором.
Несмотря на то что наш курс был и остаeтся успешным, оказалось, что в начале 
мы понимали материал не настолько хорошо, как сами об этом думали. Поэтому 
пришлось потратить немало сил на полировку своих инструментов и уточнение
идей. Теперь мы понимаем, что эти методы работают далеко не только в области
искусственного интеллекта. Мы считаем, что нашим опытом может воспользоваться 
любой, кто строит сложные системы, например компиляторы и интегрированные
среды разработки. Книга построена на основе лекций и упражнений, которые мы
сейчас используем в своeм курсе.

Содержание

В этой книге намного больше материала, чем можно пройти за односеместровый
курс. Поэтому каждый год мы отбираем некоторую часть для использования в
классе. Глава 1 представляет собой введение в нашу философию программирования. 
Здесь мы демонстрируем понятие гибкости в общем контексте природы и техники. 
Мы стараемся показать, что гибкость столь же важна, как эффективность и
правильность поведения. В каждой последующей главе мы вводим некоторый общий 
метод и иллюстрируем его набором упражнений. Это важный организующий
принцип всей книги.
В главе 2 исследуем некоторые универсально применимые способы построения
систем, способных к росту. Мощный метод организации гибкой системы — построить 
еe в виде набора языков специального назначения, каждый из которых приспособлен 
для описания некоторой подсистемы. Здесь мы разрабатываем основной
инструментарий для построения специализированных языков: показываем, как подсистемы 
можно организовать из взаимозаменяемых частей, как их можно гибко соединять 
с помощью комбинаторов, как части системы обобщаются через обeртки
и как программу часто можно упростить, абстрагируя модель предметной области.
В главе 3 мы вводим чрезвычайно мощный, хотя потенциально опасный метод 
использования полиморфных процедур, управляемых предикатами. В начале мы
строим обобщение арифметики для работы с символьными алгебраическими выражениями. 
Затем показываем, как такое обобщение можно сделать эффективным с
помощью меток типа на данных, и демонстрируем силу нашего метода на примере
простой, но легко расширяемой игры-бродилки.
В главе 4 мы вводим понятие сопоставления с образцом, сначала для использования 
в системах переписывания термов, затем через унификацию показываем,
как легко можно построить вывод типов. Сегментные переменные заставляют нас
использовать перебор с возвратами. Унификация — первый случай, где мы видим
силу представления и комбинирования структур с частичной информацией. В конце
главы мы расширяем эту идею на задачу сопоставления в произвольных графах.
В главе 5 мы исследуем возможности интерпретации и компиляции. Мы считаем, 
что программисты должны быть способны выйти за рамки своего языка программирования, 
каков бы он ни был, и использовать язык, лучше приспособленный
для решения конкретной задачи. Мы также показываем, как естественным образом 
встроить в язык перебор с возвратами путeм реализации в составе интерпре-

татора/компилятора оператора недетерминистского выбора amb и как использовать
продолжения.
В главе 6 мы показываем построение систем многослойных данных и многослойных 
процедур, где к каждому элементу данных могут в качестве аннотации быть
прикреплены метаданные различного рода. Метаданные никак не влияют на обработку 
нижележащих данных, и код для обработки нижележащих данных не обязан
даже знать о них и на них ссылаться. Однако метаданные обрабатываются своими
собственными процедурами, в сущности, параллельно основным данным. В качестве 
иллюстрации мы присоединяем к числовым данным информацию о единицах
измерения, а также демонстрируем отслеживание зависимостей, так что каждый
элемент данных оказывается снабжeн родословной, показывающей, как он получен
из элементарных источников.
Всe это собирается вместе в главе 7, где мы вводим распространение, чтобы
освободиться от парадигмы компьютерных языков, ориентированной на выражения.
Здесь мы смотрим на соединение модулей как на монтажную схему. Это позволяет 
нам гибко подключать различные источники частичной информации. Поскольку
мы отслеживаем зависимости с помощью многослойных данных, то способны организовать 
перебор, управляемый зависимостями, который значительно уменьшает
пространство поиска в больших и сложных системах.
С помощью этой книги можно построить несколько вариантов университетского
курса продвинутого уровня. Идея комбинаторов из главы 2 и полиморфные процедуры 
из главы 3 используются во всех последующих главах. Однако образцы и
сопоставление из главы 4, а также вычислители из главы 5 в дальнейших главах
не встречаются. Единственный материал из главы 5, необходимый в дальнейшем, —
оператор amb из разделов 5.4 и 5.4.1. Идея многослойности из главы 6 близко связана
с идеей полиморфных процедур, но с некоторым новым поворотом. Использование
многослойных данных для отслеживания зависимостей, которое в главе 6 служит
примером, становится важным компонентом системы в работе над распространением 
в главе 7, где зависимости служат для оптимизации поиска с возвратами.

Scheme

Программы в этой книге написаны на Scheme, функциональном по преимуществу
языке, который является вариантом Lisp. Несмотря на то что Scheme не популярный
язык и не используется широко в промышленном программировании, для этой книги
он — правильный выбор1. Цель этой книги — демонстрация и объяснение идей. По
многим причинам представление кода, воплощающего и иллюстрирующего эти идеи,
на Scheme оказывается короче и проще, чем на более популярных языках. Некоторые
из наших идей на других языках было бы почти невозможно выразить.
Языки из других семейств, кроме Lisp, требуют множества церемоний, чтобы
сказать простые вещи. В нашем же случае единственное, что удлинняет наш код, —
описательные имена для вычислительных объектов.
Благодаря тому, что синтаксис Scheme чрезвычайно прост — это всего лишь
представление естественного дерева разбора, и требуется лишь минимальный синтаксический 
анализ, — легко оказывается писать программы, работающие с текстами 
других программ, такие как интерпретаторы, компиляторы и обработчики
алгебраических выражений.

1Мы даeм краткое введение в Scheme в приложении B.