Как проектировать программы. Введение в программирование и компьютерные вычисления (6000,00 руб.)

Стр.5

Стр.6

Стр.7

Стр.8

Стр.9

Стр.10

УДК 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