Учебное пособие по программированию, в основу которого положены лекции, прочитанные на курсах летней школы, организованных по инициативе Научного комитета НАТО.
В книге рассмотрен ряд вопросов теории программирования, а именно: особенности последовательных процессов и их взаимодействие при объединении, методы написания компиляторов, обработка записей. Отдельная глава содержит обзорные сведения по языкам моделирования дискретных событий.
Книга носит оригинальный характер и представляет значительный интерес для специалистов в области программирования, алгоритмических языков, трансляторов, моделирования. Она будет полезна студентам и аспирантам соответствующих специальностей.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
В настоящей книге читателю предлагаются переводы некоторых из лекций, читавшихся в летней школе по языкам программирования, которая проводилась в Виллар-де-Ланс (Франция) в 1966 г.
Отдельные главы книги написаны разными авторами и весьма несходны по стилю. Так, например, первая глава, написанная Э. Дийкстрой и посвященная параллельным процессам, содержит аккуратное решение очень четко поставленной задачи. Возможно, что именно в силу такой четкости изложения тема главы на первый взгляд может показаться несколько узкой, так как часто именно «узкие» проблемы и решаются аккуратно. Однако рассмотренная здесь задача имеет многочисленные применения и возникает во многих случаях, когда имеют дело с параллельно работающими и взаимодействующими между собой процессами. Речь идет о разработке простого и по возможности универсального механизма вмешательства в эти процессы в такие моменты, когда несвоевременное взаимодействие их друг с другом может нарушить предусмотренную логику их функционирования. Примеры воз-можных применений идей автора читатели найдут в тексте.
Во второй главе, написанной Л. Болье, описаны методы, используемые при составлении трансляторов с языков высокого уровня. Наряду со статьей Дж. Фельдмана и Д. Гриса «Системы построения трансляторов» (сборник «Алгоритмы и алгоритмические языки», вып. 5, Изд. ВЦ АН СССР, М., 1971), которую также можно рекомендовать читателям, интересующимся этими вопросами, эта работа представляет собой один из наиболее полных обзоров по данной теме. Следует заметить, что эта глава изложена не столь четко и аккуратно, как первая.
Третья глава воспроизводит содержание лекций К. Хоора о новом типе величин сложной структуры — записях, с которыми часто приходится иметь дело при решении невычислительных задач. В свое время значение таких величин, по-видимому, недооценили, и хотя в дальнейшем эта ошибка была замечена и в какой-то мере исправлена (в более современные языки PL/I и АЛГОЛ-68 включены такие и даже более сложные типы величин), отсутствие записей в широко распространенных языках АЛГОЛ-60
СОДЕРЖАНИЕ
Предисловие редактора перевода................. 5 'V
Предисловие........................... 7 '
" ** э. ДИЙКСТРА ;
ВЗАИМОДЕЙСТВИЕ -
ПОСЛЕДОВАТЕЛЬНЫХ ПРОЦЕССОВ.............. 9 ,
Введение............................ 9
1. ПРИРОДА ПОСЛЕДОВАТЕЛЬНЫХ ПРОЦЕССОВ ............ Ю
2. СЛАБО СВЯЗАННЫЕ ПРОЦЕССЫ................... 18 »
2.1. Простой пример...................... 19
2.2. Обобщенная задача взаимного исключения ........ 26
2.3. Пример......................... 30
3. НОВЫЙ ПОДХОД К ЗАДАЧЕ ВЗАИМНОГО ИСКЛЮЧЕНИЯ ..... 33
3.1. Необходимость в более реалистическом решении...... 33
3.2. Синхронизирующие примитивы............... 35
3.3. Применение синхронизирующих примитивов к задаче взаимного исключения........................ 36
4. ОБЩИЙ СЕМАФОР .......................... 37
4.1. Типичное использование общего семафора......... 37
4.2. Избыточность общего семафора.............. 40
4.3. Ограниченный буфер................... 44
5. ВЗАИМОДЕЙСТВИЕ ЧЕРЕЗ ПЕРЕМЕННЫЕ СОСТОЯНИЯ...... 45
5.1. Пример приоритетного правила.............. 46
5.2. Пример с диалогами................... 52
6. ПРОБЛЕМА ТУПИКОВ ........................ 76
6.1. Алгоритм банкира.................... 78
6.2. Применение алгоритма банкира.............. 80
7. ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ................... 84
Л. БОЛЬЕ
МЕТОДЫ
ПОСТРОЕНИЯ КОМПИЛЯТОРОВ ............... 87
1, СПОСОБЫ ПОДСТАНОВКИ ...................... 87
1.1. Введение....................... . 87
1.2. Статические подстановки и динамические подстановки .... 89
1.3. Вложенные структуры.................. 99
2. МЕТОДЫ КОМПИЛЯЦИИ....................... 124
2.1. Структура процесса компиляции............. 124
2.2. Макровычисление .................... 125
2.3. Синтаксическое вычисление................ 133
Содержание 405
2.4. Семантическое вычисление ................ 174
2.5. Компиляторы для систем с множественным J доступом .... 243 Список литературы......................... 276
к. ХООР
ОБРАБОТКА ЗАПИСЕЙ..................... 278
Введение........................... 279
1. ОСНОВНЫЕ ПРИНЦИПЫ ...................... 282
1.1. Объекты и записи.................... 282
1.2. Свойства и поля..................... 282
1.3. Собирательные имена и классы записей.......... 283
1.4. Описания класса записей................ 283
1.5. Указатели поля..................... 284
1.6. Пример.......................... 284
1.7. Реализация....................... 285
2. ссылки ............................... 286
2.1. Функциональные связи.................. 286
2.2. Поля ссылок ...................... 286
2.3. Частично функциональные связи............. 287
2.4. Переменные типы ссылки................. 288
2.5. Пример......................... 289
2.6. Реализация..................v..... 289
3. ГЕНЕРИРОВАНИЕ ЗАПИСЕЙ .................... 291
3.1. Функция генерирования записей............. 291
3.2. Пример.......................... 291
3.3. Схемное представление.................. 292
3.4. Генерирование копий.................. 292
3.5. Реализация....................... 292
3.6. Сегменты расширения.................. 294
3.7. Автоматическое собирание свободных участков памяти .... 295
4. ПОДКЛАССЫ ЗАПИСЕЙ . . ...................... 295
4.1. Описания подклассов . ................. 295
4.2. Ссылки в подклассах и генерирование........... 296
4.3. Частные и общие поля.................. 296
4.4. Пример . . .........................i 297
4.5. Схемное представление.................. 298
4.6. Реализация....................... 298
5. РАЗЛИЧЕНИЕ КЛАССА ЗАПИСИ.................. 300
5.1. Различитель класса записи................ 300
5.2. Доступ к частным полям................. 301
5.3. Пример.............'-..,-........... 301
5.4. Обсуждение примера................... 303
5.5. Реализация....................... 304
в. ввод и вывод ЗАПИСЕЙ...................... 304
6.1. Файлы......................... 304
406___________ С одержанив
6.2. .Ввод и вывод...................... 305
6.3. Ограничения....................... 306
6.4. Пример......................... 307
6.5. Реализация........................ 308
6.6. Длинные файлы..................... 309
7. РАЗЛИЧНЫЕ РАСШИРЕНИЯ СРЕДСТВ ОБРАБОТКИ ЗАПИСЕЙ ... 310
7.1. Массив полей...................... 310-
7.2. Генераторы массивов.................. 312
7.3. Реализация массива полей................ 31$
7.4. Упакованные поля.................... 314
7.5. Перегрузка....................... 316-
7.6. Перегрузка индексирования................ 318
8. ДРУГИЕ ЯЗЫКИ, ДОПУСКАЮЩИЕ ВОЗМОЖНОСТЬ ОБРАБОТКИ ЗАПИСЕЙ ............................... 318
8.1. АЛГОЛ-60 . . ..................... 31&
8.2. ЛИСП......................... 320
8.3. СИМУЛА........................ 322
8.4. AED-0......................... 324
8.5. PL/I........................... 32&
9. СТРОГОЕ ОПРЕДЕЛЕНИЕ ОБРАБОТКИ ЗАПИСЕЙ.......... 331
Список литературы....................... 34S
У.-И. ДАЛ
ЯЗЫКИ ДЛЯ МОДЕЛИРОВАНИЯ СИСТЕМ
С ДИСКРЕТНЫМИ СОБЫТИЯМИ................ 344
1. МОДЕЛИРОВАНИЕ И ЯЗЫКИ МОДЕЛИРОВАНИЯ........... 344
2. ПРОСТЕЙШАЯ МОДЕЛЬ ДИСКРЕТНЫХ СОБЫТИЙ......... 351
3. ОСНОВНЫЕ ПОНЯТИЯ ....................... 358
В 13.1. Статическая структура................. 359
3.2. Динамическая структура................ 362
3.3. Терминология...................... 367
4. СТАТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ............'...... 367
4.1. Перманентные объекты.................. 369
4.2. Временные объекты................... 371
5. УПРАВЛЕНИЕ (ПОРЯДОК ВЫПОЛНЕНИЯ).............. 376
5.1. Императивное управление................ 377
5.2. Интеррогативное управление............... 382
6. УПОРЯДОЧЕННЫЕ МНОЖЕСТВА .................. 384
6.1. Наборы в языке СИМСКРИПТ.............. 386
6.2. Наборы в языке СИМУЛА................ 387
6.3. Наборы в языке ЦСЛ.................. 388
7. типичный ПРИМЕР} ........................ 388
8. ДРУГИЕ 1ПРИЛОЖЕНИЯ ,.............•........ 398
Список литературы..................... 401
Цена: 150руб.
