Книга английского специалиста по программированию «Функциональное программирование: применение и реализация» обобщающая опыт использования функционального программирования.
Обсуждаются особенности функциональных языков и возможности их реализации на современных ЭВМ.
Изложение иллюстрируется многочисленными примерами.
Книга «Функциональное программирование: применение и реализация» будет интересна и полезна для программистов, математиков-прикладников, для всех, кто преподает и изучает программирование.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Функциональное программирование — это способ составления программ, в которых единственным действием является
вызов функции, единственным способом расчленения программы на части является введение имени для функции и задание для этого имени выражения, вычисляющего значение функции, а единственным правилом композиции — оператор суперпозиции функции. Никаких ячеек памяти, ни операторов присваивания, ни циклов, ни, тем более, блок-схем, ни передач управления.
Алгол, Фортран и Ассемблер сделали свое дело, и тем нескольким сотням тысяч людей у нас в стране, которым приходится писать программы для ЭВМ, пожалуй, будет нелегко представить себе, как можно приступать к программированию, не опираясь на эти, казалось бы, незыблемые конструкции языков программирования.
Внимательное чтение этой книги будет на первых порах вызывать у них чувство протеста — они раз за разом будут
ощущать себя как спортсмены, которым нужно играть в волейбол с одной рукой, привязанной к телу. Потребуется большое доверие к автору для того, чтобы при чтении книги преодолеть дебют с такой заметной интеллектуальной форой.
На основании собственного болезненного опыта упражнения в функциональном программировании мне хотелось бы предупредить читателей, что ощущение трудности и необычности составления функциональных программ вполне законно и естественно.
...следует воздать должное автору, который педагогически очень тактично вводит и дозирует столь
непривычные на первый взгляд приемы функционального программирования. Более того! Чувствуя момент, когда у читателя появляются первые проблески уверенности, он честно показывает, что новые меха годятся и для старого вина, демонстрируя, как ряд приемов традиционного программирования с использованием памяти и итерационных процессов можно закодировать в функциональной нотации. С другой стороны, рассказывая о реализации функциональных программ «до конца», т. е. вплоть до аппаратной реализации, автор подталкивает активного читателя на поиски новой архитектуры ЭВМ, более непосредственно отражающей рекурсивный характер функциональных вычислений.
Академгородок
октябрь 1982 г.
А.П. Ершов
Author(s): Хендерсон П
Series: Математическое обеспечение ЭВМ
Publisher: Мир
Year: 1983
Language: Russian
Pages: 350
City: Москва
Предисловие редактора перевода 5
Предисловие 8
Глава 1. Функции и программы 11
1.1. Программирование при помощи функций 12
1.2. Программирование при помощи процедур 18
Глава 2. Строго функциональный язык 23
2.1. Символьные данные 23
2.2. Элементарные селекторы и конструкторы 28
2.3. Элементарные предикаты и арифметика 31
2.4. Рекурсивные функции 33
2.5. Другие рекурсивные функции 36
2.6. Накапливающие параметры 43
2.7. Локальные определения 47
2.8. Функции высших порядков и Л-выражения 50
2.9. Точечная запись выражений 58
Упражнения 63
Глава 3. Простые функциональные программы 67
3.1. Анализ размерностей — пример структурированного прог-
раммирования и структурированной отладки программы 68
3.2. Поиск по дереву — сравнение стратегий с приоритетом по ширине и по глубине 79
3.3. Программа функции индивидуумы 90
Упражнения 97
Глава 4. Представление и интерпретация программ 99
4.1. Абстрактная и конкретная формы программ 101
4.2. Связывание 108
4.3. Интерпретатор для варианта языка Лисп 115
Упражнения 127
Глава 5, Соответствия между функциональными и императивными проrраммами 130
5.1. Интерпретатор для императивноrо языка 131
5.2. Функциональные эквиваленты императивных nporpaмм 138
5 3. Преобразование императивных nporpaмм в функциональные 141
5.4. Аппаратное обеспечение функциональных программ 152
Упражнения 159
Глава 6. Архитектура машины для функциональных npoгpaмм 164
6.1. Эскиз машины 164
6.2. SЕСD-машина 168
6.3. Компилятор для варианта Лиспа 177
6.4. Проrраммирование компилятора 187
6.5. Завершение описания семантики 189
Упражнения 195
Глава 7. Недетерминистскне примитивы и программы с возвратами 197
7.1. Недетерминистские примитивы 197
7.2. Интерпретация недетерминистских примитивов 201
7.3. Программы с возвратами 204
Упражнения 210
Глава 8. Вычисления с задержкой - функциональный подход к параллелизму 212
8.1. Вычисления с задержкой 21З
8.2. Интерпретация операторов задержать и возобновить 217
8.З. Замедленные вычисления 222
8.4. Сети связных процессов 230
Упражнения 237
Глава 9. Функции высших порядков. 240
9.1. Типы фуикций 241
9.2. Описание синтаксиса языка 249
9.3. Описание структуры фигур 252
Упражнения 262
Глава 10. Языки проrраммирования и методы проrраммирования 264
10.1. О ясности выражения 264
10.2. Области данных 268
10.3. Преобладание присваивания 273
Упражнения 276
Глава 11. Инструментарий функциоиального программирования 278
11.1. Пространство списков 279
11.2. Принципиальная схема вычислений 285
11.3. Ввод S-выражений 286
11.4. Ввод лексем 292
11.5. Вывод S-выражений 295
11.6. Вывод лексем 296
11 7. Проrраммы перевода 298
11.8. Цикл выполнеиия nporpaммы 299
Глава 12. Основы машинного обеспечения инструментария функционального программирования 303
12.1. Хранение списков 308
12.2. Сборщик мусора 313
12.3. Хранение строк 316
12.4. Построение и отладка инструментальной системы .... 318
12.5. Раскрутка и оптимизация 325
Приложение 1. Ответы к некоторым упражнениям 329
Приложение 2. Компилятор для инструментального Лиспа 333
Приложение 3. Библиография 336
Алфавитный указатель 340
