Функциональное программирование

Предисловие редактора перевода 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 This authoritative book presents a clear introduction to the fast developing field of functional programming. It contains a detailed explanation of implementation techniques and a state-of-the-art account of optimization. The authors show how functional languages are more concise than imperative languages and exhibit certain properties that make them particularly powerful for the development of reliable, easy-to-understand software. Book by Field, Anthony J., Harrison, Peter