Как проектировать программы. Введение в программирование и компьютерные вычисления

Маттиас Фелляйзен
Роберт Брюс Финдлер
Мэтью Флэтт
Шрирам Кришнамурти

Как проектировать 
программы 

Matthias Felleisen
Robert Bruce Findler
Matthew Flatt
Shriram Krishnamurthi

The MIT Press
Cambridge, Massachusetts
London, England

How to Design Programs

An Introduction to Programming and 
Computing

Second Edition

Маттиас Фелляйзен
Роберт Брюс Финдлер
Мэтью Флэтт
Шрирам Кришнамурти

Как проектировать программы

Введение в программирование  
и компьютерные вычисления

Москва, 2022

УДК 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 (англ.) 
© Massachusetts Institute of Technology, 2018
 
Illustrations © Torrey Butzer, 2000
ISBN 978-5-97060-926-2 (рус.) 
©  Перевод, оформление, издание, ДМК Пресс, 2022

Содержание

От редакторов .................................................................................................................... 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

Содержание

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

Содержание

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

Содержание

Интермеццо 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

Содержание

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

От редакторов

Добрый день! Спасибо, что вы открыли эту книгу, даже если взяли 
с полки магазина просто посмотреть. Нам приятно в любом случае. 
Для нас удача и честь принять участие в переводе такой легендарной 
книги, чтобы вы могли прочесть ее на родном языке.
Что же делает ее легендарной? Вы наверняка заметили, что это 
перевод второго издания, которое вышло уже почти 5 лет назад, 
а первое – более 20 лет назад. Оставаться востребованным столько 
лет в стремительно меняющемся мире информационных технологий 
и языков программирования – достижение само по себе.
Авторы книги – легенды мира компьютерных наук и информатики, авторы фундаментальных работ на протяжении последних 30 лет. 
Они же являются одними из пионеров систематического, научного 
подхода к преподаванию программирования и информатики. Как результат, данная книга является отражением глубокого понимания как 
самого предмета, так и методики его преподавания, сформировавшегося у авторов за десятилетия практики.
Другой фактор долголетия этого учебника – то, что он живой. Книга 
продолжает развиваться даже после публикации: в неё постоянно вносят правки и уточнения, исправляют ошибки, она используется в качест ве основы для курсов в университетах и на онлайн-площадках.
В результате получился один из лучших в мире учебников по программированию для новичков, который увлекательно читать, который никогда не перегружает лишними деталями, всегда ясно указывает направление развития и ненавязчиво прививает правила «хорошего тона».
Авторы справедливо отмечают, что это учебник по чему-то большему, чем просто программирование. В первую очередь он учит тому, 
что в последнее время принято называть «computational thinking», 
«алгоритмическим (или вычислительным) мышлением». Этим стилем мышления пользуются не только программисты, но и повара, 
учителя, спортсмены, врачи и многие, многие другие.
Авторы книги скромничают, когда говорят, что книга ориентирована на начинающих. Профессионалы встретят в ней как отсылки 
к фундаментальным понятиям и методам компьютерных наук, так 
и эффективные методы анализа повседневных задач. Поэтому от 
всего сердца советуем вам купить эту книгу! Мы от этого богаче не 
станем, но верим, что вас она способна обогатить интеллектуально, 
творчески и профессионально, даже если разработка программного 
обеспечения – не ваша основная деятельность.

С уважением от редакторов,
Павел Борисович Иванов,
Александр Дмитриевич Чичигин,
Юрий Алексеевич Сыровецкий,
Сергей Викторович Бронников