Основания программирования

Предисловие i
I Базовые понятия 1
1. Введение в систему понятий программирования 3
1.1. Языки и системы программирования . . . . . . . . . . . 3
1.1.1. Сравнение программ на разных языках . . . . . . . . . 3
1.1.2. Язык, его реализация и среда программирования . . . . 6
1.2. Модель вычислений фон Неймана и традиционные языки . . 15
1.3. Базовые конструкции языка . . . . . . . . . . . . . . 37
1.3.1. Линейные программы и их компоненты . . . . . . . . 37
1.3.2. Не выполняемые вычислителем фрагменты программы 38
1.3.3. Подключение внешней информации (библиотек) . . . 39
1.3.4. Описания . . . . . . . . . . . . . . . . . . . . . 44
1.3.5. Действия . . . . . . . . . . . . . . . . . . . . . 46
1.4. Структура вычислений и структура текста программы . .48
1.4.1. Последовательное, параллельное и совместное исполнение . .48
1.4.2. Управление порядком вычислений . . . . . . . . . . . . 54
1.5. Работа со значениями . . . . . . . . . . . . . . . . . . . .59
2. Синтаксис, семантика и прагматика языка программирования 69
2.1. Синтаксис, семантика . . . . . . . . . . . . . . . . . . . 70
2.2. Прагматика . . . . . . . . . . . . . . . . . . . . . . . . 81
2.3. Абстрактное и конкретное представления программы . . . . . 86
2.3.1. Абстрактное представление . . . . . . . . . . . . . . . 86
2.3.2. Структура абстрактного синтаксиса . . . . . . . . . . . 88
2.3.3. Абстрактный вычислитель и абстрактная структура . . 93
2.3.4. Вызовы как пример синтаксических схем . . . . . . . . 99
2.4. Принципиальные трудности, связанные с семантикой . . . . . 100
3. Стили программирования, или программирование с птичьего полета 106
3.1. Стили программирования . . . . . . . . . . . . . . . . . . . . . 107
3.2. Программирование от состояний . . . . . . . . . . . . . . . . . 118
3.3. Структурное программирование — самый распространенный
стиль . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.4. Сентенциальное программирование . . . . . . . . . . . . . . . 132
3.5. Программирование от событий . . . . . . . . . . . . . . . . . . 135
3.6. Программирование от приоритетов . . . . . . . . . . . . . . . 142
3.7. Функциональное программирование . . . . . . . . . . . . . . . 147
3.8. Объектно-ориентированный подход . . . . . . . . . . . . . . . 151
3.9. Три технологических стиля программирования . . . . . . . . . 155
3.9.1. Программирование от переиспользования . . . . . . . 156
3.9.2. Программирование от образцов . . . . . . . . . . . . . 164
3.9.3. Специализирующее программирование . . . . . . . . . 167
3.10. Общие выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4. Понятие жизненного цикла программного обеспечения и его модели 181
4.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
4.2. Модели традиционного представления о жизненном цикле . . 184
4.2.1. Общепринятая модель . . . . . . . . . . . . . . . . . . 184
4.2.2. Классическая итерационная модель . . . . . . . . . . . 186
4.2.3. Каскадная модель . . . . . . . . . . . . . . . . . . . . . 188
4.2.4. Модель фазы-функции . . . . . . . . . . . . . . . . . . 193
4.3. Итеративные модели жизненного цикла . . . . . . . . . . . . . 196
4.3.1. Базовые технологические принципы итеративного проектирования . . 199
4.3.2. Итеративная модификация модели фазы-функции . . . 202
4.3.3. Параллельное выполнение итераций . . . . . . . . . . 209
4.3.4. Моделирование итеративного наращивания возможностей системы . . 211
4.4. Требования к программному изделию и жизненный цикл . . . 214
4.4.1. Проблемы определения и анализа требований . . . . . 215
4.4.2. Трассировка требований . . . . . . . . . . . . . . . . . 218
4.4.3. Учет трассировки требований в модели жизненного
цикла . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
4.4.4. Особенности первой итерации . . . . . . . . . . . . . . 226
4.4.5. Фаза завершения . . . . . . . . . . . . . . . . . . . . . 231
4.5. Итоги и перспективы . . . . . . . . . . . . . . . . . . . . . . . 235
II Структуры программирования 244
5. Выражения 247
5.1. Операции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
5.2. Логические выражения . . . . . . . . . . . . . . . . . . . . . . 252
5.3. Приоритет операций . . . . . . . . . . . . . . . . . . . . . . . . 260
6. Разветвление вычислений 269
6.1. Разбор случаев . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
6.1.1. Цепочка условий . . . . . . . . . . . . . . . . . . . . . 269
6.1.2. Переключение . . . . . . . . . . . . . . . . . . . . . . . 273
6.1.3. Типы данных, связанные с разветвлением . . . . . . . 278
6.2. Табличное задание разветвлений и оператор выбора Дейкстры 281
6.2.1. Таблицы решений . . . . . . . . . . . . . . . . . . . . 281
6.2.2. Охраняемые команды . . . . . . . . . . . . . . . . . . . 283
6.2.3. Условные выражения . . . . . . . . . . . . . . . . . . . 285
7. Циклические вычисления 287
7.1. Мотивация циклических вычислений . . . . . . . . . . . . . . 287
7.2. Потоковая обработка . . . . . . . . . . . . . . . . . . . . . . . 292
7.2.1. Порождение элементов потока . . . . . . . . . . . . . . 293
7.2.2. Фильтрация потока . . . . . . . . . . . . . . . . . . . . 297
7.2.3. Потоки и данные . . . . . . . . . . . . . . . . . . . . . 300
7.2.4. Потоки и цикл for . . . . . . . . . . . . . . . . . . . . . 326
7.3. Логическая структура цикла . . . . . . . . . . . . . . . . . . . 329
7.3.1. Инвариант и параметры цикла . . . . . . . . . . . . . . 329
7.3.2. Цикл Дейкстры и цикл-‘паук’ . . . . . . . . . . . . . . 332
7.3.3. Совместный цикл . . . . . . . . . . . . . . . . . . . . . 333
7.3.4. Входные и выходные потоки. Сопрограммы . . . . . . 335
7.3.5. Понятие обстановки вычислений. Действия, меняющие обстановку . . 343
7.4. Абстрактно-синтаксическое представление циклов . . . . . . 347
7.4.1. Представление циклов . . . . . . . . . . . . . . . . . . 347
7.4.2. Структурные переходы . . . . . . . . . . . . . . . . . . 348
7.4.3. Исключения . . . . . . . . . . . . . . . . . . . . . . . . 358
8. Подпрограммы 362
8.1. Виды подпрограмм . . . . . . . . . . . . . . . . . . . . . . . . 364
8.2. Именование процедур . . . . . . . . . . . . . . . . . . . . . . . 371
8.3. Контексты и обстановки. Локализация имен . . . . . . . . . . 377
8.4. Вызов процедуры . . . . . . . . . . . . . . . . . . . . . . . . . 390
8.4.1. Семантика вызова процедуры . . . . . . . . . . . . . . 390
8.4.2. Статическая и динамическая цепочки . . . . . . . . . . 393
8.4.3. Понятие экземпляра процедуры . . . . . . . . . . . . . 396
8.5. Параметризация . . . . . . . . . . . . . . . . . . . . . . . . . . 400
8.5.1. Назначение параметризации . . . . . . . . . . . . . . . 400
8.5.2. Полиморфизм и вызовы с переменным числом параметров . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
8.5.3. Механизмы передачи параметров . . . . . . . . . . . . 410
8.5.4. Рекомендации по использованию параметров . . . . . 426
8.5.5. Параметры-процедуры и параметры-функции. Процедурный тип . . . . 437
8.6. Развитие языковых средств модульности в языках линии Turbo
Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
8.6.1. Поддержка модульности в стандартном языке Pascal . 447
8.6.2. Модули в TURBO-системах программирования . . . . 453
8.6.3. Пример использования модуля . . . . . . . . . . . . . . 458
8.7. Рекурсивные программы . . . . . . . . . . . . . . . . . . . . . 463
8.7.1. Сопоставление итеративной и рекурсивной схем . . . 465
8.7.2. Рекурсия через параметры . . . . . . . . . . . . . . . . 469
8.7.3. Пример для самостоятельного анализа . . . . . . . . . 472
8.8. Процедуры в разных моделях вычислений . . . . . . . . . . . 475
9. Структуры данных 482
9.1. Общие концепции структурирования данных . . . . . . . . . . 482
9.1.1. Структура программы и структуры данных . . . . . . . 482
9.1.2. Базовые структуры данных и конструкторы структур . 485
9.1.3. Операции над вновь определяемыми типами данных . 488
9.1.4. Типизация и стили . . . . . . . . . . . . . . . . . . . . 493
9.1.5. Абстрактные типы данных . . . . . . . . . . . . . . . . 494
9.2. Базовые и выводимые типы . . . . . . . . . . . . . . . . . . . . 499
9.2.1. Перечисления . . . . . . . . . . . . . . . . . . . . . . . 499
9.2.2. Булевский тип . . . . . . . . . . . . . . . . . . . . . . . 501
9.2.3. Тип литерных . . . . . . . . . . . . . . . . . . . . . . . 501
9.2.4. Тип целых . . . . . . . . . . . . . . . . . . . . . . . . . 502
9.2.5. Вещественные типы . . . . . . . . . . . . . . . . . . . 504
9.3. Структурные типы . . . . . . . . . . . . . . . . . . . . . . . . . 508
9.3.1. Наборы компонент . . . . . . . . . . . . . . . . . . . . 510
9.3.2. Записи . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
9.3.3. Объединения . . . . . . . . . . . . . . . . . . . . . . . . 519
9.3.4. Массивы . . . . . . . . . . . . . . . . . . . . . . . . . . 524
9.3.5. Множества . . . . . . . . . . . . . . . . . . . . . . . . . 534
9.4. Рекурсивные структуры данных . . . . . . . . . . . . . . . . . 541
9.4.1. Списочные структуры . . . . . . . . . . . . . . . . . . 544
9.4.2. Указательные типы . . . . . . . . . . . . . . . . . . . . 547
9.4.3. Специальные рекурсивные структуры . . . . . . . . . . 550
9.4.4. Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
III Методы программирования 555
10. Методы программирования от состояний 560
10.1. Основные структуры программирования от состояний . . . . 561
10.2. Задача подсчета длин слов текста и задание конечного автомата561
10.2.1. Постановка задачи и первичный анализ . . . . . . . . . 561
10.2.2. Построение графа состояний . . . . . . . . . . . . . . . 563
10.2.3. Табличное представление графа состояний конечного
автомата . . . . . . . . . . . . . . . . . . . . . . . . . . 567
10.2.4. Ручная трансляция диаграмм переходов . . . . . . . . 572
10.2.5. Представления, ориентированные на автоматические
преобразования диаграмм переходов . . . . . . . . . . 579
10.2.6. Обсуждение решения . . . . . . . . . . . . . . . . . . . 588
10.3. Синтаксические таблицы . . . . . . . . . . . . . . . . . . . . . 593
10.3.1. Расширение сферы применения конечных автоматов:
анализатор как система связанных конечных автоматов 593
10.3.2. Задача анализа простых выражений . . . . . . . . . . . 595
10.3.3. Синтаксические таблицы и рекурсивный спуск . . . . 601
10.3.4. Преобразования грамматики, сохраняющие язык. Вычислительная мощность синтаксических таблиц . . 604
10.3.5. Построение графа состояний . . . . . . . . . . . . . . . 607
10.4. Диаграммы состояний и переходов. Их связь с математическими моделями . . . . . . . 609
10.5. Программные представления графа состояний . . . . . . . . . 612
10.5.1. Требования к автоматической трансляции таблиц . . . 613
10.5.2. Языки разметки и автоматическая трансляция таблиц . 614
10.5.3. Автоматное преобразование структурированных текстов617
10.6. Переход от данных к конечному автомату . . . . . . . . . . . . 625
11. Методы, основанные на рекурсии 634
11.1. Механизмы рекурсии . . . . . . . . . . . . . . . . . . . . . . . 635
11.2. Закрашивание замкнутых областей . . . . . . . . . . . . . . . 641
11.3. Переборные алгоритмы и рекурсия . . . . . . . . . . . . . . . 645
11.3.1. Перебор/генерация вариантов с возвратами . . . . . . 646
11.4. Лабиринт . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661
11.4.1. Блуждание по лабиринту и закраска области . . . . . . 662
11.4.2. Абстрактное и конкретное представления данных . . . 664
11.4.3. Абстрактное представление лабиринта . . . . . . . . . 666
11.4.4. Поиск пути в лабиринте . . . . . . . . . . . . . . . . . 673
11.5. Рекурсия при обработке символьной информации . . . . . . . 684
11.6. Рекурсия в транслирующих программах . . . . . . . . . . . . . 690
11.6.1. Синтаксический распознаватель простых выражений . 690
11.6.2. Метод рекурсивного спуска . . . . . . . . . . . . . . . 692
11.6.3. Обратная польская запись выражений: понятие, алгоритмы вычисления и построения . . 699
12. Объектно-ориентированный подход 708
12.1. Объекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 708
12.1.1. Объекты как структуры данных и права доступа . . . . 709
12.1.2. Наследование и полиморфизм . . . . . . . . . . . . . . 714
12.1.3. Множественное наследование и интерфейсы . . . . . . 718
12.2. Объектная модульность . . . . . . . . . . . . . . . . . . . . . . 722
13. Сентенциальные методы 728
13.1. Конкретизация . . . . . . . . . . . . . . . . . . . . . . . . . . . 729
13.1.1. Структура данных . . . . . . . . . . . . . . . . . . . . . 729
13.1.2. Модель вычислений и Рефал-программа . . . . . . . . 733
13.1.3. Дополнительные возможности . . . . . . . . . . . . . . 739
13.1.4. Развитие языка и его диалекты . . . . . . . . . . . . . . 744
13.2. Унификация . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746
13.2.1. Общие концепции . . . . . . . . . . . . . . . . . . . . . 746
13.2.2. Поле зрения, поле памяти и PROLOG-программа . . . 751
13.2.3. Управление исполнением программы . . . . . . . . . . 755
13.2.4. Динамическое пополнение и порождение программы . 762
13.3. Языки разметки . . . . . . . . . . . . . . . . . . . . . . . . . . 765
13.3.1. TEX и L ATEX . . . . . . . . . . . . . . . . . . . . . . . . . 765
13.3.2. Языки разметки для Internet . . . . . . . . . . . . . . . 774
13.4. Применения сентенциального программирования . . . . . . . 787
13.4.1. Аналитические преобразования . . . . . . . . . . . . . 787
13.4.2. Сентенциальные методы в традиционных языках . . . 788
14. Функциональное программирование 791
14.1. Структура данных . . . . . . . . . . . . . . . . . . . . . . . . . 791
14.2. Модель вычислений . . . . . . . . . . . . . . . . . . . . . . . . 793
14.3. Объекты и LISP . . . . . . . . . . . . . . . . . . . . . . . . . . 800
15. Моделирование 805
15.1. Модели и вычисления . . . . . . . . . . . . . . . . . . . . . . . 808
15.2. Моделирование времени . . . . . . . . . . . . . . . . . . . . . 810
15.3. Информационные системы с временем . . . . . . . . . . . . . 811
15.4. Моделирование и информационные системы . . . . . . . . . . 814
15.4.1. Информационное обеспечение моделирования . . . . . 816
15.4.2. Информационные системы для моделей принятия решений . . . . 817
15.5. Системы с дискретными событиями . . . . . . . . . . . . . . . 819
15.6. UML-моделирование и RUP . . . . . . . . . . . . . . . . . . . 829
16. Подведение итогов 831
A. Математические модели 837
A.1. Несколько терминов . . . . . . . . . . . . . . . . . . . . . . . . 837
A.2. Вычислительные интерпретации . . . . . . . . . . . . . . . . . 839
A.3. Модели Янова . . . . . . . . . . . . . . . . . . . . . . . . . . . 844
A.4. Автоматы и машины Тьюринга . . . . . . . . . . . . . . . . . . 845
A.5. Алгоритмы над структурами . . . . . . . . . . . . . . . . . . . 848
A.6. Рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 849
A.7. Совместность и параллелизм . . . . . . . . . . . . . . . . . . . 860
B. Методологические результаты 863
B.1. Логические парадоксы . . . . . . . . . . . . . . . . . . . . . . 863
B.2. Теоремы Тарского и Геделя . . . . . . . . . . . . . . . . . . . . 866
B.3. Идеальные и реальные понятия по Гильберту . . . . . . . . . . 867
B.4. Парадокс изобретателя . . . . . . . . . . . . . . . . . . . . . . 868
B.5. Типы и порядки . . . . . . . . . . . . . . . . . . . . . . . . . . 869
B.6. Чистые теоремы существования . . . . . . . . . . . . . . . . . 870
B.7. Доказательства и программы . . . . . . . . . . . . . . . . . . . 872
B.8. Основные понятия неформализуемости . . . . . . . . . . . . . 874
C. Знания, данные, умения 877
C.1. Анализ понятий . . . . . . . . . . . . . . . . . . . . . . . . . . 877
C.2. Уровень насекомого . . . . . . . . . . . . . . . . . . . . . . . . 879
C.3. Стереотипное реагирование . . . . . . . . . . . . . . . . . . . 880
C.4. Тупость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 882
C.5. Комбинационное (комбинаторное) планирование . . . . . . . . 882
C.6. Глупость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 884
C.7. Стратегическое планирование и преобразование действий . . 885
C.8. Релятивизм . . . . . . . . . . . . . . . . . . . . . . . . . . . 887
C.9. Владение методом . . . . . . . . . . . . . . . . . . . . . . . . 888
C.10. Умничанье, мессианство . . . . . . . . . . . . . . . . . . . . . 889
C.11. Многоуровневое мышление . . . . . . . . . . . . . . . . . . . . 890
C.12. Мудрствование, интуитивизм . . . . . . . . . . . . . . . . . . 891
C.13. Дао . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 891
C.14. Лжепророки . . . . . . . . . . . . . . . . . . . . . . . . . . 891
C.15. Химеры и вымыслы . . . . . . . . . . . . . . . . . . . . . . . 892