ЮрИнфоР >>> Библиотека ЮрИнфоР >>> Компьютерные науки и информационные технологии >>>

Конструкции языков программирования

ISBN 5-89158-079-9
2001. 276 c. В721
ББК 32.97
УДК 004
Твердый переплет.
Цена 1
220
Цена 2
480
Цены действительны до
21.11.2024
Цена 1 с учетом НДС
Цена 2 с учетом почтовых расходов по РФ и НДС.
ПОЛОЖИТЬ В КОРЗИНУ
ПОЛОЖИТЬ В КОРЗИНУ
Вольфенгаген В.Э.
Приемы описания

Издание осуществлено при поддержке РФФИ, проект 01-01-14068

В работе изложены основы, касающихся разработки, реализации и применения конструкций как императивных, так и функциональных языков программирования. Значительное внимание уделяется применению денотационной семантики, позволяющей в полной мере извлечь преимущества объектно-ориентированного подхода, что, в конечном счете, позволяет построить результирующую вычислительную модель чисто функционального типа.

Изложение материала сопровождается детально разобранными примерами, которые снабжены комментариями, помогающими уяснить реализацию конструкций различных языков.

Книгу можно использовать в качестве учебника или справочного пособия. Она будет полезна как студентам и аспирантам, так и профессионалам в области компьютерных наук, информационных технологий и программирования.

См. также

Содержание

Дополнительные учебно-методические материалы и компьютерные обучающие средства (практикумы, активные книги)

Содержание

Предисловие редактора серии 1

Предисловие 3

Введение 13

Модель вычислений 17

  • 1.1 Возможности модели вычислений 17
  • 1.2 Синтаксис, семантика и прагматика 19
  • 1.3 Формальная семантика и ее возможности 20
  • 1.4 Денотационная семантика 23
  • 1.5 Абстрактные объекты 25
  • 1.6 Технологическая основа 26
  • 1.7 Унификация логики программ и систем баз данных 27

2. Потоковые диаграммы 29

  • 2.1 Основные идеи теории вычислений 29
  • 2.2 Выражения, представляющие элементы 30
    • 2.2.1 Тождественная функция 31
    • 2.2.2 Константная функция 32
    • 2.2.3 Произведение 33
    • 2.2.4 Сумма 34
  • 2.3 Представление диаграммами 35
    • 2.3.1 Выражения, представляющие диаграммы 39
    • 2.3.2 Универсум для рассуждения о диаграммах 40
  • 2.4 Основные математические понятия и определения 41
  • 2.5 Идея потоковых диаграмм 43
    • 2.5.1 Построение набора примитивных сущностей 45
  • 2.6 Абстрактная потоковая машина 46
    • 2.6.1 Значение выражений 47
    • 2.6.2 Оценивающее отображение 49
    • 2.6.3 Означивание while-цикла 51
  • 2.7 Циклические диаграммы 53
  • 2.8 Синтаксический анализ $ 61

3. Пример непосредственной семантики для модели вычислений 63

  • Полнота описания 63
  • Ясность 63
  • Естественность 63
  • Реализм 63
    • 3.1 Неформальный синтаксис 64
    • 3.2 Неформальная семантика 64
      • 3.2.1 Неформальная семантика выражений 65
      • 3.2.2 Неформальная семантика команд 67
    • 3.3 Формальная семантика 68
      • 3.3.1 Синтаксис 68
      • 3.3.2 Состояние, память, вход, выход и значение 68
      • 3.3.3 Семантические функции 69
        • Денотаты выражений 69
        • Денотаты команд 71
      • 3.3.4 Семантические предложения 71
        • Семантические предложения для выражений 71
        • Семантические предложения для команд 73
      • 3.3.5 Особенности формальной семантики 74

4. Исходные понятия и обозначения: теория вычислений 75

  • 4.1 Абстрактный синтаксис 75
  • 4.2 Подходы к построению семантики 77
  • 4.3 Домены 80
    • 4.3.1 Рекурсивно определенные функции 80
    • 4.3.2 Рекурсивно определенные множества 81
    • 4.3.3 Теория вычислений 82
    • 4.3.4 Математизация в программировании 83
  • 4.4 Определение доменов 83
    • 4.4.1 Стандартные домены 83
    • 4.4.2 Конечные домены 84
    • 4.4.3 Конструкторы доменов 84
      • Функциональное пространство $[D_1 o D_2]$ 84
      • Прямое, или декартово произведение 85
      • Последовательности ^*$ 85
      • Дизъюнктная сумма $[D_1 + D_2 + …+ D_n]$ 86
    • 4.4.4 Равенства среди доменов 87
  • 4.5 Функции 88
    • 4.5.1 Ламбда-обозначения 89
      • Введение $\lambda $-обозначений 90
      • Использование $\lambda $-обозначений 91
        Явное указание области определения и области значения 91
        Использование в функциях нескольких аргументов 91
      • Применение $\lambda $-выражений к аргументам 92
      • Замена связанных переменных 93
    • 4.5.2 Функции высших порядков 93
    • 4.5.3 Соглашения об опускании скобок 94
    • 4.5.4 Каррирование 96
    • 4.5.5 Условные функции 98
    • 4.5.6 Case-конструкция 99
    • 4.5.7 Функции коррекции 100
    • 4.5.8 Порождающие функции 100
    • 4.5.9 Способы определения функций, включая рекурсию 101
      • Нерекурсивные функции 101
      • Рекурсивные функции 102
    • 4.5.10 Исключение переменных 103
    • 4.5.11 Where-конструкция 104
      • Where 104
      • Whererec 105
    • 4.5.12 Композиция и построение последовательности 105
      • Композиция 105
      • Построение последовательности 105
        Вариант 1 106
        Вариант 2 106

5. Пример денотационного описания для модели вычислений 109

  • 5.1 Абстрактный синтаксис 110
    • 5.1.1 Синтаксические домены 110
    • 5.1.2 Синтаксические предложения 110
  • 5.2 Семантика 110
    • 5.2.1 Семантические домены 110
    • 5.2.2 Вспомогательные функции 111
      • result 111
      • donothing 111
      • checkNum 111
      • checkBool 111
    • 5.2.3 Семантические функции 111
    • 5.2.4 Семантические предложения 112
      • Предложения для выражений 112
      • Предложения для команд 112

6. Стандартная семантика 113

  • 6.1 Продолжения 114
    • 6.1.1 Представление `остатка программы' 114
    • 6.1.2 Продолжения команд 115
    • 6.1.3 Продолжение выражения 116
    • 6.1.4 Непосредственная семантика и семантика продолжений 116
  • 6.2 Размещение, запас и среда 117
    • 6.2.1 Разделение 117
    • 6.2.2 Переменная и размещение 118
    • 6.2.3 Запас 118
    • 6.2.4 Среда 119
  • 6.3 Стандартные домены значений 120
  • 6.4 Блоки, декларации и диапазоны 120
  • 6.5 Стандартные домены продолжений 122
    • 6.5.1 Продолжение команды 122
    • 6.5.2 Продолжение выражения 122
    • 6.5.3 Продолжение декларации 123
  • 6.6 Стандартные семантические функции 123
    • Id 124
    • id 124
    • * 124
    • Семантические предложения 124
      Предложения для выражений 124
      Предложения для команд 124
      Предложения для декларации 125
  • 6.7 Преобразование продолжений 125
  • 6.8 Присваивание и значения L, R 128
  • 6.9 Процедуры и функции 131
    • 6.9.1 Процедуры 131
    • 6.9.2 Функции 133
    • 6.9.3 Свод основных соотношений 133
      • Домены 133
      • Предложения для деклараций 134
      • Предложения для вызовов 134

7. Пример денотационной семантики 135

  • 7.1 Пример синтаксиса 136
    • 7.1.1 Синтаксические домены 136
    • 7.1.2 Синтаксические предложения 136
  • 7.2 Пример семантики 137
    • 7.2.1 Семантические домены 137
    • 7.2.2 Семантические функции 138
    • 7.2.3 Семантические предложения 138
      • Программы 138
      • Выражения 139
      • Команды 140
      • Декларации 141
  • 7.3 Пример означивания 142

8. Выходы и передачи управления 145

  • 8.1 Выходы 145
    • 8.1.1 Выходы из команд 145
      • trap 145
      • escapeto 146
    • 8.1.2 Выходы из выражений 147
    • 8.1.3 valof и resultis 148
  • 8.2 Переходы 149
    • 8.2.1 Семантика переходов 150
      • $ :=$, output $, (E_2)$ 151
      • if $ then $ else $ 151
      • while $ do $ 152
      • begin $; $ end 152
      • $; $ 152
      • goto $ 152
      • $: $ 153
    • 8.2.2 Дополнительные аспекты семантики переходов 153
    • 8.2.3 Присваивание переменным меток в качестве значений 155

9. Разновидности процедур и функций 157

  • 9.1 Число параметров 158
    • 9.1.1 Процедуры и функции без параметров 158
    • 9.1.2 Процедуры и функции более, чем с одним параметром 159
  • 9.2 Рекурсивные процедуры и функции 160
  • 9.3 Статическое и динамическое связывание 162
    • 9.3.1 Семантика связывания 162
    • 9.3.2 Особенности динамического связывания 162
  • 9.4 Механизмы передачи параметров 163
    • 9.4.1 Вызов по значению 163
      • Представление вызова по значению 164
      • Различия семантик вызова по значению 165
    • 9.4.2 Вызов по ссылке 166
      • Простой вызов по ссылке 166
    • 9.4.3 Вызов по значению и результату 167
  • 9.5 Механизмы вызова процедур 168
    • 9.5.1 Вызов по замыканию 169
    • 9.5.2 Вызов по тексту 170
    • 9.5.3 Вызов по обозначению 171
    • 9.5.4 Конструкции цитирования 172
  • 9.6 Краткий обзор механизмов вызова и передачи 172
  • 9.7 Абстракции: выражения, обозначающие процедуры и функции 174
  • 9.8 Механизмы связывания деклараций 175

10. Структуры данных 177

  • 10.1 Операции над множествами 178
  • 10.2 Ссылки 179
  • 10.3 Массивы 179
  • 10.4 Записи 182
  • 10.5 Выражения, имеющие структуру данных в качестве значения 184
  • 10.6 Файлы 185
  • 10.7 Семантика файлов 186

11. Конструкции итераций 189

  • 11.1 repeat C until E 189
  • 11.2 Циклы event 189
  • 11.3 For-предложения 190
  • 11.4 Обобщения for-предложения 193

12. Типы 195

  • 12.1 Разновидности типов 196
  • 12.2 Правильно типизированные программы и проверка типов 196
    • 12.2.1 Проверка типов 197
    • 12.2.2 Схема денотационного описания проверки типов 198
  • 12.3 Семантика типов 199

13. Аспекты функционального программирования 201

  • 13.1 Проблематика 202
  • 13.2 Основные характеристики функциональных языков 203
    • Определение функции 206
    • Программирование в функционалах 206
    • Функции высших порядков 207
    • Представление императивных управляющих конструкций 209
    • Продолжения 210
  • 13.3 Представление распространенных функциональных языков 212
    • 13.3.1 Meta Language 212
      • Конструирование данных 212
      • Функции 213
      • Полиморфная сильная типизация 214
  • 13.4 Основные методы реализации 216
    • 13.4.1 SECD-машина 216
    • 13.4.2 Редукция графа 217
    • 13.4.3 Категориальная абстрактная машина 218
  • 13.5 Полезные качества функционального программирования 218
    • 13.5.1 Простота семантики 219
      • Семантика функциональных языков 219
        Переменная 219
        Константный объект 220
        Абстракция 220
        Аппликация 220
      • Пример денотационной семантики императивного языка 221
    • 13.5.2 Проверка корректности программы 222
    • 13.5.3 Преобразование программы 223
  • 13.6 Синтаксис упрощенного функционального языка 224
    • 13.6.1 Функциональный язык первого порядка 224
      • Программа 224
      • Выражение 224
    • 13.6.2 Функциональный язык высших порядков 224
      • Программа 224
      • Выражение 225
  • 13.7 Получение из $\lambda $-выражений машинных инструкций 225
    • 13.7.1 Компилирование правила вычисления 227
      • Компилирование композиции 228
        Правила преобразования 229
        Комментарии 229
        Соглашение 230
      • Обоснование корректности преобразования 233
    • 13.7.2 Компилирование управления средой 234
      • Комбинаторы как машинные инструкции 236
      • Равенства между комбинаторами 237
      • Алгоритм абстракции 238
      • Шаги алгоритма абстракции 239
    • 13.7.3 Большой пример 243
      • Вспомогательные примеры 243
        Бинарный оператор 243
        Унарный оператор 244
        Тождественное преобразование 244
        Аппликация 244
        Сложение двух выражений 244
        Частный случай аппликации 245
      • Дополнительные равенства 247
      • Вычисление факториала (продолжение) 247
        Проведение оптимизации вычислений 249
        Общий случай 249
  • 13.8 Ленивые и жадные вычисления 255

    Литература 257

    Предметный указатель 263

    Глоссарий