Фелляйзен М., Финдлер Р. Б., Флэтт М., Кришнамурти Ш. - Как проектировать программы [2022, PDF, RUS]

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