В книге английских специалистов рассмотрены проблемы аппликативного программирования, существенно повышающего интеллектуальность разрабатываемых программ по сравнению с традиционным программированием.
При этом спецификация предметной области существенно упрощает труд программиста.
Особое внимание уделяется вопросам реализации функциональных языков, основанных на лямбда-исчислении Черча.
В качестве базового языка рассматривается функциональный язык Норе, имеющий простой и ясный синтаксис.
Изложение сопровождается многочисленными примерами конкретных программ.
Для программистов как начинающих, так и профессионалов, а также специалистов в области информатики.
Author(s): Филд А, Харрисон П
Publisher: Мир
Year: 1993
Language: Russian
Pages: 639
City: Москва
Предисловие редактора перевода 5
Предисловие . . 6
Часть I. Программирование с помощью функций 8
Введение . 8
Глава 1. Введение в функции 11
1.1. Чистые функции 11
1.2. Функциональность 17
Резюме 19
Глава 2. Введение в функциональное программирование. Язык Норе 20
2.1. Введение понятия функции 20
2.2. Кортежи . . 23
2.3. Рекурсивные функции . 27
2.4. Объявляемые инфиксные операторы 29
2.5. Квалифицированные выражения 30
2.6. Типы данных, определяемые пользователем 33
2.7. Доказательства по индукции 49
Резюме . . . . 52
Упражнения . . 52
Глава 3. Функции высшего порядка 55
3.1. Примеры рекурсии . 56
3.2. Связывание .... 61
3.3. Другие примеры рекурсии 61
3.4. Пример применения 64
Резюме 69
Упражнения 69
Глава 4. Виды вычислений . 71
4.1. Понятие строгости . 72
4.2. Обработка «бесконечных» структур данных 74
4.3. Сети процессов . 79
4.4. Вычисление с «неизвестным» 83
Резюме . 85
Упражнения . 86
Глава 5. Другие стили функционального программирования 88
5.1. Miranda 89
5.2. Лисп 95
5.3. FP 103
Резюме - - 115
Упражнения 115
Часть II. Реализация . 117
Введение. 117
Глава 6. Математические основы: Л-исчисление 120
6.1. Введение и синтаксис 121
6.2. Вычисление Я-выражений 123
6.3. Порядок редукций и нормальные формы 127
6.4. (З-Редукция и проблема конфликта имен 132
6.5. Обход проблемы конфликта имен 135
6.6. Эффект разделения 137
6.7. Рекурсивные выражения 140
6.8. Чистое Л-исчисление 144
6.9. Л-исчисление де Брёйна 148
Резюме 149
Упражнения 150
Глава 7. Система вывода типов и проверка типов 153
7.1. Неформальное введение в проверку типов 154
7.2. Система вывода типов 160
7.3. Алгоритм проверки типа W 164
7.4. Расширения W для практической проверки типов . . . .172
7.5. Ограничения W 175
Резюме 176
Упражнения 177
Глава 8. Промежуточные формы 179
8.1. Промежуточный код для функциональных языков .... 180
8.2. Абстрактные синтаксические деревья 181
8.3. Трансляция языка Норе в промежуточный код 183
8.4. Трансляция сопоставления с образцом 185
8.5. Поиск наиОолее подходящего образца 195
8.6. Литеральные образцы 200
8.7. О порядке тестирования 201
Резюме 203
Упражнения 204
Глава 9. Методы интерпретации 206
9.1. Абстрактное представление промежуточного кода . . . 206
9.2. Энергичный интерпретатор 208
9.3. Ленивый интерпретатор 218
Резюме 225
Упражнения 226
Глава 10. Реализация на основе стеков — SECD-машина 228
10.1. SECD-машина ! 229
10.2. Ленивая SECD-машина 240
10.3. Корректность реализации SECD-машины 245
Резюме 253
Упражнения 253
Глава 11. Введение в редукцию графов 256
11.1. Представление лямбда-выражений в виде графов . . . 257
11.2. Правила редукции графов 262
11.3. Интерпретаторы, основанные на редукции графов . . . 272
11.4. Проблема свободных переменных 285
11.5. Параллельная редукция графов 287
Резюме . . . 288
Упражнения 289
Глава 12. Комбинаторная редукция 291
12.1. Основы комбинаторной логики и редукция 292
12.2. Оптимизация Карри и редукция комбинаторных графов
Тернера 296
12.3. Представление рекурсии 308
12.4. Строки направляющих 317
Резюме 321
Упражнения 322
Глава 13. Новейшие комбинаторные реализации . . . . 325
13.1. Абстрагирование свободных переменных простым л-удалением 326
13.2. Суперкомбинаторы 331
13 3. Оптимизация суперкомбинаторных реализаций 334
13.4. Категорийные комбинаторы 343
13 5. Модификации КАМ 355
Резюме 357
Упражнения 358
Глава 14. Потоковые реализации 360
14.1. Функциональный поток данных аппликативного порядка 361
14.2. Функциональный поток данных нормального порядка . . 377
14.3. Сравнение с другими моделями . . . . = 381
Резюме 382
Упражнения 383
Глава 15. Компиляции функциональных языков 385
15 1. Структура компилированной программы 336
15.2. МФП-система 389
15.3. G-машина 415
Резюме 434
Упражнения 434
Глава 16. Сборка мусора 437
16.1. Организация памяти 438
16.2. Сканирующая сборка мусора 442
16.3. Копирующие сборщики мусора 444
16.4. Сборщики мусора с подсчетом ссылок 463
Резюме 469"
Упражнения 470
Часть III. Оптимизация 472
Введение 472
Глава 17. Преобразование программ и операционный подход .... 478
17.1. Трансформационная методология раскрутки/скрутки . 480
17.2. Управление системой раскрутки/скрутки — метаязык пре-
образований .... 488
17.3. Преобразование типов данных 490
Резюме 499
Упражнения 499
Глава 18. Алгебраическое преобразование программ 502
18.1. Абстрагирование от переменных 504
18.2. Аксиомы алгебры FP и уравнения функционального
уровня 506
18.3. Линейная функция и теорема о линейном расширении . . 510
18.4. Итерационные формы линейных функций . . .... 515
18.5. Другие применения 525
18.6. Преобразование передачей продолжений 530
Резюме 535
Упражнения 536
Глава 19. Запоминание . 539
19.1. Принципы работы и основные трудности 540
19.2. Ленивые мемо-функции 543
19.3. Управление размером мемо-таблины 548
19.4. Сборка мусора для мемо-таблиц 556
Резюме 559
Упражнения . . . . 559
Глава 20. Абстрактная интерпретация 561
20.1. Общие принципы 561
20.2. Анализ строгости 565
20.3. Доказательства надежности 572
20.4. Другие применения для оптимизации программ .... 575
Резюме 578
Упражнения . 578
Приложение А. Краткое описание языка Норе 580
А.1. БНФ языка Норе . 580
А.2. Предварительно определенные типы и функции .... 583
Приложение Б. Основы теории доменов 586
Б.1. Введение 586
Б.2. Законченный частичный порядок и непрерывные функции 587
Б.З. Конструкции на доменах: новые домены из старых . . . 589
Б.4. Наименьшие фиксированные точки 591
Приложение В. Формальная семантика 593
8.1. Денотационная семантика Я-исчисления 594
8.2. Денотационная семантика функциональных языков программирования 597
8.3. Конструируемые типы данных 600
8.4. Сопоставление с образцом 601
Решение некоторых упражнений 604
Литература 621
Предметный указатель 625
