Содержание
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Краткая биография автора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
О пользовании книгой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Состав и структура представления информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Контактная информация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1 Основы функционального программирования . . . . . . . . . . . . . . . . . . 27
В этой главе рассматриваются основополагающие принципы функционального
программирования как отдельного направления в математической науке и тех-
нологии создания программного обеспечения. Приводится история развития
функционального программирования, описываются предпосылки его развития.
В главе рассматривается больше теоретического материала, нежели практи-
ческого, поэтому пока изложение ведется без рассмотрения синтаксиса языка
Haskell. Однако для приведения примеров используется именно этот язык на-
ряду с математическими формулами. Изложение знаний о языке Haskell начи-
нается с главы 2.
1.1 История функционального программирования . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Краткая история развития теории функционального программирования в мире
и в России. Разработка функциональных языков для подтверждения теорети-
ческих выкладок. Проблемы, с которыми столкнулись исследователи при разра-
ботке функциональных языков программирования. Современное состояние тео-
рии функционального программирования. Стандарт Haskell 98 как результат
унификации и стандартизации процессов развития функционального програм-
мирования.
Предпосылки создания функционального программирования . . . . . . . . . . . . . . . . . . . . . . . . 34
История языка Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6 Содержание
Заключительные слова . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42
1.2 Основные свойства функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Описание основных свойств функциональных языков программирования. Крат-
кость и простота, строгая типизация, модульность, функциональные значе-
ния и объекты, чистота и отложенные вычисления. Понимание свойств функ-
циональных языков на примере языка Haskell.
Краткость и простота . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44
Строгая типизация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Модульность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50
Функции _ это значения и объекты вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Чистота (отсутствие побочных эффектов и детерминированность) . . . . . . . . . . . . . 53
Отложенные (ленивые) вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.3 Типовые задачи, решаемые методами ФП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Краткое описание семи типовых задач, которые решаются методами функ-
ционального программирования. Получение остаточной процедуры. Построение
математического описания функций. Определение формальной семантики язы-
ка программирования. Описание динамических структур данных. Автоматиче-
ское построение ѕзначительнойї части программы по описанию структур дан-
ных, которые обрабатываются создаваемой программой. Доказательство нали-
чия некоторого свойства программы. Эквивалентная трансформация программ.
Получение остаточной процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Построение математического описания функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Определение формальной семантики языка программирования . . . . . . . . . . . . . . . . . . . . . 64
Описание динамических структур данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64
Автоматическое построение ѕзначительнойї части программы по описанию струк-
тур данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Доказательство наличия некоторого свойства программы . . . . . . . . . . . . . . . . . . . . . . . . .67
Эквивалентная трансформация программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
1.4 Конструирование функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Описание метода конструирования функций, предложенного Ч. Хоаром (син-
таксически ориентированное конструирование). Метаязык для конструирова-
ния функций. Примеры определения типов и функций для обработки этих ти-
пов.
Декартово произведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Размеченное объединение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71
Содержание 7
Примеры определения типов данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72
1.5 Доказательство свойств функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .86
Задача доказательства свойств функций. Описание процесса доказательства
свойств функций в зависимости от типа области определения функций. При-
меры доказательства свойств функций.
Область определения D _ линейно-упорядоченное множество . . . . . . . . . . . . . . . . . . . . .88
Множество D определяется как индуктивный класс . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .89
Рассмотрение некоторых примеров доказательства свойств функций . . . . . . . . . . . . .91
Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
2 Базовые принципы языка Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .99
Глава посвящена введению в основные положения языка Haskell, приводится опи-
сание синтаксиса для решения основных задач по созданию отдельных функций
и законченных модулей. Рассматриваются базовые объекты ѕсписокї и ѕфунк-
цияї для изучения в рамках функционального программирования, а также их
реализация на языке Haskell.
2.1 Списки _ основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .100
Понятие списка в функциональном программировании. Списки как основная
структура для работы с функциональными языками. Базисные операции для ра-
боты со списками. Списки и списочные структуры. Программная реализация
списков в функциональных языках. Списки в языке Haskell. Генераторы списков
и математические последовательности. Бесконечные списки и другие структу-
ры данных. Кортежи.
Проекция списков в язык Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Несколько слов о программной реализации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104
Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Определители списков и математические последовательности . . . . . . . . . . . . . . . . . . 110
Кортежи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
2.2 Списки _ основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .118
Функция _ основной объект изучения функционального программирования. Со-
глашения по именованию объектов в языке Haskell. Описание и определение
функций на языке Haskell. Образцы и клозы. Передача параметров и возвращение
значений функциями. Инфиксный способ записи функций. Функция как объект
8 Содержание
для передачи в другие функции. Программа на языке Haskell _ функция, описы-
вающая процесс вычисления.
Соглашения по именованию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .118
Общий вид определения функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Образцы и клозы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Вызовы функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Использование _-исчисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Инфиксный способ записи функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Несколько слов о функциях высшего порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
2.3 Списки _ основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131
Структуры и типы данных. Типы функций. Каррированные и некаррированные
функции. Язык Haskell и его механизмы для организации каррированных и некар-
рированных функций. Описание типов функций на языке Haskell. Частичное
применение. Ленивые (отложенные) вычисления на языке Haskell.
Структуры данных и их типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Синонимы типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Типы функций в функциональных языках . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .137
Полиморфные типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .140
2.4 Списки _ основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142
Охраняющие выражения и конструкции. Локальные переменные для оптими-
зации кода на функциональном языке и на языке Haskell. Использование накап-
ливающего параметра (аккумулятора) для оптимизации процесса вычислений.
Принципы построения определений функций с накапливающим параметром. Го-
ловная и хвостовая рекурсии.
Охрана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Ветвление алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
Локальные переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .146
Двумерный синтаксис . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Накапливающий параметр _ аккумулятор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
Принципы построения определений с накапливающим параметром . . . . . . . . . . . . . . . 152
2.5 Списки _ основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153
Модули как способы структуризации и организации программ на языке Haskell.
Импорт и экспорт данных при помощи модулей. Сокрытие данных. Абстракт-
ные типы данных и интерфейсы. Иные аспекты использования модулей.
Содержание 9
Абстрактные типы данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
Другие аспекты использования модулей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
Литературный код . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .160
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
3 Классы и их экземпляры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Эта глава посвящена рассмотрению симбиоза парадигм функционального
и объектно-ориентированного программирования. Большинство современных
функциональных языков поддерживают механизмы и методы, разработанные в
рамках объектно-ориентированного программирования, в том числе и такие ба-
зовые концепты, как ѕнаследованиеї, ѕинкапсуляцияї и ѕполиморфизмї. Не обо-
шел своим вниманием этот аспект и язык Haskell, в котором имеются доста-
точные средства для программирования в объектно-ориентированном стиле.
3.1 Параметрический полиморфизм данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Понятие класса и его реализации в языке Haskell. Чистый (параметрический)
полиморфизм на языке Haskell. Примеры параметрического полиморфизма в им-
перативных и функциональных языках, а также в языке Haskell.
3.2 Классы в языке Haskell как способ абстракции действительности . . . . . 170
Расширенное описание понятия класса в языке Haskell. Класс как высшая аб-
стракция данных и методов для их обработки. Методы класса _ шаблоны функ-
ций для реализации обработки данных. Минимальное описание методов класса
и связь методов.
Модель типизации Хиндли-Милнера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .171
Определение классов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
3.3 Наследование и реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Наследование классов и наследование методов. Экземпляры классов _ реализа-
ция интерфейсов, предоставляемых реализуемым классом. Реализация методов
для обработки данных. Класс _ шаблон типа, реализация класса _ тип данных.
Наследование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .180
Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .182
Реализация для существующих типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
Сорта типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
Дополнительные возможности при определении типов данных . . . . . . . . . . . . . . . . . . .189
10 Содержание
3.4 Стандартные классы языка Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
Краткое описание всех стандартных классов, разработанных для облегчения
программирования на языке Haskell. Дерево наследования стандартных классов.
Типичные способы использования стандартных классов языка Haskell. Реализа-
ция стандартных классов _ типы в языке Haskell.
Класс Bounded . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192
Класс Enum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
Класс Eq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Класс Floating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Класс Fractional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
Класс Functor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .197
Класс Integral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
Класс Ix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Класс Monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Класс Num . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Класс Ord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
Класс Read . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
Класс Real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
Класс RealFloat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
Класс RealFrac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
Класс Show . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
3.5 Сравнение с другими языками программирования . . . . . . . . . . . . . . . . . . . . . 207
Более или менее полное сравнение понятий ѕклассї и ѕреализация классаї в язы-
ке Haskell с объектно-ориентированными языками программирования (на приме-
ре языков C++ и Java, а также некоторых других языков). Глобальные отличия
понятия ѕклассї в функциональных и объектно-ориентированных языках.
Окончательные замечания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .209
Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .210
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
4 Монады _ императивный мир в функциональной парадигме .213
Глава описывает такое незаурядное понятие, введенное в функциональной па-
радигме программирования, как ѕмонадаї. Монады, основанные на математи-
ческой теории категорий, позволяют внедрить в функциональный подход опре-
деленные структуры для выполнения императивных действий, как, например,
Содержание 11
операции ввода/вывода, обработка исключений, хранение состояний в процес-
се вычислений, и многие другие действия, связанные с побочными эффектами.
Вместе с тем монады позволяют обернуть императивные действия в функци-
ональную оболочку, спрятав все от ѕимперативного мираї внутри монады.
4.1 Монада как тип-контейнер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
Описание монады как типа-контейнера. Использование монад в функциональ-
ных языках. Свойства монадических типов. Операции связывания с передачей
и без передачи результата выполнения операции на предыдущем шаге. Правила
построения монад.
Определение понятия ѕмонадаї . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
Нотация do . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
Правила построения монад . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
4.2 Последовательное выполнение действий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .222
Действие _ элемент функциональной парадигмы. Императивный код внутри
функционального. Выполнение действий и возвращение результата. Сокращен-
ный способ записи последовательности действий. Списки действий. Програм-
мирование при помощи действий.
Класс Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
Монада State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
4.3 Операции ввода/вывода в языке Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .239
Более или менее полное описание базовых операций ввода/вывода в языке Haskell.
Монада IO. Обработка исключений. Использование файлов, каналов и обработчи-
ков. Нарушение теоретических принципов функционального программирования
в монаде IO.
Действия ввода/вывода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
Программирование при помощи действий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
Обработка исключений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
Файлы и потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
Окончательные замечания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .251
4.4 Стандартные монады языка Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
Подробное описание монадических типов в стандартной библиотеке языка
Haskell. Назначение и применимость монадических типов. Примеры использо-
вания стандартных монадических типов (кроме списков и монады IO). Модуль
Monad. Монады Glasgow Haskell Compiler.
12 Содержание
Модуль Monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
Стандартные монады . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
4.5 Разработка собственных монад . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
Критерии возможности и необходимости разработки собственного монадиче-
ского типа. Комбинирование монадических вычислений. Преобразователи монад.
Примеры преобразования.
Комбинирование монадических вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .263
Преобразователи монад . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
Пример с преобразователем StateT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
Окончательные замечания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .268
Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .269
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
5 Комбинаторная логика и _-исчисление . . . . . . . . . . . . . . . . . . . . . . . . 273
В главе рассматриваются основополагающие теоретические формализмы, ко-
торые стояли у истоков функционального программирования, а именно ком-
бинаторная логика и _-исчисление, разработанные в качестве расширений фор-
мальной логики и теории множеств в начале XX в. Приводятся самые основы
этих направлений дискретной математики, достаточные для понимания сути
того, что в свое время стояло за парадигмой функционального программирова-
ния.
5.1 Основы комбинаторной логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
Введение в комбинаторную логику. Поверхностное описание принципов комбина-
торной логики. Комбинаторы и вычисления при помощи комбинаторов. Базисы
в комбинаторной логике. Использование базисных комбинаторов для выраже-
ния любых вычислительных процессов. Числа и иные математические объекты
в виде комбинаторов.
Базовые комбинаторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
Комбинатор неподвижной точки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
Нумералы и арифметические операции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
Заключительные слова . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .286
5.2 Абстракция функций как вычислительных процессов . . . . . . . . . . . . . . . . . 288
Функция _ объект математического исследования. Вычислительный процесс _
функция. Описание функций как _-выражений. Свободные и связанные иденти-
Содержание 13
фикаторы. Применение (аппликация) значений к _-выражениям. Непрерывная
точка функций и теорема о непрерывной точке.
ѕНаивноеї определение _-исчисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
Связь с комбинаторной логикой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
Редукция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
Тезис Черча-Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
5.3 _-исчисление как теоретическая основа функционального программирова-
ния . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .298
Предположение о том, что любая функция представима в виде _-выражения.
Интенсионал и экстенсионал функций. Формальная система. Построение фор-
мальной системы для обоснования теории функционального программирования.
Правила вывода. Соответствия между вычислениями функциональных про-
грамм и редукцией _-выражений.
Построение формальной системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
Функциональное программирование как формальная система . . . . . . . . . . . . . . . . . . . . . 303
Теорема Черча-Россера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
5.4 Кодирование данных в _-исчислении . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
Механизм кодирования данных в _-исчислении. _-исчисление _ достаточный
формализм для представления значений истинности, упорядоченных пар, на-
туральных чисел, списков, а также базовых операций над этими объектами.
Булевские значения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
Упорядоченные пары . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
Натуральные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
Списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
5.5 Редукция и вычисления в функциональных языках . . . . . . . . . . . . . . . . . . . .315
Понятие редукции. Частичные вычисления с точки зрения редукции
_-выражений. Различные редукционные стратегии и их свойства.
Стратегия редукции и стратегия вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
Ленивая редукция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .327
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
6 Трансляторы программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .331
14 Содержание
В главе 6 представлено краткое описание теории построения трансляторов
для интерпретации и компиляции языков программирования. Теория рассмат-
ривается на примерах, написанных на языке Haskell. Кроме того, рассматрива-
ются способы построения парсеров, а также готовые библиотеки для синтак-
сического анализа. Суперкомпиляция.
6.1 Математическая лингвистика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .331
Краткое введение в математическую лингвистику. Обзор методов и принци-
пов математической лингвистики. Классификация языков и грамматик. Ко-
нечные автоматы и контекстно-свободные языки. Грамматики типа LL(k).
Контекстно-зависимые грамматики.
Базовые понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
Расширенная нотация Бэкуса _ Наура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
Классификация грамматик . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
Конечные лингвистические автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
Синтаксический анализ контекстно-свободных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
6.2 Краткое введение в теорию построения трансляторов . . . . . . . . . . . . . . . . . 346
Трансляторы: определения, типы и классификация, применимость для тех или
иных типов языков и грамматик. Интерпретаторы и компиляторы. Компиля-
торы компиляторов. Методы построения трансляторов. Автоматическое по-
строение транслятора по грамматике языка (для ограниченного множества
языков). Понятие трансформационной грамматики.
Классификация трансляторов и их типовые структуры . . . . . . . . . . . . . . . . . . . . . . . . . 347
Трансформационные грамматики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
Автоматическое построение анализатора для отдельных типов языков . . . . . . . . . 358
6.3 Реализация трансляторов на языке Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . .360
Функциональные языки, как естественный инструмент реализации транслято-
ров. Синтаксические анализаторы. Методы написания трансляторов на языке
Haskell. Примеры синтаксических анализаторов для различных форматов дан-
ных. Пример вычисления арифметических выражений, записанных в различной
нотации.
Простейшие парсеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .361
Комбинаторы синтаксического анализа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
Дополнительные комбинаторы синтаксического анализа . . . . . . . . . . . . . . . . . . . . . . . . . 366
Анализ нотации Бэкуса _ Наура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
Содержание 15
6.4 Библиотеки для создания трансляторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .372
Описание имеющихся библиотек для языка Haskell, предназначенных для созда-
ния трансляторов. Монадическая библиотека Parsec для самостоятельного со-
здания трансляторов. Компилятор компиляторов Happy.
Монадическая библиотека парсеров Parsec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
Компилятор компиляторов Happy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
6.5 Частичные вычисления, трансформация программ и суперкомпиляция 381
Задача трансформации программ. Частичные вычисления, как инструмент
для трансформации программ. Частичный вычислитель _ инструмент для по-
лучения остаточного кода заданной функциональной программы. Интерпрета-
тор, компилятор и компилятор компиляторов, их связь. Проекции Футамуры-
Турчина. Суперкомпиляция.
Частичные вычисления и трансляция программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
Проекции Футамуры _ Турчина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .385
Трансформация программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .392
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
7 ФП и искусственный интеллект . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
Заключительная глава книги рассматривает такую область человеческого зна-
ния, как искусственный интеллект, то есть методы решения слабоформали-
зованных задач, для которых не существует алгоритмического решения либо
такое решение слишком сложно. Такой интерес связан с тем, что именно па-
радигма функционального программирования нашла свое непосредственное при-
менение в рамках искусственного интеллекта.
7.1 Основные задачи искусственного интеллекта . . . . . . . . . . . . . . . . . . . . . . . . . . .396
Историческая справка о развитии искусственного интеллекта, как области на-
учного исследования. Введение в базовые понятия искусственного интеллекта.
Место функционального программирования в искусственном интеллекте. Функ-
циональное и логическое программирования. Задачи искусственного интеллек-
та, которые могут быть решены при помощи методов и средств функциональ-
ного программирования.
История развития искусственного интеллекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .398
Различные подходы к построению систем искусственного интеллекта . . . . . . . . . . . 402
Место функционального программирования в искусственном интеллекте . . . . . . . .405
16 Содержание
7.2 Нечеткая математика и функциональное программирование . . . . . . . . . . 407
Небольшой экскурс в нечеткую математику. Функции принадлежности и линг-
вистические переменные. Базовые операции над функциями принадлежности.
Кусочно-линейные функции принадлежности. Операции сравнения, арифмети-
ческие и логические операции над кусочно-линейными функциями принадлежно-
сти. Использование языка Haskell для реализации методов обработки кусочно-
линейных функций принадлежности.
Базовые концепты нечеткой логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
От нечеткой логики к нечеткой математике . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
Функции принадлежности как способ описания нечетких значений . . . . . . . . . . . . . . 411
Нечеткие и лингвистические переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
Операции над функциями принадлежности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
Пример модуля на языке Haskell для обработки кусочно-линейных функций принад-
лежности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
7.3 Логический вывод на знаниях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
Знания и данные. Модели представления знаний. Понятие логического вывода
на знаниях. Стратегии вывода на знаниях. Машины вывода. Эволюция машин-
ного вывода на знаниях. Интерпретаторы функциональных языков как есте-
ственные машины вывода. Язык Haskell и его возможности в логическом выводе
на знаниях. Универсальный вывод на продукционной модели знания.
Знания и данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
Вывод на знаниях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
Прямой нечеткий вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
Обратный нечеткий вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
Некоторые окончательные замечания о машинном выводе . . . . . . . . . . . . . . . . . . . . . . . . 442
7.4 Общение с компьютером на естественном языке . . . . . . . . . . . . . . . . . . . . . . . 443
Принципы общения с компьютерными системами на естественном языке. Огра-
ниченный естественный язык, деловая проза. Трансляция фраз на естественном
языке во внутренний язык представления смысла. Понимание текстов на есте-
ственном языке. Использование методов функционального программирования.
Обобщенная схема интеллектуальных диалоговых систем . . . . . . . . . . . . . . . . . . . . . . . . 444
Схема анализа входного текста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
Некоторые окончательные замечания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
7.5 Перспективы функционального программирования . . . . . . . . . . . . . . . . . . . . 454
Содержание 17
Описание видения будущего функционального программирования, функциональ-
ных языков и языка Haskell. Значение функциональной парадигмы для техноло-
гии программирования вообще.
Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .460
Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
Ответы на задачи для самостоятельного решения . . . . . . . . . . . . . . . . . 465
Решения задач из главы 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
Решения задач из главы 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
Решения задач из главы 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
Решения задач из главы 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
Решения задач из главы 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
Решения задач из главы 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
A Функциональные языки программирования и Интернет-ресурсы
по функциональному программированию . . . . . . . . . . . . . . . . . . . . . . . . . 496
Список наиболее известных и широко используемых функциональных языков
программирования с краткой аннотацией. Список Интернет-ресурсов, посвя-
щенных функциональному программированию как в русском сегменте Интерне-
та, так и во всем остальном мире.
Функциональные языки программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496
Русские Интернет-ресурсы по функциональному программированию . . . . . . . 502
Иностранные Интернет-ресурсы по функциональному программированию . . 503
B Опции различных сред разработки на языке Haskell . . . . . . . . . 506
Описание типичных настроек интегрированных сред разработки и компилято-
ров на примере продуктов HUGS 98 и GHC для полноценной работы и выполне-
ния различных задач на языке Haskell. Список команд, ключей командной строки
и внутренних директив интерпретатора HUGS 98. Список параметров команд-
ной строки для компилятора GHC. Другие функциональные средства разработ-
ки.
Интегрированная среда разработки HUGS 98 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
Компилятор GHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .510
Компилятор NHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .523
Компилятор компиляторов Happy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
18 Введение
C Описание стандартного модуля Prelude . . . . . . . . . . . . . . . . . . . . . . . 530
Список функций из стандартного модуля языка Haskell Prelude с более или менее
подробным описанием.
Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
Описание некоторых операторов языка Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
D Краткий словарь терминов из области функционального програм-
мирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588
Краткий словарь терминов, имеющих отношение к функциональному програм-
мированию. для каждого термина даются ссылки на страницы, где он описан,
а также переводы на некоторые иностранные языки.
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598
Общая литература по функциональному программированию . . . . . . . . . . . . . . . . 598
Книги, руководства и статьи по языку Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
Комбинаторная логика и _-исчисление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
Математическая лингвистика и теория построения трансляторов . . . . . . . . . . . 602
Искусственный интеллект . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603