УДК 004.2
ББК 32.97
Ф37
Ф37 Как проектировать программы / пер. с англ. А. Н. Киселева; под ред.
П. Б. Иванова, А. Д. Чичигина, Ю. А. Сыровецкого, С. В. Бронникова. – М.:
ДМК Пресс, 2022. – 724 с.: ил.
Фелляйзен М., Финдлер Р. Б., Флэтт М., Кришнамурти Ш.
ISBN 978-5-97060-926-2
Эта книга повествует о методах «хорошего программирования» – то есть о таком
подходе к созданию программного обеспечения, который опирается на системное
мышление, планирование и понимание задач разработчика на каждом этапе.
В числе рассматриваемых тем – фундаментальные понятия систематического
проектирования, типы данных, способы записи объемных данных, создание
и использование абстракций, тестирование программ и функций и др.
Издание адресовано профессионалам и энтузиастам программирования, не
имеющим прежнего опыта систематического проектирования программ, а также
преподавателям технических вузов, которые могут использовать представленный
материал в рамках учебного курса.
УДК 004.2
ББК 32.97
The rights to the russian launguage edition obtained thougth Alxander Korgzhenevski Agency
(Moscow). All rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой
бы то ни было форме и какими бы то ни было средствами без письменного разрешения
владельцев авторских прав.
ISBN 978-0-26253-480-2 (англ.)
ISBN 978-5-97060-926-2 (рус.)
© Massachusetts Institute of Technology, 2018
Illustrations © Torrey Butzer, 2000
© Перевод, оформление, издание, ДМК Пресс, 2022
Стр.5
Содержание
От редакторов .................................................................................................................... 10
От издательства ................................................................................................................. 11
Вступление ......................................................................................................................... 12
Пролог: как писать программы ....................................................................................... 29
I ДАННЫЕ ФИКСИРОВАННОГО РАЗМЕРА ........................................55
1 Арифметика ................................................................................................................ 56
1.1. Арифметика чисел ............................................................................................... 57
1.2. Арифметика строк................................................................................................ 59
1.3. А теперь все смешаем .......................................................................................... 61
1.4. Арифметика изображений .................................................................................. 63
1.5. Арифметика логических значений ..................................................................... 66
1.6. Смешанные операции с логическими значениями .......................................... 67
1.7. Предикаты: знай свои данные ............................................................................. 69
2 Функции и программы .............................................................................................. 72
2.1. Функции ................................................................................................................ 72
2.2. Вычисления .......................................................................................................... 76
2.3. Композиция функций .......................................................................................... 80
2.4. Глобальные константы ......................................................................................... 83
2.5. Программы ........................................................................................................... 85
3 Как проектировать программы ............................................................................... 98
3.1. Проектирование функций ................................................................................... 99
3.2. Практические упражнения: функции ................................................................106
3.3. Знание предметной области ..............................................................................106
3.4. От функций к программам .................................................................................107
3.5. О тестировании ...................................................................................................108
3.6. Проектирование интерактивных программ .....................................................110
3.7. Миры виртуальных питомцев ............................................................................120
4 Интервалы, перечисления и детализация ............................................................122
4.1. Программирование с условиями .......................................................................122
4.2. Условные вычисления .........................................................................................124
4.3. Перечисления ......................................................................................................127
4.4. Интервалы ...........................................................................................................131
4.5. Детализация ........................................................................................................135
4.6. Проектирование с использованием детализации ............................................143
4.7. Миры с конечными состояниями .......................................................................146
5 Добавляем структуру ...............................................................................................154
5.1. От позиций к структурам posn ...........................................................................154
5.2. Вычисления со структурами posn ......................................................................155
5.3. Программирование с posn ..................................................................................156
5.4. Определение структурных типов .......................................................................158
5.5. Вычисления со структурами ...............................................................................163
5.6. Программирование со структурами ..................................................................167
5.7. Вселенная данных ...............................................................................................174
Стр.6
6
Содержание
5.8. Проектирование с использованием структур ...................................................178
5.9. Структура в мире .................................................................................................181
5.10. Графический редактор ......................................................................................182
5.11. Больше виртуальных питомцев .......................................................................184
6 Структуры и детализация ........................................................................................187
6.1. Проектирование с использованием детализации, снова .................................187
6.2. Смешивание миров .............................................................................................200
6.3. Ошибки ввода ......................................................................................................203
6.4. Проверка состояния мира...................................................................................207
6.5. Предикаты равенства ..........................................................................................209
7 Итоги ...........................................................................................................................211
Интермеццо 1. Язык для начинающих студентов .......................................................212
Словарь BSL ................................................................................................................212
Грамматика BSL .........................................................................................................213
Значение в языке BSL ................................................................................................217
Значения и вычисления ............................................................................................220
Ошибки в BSL .............................................................................................................220
Логические выражения .............................................................................................223
Определения констант ..............................................................................................224
Определения структур ...............................................................................................226
Тесты в BSL .................................................................................................................228
Сообщения об ошибках в BSL ...................................................................................229
II ДАННЫЕ ПРОИЗВОЛЬНОГО РАЗМЕРА ...........................................237
8 Списки ........................................................................................................................238
8.1. Создание списков ................................................................................................238
8.2. Что такое '(), что такое cons ................................................................................243
8.3. Программирование со списками .......................................................................245
8.4. Вычисления со списками ....................................................................................249
9 Проектирование с определениями данных, ссылающимися
на самих себя ............................................................................................................251
9.1. Практические упражнения: списки ...................................................................258
9.2. Непустые списки .................................................................................................260
9.3. Натуральные числа .............................................................................................266
9.4. Русская матрешка ................................................................................................270
9.5. Списки в интерактивных программах ..............................................................274
9.6. Замечания о списках и множествах ...................................................................279
10 Еще о списках............................................................................................................284
10.1. Функции, создающие списки ...........................................................................284
10.2. Структуры в списках .........................................................................................287
10.3. Списки в списках, файлы ..................................................................................291
10.4. И снова о графическом редакторе ...................................................................300
11 Проектирование методом композиции ................................................................312
11.1. Функция list .......................................................................................................312
11.2. Композиция функций .......................................................................................314
Стр.7
Содержание
7
11.3. Повторяющиеся вспомогательные функции ..................................................316
11.4. Обобщающие вспомогательные функции.......................................................323
12 Проекты: списки .......................................................................................................333
12.1. Реальные данные: словари ...............................................................................333
12.2. Реальные данные: iTunes ..................................................................................335
12.3. Игры со словами, иллюстрация приема композиции ....................................340
12.4. Игры со словами, суть проблемы .....................................................................345
12.5. «Питон» ..............................................................................................................347
12.6. Простой «Тетрис» ..............................................................................................350
12.7. Полная игра «Космические захватчики» .........................................................353
12.8. Конечные автоматы ..........................................................................................354
13 Итоги ...........................................................................................................................362
Интермеццо 2. Quote, unquote .......................................................................................364
Цитирование ..............................................................................................................364
Квазицитирование и антицитирование ..................................................................365
Объединение с антицитированием ..........................................................................370
III АБСТРАКЦИИ ....................................................................................................375
14 Сходства повсюду.....................................................................................................376
14.1. Сходства в функциях .........................................................................................376
14.2. Отличающиеся сходства ...................................................................................378
14.3. Сходства в определениях данных ....................................................................381
14.4. Функции – это значения ...................................................................................384
14.5. Вычисления с функциями ................................................................................385
15 Проектирование абстракций ..................................................................................389
15.1. Абстрагирование примеров .............................................................................389
15.2. Сходства в сигнатурах .......................................................................................394
15.3. Единая точка управления ................................................................................399
15.4. Абстрагирование макетов ................................................................................400
16 Использование абстракций .....................................................................................402
16.1. Имеющиеся абстракции ...................................................................................403
16.2. Локальные определения ...................................................................................405
16.3. Локальные определения добавляют выразительности ..................................409
16.4. Вычисления с локальными определениями ....................................................411
16.5. Использование абстракций на примерах ........................................................415
16.6. Проектирование с использованием абстракций ............................................420
16.7. Практические упражнения: абстракция ..........................................................422
16.8. Проекты: абстракция ........................................................................................423
17 Безымянные функции ..............................................................................................426
17.1. Определение функций с по мощью лямбда-выражений.................................427
17.2. Вычисления с лямбда-выражениями ...............................................................429
17.3. Абстрагирование с по мощью лямбда-выражений ..........................................432
17.4. Определение спецификаций с по мощью лямбда-выражений ......................435
17.5. Представление с по мощью лямбда-выражений .............................................442
18 Итоги ...........................................................................................................................447
Стр.8
8
Содержание
Интермеццо 3. Область видимости и абстракции .......................................................448
Область видимости ....................................................................................................448
Циклы в языке ISL ......................................................................................................453
Сопоставление с образцом ........................................................................................461
IV ПЕРЕПЛЕТАЮЩИЕСЯ ДАННЫЕ ........................................................... 468
19 Поэзия S-выражений ...............................................................................................469
19.1. Деревья ...............................................................................................................469
19.2. Леса .....................................................................................................................477
19.3. S-выражения ......................................................................................................479
19.4. Проектирование с использованием взаимосвязанных данных ....................485
19.5. Проект: BST ........................................................................................................487
19.6. Упрощение функций .........................................................................................491
20 Итеративное уточнение ...........................................................................................494
20.1. Анализ данных ..................................................................................................494
20.2. Уточнение определений данных ......................................................................496
20.3. Уточнение функций ..........................................................................................498
21 Уточнение интерпретатора .....................................................................................501
21.1. Интерпретация выражений ..............................................................................501
21.2. Интерпретация переменных ............................................................................504
21.3. Интерпретация функций ..................................................................................507
21.4. Интерпретация всего и вся ...............................................................................509
22 Проект: обработка XML ...........................................................................................512
22.1. XML как S-выражения .......................................................................................512
22.2. Отображение XML-перечислений ....................................................................518
22.3. Предметно-ориентированные языки ..............................................................523
22.4. Чтение XML ........................................................................................................528
23 Одновременная обработка .....................................................................................533
23.1. Одновременная обработка двух списков: случай 1 ........................................533
23.2. Одновременная обработка двух списков: случай 2 ........................................534
23.3. Одновременная обработка двух списков: случай 3 ........................................537
23.4. Упрощение функций .........................................................................................541
23.5. Проектирование функций с двумя сложными аргументами .........................542
23.6. Практические упражнения: два аргумента .....................................................544
23.7. Проект: база данных ..........................................................................................548
24 Итоги ...........................................................................................................................560
Интермеццо 4. Природа чисел .......................................................................................561
Арифметика с числами фиксированного размера ..................................................561
Переполнение ............................................................................................................567
Потеря значимости ....................................................................................................567
Числа в *SL ..................................................................................................................568
V ГЕНЕРАТИВНАЯ РЕКУРСИЯ ....................................................................574
25 Нестандартная рекурсия .........................................................................................575
25.1. Рекурсия без структуры ....................................................................................575
Стр.9
9
Содержание
25.2. Рекурсия, игнорирующая структуру ................................................................579
26 Проектирование алгоритмов ..................................................................................585
26.1. Адаптация рецепта проектирования ...............................................................585
26.2. Завершимость рекурсии ...................................................................................587
26.3. Структурная и генеративная рекурсии ............................................................590
26.4. Выбор .................................................................................................................591
27 Вариации на тему .....................................................................................................597
27.1. Фракталы, первое знакомство ..........................................................................597
27.2. Бинарный поиск ................................................................................................600
27.3. Синтаксический анализ ....................................................................................606
28 Математические примеры ......................................................................................610
28.1. Метод Ньютона ..................................................................................................610
28.2. Интегрирование ................................................................................................614
28.3. Проект: гауссово исключение...........................................................................621
29 Алгоритмы с возвратами .........................................................................................627
29.1. Обход графов .....................................................................................................627
29.2. Проект: возврат .................................................................................................636
30 Итоги ...........................................................................................................................643
Интермеццо 5. Стоимость вычислений..........................................................................644
Конкретное время, абстрактное время ....................................................................645
Определение термина «порядка» .............................................................................651
Почему программы используют предикаты и селекторы? .....................................654
VI АККУМУЛЯТОРЫ ............................................................................................658
31 Потеря знаний ...........................................................................................................659
31.1. Проблема структурной обработки ...................................................................659
31.2. Проблема генеративной рекурсии ...................................................................663
32 Проектирование функций с аккумулятором ........................................................668
32.1. Условия применения аккумулятора .................................................................668
32.2. Добавление аккумуляторов ..............................................................................670
32.3. Преобразование простых функций в функции с аккумуляторами ...............672
32.4. Графический редактор с поддержкой мыши ..................................................684
33 Дополнительные примеры использования аккумуляторов ...............................687
33.1. Аккумуляторы и деревья ..................................................................................687
33.2. Представления данных с аккумуляторами......................................................693
33.3. Аккумуляторы как результаты .........................................................................699
34 Итоги ...........................................................................................................................706
Эпилог: что дальше ..........................................................................................................708
Предметный указатель ....................................................................................................714
Стр.10