Хендерсон П.
438 Функциональное программирование. Применение и реализация: Пер. с англ.—М.: Мир, 1983.—349 с., ил.
Книга английского специалиста по программированию, обобщающая опыт использования функционального программирования. Обсуждаются особенности функциональных языков и возможности их реализации на современных ЭВМ. Изложение иллюстрируется многочисленными примерами. „_„,„„„».,•
Для программистов, математиков-прикладников, для всех, кто преподает и изучает программирование.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Функциональное программирование — это способ составления программ, в которых единственным действием является вызов функции, единственным способом расчленения программы на части является введение имени для функции и задание для этого имени выражения, вычисляющего значение функции, а единственным правилом композиции — оператор суперпозиции функции. Никаких ячеек памяти, ни операторов присваивания, ни циклов, ни, тем более, блок-схем, ни передач управления.
Алгол, Фортран и Ассемблер сделали свое дело, и тем нескольким сотням тысяч людей у нас в стране, которым приходится писать программы для ЭВМ, пожалуй, будет нелегко представить себе, как можно приступать к программированию, не опираясь на эти, казалось бы, незыблемые конструкции языков программирования.
Внимательное чтение этой книги будет на первых порах вызывать у них чувство протеста — они раз за разом будут ощущать себя как спортсмены, которым нужно играть в волейбол с одной рукой, привязанной к телу. Потребуется большое доверие к автору для того, чтобы при чтении книги преодолеть дебют с такой заметной интеллектуальной форой.
На основании собственного болезненного опыта упражнения в функциональном программировании мне хотелось бы предупредить читателей, что ощущение трудности и необычности составления функциональных программ вполне законно и естественно.
Мало того, они могут взять себе в союзницы историю науки. Известный американский ученый Алонсо Чёрч, автор лямбда-нотации и тезиса Чёрча, создал на подступах к теории алгоритмов лямбда-исчисление, которое сейчас можно считать не чем иным, как теоретической моделью современного функционального программирования. Он бился немало месяцев над тем, чтобы запрограммировать в лямбда-исчислении операцию вычитания единицы из натурального числа
I 0-1=0
ОГЛАВЛЕНИЕ
Предисловие редактора перевода ... ...... .......... 5
Предисловие............................ 8
Глава 1. Функции и программы ,................. 11
1.1. Программирование при помощи функций . . . . . . . , 12
1.2. Программирование при помощи процедур.......... 18
Глава 2. Строго функциональный язык............... 23
2.1. Символьные данные................... 23
2.2. Элементарные селекторы и конструкторы......... 28
2.3. Элементарные предикаты и арифметика.......... 31
2.4.- Рекурсивные функции . . t................ 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
S77 а
Глава 5. Соответствия между функциональными и императивными
программами ....................... ;зд
5.1. Интерпретатор для императивного языка ........ : ^
5.2. Функциональные эквиваленты императивных программ . . J38
5.3. Преобразование императивных программ в функциональные !41
5.4. Аппаратное обеспечение функциональных программ . . . \у) Упражнения ........................ 159
Глава 6. Архитектура машины для функциональных программ ... ig4
6.1. Эскиз машины ...................... ii54
6.2. SECD-машина ...................... 1/35
6.3. Компилятор для варианта Лиспа
6.4. Программирование компилятора
6.5. Завершение описания семантики у Упражнения .......................... 195
Глава 7. Недетерминистские примитивы и программы с возвратил:!! 197
7.1. Недетерминистские примитивы .............. 197
7.2. Интерпретация недетерминистских примитивов ...... 201
7.3. Программы с возвратами ................. 204
Упражнения .... ..................... 210
Глава 8. Вычисления с задержкой — функциональный подход к парал-
лелизму ......................... 212
8.1. Вычисления с задержкой ................ 213
8.2. Интерпретация операторов задержать и возобновить ... 217
8.3. Замедленные вычисления .... ............. 222
8.4. Сети связных процессов ................. 230
Упражнения ......................... 237
Глава 9. Функции высших порядков ............ .... 240
9.1. Типы функций ...................... 241
9.2. Описание синтаксиса языка ... ............ 249
9.3. Описание структуры фигур ................ 252
Упражнения ......................... 262
Глава 10. Языки программирования и методы программирования . . 264
10.1. О ясности выражения .................. 264
10.2. Области данных ..................... 268
10.3. Преобладание присваивания ............... 273
Упражнения . . .............. . ' ....... 276
Глава И. Инструментарий функционального программирования . . . 278
11.1. Пространство списков .................. 279
11.2. Принципиальная схема вычислений ........... . 285
11.3. Ввод S-выражений .................... 286
11.4. Ввод лексем ....................... 292
1 1 .5. Вывод S-выражений ................... 295
11.6. Вывод лексем ...................... 296
11.7. Программы перевода ................... 298
11.8. Цикл выполнения программы ............... 299
Оглавление
\
Ьава 12. Основы машинного обеспечения инструментария функцио-
1 нального программирования................ 303
' 12.1. Хранение списков.................... 308
' 12.2. Сборщик мусора..................... 313
; 12.3. Хранение строк ,.................... 316
12.4. Построение и отладка инструментальной системы .... 31й
12.5. Раскрутка и оптимизация................ 325
Приложение 1. Ответы к некоторым упражнениям......... 32У
Приложение 2. Компилятор для инструментального Лиспа..... 333
Приложение 3. Библиография................... 336
Алфавитный указатель..........,.,,,.,.,,,, 340
Цена: 300руб.
