Харольд Абельсон - Структура и интерпретация компьютерных программ

Harold Abelson
and

Gerald Jay Sussman
with

Julie Sussman

Structure and Interpretation
of Computer Programs

The MIT Press
Cambridge, Massatchusetts
New York

The McGraw-Hill Companies, Inc.
St.Louis
San Francisco
Montreal

London, England
Toronto

Харольд Абельсон
Джеральд Джей Сассман
при участии

Джули Сассман

Структура и интерпретация
компьютерных программ
Добросвет, 2006

3

Эта книга посвящается, с уважением и любовью, духу, который живет внутри
компьютера.

“Мне кажется, чрезвычайно важно, чтобы мы, занимаясь информатикой, получали радость от общения с компьютером. С самого начала это было громадным удовольствием. Конечно, время от времени встревали заказчики, и
через какое-то время мы стали серьезно относиться к их жалобам. Нам стало
казаться, что мы вправду отвечаем за то, чтобы эти машины использовались
успешно и безошибочно. Я не думаю, что это так. Я считаю, что мы отвечаем
за то, чтобы их тренировать, указывать им новые направления и поддерживать уют в доме. Я надеюсь, что информатика никогда не перестанет быть
радостью. Я надеюсь, что мы не превратимся в миссионеров. Не надо чувствовать себя продавцом Библий. Таких в мире и так достаточно. То, что Вы
знаете о программировании, могут выучить и другие. Не думайте, что в ваших руках ключ к успешной работе с компьютерами. Что у Вас, как я думаю
и надеюсь, есть — это разум: способность увидеть в машине больше, чем Вы
видели, когда Вас впервые к ней подвели, увидеть, что Вы способны сделать
ее бóльшим.”
Алан Дж. Перлис (1 апреля 1922 – 7 февраля 1990)

Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

Предисловие ко второму изданию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Предисловие к первому изданию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1. Построение абстракций с помощью процедур . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1. Элементы программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1. Выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.2. Имена и окружение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.3. Вычисление комбинаций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.4. Составные процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.5. Подстановочная модель применения процедуры . . . . . . . . . . . . . . . . . . . .
1.1.6. Условные выражения и предикаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.7. Пример: вычисление квадратного корня методом Ньютона . . . . . . . . . .
1.1.8. Процедуры как абстракции типа «черный ящик» . . . . . . . . . . . . . . . . . . .
1.2. Процедуры и порождаемые ими процессы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1. Линейные рекурсия и итерация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.2. Древовидная рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.3. Порядки роста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.4. Возведение в степень . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.5. Нахождение наибольшего общего делителя . . . . . . . . . . . . . . . . . . . . . . . .
1.2.6. Пример: проверка на простоту . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Формулирование абстракций с помощью процедур высших порядков . . . . . .
1.3.1. Процедуры в качестве аргументов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2. Построение процедур с помощью lambda . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.3. Процедуры как обобщенные методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.4. Процедуры как возвращаемые значения . . . . . . . . . . . . . . . . . . . . . . . . . . .

22
25
26
27
29
31
33
35
40
43
47
48
53
58
59
62
64
69
70
74
78
83

2. Построение абстракций с помощью данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1. Введение в абстракцию данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Пример: арифметические операции над рациональными числами . . . .
2.1.2. Барьеры абстракции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

90
93
93
97

5

Оглавление

6

2.2.

2.3.

2.4.

2.5.

2.1.3. Что значит слово «данные»? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2.1.4. Расширенный пример: интервальная арифметика . . . . . . . . . . . . . . . . . . . 102
Иерархические данные и свойство замыкания . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
2.2.1. Представление последовательностей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
2.2.2. Иерархические --">