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

Description

Эта книга повествует о методах «хорошего программирования» – то есть о таком подходе к созданию программного обеспечения, который опирается на системное мышление, планирование и понимание задач разработчика на каждом этапе. В числе рассматриваемых тем – фундаментальные понятия систематического проектирования, типы данных, способы записи объемных данных, создание и использование абстракций, тестирование программ и функций и др. Издание адресовано профессионалам и энтузиастам программирования, не имеющим прежнего опыта систематического проектирования программ, а также преподавателям технических вузов, которые могут использовать представленный материал в рамках учебного курса. От издательства Вступление Пролог: как писать программы I Данные фиксированного размера 1. Арифметика 1.1. Арифметика чисел 1.2. Арифметика строк 1.3. А теперь все смешаем 1.4. Арифметика изображений 1.5. Арифметика логических значений 1.6. Смешанные операции с логическими значениями 1.7. Предикаты: знай свои данные 2. Функции и программы 2.1. Функции 2.2. Вычисления 2.3. Композиция функций 2.4. Глобальные константы 2.5. Программы 3. Как проектировать программы 3.1. Проектирование функций 3.2. Практические упражнения: функции 3.3. Знание предметной области 3.4. От функций к программам 3.5. О тестировании 3.6. Проектирование интерактивных программ 3.7. Миры виртуальных питомцев 4. Интервалы, перечисления и детализация 4.1. Программирование с условиями 4.2. Условные вычисления 4.3. Перечисления 4.4. Интервалы 4.5. Детализация 4.6. Проектирование с использованием детализации 4.7. Миры с конечными состояниями 5. Добавляем структуру 5.1. От позиций к структурам posn 5.2. Вычисления со структурами posn 5.3. Программирование с posn 5.4. Определение структурных типов 5.5. Вычисления со структурами 5.6. Программирование со структурами 5.7. Вселенная данных 5.8. Проектирование с использованием структур 5.9. Структура в мире 5.10. Графический редактор 5.11. Больше виртуальных питомцев 6. Структуры и детализация 6.1. Проектирование с использованием детализации, снова 6.2. Смешивание миров 6.3. Ошибки ввода 6.4. Проверка состояния мира 6.5. Предикаты равенства 7. Итоги Интермеццо 1. Язык для начинающих студентов Словарь BSL Грамматика BSL Значение в языке BSL Значения и вычисления Ошибки в BSL Логические выражения Определения констант Определения структур Тесты в BSL Сообщения об ошибках в BSL II Данные произвольного размера 8. Списки 8.1. Создание списков 8.2. Что такое '(), что такое cons 8.3. Программирование со списками 8.4. Вычисления со списками 9. Проектирование с определениями данных, ссылающимися на самих себя 9.1. Практические упражнения: списки 9.2. Непустые списки 9.3. Натуральные числа 9.4. Русская матрешка 9.5. Списки в интерактивных программах 9.6. Замечания о списках и множествах 10. Еще о списках 10.1. Функции, создающие списки 10.2. Структуры в списках 10.3. Списки в списках, файлы 10.4. И снова о графическом редакторе 11. Проектирование методом композиции 11.1. Функция list 11.2. Композиция функций 11.3. Повторяющиеся вспомогательные функции 11.4. Обобщающие вспомогательные функции 12. Проекты: списки 12.1. Реальные данные: словари 12.2. Реальные данные: iTunes 12.3. Игры со словами, иллюстрация приема композиции 12.4. Игры со словами, суть проблемы 12.5. «Питон» 12.6. Простой «Тетрис» 12.7. Полная игра «Космические захватчики» 12.8. Конечные автоматы 13. Итоги Интермеццо 2. Quote, unquote Цитирование Квазицитирование и антицитирование Объединение с антицитированием III Абстракции 14. Сходства повсюду 14.1. Сходства в функциях 14.2. Отличающиеся сходства 14.3. Сходства в определениях данных 14.4. Функции – это значения 14.5. Вычисления с функциями 15. Проектирование абстракций 15.1. Абстрагирование примеров 15.2. Сходства в сигнатурах 15.3. Единая точка управления 15.4. Абстрагирование макетов 16. Использование абстракций 16.1. Имеющиеся абстракции 16.2. Локальные определения 16.3. Локальные определения добавляют выразительности 16.4. Вычисления с локальными определениями 16.5. Использование абстракций на примерах 16.6. Проектирование с использованием абстракций 16.7. Практические упражнения: абстракция 16.8. Проекты: абстракция 17. Безымянные функции 17.1. Определение функций с по­мощью лямбда-выражений 17.2. Вычисления с лямбда-выражениями 17.3. Абстрагирование с по­мощью лямбда-выражений 17.4. Определение спецификаций с по­мощью лямбда-выражений 17.5. Представление с по­мощью лямбда-выражений 18. Итоги Интермеццо 3. Область видимости и абстракции Область видимости Циклы в языке ISL Сопоставление с образцом IV Переплетающиеся данные 19. Поэзия S-выражений 19.1. Деревья 19.2. Леса 19.3. S-выражения 19.4. Проектирование с использованием взаимосвязанных данных 19.5. Проект: BST 19.6. Упрощение функций 20. Итеративное уточнение 20.1. Анализ данных 20.2. Уточнение определений данных 20.3. Уточнение функций 21. Уточнение интерпретатора 21.1. Интерпретация выражений 21.2. Интерпретация переменных 21.3. Интерпретация функций 21.4. Интерпретация всего и вся 22. Проект: обработка XML 22.1. XML как S-выражения 22.2. Отображение XML-перечислений 22.3. Предметно-ориентированные языки 22.4. Чтение XML 23. Одновременная обработка 23.1. Одновременная обработка двух списков: случай 1 23.2. Одновременная обработка двух списков: случай 2 23.3. Одновременная обработка двух списков: случай 3 23.4. Упрощение функций 23.5. Проектирование функций с двумя сложными аргументами 23.6. Практические упражнения: два аргумента 23.7. Проект: база данных 24. Итоги Интермеццо 4. Природа чисел Арифметика с числами фиксированного размера Переполнение Потеря значимости Числа в *SL V Генеративная рекурсия 25. Нестандартная рекурсия 25.1. Рекурсия без структуры 25.2. Рекурсия, игнорирующая структуру 26. Проектирование алгоритмов 26.1. Адаптация рецепта проектирования 26.2. Завершимость рекурсии 26.3. Структурная и генеративная рекурсии 26.4. Выбор 27. Вариации на тему 27.1. Фракталы, первое знакомство 27.2. Бинарный поиск 27.3. Синтаксический анализ 28. Математические примеры 28.1. Метод Ньютона 28.2. Интегрирование 28.3. Проект: гауссово исключение 29. Алгоритмы с возвратами 29.1. Обход графов 29.2. Проект: возврат 30. Итоги Интермеццо 5. Стоимость вычислений Конкретное время, абстрактное время Определение термина «порядка» Почему программы используют предикаты и селекторы? VI Аккумуляторы 31. Потеря знаний 31.1. Проблема структурной обработки 31.2. Проблема генеративной рекурсии 32. Проектирование функций с аккумулятором 32.1. Условия применения аккумулятора 32.2. Добавление аккумуляторов 32.3. Преобразование простых функций в функции с аккумуляторами 32.4. Графический редактор с поддержкой мыши 33. Дополнительные примеры использования аккумуляторов 33.1. Аккумуляторы и деревья 33.2. Представления данных с аккумуляторами 33.3. Аккумуляторы как результаты 34. Итоги Эпилог: что дальше Предметный указатель