Материал этой книrи был основой вводноrо курса по информатике в MIT начиная с
1980 rода. К тому времени, как было выпущено первое издание, мы преподавали этот
материал в течение четырех лет, и прошло еще двенадцать лет до появления BToporo
издания. Нам приятно, что наша работа была широко признана и включена в друrие
тексты. Мы видели, как наши ученики черпали идеи и проrраммы из этой книrи и
на их основе строили новые компьютерные системы и языки. Буквально по старому
талмудическому каламбуру, наши ученики стали нашими строителями. Мы рады, что у
нас такие одаренные ученики и такие превосходные строители.
...
Проrраммированием занимаются учителя, rенералы, диетолоrи, психолоrи и родите-
ли. Проrраммированию подверrаются армии, ученики и некоторые виды обществ. При
решении крупных задач приходится при менять последовательно множество проrрамм,
большая часть которых возникает прямо в процессе решения. Эти проrраммы изобилу-
ют деталями, относящимися к той конкретной задаче, которую они решают. Если же
Вы хотите оценить проrраммирование как интеллектуальную деятельность особоrо po-
да, то Вам следует обратиться к проrраммированию компьютеров; читайте и пишите
компьютерные проrраммы - MHoro проrрамм. Не так уж важно, что будет в них напи-
сано и как они будут при меняться. Важно то, насколько хорошо они работают и как
rладко стыкуются с друrими проrраммами при создании еще более крупных проrрамм.
Проrраммист должен равно стремиться и к совершенству в деталях, и к соразмерности
сложноrо целоrо. В книrе, которую Вы держите в руках, словом «проrраммирование» мы
будем обозначать прежде Bcero создание, выполнение и изучение проrрамм, написанных
на одном из диалектов языка Лисп и предназначенных для выполнения на цифровом
компьютере. Использование Лиспа не оrраничивает нас в том, что мы можем описать в
наших проrраммах, - лишь в способе их выражения.
...
“Мне кажется , чрезвычайно важно, чтобы мы , занимаясь информатикой , по ¬
лучали радость от общения с компьютером. С самого начала это было гро ¬
мадным удовольствием. Конечно, время от времени встревали заказчики , и
через какое-то время мы стали серьезно относиться к их жалобам. Нам стало
казаться , что мы вправду отвечаем за то, чтобы эти машины использовались
успешно и безошибочно. Я не думаю, что это так. Я считаю, что мы отвечаем
за то, чтобы их тренировать, указывать им новые направления и поддержи ¬
вать уют в доме. Я надеюсь, что информатика никогда не перестанет быть
радостью. Я надеюсь, что мы не превратимся в миссионеров. Не надо чув¬
ствовать себя продавцом Библий. Таких в мире и так достаточно. То, что Вы
знаете о программировании , могут выучить и другие. Не думайте, что в ва ¬
ших руках ключ к успешной работе с компьютерами. Что у Вас, как я думаю
и надеюсь, есть — это разум: способность увидеть в машине больше, чем Вы
видели , когда Вас впервые к ней подвели , увидеть, что Вы способны сделать
ее большим.”
Алан Дж. Перлис (1 апреля 1922 - 7 февраля 1990)
Author(s): Абельсон Х., Сассман Д.
Edition: 2
Publisher: Доброcвет
Year: 2006
Language: Russian
Pages: 608
Предисловие 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
