Непейвода Н.Н., Скопин И.Н. Основания программирования
Подождите немного. Документ загружается.
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
905
Формула
Хорнова, 747
Функтор, 751
Функция
расстановки, 529
рекурсивная, 856
сигнализирующая, 638
Функция моделирования, 203
Х
Хеширование, см. Функция расста-
новки
Ц
Цель, 752
Цикл
Бема-Джакопини, 129, 843, 845
Кнута, 843
Ч
Чум
фундированный, 639
Ш
Шаблон, 722
Э
Эквивалентность
схем
логико-термальная, 843
функциональная, 842
Эклектика, 111
Эпименид, 864
Я
Язык
Ada, 31
Algol 60, 25, 26, 382, 390,392, 395,
397, 414, 417, 446
Algol 68, см. Алгол 68
FORTRAN, 7, 24–26, 68, 71, 80,
102,251,273,326,362,381,382,
414
Java, 33
LISP, 791–804
Lisp, 5, 12
Pascal, 28
Perl, 140
PL/1, 26
Plankalkul, 791
Prolog, 5, 12, 746–763
SNOBOL, 134
SNOBOL-A, 134
Алгол 68, 4, 7, 11, 27, 40, 42, 52,
58, 280
Рефал, 5, 12, 13, 59, 132, 729–745
С, 29
Симула-67, 26
прагматическое расширение, 13
разметки, 614, 617, 765
L
A
T
E
X, 615, 617, 766
T
E
X, 615, 765
HTML, 615, 774
plain T
E
X, 766
SGML, 774
XML, 615, 617, 781
реализация, 7
реализованный, 14
эталонный, 13
Языки
операционные, 7
традиционные, 7, 15, 22
форматные, 39
Ячейка, 16
Ящик
серый, 161
черный, 161
Оглавление
Предисловие 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
906
ОГЛАВЛЕНИЕ
907
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
908
ОГЛАВЛЕНИЕ
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
ОГЛАВЛЕНИЕ
909
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
910
ОГЛАВЛЕНИЕ
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
ОГЛАВЛЕНИЕ
911
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
912
ОГЛАВЛЕНИЕ
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. T
E
X и L
A
T
E
X . . . . . . . . . . . . . . . . . . . . . . . . . 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
ОГЛАВЛЕНИЕ
913
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