ISSN 2075-8456

9 772075 845008
Последняя ревизия этого выпуска журнала, а также последующие
выпуски могут быть загружены с сайта http://fprog.ru/.
Авторы журнала будут благодарны за любые замечания и предло-
жения, присланные по адресам электронной почты, указанным в
заголовках статей.
Редакция журнала: [email protected].

Журнал «Практика функционального программирования»

Авторы статей: Дмитрий Астапов
Роман Душкин
Сергей Зефиров
Евгений Кирпичёв
Алексей Отт
Дэн Пипони (в переводе Кирилла Заборского)
Редактор: Лев Валкин
Корректор: Ольга Боброва
Иллюстрации: Обложка
©iStockPhoto/Matt Knannlein
©iStockPhoto/Branislav Tomic
Круги ада
©iStockPhoto/Yuri Schipakin
Шрифты: Текст
Myriad Pro © Adobe Systems Inc.
Обложка
Days © Александр Калачёв, Алексей Маслов
Cuprum © Jovanny Lemonad
Ревизия: 495 (2009-09-13)

Журнал «Практика функционального программиро-

вания» распространяется в соответствии с условия-
ми Creative Commons Attribution-Noncommercial-No
Derivative Works 3.0 License.
Копирование и распространение приветствуется.
Сайт журнала: http://fprog.ru/
© 2009 «Практика функционального программирования»
Оглавление

От редактора 5

1. Лень бояться. Сергей Зефиров 10

1.1. Обязательное условие . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2. Сравнение с лучшим образцом . . . . . . . . . . . . . . . . . . 14
1.3. Ленивый код . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4. Размышления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5. Чистый параллелизм . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2. Функции и функциональный подход. Роман Душкин 22

2.1. Простые примеры функций . . . . . . . . . . . . . . . . . . . . . 24
2.2. Теоретические основы функционального подхода . . . . . . 30
2.3. Дополнительные примеры с отдельными элементами про-
граммирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4. Общие свойства функций в функциональных языках про-
граммирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3. Изменяемое состояние: опасности и борьба с ними. Евгений

Кирпичёв 41
3.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2. Опасности изменяемого состояния . . . . . . . . . . . . . . . . 42
3.3. Круги ада . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4. Борьба . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.5. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Оглавление Оглавление

4. Давно не брал я в руки шашек. Дмитрий Астапов 76

4.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.2. Постановка задачи и функция main . . . . . . . . . . . . . . . . 78
4.3. Формализация правил игры . . . . . . . . . . . . . . . . . . . . 80
4.4. Компьютерный игрок с примитивной стратегией . . . . . . . 84
4.5. Сбор информации о доступных ходах со взятием . . . . . . . 87
4.6. Сбор информации о доступных ходах: вторая попытка . . . 89
4.7. Передвижение фигур . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.8. Доска, фигуры, координаты . . . . . . . . . . . . . . . . . . . . . 94
4.9. Выход в «дамки» и отображение состояния доски . . . . . . . 96
4.10. Создание доски . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.11. Диагонали . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.12. Реализация availableAttacks и availableMoves . . . . . . . . . . 102
4.13. Финальные штрихи . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.14. Разбиение программного кода на модули . . . . . . . . . . . . 108
4.15. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

5. Моноиды в Haskell и их использование. Dan Piponi 113

5.1. Определение моноидов . . . . . . . . . . . . . . . . . . . . . . . 114
5.2. Некоторые применения моноидов . . . . . . . . . . . . . . . . 115
5.3. Монада Writer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.4. Коммутативные моноиды, некоммутативные моноиды и ду-
альные моноиды . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.5. Произведение моноидов . . . . . . . . . . . . . . . . . . . . . . 121
5.6. «Сворачиваемые» данные . . . . . . . . . . . . . . . . . . . . . . 123
5.7. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

6. Обзор литературы о функциональном программировании.

Алексей Отт 126
6.1. Литература на русском языке . . . . . . . . . . . . . . . . . . . 127
6.2. Англоязычная литература . . . . . . . . . . . . . . . . . . . . . . 138
6.3. Рекомендации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.4. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

© 2009 «Практика функционального программирования» ii

От редактора

Языки программирования, используемые в разработке промышлен-

ных систем, не стоят на месте. Вводятся в оборот новые идиомы, да и са-
ми языки расширяются с целью добавления возможности оперировать
абстракциями более высокого порядка. Языки C# и Visual Basic обзаве-
лись абстракцией LINQ, позволяющей декларативно производить запро-
сы к структурированной информации, базам данных. В язык Java добави-
ли обобщённые типы данных («generics»); велись жаркие дебаты по добав-
лению замыканий в стандарт Java 7 [2]. Замыкания и лямбда-выражения
появляются в новой редакции стандарта C++. Да и предлагавшаяся аб-
стракция «концептов» в C++, структурирующая описание полиморфных
интерфейсов, возникла из необходимости бороться с нарастающей слож-
ностью создаваемых человеком информационных систем. Есть ли что-
то общее между этими нововведениями, или разные языки развиваются
независимо и разнонаправленно?
Как оказывается, общий вектор развития языков прослеживается без
особого труда. С целью повышения уровня абстракции от аппаратуры и
приближения к проблемным областям всё большее количество концеп-
ций, созданных в рамках парадигмы функционального программирова-
ния, находят своё место в императивных языках.
Функциональная парадигма программирования и функциональные
¹Неформальный термин «промышленная система» или «промышленный язык» ис-
пользуется для контраста с «академическими», «учебными» или «экспериментальными»
системами и языками.
²Пока верстался номер, комитет по стандартизации C++ принял решение воздер-
жаться от включения «концептов» в новый стандарт языка [6], не сумев упростить пред-
ложенное расширение до состояния работоспособности.
языки уже долгое время являются источником «новых» идей в массо-
вых языках программирования. Отказ от ручного управления памятью
и использование сборщика мусора (Smalltalk, Java, C#) пришли из функ-
циональных языков типа LISP, где сборка мусора появилась ещё в 1959
году. Генераторы списков в языке Python и новом стандарте JavaScript
пришли из функциональных языков Haskell и Miranda, впервые появив-
шись в функциональном языке NPL. Некоторые абстракции в императив-
ных языках разработаны почти независимо от соответствующих абстрак-
ций в функциональных языках, но развиваются десятилетиями позже. Так,
например, проект «концептов» в новом стандарте C++ соответствовал
«классам типов» в языке Haskell, появившимся в нём в 1989 году [1].
Технология LINQ в .Net тоже является прямым результатом мышления
в функциональном стиле. Не случайно, что автор LINQ, Эрик Мейер [3, 4],
является одним из дизайнеров функционального языка Haskell. Вот что
говорит ведущий архитектор языка C#, а также создатель Turbo Pascal и
Delphi, Андерс Хейлсберг [5]:

Функциональное программирование, по-моему, — чрез-

вычайно интересная парадигма. Если взглянуть на C# 3.0, то
станет видно, что именно идеи из мира функционального
программирования послужили источником вдохновения для
LINQ и составляющих его элементов языка. Мне кажется, сей-
час, наконец, наступил момент, когда функциональному про-
граммированию пора выйти в массы.

Как мы видим, элементы функционального программирования прони-

кают в массы путём постепенного внедрения в обычные, императивные
языки. Что необходимо программисту для эффективного использования
этих элементов? Мы убеждены, что для наиболее эффективного усвоения
того или иного метода или парадигмы программирования, их нужно изу-
чать в максимально чистом виде, удалённом от «мусора» альтернативных
подходов. Владение функциональной парадигмой в её «чистом» виде поз-
воляет эффективно применять новые функциональные элементы совре-
менных языков для управления сложностью разрабатываемых систем, а
³List comprehensions, нотация, позволяющая создавать и фильтровать списки элемен-
тов декларативным путём.

© 2009 «Практика функционального программирования» 6

также существенно обогащает набор инструментов, доступных для реше-
ния той или иной задачи.

Практика функционального программирования

Вашему вниманию представляется первый выпуск журнала, посвя-
щённого практике функционального и декларативного программирова-
ния. Мы ставим своей задачей помочь вам сориентироваться в инстру-
ментарии функционального программирования, в используемых в функ-
циональной парадигме подходах к декомпозиции задач, способах упро-
щения программирования и снижения количества дефектов в разрабаты-
ваемых системах.
Первый номер журнала посвящён погружению в предмет функцио-
нального программирования. Вводные статьи Сергея Зефирова «Лень бо-
яться» и Романа Душкина «Функции и функциональный подход» затра-
гивают философию парадигм программирования. Более практически на-
правленная часть журнала представлена статьёй Евгения Кирпичёва «Из-
меняемое состояние: опасности и борьба с ними», классифицирующей ти-
пы проблем, возникающих при небрежном использовании сущностей с
изменяемым состоянием, и следующей за ней статьёй Дмитрия Астапова
«Давно не брал я в руки шашек», на протяжении нескольких страниц рас-
крывающей подход проектирования «сверху вниз» на подробном приме-
ре написания игры в шашки на языке Haskell. Статья Дэна Пипони «Моно-
иды в Haskell и их использование» в переводе Кирилла Заборского про-
стым языком обьясняет практическое применение моноидов для созда-
ния элегантных полиморфных алгоритмов. Номер завершается внуши-
тельным «Обзором литературы о функциональном программировании»
Алексея Отта, содержащим множество ссылок на русскоязычную и англо-
язычную литературу по разным языкам и аспектам декларативного про-
граммирования.
Авторский коллектив журнала состоит из профессионалов промыш-
ленного программирования, участников международных олимпиад, кон-
курсов и конференций по функциональному программированию и пре-
подавателей вузов России, стран ближнего и дальнего зарубежья.
Приятного чтения!

© 2009 «Практика функционального программирования» 7

Литература Литература

Лев Валкин, [email protected]

Литература
[1] A comparison of C++ concepts and Haskell type classes / J.-P. Bernardy,
P. Jansson, M. Zalewski et al. // WGP ’08: Proceedings of the ACM SIGPLAN
workshop on Generic programming. — New York, NY, USA: ACM, 2008. —
Pp. 37–48.

[2] Closures for the Java Programming Language (v0.5). — Предло-

женное дополнение к языку Java: URL: http://www.javac.info/
closures-v05.html (дата обращения: 20 июля 2009 г.).

[3] Erik Meijer. On LINQ. — Видеоинтервью: URL: http://www.infoq.

com/interviews/erik-meijer-linq (дата обращения: 20 июля
2009 г.). — 2007. — Создатель LINQ, Эрик Мейер, рассказывает о ди-
зайне и возможностях LINQ, о том, как его использовать, зачем его
использовать, чем LINQ отличается от XQuery, как LINQ связывается
с ORM и о многом другом.

[4] Erik Meijer. Functional Programming. — Канал 9 MSDN: URL:

http://channel9.msdn.com/shows/Going+Deep/
Erik-Meijer-Functional-Programming/ (дата обращения:
20 июля 2009 г.). — 2008. — Видео, в котором Эрик Мейер, архитектор
Microsoft SQL Server, Visual Studio и .Net, рассказывает о функци-
ональном программировании, академических и промышленных
применениях функциональных языков.

[5] The A-Z of Programming Languages: C#. — Статья в Computerworld: URL:

http://www.computerworld.com.au/article/261958/-z_
programming_languages_c (дата обращения: 20 июля 2009 г.). —
2008. — Интервью с ведущим архитектором языка C#, Андерсом
Хейлсбергом.

[6] The Removal of Concepts From C++0x. — Статья в InformIT: URL:

http://www.informit.com/guides/content.aspx?g=

© 2009 «Практика функционального программирования» 8

Литература Литература

cplusplus&seqNum=441 (дата обращения: 20 июля 2009 г.). —

2009. — Рассматриваются причины отказа от включения «концептов»
в стандарт языка C++.

© 2009 «Практика функционального программирования» 9

 Лень бояться
Неформальная статья о ленивых вычислениях

Сергей Зефиров
[email protected]

Аннотация

Интересующиеся функциональным программированием

часто встречают прилагательное «ленивый» в связи с таки-
ми существительными, как «язык» и «порядок вычислений».
Встретив же, идут в интернет и находят что-то наподобие
«ленивый порядок вычислений, иначе называемый вызов-
по-необходимости, строго нормализующий порядок вычис-
лений, удовлетворяющий условиям алмазной леммы Чёрча-
Россера», после чего ближайшее знакомство с функциональ-
ными языками откладывается на потом.
Небольшой опус, введение к которому вы читаете, пред-
ставляет собой попытку неформально объяснить, что же та-
кое «ленивые вычисления». Они часто встречаются в повсе-
дневной жизни программиста и, на мой взгляд, по своей сути
не сложнее новой платформы или компьютерной архитекту-
ры.
1.1. Обязательное условие

1.1. Обязательное условие

Ни один язык программирования не обходится без условных кон-
струкций. В большинстве языков они являются неотъемлемой частью син-
таксиса и семантики (смысла конструкций языка) и поэтому воспринима-
ются как нечто, данное свыше. Соответственно, их редко рассматривают
в подробностях, хотя они весьма интересны, ведь именно здесь програм-
мист впервые встречается с ленивыми вычислениями.
На Си и его спутниках самая распространенная условная конструк-
ция — оператор ветвления if:
if ( condition ) {
action1
} else {
action2
}
При рассуждении о программе с условием мы делаем, фактически,
подстановку действий: сначала из action1, а потом из action2. При её вы-
полнении процессор и в самом деле выполняет подстановку — по край-
ней мере, результат выполнения программы с условными переходами на
глаз неотличим от результата выполнения программы с условной подста-
новкой.
Умозрительная и физическая подстановки действий грубо соответ-
ствуют одному из порядков вычисления функциональных программ —
порядку под названием call-by-name (передача-по-имени). Вкратце его
можно описать так: ничего не вычисляй сразу, результаты вычислений
могут не понадобиться, запоминай вычисления. В императивных языках
считается, что вычисления внутри одной из ветвей понадобятся сразу, как
только станет возможным вычислить условие.
Обычная реализация передачи-по-имени сводится к построению
структур в памяти: вместо вычисления x+y создаётся узел дерева +(x, y),
вместо тяжёлого вызова f (x) создаётся узел call(f, x). Когда же требует-
ся значение вычисления, вызывается интерпретатор структур.
Более привычный порядок вычислений называется call-by-value
(передача-по-значению). В нём всё честно: всё надо вычислять всегда.
Увидев вычисление, надо немедленно его произвести, сохранить резуль-

© 2009 «Практика функционального программирования» 11

1.1. Обязательное условие

тат в переменную, подставить как аргумент или вернуть как результат

выполнения функции. Большинство языков программирования так себя
и ведут большую часть времени, пока не дойдут до условного оператора.
Такая смесь двух способов вычислений с преобладанием call-by-value
называется энергичным порядком вычислений [3].
Передача-по-значению приводит к необходимости защиты от излиш-
них вычислений, как в примере из Таблицы 1.1. Сначала результат слож-
ного и дорогого вычисления требовался в обеих ветвях условия. Потом у
нас изменились требования, он стал требоваться только в одной ветви, и,
по-хорошему, нам надо перенести вычисления внутрь условия.

Было Отредактировали Надо

x = COMPUTATION; x = COMPUTATION;
if (condition) {
if (condition) { if (condition) {
a = COMPUTATION;
a = x; a = x;
} else {
} else { } else {
b = 10;
b = −x; b = 10;
}
} }

Таблица 1.1. Защита от ненужных вычислений

Если бы мы использовали порядок вычисления call-by-name, то можно

было бы остановиться на втором варианте, сэкономив время на рефакто-
ринг. При выполнении в x положат не результат, а запрос на вычисления,
переменная a также будет работать с запросом, и он будет вычислен, толь-
ко когда (и если!) понадобится.
Прямое использование call-by-name с её практически текстовыми
подстановками само по себе не очень эффективно. Возьмем простую по-
следовательность: x = z + 1; y = x × x. В y попадёт запрос на вычисление
×(+(z, 1), +(z, 1)). Значение z будет вычислено два раза, два раза будет
выполнено сложение. Пустая трата ресурсов.
Поэтому был изобретён ещё один способ вычислений — call-by-need.
Это подстановка с запоминанием. Последовательность x = z + 1; y = x × x
так и останется этой последовательностью. Если нам потребуется y , то мы
вычислим левый аргумент выражения x, и далее по цепочке, и запомним,

© 2009 «Практика функционального программирования» 12

1.1. Обязательное условие

что x чему-то равен. Когда мы приступим к вычислению правого аргумен-

та умножения, мы просто возьмём уже вычисленное значение. Вуаля! Вы-
числение z требуется всего один раз, и сложение срабатывает тоже один
раз.
Метод call-by-need называется «ленивым порядком вычислений».
Таким образом, мы имеем дело с тремя методами вычислений:

call-by-value Известен как «энергичный порядок вычислений» или «стро-

гий порядок вычислений». Встречается чаще всего. Вычислит всё,
до чего дотянется, если не контролировать каждый шаг. Для полно-
ценной работы требует call-by-name в заметных дозах. Проще всего
реализуется, поэтому столь распространён.

call-by-name Простая подстановка структуры вычислений. Вычислит

только нужное, но может вычислять некоторые части нужного боль-
шее количество раз, чем требуется. В языках программирования
встречается в малых объёмах из-за низкой эффективности реали-
зации. Основной прием в рассуждениях о программах, как импера-
тивных, так и функциональных.

call-by-need Ленивый порядок вычислений. Со стороны выглядит как

предыдущий, только работает быстрее. Считается, что встречается
редко и только в специально отведённых местах. Тем не менее, он
часто встречается в обычных программах (вычисление по требова-
нию с запоминанием) и используется при оптимизации программ
для устранения повторных вычислений.

Только один известный язык программирования — Algol-60 — ис-

пользовал семантику call-by-name в промышленных масштабах. Осталь-
ные либо подходят к делу не столь радикально и применяют её только по
месту, либо делают гораздо более широкий шаг и сразу берутся за полно-
стью ленивые вычисления.
¹Call-by-name и call-by-need Тьюринг-полны, в то время как основная для большин-
ства языков семантика сall-by-value не является Тьюринг-полной. Условные конструкции
с семантикой сall-by-name обеспечивают таким языкам Тьюринг-полноту.

© 2009 «Практика функционального программирования» 13

1.2. Сравнение с лучшим образцом

Главное — то, что некоторая ленивость присутствует практически в

любом языке программирования. Без неё никуда, всего же на свете не вы-
числишь.

1.2. Сравнение с лучшим образцом

Одним из немногих языков, использующих ленивый порядок вычис-
лений, является Haskell. Вот пример небольшой функции на нём:
False && x = False
True && x = x
Это определение оператора && путём сравнения с образцом. Всё до-
статочно прозрачно: если False хотя бы слева, то что бы ни было справа,
ответом будет False, поэтому переменная x игнорируется. Если же слева
True, то результатом будет значение справа.
Результатом False && error ”unreachable!” будет False — до
error дело не дойдёт. А результатом 10/0 == 10 && True будет деление
на ноль.
Для выбора одного из клозов && нам надо вычислить левый аргумент.
Если его значение равно False, то правый аргумент вообще не понадо-
бится!
Внимательный читатель наверняка уже сопоставил эти правила с пра-
вилами вычисления логических связок в языке Си и его спутниках, где
логические связки также вычисляются до понимания результата и не
дальше. В условии if (i≥0 && i<10 && arr[i] != EOF) ... до
проверки arr[i] дело может не дойти (как выше не запустился
error ”unreachable!”).
В стандартном Паскале, где нет закорачивания вычислений логиче-
ских связок (short circuit evaluation [8]), все выражения в приведенном вы-
ше условии будут вычислены. В результате мы получим ошибку выхода за
границы массива, несмотря на то, что проверили все условия.
В C++ нас ожидает другой сюрприз: если мы попытаемся переопреде-
лить оператор && для нового типа данных, мы с удивлением обнаружим,
что && вычисляет оба аргумента.

© 2009 «Практика функционального программирования» 14

1.3. Ленивый код

Ниже я приведу ещё один пример на Хаскеле, на этот раз для логиче-
ского типа со значением «Unknown»:
data BoolU = FALSE ∣ TRUE ∣ Unknown
FALSE && x = FALSE
TRUE && x = x
Unknown && FALSE = FALSE
Unknown && x = Unknown
Только в случае, когда мы не уверены в левом аргументе, мы вынуж-
дены вычислять правый. Поэтому ошибку обращения вне границ массива,
как в примере тремя абзацами выше, мы получим, только если мы не смо-
жем чётко понять, больше ли i нуля и меньше ли i десяти. Но в этом случае
мы эту ошибку заслужили, по-моему.
При реализации на C++ типа enum {False, True, Unknown} опера-
тор && для него будет вести себя одинаково плохо вне зависимости от сте-
пени нашей уверенности в результатах сравнения — он всегда будет вы-
числять оба операнда. Нам придётся придумывать что-то ещё, например,
применять указатели. Чего мы не заслужили — то, что может быть автома-
тизировано, должно быть автоматизировано.
Логические связки — это второе и последнее место в привычных язы-
ках программирования, где дела могут идти ленивым порядком. Осталь-
ное реализуется с помощью обычного программного кода, более или ме-
нее независимого от языка программирования, о чём будет следующая
часть.

1.3. Ленивый код

Выборка данных по SQL запросу часто осуществляется чем-то вроде
строящегося в процессе работы итератора. Мы создаём структуру данных
с двумя функциями: получить голову и получить хвост. Голова будет оче-
редной строкой выборки, а хвост будет вычислением, позволяющим по-
лучить последующие строки (если они есть), по одной строке с хвостом за
раз. Это и есть итератор, только потенциально бесконечный.
И тут мы подходим к причине, по которой ленивые языки трудно ис-
пользовать.

© 2009 «Практика функционального программирования» 15

1.4. Размышления

Мы создали запрос к БД и даже что-то из неё выбрали. В процессе мы

решили, что в БД чего-то не хватает, и добавили туда информацию, кото-
рая может влиять на содержимое нашего SQL запроса. Совсем плохо, если
это решили и добавили не мы.
Получается, что мы можем получить данные, в которых, допустим, на-
рушен порядок сортировки строк. Или можем не получить актуальные
данные.
Иными словами, работая лениво, мы не можем вести простые рассуж-
дения о последовательности действий. А раз не можем рассуждать о по-
следовательности, то не можем просто предсказать время работы.
Это приводит к необходимости чётко разграничивать участки про-
граммы, где последовательность действий надо контролировать, и
остальные, где такой контроль не нужен.
В этом есть и плюсы, и минусы. С одной стороны, добавляется работы
по разделению программы на разные участки — это минус. С другой сто-
роны, как показывает практика, количество кода, где неважно, что за чем
будет вычисляться, больше в разы, если не на порядки.
Получается, что мы экономим свой труд, поскольку в большем количе-
стве мест дополнительная работа не требуется. Экономия состоит и в от-
сутствии необходимости рефакторинга, и в простоте самого рефакторин-
га: в коде, где нет зависимости от порядка вычислений, порядок опреде-
лений не важен. Последовательности определений «x = f (z); y = g(x);»
и «y = g(x); x = f (z);» имеют один и тот же смысл. Мы упрощаем для се-
бя рассуждения о программе, поскольку можем проводить простую тек-
стовую подстановку без оглядок на состояние мира или переменных. Мы,
наконец, можем заглядывать глубоко в структуры данных и использовать
их части напрямую, без боязни, что кто-то их поменяет.

1.4. Размышления
Уже достаточно долго меня мучает вопрос: почему ленивые вычис-
ления так тяжело воспринимаются даже весьма умными людьми? Что их
²В современных функциональных языках такое разграничение поддерживается си-
стемой типов.

© 2009 «Практика функционального программирования» 16

1.4. Размышления

останавливает?
Более или менее приемлемый ответ пришёл ко мне после знаком-
ства с различными параллельными архитектурами вычислительных си-
стем. Если быть кратким, то обычный процессор умеет делать scatter (пи-
сать в любое место памяти) и gather (читать из любого места памяти). Труд-
ности синхронизации двух параллельно выполняющихся процессов раз-
брасывания и собирания данных велики, поэтому их как-то ограничива-
ют: отдавая предпочтение одному из них при реализации, разделяя их во
времени или действуя иначе. Например, процессоры GPU умеют только
gather (причем, в ограниченном объёме), машины динамического потока
данных — scatter (и тоже в ограниченном объёме). Труден и анализ про-
извольной рекурсии, поэтому от неё тоже избавляются (GPU).
Например, на GPU делать обработку изображений просто, а анализ —
тяжело; с задачей «получить N координат максимальных результатов об-
работки изображения» мы не смогли справиться за пару недель. На GPU
нельзя сделать сортировку слиянием или быструю сортировку, надо де-
лать bitonic sort, при этом управление сортировкой внешнее (рекурсии-
то нет, как и локальных массивов); в цикле вычисляются параметры оче-
редного прохода и запускается шаг параллельного алгоритма. Для про-
грамм типа компиляторов GPU вообще не применимо — в компиляторах
используются практически неограниченные структуры, не ложащиеся на
массивы.
Изучение программирования GPU имеет вполне определённую
цель — ускорить выполнение программ. Но это подходит не для любых
программ — компиляторы от использования GPU только проиграют, на
данный момент. Поэтому создатели компиляторов на GPGPU не смотрят.
Применение ленивых вычислений может сократить код логики про-
граммы, тех вычислений, что можно записать в нём с выгодой. Но они не
помогут, когда большую часть времени занимает ввод-вывод или когда
³Что может сказаться на производительности.
⁴Максимальных по какому-то критерию, например, по величине результатов алго-
ритма определения подходящих для отслеживания точек — чем выше «яркость», тем
лучше отслеживать.
⁵Техника использования графического процессора видеокарты для общих вычисле-
ний, см. [5].

© 2009 «Практика функционального программирования» 17

1.5. Чистый параллелизм

требуется удовлетворить неким временным условиям.

По-моему, в этом GPU и ленивые вычисления схожи: они подходят не
для всех задач, надо с ними разбираться, чтобы понимать, могут ли они
пригодиться в конкретных задачах. Многих это и останавливает, посколь-
ку «известный путь самый короткий». Но наблюдения показывают, что об-
ласти применения как GPU, так и ленивых вычислений расширяются: в
GPU не так давно добавили практически произвольную рекурсию, а лени-
вые вычисления помогают лучше структурировать анализ при обработке
в условиях временных ограничений.
Уподобление ленивых вычислений компьютерной архитектуре поз-
воляет провести ещё одну интересную параллель. Языки программиро-
вания с ленивым порядком вычислений можно представить как авто-
код немного непривычного компьютера или виртуальной машины. Ну,
ещё одна архитектура, сколько их в карьере программиста. А автокоды
бывают очень пристойными: «Советская Ада» Эль-76 Эльбруса, Java для
JavaVM, C# для .Net. В свое время на автокоде МИР (Машины для Инже-
нерных Расчётов) [10] решали весьма серьёзные задачи, к которым было
трудно подступиться на машинах побольше.

1.5. Чистый параллелизм

Раз речь зашла о параллельных архитектурах, нельзя не упомянуть и
о том, как распараллеливание связано с разбиением на чистый код (без
побочных эффектов) и остальной.
Если в двух внешне независимых участках кода есть вызов функции с
неизвестным побочным эффектом (допустим, отладочная печать), то вы-
полнять эти участки кода параллельно нельзя, поскольку порядок вызова
этих внешних функций может измениться.
Чистый же код можно переставлять, как угодно [1] — зависимости в
нем выражены исключительно явным образом. Это не означает лёгкости
⁶Приём очень простой: создаётся (практически бесконечный) генератор итераций
анализа. Управляющая часть программы выбирает из потока итераций до тех пор, по-
ка не кончится время на реакцию или не будет найдено удовлетворительное решение.
Таким образом, анализ не знает о временных ограничениях, а управляющая часть — об
алгоритме.

© 2009 «Практика функционального программирования» 18

1.6. Заключение

анализа для автоматического распараллеливания, но упрощает ручное

распараллеливание. Практика показывает, что это действительно так: из-
менения в двух строках одного многопроходного оптимизатора нашего
проекта ускорили процесс оптимизации на 10% на двух ядрах по сравне-
нию с одним. Код оптимизатора занимает порядка 800 строк, то есть, мы
получили 10% ускорения за счёт 0.3% изменений кода. Получается, что ле-
нивый порядок вычислений, заставивший нас трудиться над разбиением
кода на отдельные части, подготовил код для параллельного выполнения.
Более того, в чистом коде без побочных эффектов проще проверять
всякого рода условия, например, что мы не зациклимся, или что не будет
ошибок обращений к массивам [9].

1.6. Заключение
Приведу немного статистики. В gcc 4.2.2, большом проекте на C, есть
файл bitmap.c. Он довольно средний по размерам: 1500 строк, 40 функ-
ций. Он содержит 132 оператора if и один тернарный оператор ?:. Таким
образом, на функцию приходится более трех операторов if, по одному
условному оператору на каждые 12 строк. Получается, что мы, обычные
программисты, используем грубый аналог call-by-name примерно 5—6
раз за рабочий день.
Можно оценить и количество использования ленивых вычислений в
gcc. Поиск «grep -E -i recog_memoiz *.c» дал 13 файлов из 299 (33 исполь-
зования) всё того же gcc 4.2.2. Везде используется call-by-need — произ-
водится вычисление и запоминается промежуточный результат. Немного,
но используется.
Если интересно, поищите у себя в коде что-либо наподобие установки
в конструкторе некоего поля в NULL, и чтобы рядом где-нибудь был getter
вида:
if ( m_field == NULL )
m_field = computation ;
return m_field ;

⁷≈ 17000 отлаженных строк кода в год для программистов вне США. 68 строк кода в
день.

© 2009 «Практика функционального программирования» 19

Литература Литература

Наверняка найдётся нечто похожее, что означает наличие ленивых

вычислений.
Не стоит бояться ленивых вычислений. Они встречаются даже чаще,
чем я думал, и гораздо привычней, чем принято считать. Они позволяют
структурировать программу так, что в ней открываются новые возмож-
ности для экономии времени программиста и увеличения скорости ра-
боты на современных системах. И уж тем более не стоит бояться ленивых
языков программирования: они не страшней автокода многих существу-
ющих, или существовавших ранее, машин.

Литература
[1] Data dependencies. — Ссылка в Wikipedia, URL: http://en.
wikipedia.org/wiki/Data_dependencies (дата обращения:
20 июля 2009 г.). — О зависимости по данным и их влиянии на па-
раллелизм. В этой статье говорится только про параллелизм уровня
инструкций, но если поставить части массивов или других структур
данных на место переменных, то получим всё то же самое, только для
параллелизма большего объёма.

[2] Efficient gather and scatter operations on graphics processors / B. He,

N. K. Govindaraju, Q. Luo, B. Smith. — 2008. — О реализации произ-
вольного доступа к памяти на GPU.

[3] Evaluation strategy. — Статья в Wikipedia, URL: http://en.

wikipedia.org/wiki/Evaluation_strategy (дата обраще-
ния: 20 июля 2009 г.). — Описываются все известные порядки вы-
числений.

[4] General-purpose computation on graphics processing units. — URL:

http://gpgpu.org/ (дата обращения: 20 июля 2009 г.). — Об ис-
пользовании GPU в гражданских целях.

[5] General-purpose computing on graphics processing units. — Ссылка

в Wikipedia, URL: http://en.wikipedia.org/wiki/GPGPU (да-

© 2009 «Практика функционального программирования» 20

Литература Литература

та обращения: 20 июля 2009 г.). — О технике использования графи-

ческого процессора видеокарты для общих вычислений.

[6] Kiselyov O. Incremental multi-level input processing with left-fold

enumerator: predictable, high-performance, safe, and elegant. — О без-
опасном применении ленивых итераторов. Предназначено для силь-
ных духом, поскольку содержит магию типов Haskell высшего уровня.

[7] Mitchell N. — Catch: Case Totality Checker for Haskell. — Проверка пол-
ноты разбора по образцу. По сравнению с тестами экономит время;
отыскивает ошибки, которые тесты отловить не в состоянии.

[8] Short circuit evaluation. — Статья в Wikipedia, URL: http://en.

wikipedia.org/wiki/Short_circuit_evaluation (дата об-
ращения: 20 июля 2009 г.). — Логические операторы в разных языках
программирования.

[9] Single Assignment C. — URL: http://sac-home.org/ (дата обра-

щения: 20 июля 2009 г.). — Чего можно добиться, отказавшись от раз-
рушающего присваивания.

[10] Машина для Инженерных Расчётов. — Ссылка в Wikipedia, URL:

http://ru.wikipedia.org/wiki/МИР_(компьютер) (дата
обращения: 20 июля 2009 г.). — Об одной из первых в мире пер-
сональной ЭВМ, созданной в 1965 году Институтом кибернетики
Академии наук Украины. МИР выпускалась серийно и предназнача-
лась для использования в учебных заведениях, инженерных бюро и
научных организациях.

© 2009 «Практика функционального программирования» 21

Функции и функциональный подход

Роман Душкин
[email protected]

Аннотация

В статье в сжатой форме рассказывается про функци-

ональный подход к описанию вычислительных процессов
(и в общем к описанию произвольных процессов в реальном
мире), а также про применение этого подхода в информати-
ке в функциональной парадигме программирования. Приме-
ры реализации функций даются на языке программирования
Haskell.
Введение
Вряд ли можно подтвердить или даже доказать какую-либо законо-
мерность, но можно предположить, что два способа вычисления — про-
цедурный и функциональный — как-то связаны с особенностями чело-
веческого разума, различающимися у разных людей. Такие особенности
издревле приводили к попыткам классификации человеческих характе-
ров по каким-либо дуальным шкалам. В качестве банальнейшего при-
мера можно привести шкалу «интровертность — экстравертность», хотя
причины, приведшие к появлению двух парадигм вычислений находятся
в какой-то другой плоскости, нежели приведённый пример.
И процедурный, и функциональный стили вычислений были известны
в далёком прошлом, и сейчас уже невозможно узнать, какой подход по-
явился первым. Последовательности шагов вычислений — особенность
процедурного стиля — можно рассматривать в качестве естественного
способа выражения человеческой деятельности при её планировании.
Это связано с тем, что человеку приходится жить в мире, где неумолимый
бег времени и ограниченность ресурсов каждого отдельного индивидуу-
ма заставляют людей планировать по шагам свою дальнейшую жизнеде-
ятельность.
Вместе с тем нельзя сказать, что функциональный стиль вычислений
не был известен человеку до возникновения теории вычислений в том
или ином виде. Такие методики, как декомпозиция задачи на подзадачи
и выражение ещё нерешённых проблем через уже решённые, составля-
ющие суть функционального подхода, также были известны с давних вре-
мён. Тут необходимо отметить, что эти методики вполне могут применять-
ся и в рамках процедурного подхода как проявление в нём функциональ-
ного стиля. Именно этот подход и является предметом рассмотрения на-
стоящей статьи, а объясняться его положения будут при помощи функци-
онального языка Haskell.
Итак, ниже читателю предлагается ознакомиться со способами опре-
деления функций, изучить дополнительные интересные методы в рамках
¹Описание языка можно найти на официальном сайте: на английском языке http:
//www.haskell.org/ или на русском языке http://www.haskell.ru/; также
для изучения языка можно воспользоваться книгой [11].

© 2009 «Практика функционального программирования» 23

2.1. Простые примеры функций

функционального подхода, а также углубиться в теоретический экскурс

для понимания основ функционального подхода. Автор надеется, что раз-
работчик программного обеспечения с любым уровнем подготовки смо-
жет найти для себя что-нибудь новое.

2.1. Простые примеры функций

В одной из компаний, где в своё время довелось работать автору,
при отборе на вакантные должности инженеров-программистов канди-
датам давалась задача: необходимо написать функцию, которая получает
на вход некоторое целое число, а возвращает строку с представлением
данного числа в шестнадцатеричном виде. Задача очень простая, но вме-
сте с тем она позволяет легко выяснить, какими методами решения задач
руководствуются кандидаты, поэтому основной упор на собеседовании
делался не на правильность написания кода, а на подход и канву рассуж-
дений при написании этой функции. Более того, если кандидат затруднял-
ся с алгоритмом, ему он полностью разъяснялся, поскольку интерес пред-
ставляли именно ход рассуждений и окончательный способ реализации
алгоритма. Для решения задачи разрешалось использовать любой язык
программирования на выбор кандидата, включая псевдоязык описания
алгоритмов, блок-схемы и прочие подобные вещи.
Сам алгоритм прост: необходимо делить заданное число на основание
(в задаваемой задаче, стало быть, на 16), собирать остатки и продолжать
этот процесс до тех пор, пока в результате деления не получится 0. По-
лученные остатки необходимо перевести в строковый вид посимвольно
(учитывая шестнадцатеричные цифры), после чего конкатенировать все
эти символы в результирующую строку в правильном направлении (пер-
вый остаток должен быть последним символом в результирующей строке,
второй — предпоследним и т. д.).
Каковы были типовые рассуждения большинства приходящих на со-
беседование? «Получаем входное число — организуем цикл while до тех
пор, пока параметр цикла не станет равен 0 — в цикле собираем остат-
ки от деления параметра на основание, тут же переводим их в символы
и конкатенируем с переменной, которая потом будет возвращена в каче-

© 2009 «Практика функционального программирования» 24

2.1. Простые примеры функций

стве результата — перед возвращением переменную обращаем». Неко-

торые кандидаты оптимизировали эти рассуждения и уже в цикле конка-
тенировали символы в правильном порядке, так что впоследствии пере-
менную обращать было не надо. Некоторые кандидаты пользовались цик-
лом for, некоторые добавляли всякие «рюшечки». Но за всё время рабо-
ты автора в этой компании ни один из кандидатов не предложил решения
задачи в функциональном стиле.
Вот как выглядит типовая функция для описанной цели на языке C++:
std :: string int2hex ( int i ) {
std :: string result = ”” ;
while ( i ) {
result = hexDigit ( i % 16) + result ;
i /= 16;
}
return result ;
}
Здесь функция hexDigit возвращает символ, соответствующий шест-
надцатеричной цифре.
Как же решить эту задачу при помощи функционального подхода?
При размышлении становится ясно, что взяв первый остаток от деления
на 16 и после этого целочисленно разделив само число на 16, задача сво-
дится к той же самой. И такое сведение будет происходить до тех пор, пока
число, которое необходимо делить, не станет равным 0. Налицо рекурсия,
которая является одним из широко используемых методов функциональ-
ного программирования. На языке Haskell эта задача может быть решена
следующим образом:
int2hex :: Integer → String
int2hex 0 = ””
int2hex i = int2hex ( i ‘ div ‘ 16) ++
hexDigit ( i ‘ mod ‘ 16)
Здесь функции div и mod, записанные в инфиксном стиле, возвраща-
ют соответственно результат целочисленного деления и остаток от тако-
го деления. Инфиксный стиль в языке Haskell позволяет записывать функ-
ции двух аргументов между ними при вызове — в данном случае имя

© 2009 «Практика функционального программирования» 25

2.1. Простые примеры функций

функции необходимо заключать в обратные апострофы (‘) (обычно ин-

фиксный стиль используется для повышения степени удобочитаемости
кода для функций с наименованиями вроде isPrefixOf и т. д.). Функция
(++) конкатенирует две строки. Все эти функции определены в стандарт-
ном модуле Prelude. Первая строка определения функции, так называе-
мая сигнатура, определяет тип функции. Для языка Haskell описание сиг-
натур не является необходимым, поскольку компилятор самостоятельно
выводит типы всех объектов, но правилом хорошего тона при написа-
нии исходных кодов программ является простановка сигнатуры для каж-
дой функции. Кроме того, сигнатура может являться ограничением на тип
функции (в вышеприведённом примере автоматически выведенный тип
функции int2hex будет более общим, чем записано в сигнатуре; более об-
щий тип этой функции: Integral ⇒ → String, где Integral — это
класс типов таких значений, над которыми можно производить целочис-
ленные арифметические операции).
Вторая строка определяет результат функции int2hex в случае, ко-
гда значение её единственного входного параметра равно 0. Третья стро-
ка, соответственно, определяет результат функции в оставшихся случа-
ях (когда значение входного параметра ненулевое). Здесь применён ме-
ханизм сопоставления с образцами, когда для определения функции за-
писывается несколько выражений, каждое из которых определяет зна-
чение функции в определённых условиях. В других языках программи-
рования для этих целей обычно используются if-then-else или case-
конструкции. Вот как, к примеру, та же самая функция будет записана
на языке C++:
std :: string int2hex ( int i ) {
if ( i ) {
return int2hex ( i / 16) + hexDigit ( i % 16) ;
} else {
return ”” ;
}
}

²В литературе по функциональному программированию для обозначения одного та-

кого выражения в определении функции иногда используется термин «клоз» (от англ.
«clause»).

© 2009 «Практика функционального программирования» 26

2.1. Простые примеры функций

Представленный пример уже достаточно показывает отличие двух

подходов к представлению вычислений. Тем не менее, уже сейчас видно,
что есть широкий простор для усовершенствования кода. В первую оче-
редь это касается основания преобразования, ведь часто при програм-
мировании необходимы числа в двоичной и восьмеричной записи. Бо-
лее того, почему бы не сделать универсальную функцию для преобразо-
вания числа в произвольную систему счисления? Эта задача легко реша-
ется преобразованием уже написанной функции³:
convert :: Int → Int → String
convert _ 0 = ””
convert r i = convert r ( i ‘ div ‘ r ) ++
digit r ( i ‘ mod ‘ r )
Здесь в сигнатуру внесены два изменения. Во-первых тип Integer
изменён на тип Int, что связано с необходимостью ограничения (тип
Integer представляет неограниченные целые числа, тип Int — огра-
ниченные интервалом [−229 ; 229 − 1]) для оптимизации вычислений. Во-
вторых, теперь функция convert принимает два параметра. Первым па-
раметром она принимает основание системы счисления, в которую необ-
ходимо преобразовать второй параметр. Как видно, определение функ-
ции стало не намного сложнее. Ну и в-третьих, в первом клозе определе-
ния на месте первого параметра стоит так называемая маска подстанов-
ки (_), которая обозначает, что данный параметр не используется в теле
³Для простоты изложения в статье приведены определения функций, работающих
с положительными числами. Если передать им в качестве входного значения число 0,
то в результате будет некорректное преобразование в пустую строку. Данная проблема
решается несложно — например, функцию int2hex можно дополнить следующим об-
разом:
int2hex :: Int → String
int2hex i = int2hex ’ i True
where
int2hex ’ 0 True = ”0”
int2hex ’ 0 False = ””
int2hex ’ i _ = int2hex ’ ( i ‘ div ‘ 16) False ++
hexDigit ( i ‘ mod ‘ 16)
В качестве упражнения читателю предлагается написать новое определение функции
convert по аналогии с приведённым определением функции int2hex.

© 2009 «Практика функционального программирования» 27

2.1. Простые примеры функций

функции.
Соответственно, функция digit, возвращающая цифру в заданном ос-
новании, теперь тоже должна получать и само основание. Но её вид, в от-
личие от функции hexDigit, которая являлась простейшим отображени-
ем первых шестнадцати чисел на соответствующие символы шестнадца-
теричной системы счисления, теперь должен стать совершенно иным. На-
пример, вот таким:
digit r i ∣ r < 37 = if ( i < 10)
then show i
else [( toEnum ( i +
55)):: Char ]
∣ otherwise = ”(” ++ ( show i ) ++ ”)”
В определении функции digit используется несколько интересных
особенностей языка Haskell. Во-первых, вместо механизма сопоставления
с образцами в определении применен механизм охраны (охранных выра-
жений), которые также позволяют сравнивать входные параметры с неко-
торыми значениями и осуществлять ветвление вычислений. Вторая осо-
бенность — использование выражения if-then-else для тех же самых
целей в первом варианте. Особой разницы между этими подходами нет,
вдумчивому читателю предлагается поэкспериментировать с охранными
и условными выражениями (подробности синтаксиса — в специализиро-
ванной литературе, рекомендуется использовать справочник [10]).
Функции show и toEnum опять же описаны в стандартном модуле
Prelude, который подгружается всегда. Первая функция преобразует лю-
бое значение в строку (её тип — → String), вторая — преобразует це-
лое число в заданный тип (её тип — Int → , причём конкретно в данном
случае она преобразует целое в код символа Char). Таким образом, алго-
ритм работы функции digit прост: если основание системы счисления не
превышает 36 (это число — сумма количества десятеричных цифр и букв
латинского алфавита, в исходном коде записывается как «меньше 37»), то
результирующая строка собирается из символов цифр и латинских букв.
Если же основание больше или равно 37, то каждая цифра в таких систе-
мах счисления записывается как соответствующее число в десятичной си-
стеме, взятое в круглые скобки. Для понимания способа работы функции
digit можно запустить её с различными параметрами и посмотреть ре-

© 2009 «Практика функционального программирования» 28

2.1. Простые примеры функций

зультат:
> digit 1 0
”0”

> digit 10 9
”9”

> digit 16 10
”A”

> digit 20 15
”F”

> digit 36 35
”Z”

> digit 100 50

”(50)”
Теперь можно легко определить несколько практичных дополнитель-
ных функций:
int2bin = convert 2
int2oct = convert 8
int2hex = convert 16
Такая запись может выглядеть необычно для тех, кто не знаком с функ-
циональным программированием. Используемый здесь подход называ-
ется «частичным применением». В данных определениях производится
частичный вызов уже определённой ранее функции convert, принима-
ющей на вход два параметра. Здесь ей передаётся всего один параметр,
в результате чего получаются новые функции, ожидающие на вход один
параметр. Этот подход проще всего понять, представив, что первый па-
раметр функции convert просто подставлен во все места, где он встреча-
ется в теле функции. Так частичная подстановка convert 2 превращает
определение в:
convert :: Int → Int → String
convert 2 0 = ””

© 2009 «Практика функционального программирования» 29

2.2. Теоретические основы функционального подхода

convert 2 i = convert 2 ( i ‘ div ‘ 2) ++

digit 2 ( i ‘ mod ‘ 2)
Поскольку данное определение можно легко преобразовать в функ-
цию одного параметра (первый же теперь зафиксирован и является кон-
стантой), современные трансляторы языка Haskell проводят именно та-
кую оптимизацию, создавая дополнительное определение новой функ-
ции для частичных применений.
Осталось упомянуть, что при частичном применении тип функции
как бы сворачивается на столько параметров, сколько было частично
применено. В рассматриваемом примере тип функций int2bin, int2oct
и int2hex равен Int → String.

2.2. Теоретические основы функционального

подхода
Несмотря на то, что фактически функциональный подход к вычисле-
ниям был известен с давних времён, его теоретические основы начали
разрабатываться вместе с началом работ над вычислительными машина-
ми — сначала механическими, а потом и электронными. С развитием тра-
диционной логики и обобщением множества сходных идей под сводом
кибернетики появилось понимание того, что функция является прекрас-
ным математическим формализмом для описания реализуемых в физиче-
ском мире устройств [6]. Но не всякая функция, а только такая, которая: во-
первых, не имеет побочных эффектов, и во-вторых, является детермини-
рованной. Данные ограничения на реализуемость в реальности связаны
с физическими законами сохранения, в первую очередь энергии. Имен-
но такие чистые процессы рассматриваются в кибернетике при помощи
методологии чёрного ящика — результат работы такого ящика зависит
только от значений входных параметров.
Ну и классическая иллюстрация этой ситуации:

x1 - - y1
x - -
X 2 …- F …- y2 Y
xm yn

© 2009 «Практика функционального программирования» 30

2.2. Теоретические основы функционального подхода

Таким образом, функциональное программирование предлагает

практические методы реализации кибернетических идей. Сегодня та-
кие методы всё больше распространяются в области промышленного
создания информационных и автоматизированных систем, поскольку
при проектировании этих систем применяются методы декомпозиции
функциональности и связывания отдельных функций в цепочки ис-
полнения вычислений. Так, к примеру, автоматизированные системы
управления технологическими процессами (АСУ ТП) могут представлять-
ся в виде блоков обработки информации, соединённых друг с другом
информационными потоками от датчиков к пункту принятия решений
и обратно к исполнительным устройствам. Каждый элемент на должном
уровне абстракции представляет собой как раз такой чёрный ящик,
представимый вычислимой детерминированной функцией.
Одним из ведущих ученых, заложивших формальные основы теории
вычислений, был А. Чёрч, предложивший λ-исчисление в качестве фор-
мализма для представления вычислимых функций и процессов [4]. Дан-
ный формализм основан на систематическом подходе к построениюи ис-
следованиям операторов, для которых другие операторы могут бытькак
формальными аргументами, так и возвращаемым результатом вычисле-
ний. Это — проявление функций высших порядков, то есть таких функций,
аргументами которых могут быть другие функции. Функциональные язы-
ки программирования основаны на λ-исчислении, поскольку функция яв-
ляется отображением λ-терма в конкретный синтаксис, включая функци-
ональную абстракцию и применение (аппликацию).
Как формальная система λ-исчисление представляет собой достаточ-
но сложную и содержательную теорию, которой посвящено множество
книг (некоторые из них приведены в списке литературы [4, 11, 13]). Вме-
сте с тем, λ-исчисление обладает свойством полноты по Тьюрингу, то есть
теория предлагает нотацию для простейшего языка программирования.
Более того, дополнения к теории, расширяющие её свойства, позволяют
строить прикладные языки программирования на основе заданных дено-
тационных семантик [8]. Так, к примеру, ядро языка программирования
Haskell представляет собой типизированное λ-исчисление.
Также стоит упомянуть про комбинаторную логику [7], которая ис-
пользует несколько иную нотацию для представления функций, а в каче-

© 2009 «Практика функционального программирования» 31

2.2. Теоретические основы функционального подхода

стве базового правила вывода в формальной системе использует только

аппликацию (применение). В этой формальной системе отсутствует поня-
тие связанной переменной, а объекты-функции (или «комбинаторы») про-
сто прикладываются друг к другу. Базис системы состоит из одного ком-
бинатора, то есть утверждается, что любая функция может быть выражена
через этот единственный базисный комбинатор. Сама по себе комбина-
торная логика изоморфна λ-исчислению, но обладает, по словам некото-
рых специалистов, большей выразительной силой. В дополнение можно
отметить, что некоторые исследователи подходят к комбинаторной логи-
ке как к средству наименования λ-термов (например, λx.x ≡ I), что про-
сто облегчает запись аппликативных выражений.
Необходимо отметить, что несмотря на глубокую теоретическую про-
работку вопросов теории вычислений и наличие прикладных инструмен-
тов в виде языков программирования, вопросы создания качественно-
го инструментария непосредственно для процесса разработки для функ-
циональной парадигмы рассматриваются мало. Так, к примеру, Ф. Уод-
лер отмечает [3], что отсутствие достаточного количества удобных и рас-
пространённых инструментальных средств оказывает негативное влия-
ние на возможности использования функциональных языков программи-
рования. Как следствие, функциональные языки программирования, мно-
гие из которых являются действительно универсальными и отличными
средствами решения задач, до сих пор не могут выйти из узких стен науч-
ных лабораторий и найти широкого пользователя в среде разработчиков
программного обеспечения.
Вместе с тем уже сегодня имеются прекрасные методики функцио-
нального анализа и проектирования, применение которых на этапах под-
готовки требований и разработки проекта программного продукта поз-
волит усовершенствовать процесс разработки и ввести в него элементы
функционального программирования.
В первую очередь речь идёт о методологии структурного анализа
и проектирования SADT [12]. Нотации DFD (англ. «Data Flow Diagrams» —
диаграммы потоков данных) и в особенности IDEF0 (англ. «Integration
Definition for Function Modeling» — интегрированная нотация для моде-
лирования функций), предлагаемые в рамках этой методологии, отлич-
но проецируются на методы и технологии функционального программи-

© 2009 «Практика функционального программирования» 32

2.3. Дополнительные примеры с отдельными элементами
программирования
рования. Так, например, в IDEF0 каждый блок представляет собой функ-
цию, которая связана с другими функциями при помощи отношений де-
композиции и получения/передачи параметров. Диаграммы IDEF0 могут
быть в автоматизированном режиме преобразованы в шаблоны модулей
на каком-либо функциональном языке, а методика обратного проектиро-
вания позволит преобразовать модули на том же языке Haskell в диаграм-
мы IDEF0. Тем самым можно построить инструментарий, в чём-то схожий
с известными средствами для объектно-ориентированного программи-
рования, на основе языка моделирования UML (англ. «Unified Modeling
Language» — унифицированный язык моделирования).
К тому же и сам язык UML позволяет применять функциональный под-
ход [5]. Диаграммы вариантов использования можно рассматривать как
верхний уровень абстракции функциональности программных средств,
выражаемой при помощи функций. В дальнейшем при декомпозиции
каждого варианта использования при помощи диаграмм последователь-
ностей или конечных автоматов можно также предусмотреть автоматизи-
рованный процесс кодогенерации.
Впрочем, эта тема ещё ждёт своего исследователя и реализатора.

2.3. Дополнительные примеры с отдельными

элементами программирования
Для полноты изложения осталось привести несколько примеров
функций, которые используют особые элементы функционального про-
граммирования, связанные с оптимизацией, улучшением внешнего вида
исходного кода и т. д. Для демонстрации большинства таких элементов
программирования приведем следующее преобразование уже рассмот-
ренной функции convert:
convert ’ :: Int → Int → String
convert ’ r i = convert_a r i ””
where
convert_a _ 0 result = result
convert_a r i result = convert_a r ( i ‘ div ‘ r )
( digit r ( i ‘ mod ‘

© 2009 «Практика функционального программирования» 33

2.3. Дополнительные примеры с отдельными элементами
программирования
++
result )
Данное определение необходимо разобрать подробно.
Функция convert’ выполняет абсолютно то же вычисление, что
и функция convert, однако оно основано на подходе, который называет-
ся «накапливающий параметр» (или «аккумулятор»). Дело в том, что в из-
начальном определении функции convert используется рекурсия, кото-
рая в некоторых случаях может приводить к неоптимальным вычисли-
тельным цепочкам. Для некоторых рекурсивных функций можно прове-
сти преобразование так, что они принимают вид хвостовой рекурсии, ко-
торая может выполняться в постоянном объёме памяти.
В функциональном программировании такое преобразование делают
при помощи накапливающего параметра. Определение начальной функ-
ции заменяют на вызов новой функции с накапливающим параметром,
а в данном вызове передают начальное значение этого параметра. Допол-
нительная же функция производит вычисления как раз в накапливающем
параметре, делая рекурсивный вызов самой себя в конце всех вычисле-
ний (в этом и заключается смысл хвостовой рекурсии). Соответственно,
здесь видно, что функция convert_a вызывает саму себя в самом конце
вычислений, а приращение цифр в новой системе счисления производит-
ся в третьем параметре, который и является накапливающим.
Особо надо обратить внимание на вид функции convert_a. Её опреде-
ление записано непосредственно в теле функции convert’ после ключе-
вого слова where. Это — ещё один из элементов программирования, кото-
рый заключается в создании локальных определений функций или «замы-
каний». Замыкание находится в области имён основной функции, поэтому
из его тела видны все параметры. Кроме того, замыкания могут использо-
ваться для оптимизации вычислений — для некоторых функциональных
языков программирования справедливо, что если в теле основной функ-
ции несколько раз вызвать локальную функцию с одним и тем же набором
параметров, то результат будет вычислен один раз. Замыкания определя-
ются в языке Haskell двумя способами: префиксно при помощи ключево-
го слова let и постфиксно при помощи рассмотренного ключевого слова
where (у этих ключевых слов имеется семантическое различие, несуще-
ственное здесь).

© 2009 «Практика функционального программирования» 34

2.3. Дополнительные примеры с отдельными элементами
программирования
Кроме того, представленный пример демонстрирует так называемый
двумерный синтаксис, который применяется в языке Haskell для мини-
мизации количества специальных разделительных символов. Два клоза
определения локальной функции convert_a начинаются с одной и той же
позиции символа, и это важно. Этому же принципу подчиняются все пере-
числения «операторов»: их можно записывать друг под другом в одном
столбце, а можно отделять друг от друга точкой с запятой.
Дополнительные приёмы программирования, описание ключевых
слов, а также описание метода преобразования функции к хвостовой ре-
курсии в деталях описаны в книге [10].
Здесь же осталось упомянуть то, что полученные функции convert
и convert’ можно использовать так, как любые иные: передавать в ка-
честве аргументов, частично применять и т. д. Например, для получения
списка чисел в заданной системе счисления (в двоичной, скажем) можно
воспользоваться таким вызовом:
map ( convert 2) [1..100]
Данный вызов вернёт список двоичных представлений чисел от 1
до 100, поскольку стандартная функция map применяет заданную функ-
цию к каждому элементу заданного списка и возвращает список резуль-
татов таких применений.
Для окончательного оформления исходного кода в исполняемом мо-
дуле необходимо разработать функцию main, которая будет использо-
ваться как точка входа в откомпилированную программу. Пример такой
функции ниже:
main :: IO ()
main = putStr $ convert ’ 2 14
Здесь стандартная функция putStr выводит на экран результат рабо-
ты функции convert’. Оператор ($) позволяет записывать функции друг
за другом без лишних скобок — это просто оператор применения функ-
ции с наинизшим приоритетом, используемый для облегчения исходного
кода. Вместо такой записи можно было бы написать тождественную:
main = putStr ( convert ’ 2 14)

© 2009 «Практика функционального программирования» 35

2.4. Общие свойства функций в функциональных языках
программирования
Дело в том, что операция применения функции (аппликация) имеет
в языке Haskell самый высокий приоритет исполнения, при этом она яв-
ляется левоассоциативной, то есть при записи putStr convert’ 2 14
транслятор языка выдал бы ошибку, поскольку к функции putStr произ-
водится попытка применения параметра convert’, который не проходит
статической проверки типов.

2.4. Общие свойства функций в функциональ-

ных языках программирования
Осталось кратко суммировать всё вышеизложенное и изучить общие
свойства функций, рассматриваемые в функциональном программирова-
нии. К таким свойствам наиболее часто относят чистоту (то есть отсут-
ствие побочных эффектов и детерминированность), ленивость и возмож-
ность производить частичные вычисления.
Итак, как уже упоминалось, физически реализуемыми являются та-
кие кибернетические машины, выход которых зависит только от значе-
ний входных параметров. Это положение относится и к таким кибернети-
ческим машинам, которые имеют внутренний накопитель — память (на-
пример, автомат Мили); использование внутреннего состояния модели-
руется передачей его значения из вызова в вызов в последовательности
функций так, что это внутреннее состояние может рассматриваться в ка-
честве входного параметра. Данное положение нашло чёткое отражение
в парадигме функционального программирования, поскольку в ней при-
нято, что функции, являясь математическими абстракциями, должны об-
ладать свойством чистоты. Это означает, что функция может управлять
только выделенной для неё памятью, не модифицируя память вне своей
области. Любое изменение сторонней памяти называется побочным эф-
фектом, а функциям в функциональных языках программирования обыч-
но запрещено иметь побочные эффекты.
Так же и с детерминированностью. Детерминированной называется
функция, выходное значение которой зависит только от значений вход-
ных параметров. Если при одинаковых значениях входных параметров
в различных вызовах функция может возвращать различные значения,

© 2009 «Практика функционального программирования» 36

2.4. Общие свойства функций в функциональных языках
программирования
то говорят, что такая функция является недетерминированной. Соответ-
ственно, обычно функции в функциональной парадигме являются детер-
минированными.
Конечно, есть некоторые исключения, к примеру, системы ввода-
вывода невозможно сделать без побочных эффектов и в условиях пол-
ной детерминированности. Также и генерация псевдослучайных чисел
осуществляется недетерминированной функцией. Можно привести ещё
несколько подобных примеров. Само собой разумеется, что универсаль-
ный язык программирования, каковым является язык Haskell, должен
предоставлять средства для решения этих практических задач. В данном
случае побочные эффекты и недетерминированность вынесены из ядра
языка и обёрнуты в так называемую монаду, которая скрывает в себе все
нефункциональные особенности (описание монад выходит за рамки на-
стоящей статьи).
Очень интересным свойством функций является ленивость. Не все
функциональные языки предоставляют разработчику возможность опре-
делять ленивые функции, но язык Haskell изначально является ленивым,
и разработчику необходимо делать специальные пометки для функций,
которые должны осуществлять энергичные вычисления. Ленивая страте-
гия вычислений заключается в том, что функция не производит вычисле-
ний до тех пор, пока их результат не будет необходим в работе програм-
мы. Так значения входных параметров никогда не вычисляются, если они
не требуются в теле функции. Это позволяет, помимо прочего, создавать
потенциально бесконечные структуры данных (списки, деревья и т. д.), ко-
торые ограничены только физическим размером компьютерной памяти.
Такие бесконечные структуры вполне можно обрабатывать ленивым спо-
собом, поскольку вычисляются в них только те элементы, которые необ-
ходимы для работы. Передача на вход какой-либо функции бесконечного
списка не влечёт зацикливания программы, поскольку она не вычисляет
весь этот список целиком (что было бы невозможным).
В качестве примера, наглядно иллюстрирующего ленивую стратегию
вычислений, можно привести определение следующей несколько беспо-
лезной функции:
firstNumbers n = take n [1..]

© 2009 «Практика функционального программирования» 37

2.4. Общие свойства функций в функциональных языках
программирования
Данная функция возвращает список из n первых натуральных чисел.
Стандартная функция take возвращает n первых членов произвольного
списка, а вторым аргументом ей на вход подаётся бесконечный список на-
туральных чисел, записываемый как [1..]. Соответственно, при вызове
функции firstNumbers происходит вычисление только заданного коли-
чества целых чисел.
Ну и в качестве наиболее распространённого примера использования
ленивых вычислений можно привести такой, который используется даже
в императивных языках программирования. Операции булевской алгеб-
ры И и ИЛИ в реализации для языков программирования могут не вычис-
лять второй аргумент, если значение первого равно False (в случае опе-
рации И) или True (в случае операции ИЛИ, соответственно).
Наконец, уже упоминалось, что у функций есть тип. В функциональных
языках программирования принято, чтобы тип функций был каррирован-
ным, то есть имел такой вид:

A1 → (A2 → . . . (An → B) . . .)
где A1 , A2 , …An — типы входных параметров, а B — тип результата.
Такой подход к определению типов функций был предложен М. Шейн-
финкелем как способ, позволяющий проводить частичные вычисле-
ния [2]. Метод был развит Х. Карри [11], в честь которого он, собственно,
и назван.
Каррированность функций означает, что такие функции принимают
входные параметры по одиночке, а в результате такого одиночного при-
менения получается новая функция. Так, если в функцию указанного выше
типа подать первый параметр типа A1 , то в итоге получится новая функ-
ция с типом:

A2 → (A3 → . . . (An → B) . . .)
Когда на вход функции подаются все входные параметры, в результате
получается значение типа B .
⁴Моисей Исаевич Шейнфинкель (в зарубежной литературе известен как Moses
Schönfinkel [1]) — русский математик, обозначивший концепцию комбинаторной логики.
Прим. ред.

© 2009 «Практика функционального программирования» 38

Литература Литература

В свою очередь это означает не только возможность частичного при-

менения, но и то, что функции сами по себе могут быть объектами вы-
числений, то есть передаваться в качестве параметров другим функциям
и быть возвращаемыми в качестве результатов. Ведь никто не ограничи-
вает указанные типы A1 , A2 , …An и B только атомарными типами, это мо-
гут быть также и функциональные типы.
Перечисленные свойства функций в функциональных языках про-
граммирования открывают дополнительные возможности по использо-
ванию функционального подхода, поэтому разработчикам программного
обеспечения рекомендуется изучить этот вопрос более подробно.

Заключение
Оставим идеалистам споры о преимуществах и недостатках тех или
иных подходов к программированию. Важно понимать, что знание обо-
их методов описания вычислительных процессов позволяет более полно-
ценно взглянуть на проектирование и разработку программных средств.
К сожалению, на уроках программирования (информатики) в средних
учебных заведениях редко изучают оба подхода, в результате чего у на-
чинающих специалистов и интересующихся имеется известный перекос
в сторону процедурного стиля.
Владение функциональным стилем и его основными методиками (де-
композицией и выражением ещё нерешённых задач через уже решён-
ные) позволяет более эффективно решать управленческие задачи, по-
скольку эти приёмы также повсеместно встречаются в области регулиро-
вания и управления. В виду вышеизложенного автор надеется, что рас-
пространение и популяризация парадигмы функционального програм-
мирования позволит не только взращивать более серьёзных и вдумчивых
специалистов в области информационных и автоматизированных систем,
но и решит некоторые проблемы подготовки управленческих кадров.

Литература
[1] Moses Schönfinkel. — Статья в Wikipedia: URL: http://en.

© 2009 «Практика функционального программирования» 39

Литература Литература

wikipedia.org/wiki/Moses_Schönfinkel (дата обращения:

20 июля 2009 г.).

[2] Schönfinkel M. Über die baustein der mathematischen logik. // Math.

Ann. — 1924. — Vol. 92. — Pp. 305–316.

[3] Wadler P. Why no one uses functional languages // ACM SIGPLAN Not. —
1998. — Vol. 33, no. 8. — Pp. 23–27.

[4] Х. Барендрегт. Ламбда-исчисление. Его синтаксис и семантика: Пер.

с англ. — М.: Мир, 1985. — 606 с.

[5] Буч Г., Рамбо Дж., Якобсон И. Язык UML. Руководство пользователя. —
М.: ДМК Пресс, 2007. — 496 с.

[6] Винер Н. Кибернетика, или Управление и связь в животном и машине:

Пер. с англ. — М.: Советское радио, 1958. — 216 с.

[7] Вольфенгаген В. Э. Комбинаторная логика в программировании. Вы-

числения с объектами в примерах и задачах. — М.: МИФИ, 1994. —
204 с.

[8] Вольфенгаген В. Э. Конструкции языков программирования. Приёмы

описания. — М.: АО «Центр ЮрИнфоР», 2001. — 276 с.

[9] Душкин Р. В. Функциональное программирование на языке Haskell. —

М.: ДМК Пресс, 2007.

[10] Душкин Р. В. Справочник по языку Haskell. — М.: ДМК Пресс, 2008. —

544 с.

[11] Карри Х. Б. Основания математической логики. — М.: Мир, 1969. —

568 с.

[12] Марка Д. А., Макгоуэн К. Методология структурного анализа и проек-

тирования SADT. — М.: Метатехнология, 1993.

[13] Филд А., Харрисон П. Функциональное программирование: Пер. с ан-

гл. — М.: Мир, 1993. — 637 с.

© 2009 «Практика функционального программирования» 40

Изменяемое состояние: опасности и
борьба с ними

Евгений Кирпичёв
[email protected]

Аннотация

В этой статье рассматриваются опасности использова-

ния изменяемого состояния в программах, преимущества ис-
пользования неизменяемых структур и способы минимиза-
ции нежелательных эффектов от изменяемого состояния в тех
случаях, когда оно все-таки необходимо.
3.1. Введение

3.1. Введение
Одно из ключевых отличий многих функциональных языков от
объектно-ориентированных и процедурных — в поощрении использо-
вания неизменяемых данных; некоторые языки, в частности Haskell, даже
не содержат в синтаксисе оператора присваивания! Апологеты функци-
онального программирования объясняют это решение, в частности, тем,
что отказ от изменяемых данных резко повышает корректность программ
и делает их значительно более удобными для анализа с помощью фор-
мальных методов. Это действительно так, и в данной статье мы в этом убе-
димся. Однако полный отказ от изменяемых данных зачастую не оправ-
дан по следующим причинам:

1) Некоторые техники программирования, применяющиеся в функци-

ональных языках без присваиваний (к примеру, ленивые вычисле-
ния), применимы в более традиционных языках, таких как Java или
C++, лишь с огромным трудом.

2) Для некоторых алгоритмов и структур данных не известно или

не существует столь же эффективных аналогов без использования
присваиваний (к примеру, для хэш-таблиц и систем непересекаю-
щихся множеств).

3) Многие предметные области по своей сути содержат изменяемые

объекты (например, банковские счета; элементы систем в задачах
имитационного моделирования, и т. п.), и переформулировка зада-
чи на язык неизменяемых объектов может «извратить» задачу.

В данной статье мы поговорим о том, как пользоваться изменяемыми

данными, не жертвуя простотой и корректностью кода.

3.2. Опасности изменяемого состояния

Перед тем, как перейти к техникам нейтрализации опасностей изме-
няемых данных, перечислим сами эти опасности.

© 2009 «Практика функционального программирования» 42

3.2. Опасности изменяемого состояния

3.2.1. Неявные изменения

Необходимое условие корректности программы — целостность ее
внутреннего состояния, выполнение некоторых инвариантов (к примеру,
совпадение поля size у объекта типа «связный список» с реальным чис-
лом элементов в этом списке). Код пишется так, чтобы в моменты, когда
состояние программы наблюдаемо, инварианты не нарушались: каждая
отдельная процедура начинает работать в предположении, что все инва-
рианты программы выполняются и гарантирует, что после ее завершения
инварианты выполняются по-прежнему.
Инварианты могут охватывать сразу несколько объектов: к примеру, в
задаче представления ненаправленных графов логично требовать инва-
рианта «если узел A связан ребром с узлом B, то и узел B связан ребром с
узлом A».
Сохранение такого инварианта представляет собой непростую зада-
чу: всякая процедура, меняющая один из составляющих его объектов,
обязана знать не только о существовании всех остальных составляющих
этого инварианта, но и обо всех составляющих всех инвариантов, завися-
щих от этого объекта! В противном случае, процедура может, сама того не
ведая, нарушить инвариант.
Добиться такого знания порой чрезвычайно сложно; еще сложнее
сделать это без нарушения модульности. Поэтому программисты стре-
мятся делать инварианты охватывающими как можно меньше объектов
и зависящими от как можно меньшего числа их изменяемых свойств.
Рассмотрим классический пример, иллюстрирующий данную пробле-
му.
Пример: Обходчик интернета. Предположим, что мы разрабатыва-
ем программу — обходчик интернета. Она ходит по графу некоторого
подмножества интернета и собирает данные со встречаемых страничек.
В графе интернета узлами являются страницы, ребрами — ссылки с од-
них страниц на другие. В результате работы программа записывает в базу
ссылки на некоторые из найденных страничек вместе с определенной до-
полнительной информацией.
Структура классов выглядит примерно так:
public class Address {

© 2009 «Практика функционального программирования» 43

3.2. Опасности изменяемого состояния

private String url ;

public String getUrl () {
return url ;
}
public void setUrl ( String u ) {
this . url = u ;
}
int hashCode () {
return url . hashCode () ;
}
boolean equals ( Address other ) {
return url . equals ( other . url ) ;
}
}

public class Node {

Address address ;
List < Node > inLinks , outLinks ;
}

public class Graph {

Map < Address , Node > addr2node = new
HashMap < Address , Node >() ;
}
Во время разработки программы в один прекрасный момент выясня-
ется, что доступ к некоторым страничкам приводит к перенаправлению
(redirect) на другой адрес. Если в базе оказывается записан исходный ад-
рес, то когда другая программа будет считывать адреса из базы и загру-
жать соответствующие странички, она потратит лишнее время на перена-
правление — поэтому лучше записать в базу новый адрес, полученный
после перенаправления. В код добавляется следующее небольшое изме-
нение:
Page download ( Address address ) {
...
if ( response . isRedirect () ) {
address . setUrl ( response . getRedirectedUrl () ) ;

© 2009 «Практика функционального программирования» 44

3.2. Опасности изменяемого состояния

http://... http://...
Node 1 Node 2
...

http://... http://... http://...

Node 3 Node 4 Node 5

Рис. 3.1. Организация объекта класса HashMap

}
...
}
И тут про некоторые адреса, определенно обязанные содержать-
ся в графе, addr2node.containsKey(address) вдруг начинает отвечать
False! Опытные читатели, скорее всего, заметят здесь проблему; одна-
ко, будучи встречена впервые, она может потребовать для решения па-
ры часов отладки и сомнений в собственном душевном здоровье и ка-
честве стандартной библиотеки. На деле проблема очень проста: метод
download модифицировал объект address, но не учел, что его состояние
является частью инварианта объекта addr2node.
Вспомним, как устроен класс HashMap в языке Java (рис. 3.1). Он реа-
лизует хэш-таблицу с закрытой адресацией: каждому хэш-коду (по моду-
лю выделенной длины хэш-таблицы) соответствует «корзина» — список
элементов, чей ключ обладает таким хэш-кодом.
Отмеченный на рисунке элемент соответствует адресу, измененно-
му в методе download. В результате изменения поменялся и его хэш-код,
однако элемент остался в корзине, соответствующей старому хэш-коду!
В результате методом download оказывается нарушен инвариант класса
HashMap — «Хэш-код всех ключей в одной корзине по модулю длины таб-
лицы равен номеру этой корзины».
Теперь, к примеру, при попытке проверить наличие нового адреса в
графе, поиск будет производиться в корзине, соответствующей хэш-коду
нового адреса — конечно же, ключа там не окажется, т.к. он находится
в другой корзине. При попытке проверить наличие в графе старого адре-
са, поиск будет производиться в корзине, соответствующей старому адре-
су — однако самого адреса там также не окажется. Таким образом, после

© 2009 «Практика функционального программирования» 45

3.2. Опасности изменяемого состояния

выполнения метода download в графе будут «отсутствовать» и старый, и

новый адреса.
Как видно, объекты класса Address можно изменять только если из-
вестно, что они не содержатся ни в каком контейнере!
Единственное, по-видимому, решение данной проблемы — никогда
не использовать изменяемые поля в качестве ключей контейнеров, в
частности, в методах equals, hashCode, compareTo. Эта проблема на-
столько часта и опасна, что некоторые среды разработки генерируют пре-
дупреждение, если в одном из этих методов используется изменяемое по-
ле.
В рассматриваемой задаче компромиссное решение таково: иметь в
классе Address два поля: одно, неизменяемое, соответствует изначаль-
ному адресу странички, без учета перенаправлений, и именно им индек-
сируются узлы в графе; второе, изменяемое, соответствует конечному ад-
ресу с учетом перенаправлений, и именно оно записывается в базу, но не
используется в качестве ключа.

3.2.2. Кэширование и разделение

Следующая опасность изменяемых данных заключается в том , что их
наличие существенно усложняет корректное кэширование. Рассмотрим
один из классических примеров этой проблемы, широко известный в со-
обществе Java-программистов.
Пример: Геометрические классы GUI-библиотеки AWT. AWT содер-
жит классы Point, Dimension, Rectangle, обозначающие соответственно:
точку на плоскости, размеры прямоугольника и прямоугольник. Методы-
аксессоры у классов окон возвращают объекты этих классов на запросы
о положении и размере окна. Все три класса изменяемы:
class Point {
int x , y ;
}
class Dimension {
int width , height ;
}
class Rectangle {

© 2009 «Практика функционального программирования» 46

3.2. Опасности изменяемого состояния

int x , y , width , height ;

}
Как должен выглядеть метод получения размеров окна, возвращаю-
щий Dimension?
class Component {
private Dimension size ;
...
Dimension getSize () {
return size ;
}
...
}
Этот код, конечно же, неверен! Клиент может изменить возвра-
щенный объект, тем самым нарушив инвариант класса Component —
«Всякое изменение размеров объекта типа Component оповещает
всех клиентов, подписавшихся на это изменение (с помощью метода
addComponentListener)». Заметим, что клиент может и не иметь ни-
какого злого умысла при изменении такого возвращенного объекта —
например, его может интересовать центр окна, который он станет
вычислять таким образом:
Point center = w . getLocation () ;
center . x += w . getSize () . width /2;
center . y += w . getSize () . height /2;
Такая реализация getSize недопустима. Правильная реализация обя-
зана возвращать объект, изменение которого не может повлиять на окно.
Dimension getSize () {
return new Dimension ( size . width , size . height ) ;
}
Однако такая реализация обладает другим недостатком — низкой
производительностью: всякий раз при вызове getSize создается новый
объект. В ситуации, к примеру, вызова менеджера размещения окон для
сложного интерфейса методы getSize, getLocation, getBounds могут
вызываться десятки тысяч раз, и издержки на создание объекта становят-
ся совсем не безобидными.

© 2009 «Практика функционального программирования» 47

3.2. Опасности изменяемого состояния

Точно такие же проблемы возникают при возвращении массивов ме-

тодов.
Рассмотрим еще один пример.
Пример: Корзина в интернет-магазине. В программе, реализующей
интернет-магазин, есть класс «корзина». Общая стоимость продуктов за-
висит от стоимости каждого продукта и скидки, вычисляющейся по неко-
торым сложным правилам, зависящим от самих продуктов, от покупателя
и т. п. Правила настолько сложные, что всякий раз вычислять стоимость
корзины заново — неэффективно, поэтому она кэшируется и сбрасыва-
ется при изменении набора продуктов.
class Cart {
private Customer customer ;
private List < Product > products ;
private int totalPrice = − 1;

private int computeTotalPrice () {

// Scary code here
}

public int getTotalPrice () {

if ( totalPrice == − 1)
totalPrice = computeTotalPrice () ;
return totalPrice ;
}
public void addProduct ( Product p ) {
products . add ( p ) ;
totalPrice = − 1;
}
public void removeProduct ( Product p ) {
products . remove ( p ) ;
totalPrice = − 1;
}
}

¹При возвращении списков и других коллекций проблемы несколько меньше, по-

скольку они допускают инкапсуляцию изменений, давая возможность переопределить
изменяющие методы (add, set, …) и, к примеру, запретить изменения.

© 2009 «Практика функционального программирования» 48

3.2. Опасности изменяемого состояния

Стоимость продуктов может изменяться во время работы магазина,

поэтому в классе Product есть метод setPrice.
Близится праздник, и наш герой (назовем его Петром) подбирает по-
дарки для своей семьи; это нелегкое дело отнимает у него 2 дня. С прибли-
жением праздника в интернет-магазине начинается распродажа, и неко-
торые товары дешевеют. К концу второго дня корзина Петра полна подар-
ков, и он уже готов нажать «Checkout», но тут он замечает, что — о ужас! —
указанная в корзине сумма заказа не соответствует суммарной стоимо-
сти товаров. Пётр негодует: закэшированное значение totalPrice не бы-
ло обновлено при изменении цен продуктов — нарушился инвариант
«totalPrice равно либо −1, либо истинной суммарной цене содержа-
щихся в корзине продуктов», поскольку метод setPrice действовал лишь
над объектом класса Product, ничего не зная об объекте Cart, в чьем ин-
варианте этот Product присутствовал.
Для решения этой проблемы придется либо отказаться от кэширова-
ния цены вовсе, либо сделать так, чтобы класс Product позволял под-
писываться на изменения цены. Оба решения одинаково плохи: первое
неэффективно, второе — сложно и подвержено ошибкам: класс Product,
бывший обычной структурой данных, обрастает всевозможными опове-
щателями, а все его пользователи обязаны на эти оповещения подписы-
ваться. Легко представить, какая путаница будет в коде, учитывая, что
бизнес-область содержит множество взаимосвязанных объектов с изме-
няемыми свойствами — гораздо больше, чем просто Product и Cart.

3.2.3. Многопоточность
Подавляющее большинство багов в многопоточных программах свя-
зано с изменяемыми данными, а именно — с тем, что две (или более) кор-
ректных последовательности изменений, переплетаясь в условиях мно-
гопоточности, вместе образуют некорректную. Вот классический пример
такой ошибки.
Пример: Банковские транзакции. Пусть есть класс BankAccount, под-
держивающий операции deposit (положить деньги на счет) и withdraw
(снять деньги со счета).
class BankAccount {

© 2009 «Практика функционального программирования» 49

3.2. Опасности изменяемого состояния

void deposit ( int amount ) {

setMoney ( getMoney () + amount ) ;
}
void withdraw ( int amount ) {
if ( amount > getMoney () )
throw new InsufficientMoneyException () ;
setMoney ( getMoney () − amount ) ;
}
}
Предположим, у супругов Ивана да Марьи есть общий семейный счет,
на котором лежит 100 рублей. Иван решает положить на счет 50 рублей, а
Марья в это же время решает положить на счет 25 рублей.

Действия Ивана Действия Марьи Деньги на счете

deposit(50) deposit(25) 100
getM oney() → 100 100
getM oney() → 100 100
setM oney(100 + 50) 150
setM oney(100 + 25) 125
Итого 125

В результате деньги Ивана оказываются выброшенными на ветер.

Причина этого — переплетение трасс: каждая из операций по отдель-
ности работает правильно, однако лишь в предположении, что состояние
системы во время ее работы контролируется только ею; это предположе-
ние оказывается неверным. Такая проблема может возникнуть не толь-
ко в условиях многопоточности, но в этих условиях она проявляется осо-
бенно часто и ярко. Возможные пути решения — использование обыкно-
венных примитивов синхронизации или специальных средств, таких как
транзакции.

© 2009 «Практика функционального программирования» 50

3.2. Опасности изменяемого состояния

3.2.4. Сложный код

С введением изменяемых данных в коде появляется измерение вре-
мени как на высоком уровне (взаимодействия компонентов), так и на низ-
ком — уровне последовательности строк кода. Вслед за ним приходит до-
полнительная сложность: необходимо не только решить, что надо сде-
лать, но и в каком порядке. Она проявляется, в основном, в реализациях
сложных структур данных и алгоритмов.
Пример: Двусвязный список. Корректная реализация этой структу-
ры данных — на удивление трудное дело: немногие могут реализовать
двусвязный список правильно с первой попытки. Вот (слегка сокращен-
ный) фрагмент кода, осуществляющего вставку в двусвязный список в
GNU Classpath. Он выглядит невинно, но можете ли вы в уме убедиться в
его корректности, не рисуя на бумаге диаграмм для трех возможных слу-
чаев и не отслеживая последовательно влияние каждой строки кода на
диаграмму?
public void add ( int index , Object o ) {
Entry e = new Entry ( o ) ;
if ( index < size ) {
Entry after = getEntry ( index ) ;
e . next = after ;
e . previous = after . previous ;
if ( after . previous == null )
first = e ;
else
after . previous . next = e ;
after . previous = e ;
} else if ( size == 0) {
first = last = e ;
} else {
e . previous = last ;
last . next = e ;
last = e ;
}
size ++;
}

© 2009 «Практика функционального программирования» 51

3.2. Опасности изменяемого состояния

Рис. 3.2. Вставка в красно-черное дерево

Пример: Красно-черные деревья. Более радикальный пример — ре-

ализация красно-черных деревьев: на рис. 3.2 представлен вид «с высоты
птичьего полета» на процедуры вставки элемента в такую структуру дан-
ных: в изменяемое дерево на Java (из GNU Classpath), в неизменяемое на
Java (из библиотеки functionaljava) и в неизменяемое на Haskell.
Даже использование диаграмм на бумаге не решает проблемы нали-
чия времени: для отражения изменений во времени приходится в каждой
строке кода либо перерисовывать диаграмму заново на чистом участке
листа, либо зачеркивать ее части, увеличивая путаницу.

3.2.5. Наследование
Классы с изменяемым состоянием плохо поддаются наследованию.
Класс-наследник, согласно принципу подстановки Лисков, должен быть
пригоден к использованию вместо базового класса в любом контексте —
в частности, должен поддерживать все его операции и сохранять все его
инварианты и спецификации операций. По отношению к операциям, спо-
собным изменять состояние объекта базового класса, это означает, что
класс-наследник не имеет права накладывать дополнительные ограни-
чения на это изменяемое состояние, т.к. тем самым он нарушит специфи-
кацию и инварианты изменяющих методов. Рассмотрим классическую ил-
²Имеется в виду «принцип подстановки Барбары Лисков», также известный как LSP
(Liskov Substitution Principle), гласящий «Если тип S унаследован от типа T, то должно быть
возможным подставить объект типа S в любом месте программы, ожидающем тип T, без
изменения каких-либо желаемых свойств программы — в т. ч. корректности» [3].

© 2009 «Практика функционального программирования» 52

3.2. Опасности изменяемого состояния

люстрацию этой проблемы.

Пример: Геометрические фигуры.
class Rectangle {
private int width , height ;
public Rectangle ( int w , h ) {
this . width = w ;
this . height = h ;
}
int getWidth () {...}
int getHeight () {...}
void setWidth ( int width ) {...}
void setHeight ( int height ) {...}
}
class Square extends Rectangle {
public Square ( int side ) {
super ( side , side ) ;
}
}
В классе Rectangle спецификация операций setWidth и setHeight
такова:

• r.getWidth() == w && r.getHeight() == h

⇒ после r.setWidth(w2) верно
r.getWidth() == w2 && r.getHeight() == h

• r.getWidth() == w && r.getHeight() == h

⇒ после r.setHeight(h2) верно
r.getWidth() == w && r.getHeight() == h2

Вызов setWidth или setHeight на объекте класса Square обязан так-

же удовлетворять этим спецификациям, однако при этом, очевидно, будет
разрушен инвариант класса Square «getWidth() == getHeight()».
Правило стоит повторить еще раз: Класс-наследник не имеет права на-
кладывать дополнительные ограничения на изменяемое состояние базо-
вого класса.

© 2009 «Практика функционального программирования» 53

3.3. Круги ада

3.3. Круги ада

Ознакомившись с некоторыми недостатками изменяемого состояния,
приступим к организации борьбы с ними. Первый этап борьбы — подроб-
ное изучение врага. Выполним классификацию вариантов изменяемого
состояния по степени их «вредности».
Прекрасная классификация предложена Скоттом Джонсоном в [2];
приведем ее с небольшими изменениями и добавлениями. Чем больше
номер круга ада, тем больше опасностей подстерегает нас. Избавление от
опасностей будет зачастую заключаться в переходе с большего номера к
меньшему.
1) Отсутствие изменяемого состояния. Этот «нулевой» круг ада абсо-
лютно безопасен с точки зрения вышерассмотренных проблем, но
достижим лишь в теории.

2) Невидимое программисту изменяемое состояние — код алгорит-

мов, не использующих изменяемое состояние, компилируется в ма-
шинный код, использующий изменяемые регистры, стек, память,
что при правильной реализации компилятора заметить невозмож-
но. Этот круг так же безопасен с практической точки зрения, как и
предыдущий.

3) Невидимое клиенту изменяемое состояние — скажем, локальные

переменные-счетчики внутри процедуры: изменение таких пере-
менных ненаблюдаемо извне самой процедуры. Этот круг безопа-
сен с точки зрения клиента.

4) Монотонное изменяемое состояние — переменные, присваива-

ние которых происходит не более 1 раза: переменная вначале не
определена, а затем определена. Это довольно безобидный тип из-
меняемого состояния, поскольку у переменной всего 2 состояния,
лишь одно из которых не целостно (к тому же, перевести пере-
менную в неопределенное состояние невозможно!), и обычно лег-
ко обеспечить, чтобы в нужный момент такая переменная оказалась
³В некоторых языках используются системы эффектов [1], позволяющие компилято-
ру делать подобные суждения автоматически.

© 2009 «Практика функционального программирования» 54

3.3. Круги ада

Рис. 3.3. Круги ада

определена. Монотонное изменяемое состояние часто использует-

ся для реализации ленивых вычислений.

5) Двухфазный цикл жизни. Это разновидность п. 4, при которой со-

стояний у объекта более двух, при этом жизнь объекта поделена на
две фазы: инициализация («наполнение»), при которой к нему про-
исходит доступ только на запись, и мирная жизнь, при которой до-
ступ производится только на чтение. Например, система сначала со-
бирает статистику, а затем всячески анализирует ее. Необходимо га-
рантировать, что во время фазы чтения не будет производиться за-
пись, и наоборот. Позднее будет рассмотрен прием («заморозка»),
позволяющий давать такую гарантию.

6) Управляемое изменяемое состояние — такое, как внешняя СУБД: в

системе присутствуют специальные средства для координации из-
менений и ограничения их опасностей, например, транзакции.

7) Инкапсулированное изменяемое состояние — переменные, до-

ступ к которым производится только из одного места (скажем,
private поля объектов). Контроль за целостностью состояния лежит
целиком на реализации объекта, и если реализация правильная, то
не существует способа привести объект в не-целостное состояние
(инварианты самого объекта не нарушаются). Достаточно правиль-
но реализовать сам объект. Тем не менее, для контроля инвариан-
тов, охватывающих несколько объектов, по-прежнему необходимы

© 2009 «Практика функционального программирования» 55

3.4. Борьба

специальные средства; либо же необходимо инкапсулировать весь

контроль за состоянием этих нескольких объектов в другом объек-
те.

8) Неинкапсулированное изменяемое состояние — глобальные пе-

ременные. Всем известно, что это — страшное зло. В этом случае
нельзя сказать ничего о том, кто и когда изменяет глобальную пе-
ременную, не изменяет ли ее кто-нибудь прямо сейчас, между вот
этими двумя строками кода, и т. п.

9) Разделяемое между несколькими процессами изменяемое со-

стояние. В условиях многопоточности управление изменяемым со-
стоянием превращается в ад во всех случаях, кроме тривиальных.
Огромное количество исследований посвящено разработке мето-
дик, позволяющих хоть как-то контролировать корректность мно-
гопоточных программ, но пока что главный вывод таков: хотите из-
бежать проблем с многопоточностью — минимизируйте изменяе-
мое состояние. Основная причина трудностей заключается в том,
что если имеется N потоков, каждый из которых проходит K состо-
яний, то количество возможных последовательностей событий при
одновременном выполнении этих потоков имеет порядок K N . Тех-
ники, позволяющие минимизировать подобные эффекты, рассмот-
рены ниже.

3.4. Борьба
Прежде чем перейти к обсуждению техник обезвреживания изменяе-
мого состояния, обсудим следующие глобальные идеи:

• Минимизация общего числа состояний: Чем меньше у системы со-

стояний, тем меньшее количество случаев надо учитывать при вза-
имодействии с ней. Следует помнить и о том, что чем больше со-
стояний, тем больше и последовательностей состояний, а именно
непредусмотренные последовательности состояний зачастую яв-
ляются причинами багов.

© 2009 «Практика функционального программирования» 56

3.4. Борьба

• Локализация изменений: Чем более локальные (обладающие

меньшей областью видимости) объекты затрагивает изменение,
тем из меньшего числа мест в коде изменение может быть замечено.
Чем менее изменения размазаны между несколькими объектами во
времени, тем легче логически сгруппировать их в несколько круп-
ных и относительно независимых изменений объектов. К примеру,
при сложном изменении узла структуры данных лучше сначала вы-
числить все новые характеристики этого узла, а затем произвести
изменения, нежели производить изменения сразу в самом узле.

• Разграничение права на наблюдение и изменение состояния (ин-

капсуляция): Чем меньше клиентов могут изменить состояние, тем
меньше действия этих клиентов нужно координировать. Чем мень-
ше клиентов могут прочитать состояние, тем легче его защищать от
изменений во время чтения.

• Исключение наблюдаемости промежуточных не-целостных со-

стояний: Если систему невозможно застать в таком состоянии, то
снаружи она всегда выглядит целостной и корректно работающей.

• Навязывание эквивалентности состояний и их последователь-

ностей: Если некоторые состояния или их последовательности в
каком-то смысле эквивалентны, то клиент избавлен от необходимо-
сти учитывать их частные случаи.

И, наконец, сами техники.

3.4.1. Осознание или отказ

Самый первый и самый важный шаг, который следует предпринять,
разрабатывая систему, использующую изменяемое состояние — понять,
чем в действительности обусловлено его наличие. Действительно ли в
предметной области есть понятие объектов, изменяющихся во времени?
Действительно ли в предметной области меняются именно те объекты,
которые вы собираетесь сделать изменяемыми?
К примеру, неудачное архитектурное решение об изменяемости гео-
метрических классов java.awt было бы отброшено уже на этом этапе: в

© 2009 «Практика функционального программирования» 57

3.4. Борьба

геометрии не бывает изменяемых точек и прямоугольников! Авторы биб-

лиотеки неверно определили изменяющиеся сущности: в действительно-
сти меняются не координаты точки — левого верхнего угла окна, а меня-
ется то, какая именно точка является левым верхним углом окна.
Аналогично этому примеру, множества и словари, в их математиче-
ском понимании, также не являются сами по себе изменяемыми объек-
тами — во многих задачах оправдано использование чисто функцио-
нальных структур данных (структур данных, не использующих присваи-
вания). К примеру, в интерфейс чисто функционального множества вме-
сто операции «добавить элемент» входит операция «получить множество,
отличающееся от данного наличием указанного элемента». Такие структу-
ры допускают реализацию, совершенно не уступающую по эффективно-
сти изменяемым структурам, а в некоторых задачах и существенно пре-
восходящую их (как ни странно, по потреблению памяти) — см. [5].
Если предметная область диктует наличие изменяющихся во времени
объектов, то необходимо признать этот факт и помнить о нем постоянно.
Особенно важно это в условиях многопоточности.
Необходимо осознать, что код — это больше не спецификация работы
алгоритма, а разворачивающаяся во времени последовательность собы-
тий с ненулевой длительностью: ни один вызов метода, ни одно присваи-
вание не проходит мгновенно, и между любыми двумя строками кода есть
временной «зазор».
Это кажется тривиальным, но если постоянно помнить об этих пра-
вилах, то многие глупые (и не только) ошибки многопоточного програм-
мирования или неявного взаимодействия становятся отчетливо видны на
этапе написания, а не на этапе отладки продакшн-системы.

3.4.2. Инкапсуляция
Большинство описанных ранее проблем с изменяемым состоянием
возникает из-за того, что слишком многие клиенты (функции, классы, мо-
дули) изменяют состояние, и слишком многие его читают. При этом ско-
ординировать чтение и изменение корректным образом не удается без
нарушения модульности и сильного усложнения кода. Минимизировать
проблемы такого рода можно, разграничив доступ к состоянию — предо-

© 2009 «Практика функционального программирования» 58

3.4. Борьба

ставив клиентам как можно меньше способов прочтения и изменения со-

стояния. Вместе с этим крайне важно, чтобы доступ был согласован с раз-
биением системы на компоненты. Так компонент, читающий состояние в
процессе своей работы, должен либо быть тесно связан с компонентами,
могущими его записывать, либо получать доступ к состоянию только в мо-
менты, когда оно не может изменяться, либо проективаться с учетом того,
что состояние может измениться в любой момент.
Вот несколько советов, связанных с инкапсуляцией:

Не возвращайте изменяемые объекты из «читающих» методов Если

метод, по своей сути, предназначен для выяснения какого-то свойства
объекта (скажем, даты создания), а не для получения доступа к этому
свойству, то он должен возвращать неизменяемый объект. В крайнем слу-
чае, он должен возвращать «свежий» объект (как сделано в java.awt),
но через возвращенный объект должно быть невозможно повлиять на ис-
ходный объект.

• Возвращать дату создания в виде объекта класса Calendar, возвра-

щая private-поля, недопустимо, т.к. объекты класса Calendar из-
меняемы. Гораздо лучше возвращать дату создания в виде long —
например, в виде числа миллисекунд с 1 января 1970 года (число,
возвращаемое функцией System.currentTimeMillis() в Java).

• Возвращая коллекцию, возвращайте ее неизменяемую обертку.

• Возвращая коллекцию, позаботьтесь о том, чтобы составляющие ее

объекты были неизменяемы.

Не возвращайте массивы — возвращайте коллекции Если необходи-

мо получить доступ к свойству типа «набор объектов», то возвращайте
его в виде коллекции, а не в виде массива. Доступ к массивам не инкапсу-
лирован: имея в своем распоряжении массив, всякий клиент может про-
читать или перезаписать какие-то из его элементов; при этом невозможно
гарантировать атомарность доступа в условиях многопоточности, тогда
как коллекции позволяют переопределять операторы чтения и записи и
делать их атомарными (synchronized).

© 2009 «Практика функционального программирования» 59

3.4. Борьба

Предоставляйте интерфейс изменения, соответствующий предметной

области Скажем, класс BankAccount должен предоставлять не метод
getMoney/setMoney, а методы deposit и withdraw. Благодаря этому ре-
ализация атомарности и контроль за инвариантами банка (скажем, нену-
левое количество денег на счете и сохранение общего числа денег в
банке) ляжет на реализацию BankAccount, а не на клиентов, вызываю-
щих getMoney/setMoney. Сюда же можно отнести атомарные операции:
AtomicInteger.addAndGet, ConcurrentMap.putIfAbsent, и т. п. Об этой
технике речь пойдет ниже, в разделе «Многопоточные техники».

3.4.3. Двухфазный цикл жизни и заморозка

Довольно часто изменяемые данные требуются для того, чтобы нако-
пить информацию и проинициализировать некоторый объект, который
затем будет использоваться уже без изменений. Таким образом, цикл жиз-
ни объекта делится на две фазы: фаза записи (накопления) и фаза чте-
ния; причем во время фазы накопления не производится доступ на чте-
ние извне, а во время фазы чтения не производится запись. В результате
все, кто читают объект, видят его неизменным. Для корректной работы
системы достаточно обеспечить, чтобы чтение и запись не пересекались
во времени.
В точке перехода от фазы накопления к фазе чтения можно подгото-
вить информацию (закэшировать какие-то значения, построить индексы),
что сделает чтение более эффективным.
Существует два подхода к организации двухфазного цикла жизни: ста-
тический и динамический.

Статический подход предполагает, что интерфейсы объекта в фазе чте-

ния и фазе записи отличаются.
public interface ReadFacet {
Foo getFoo ( int fooId ) ;
Bar getBar () ;
}
public interface WriteFacet {
void addQux ( Qux qux ) ;

© 2009 «Практика функционального программирования» 60

3.4. Борьба

void setBaz ( Baz baz ) ;

ReadFacet freeze () ;
}

class Item implements WriteFacet {

...
ReadFacet freeze () {
return new FrozenItem ( myData ) ;
}
}
class FrozenItem implements ReadFacet {
FrozenItem ( ItemData data ) {
this . data = data . clone () ;
prepareCachesAndBuildIndexes () ;
}
...
}
Клиент получает объект типа WriteFacet, производит в него запись, а
затем, когда запись окончена, замораживает объект и в дальнейшем поль-
зуется для чтения полученным ReadFacet. Конечно, необходимо, чтобы
созданный объект ReadFacet был полностью независим от заморажива-
емого, в противном случае дальнейший вызов записывающих методов ис-
портит его.
Зачастую организовывать два лишних интерфейса неудобно, или же
такой возможности может просто не оказаться: скажем, клиент ожидает
библиотечный интерфейс, содержащий и методы чтения, и методы запи-
си. При этом все же желательно иметь возможность гарантировать отсут-
ствие записей после начала чтения, и возможность построить кэши после
фазы чтения с гарантией их будущей целостности. Тут пригодится второй
подход к заморозке.

Динамический подход предполагает, что формально интерфейсы объ-

екта в фазе чтения и записи одинаковы, однако фактически поддержива-
емые операции отличаются, как и в случае статического подхода.

© 2009 «Практика функционального программирования» 61

3.4. Борьба

class Item implements QuxAddableAndFooGettable {

private boolean isFrozen = false ;
...
void addQux ( Qux qux ) {
if ( isFrozen ) throw new
IllegalStateException () ;
...
}

Foo getFoo ( int fooId ) {

if (! isFrozen ) throw new
IllegalStateException () ;
// Efficiently get foo using caches / indexes
}

void freeze () {
prepareCachesAndBuildIndexes () ;
isFrozen = true ;
}
}
Здесь статическая проверка заменяется на динамическую, однако об-
щая идея остается той же: на фазе записи объект предоставляет только
интерфейс записи, на фазе чтения — только интерфейс чтения.
В качестве иллюстрации такого подхода рассмотрим пример из прак-
тики автора.
Пример: Кластеризация документов. Каждый документ в программе
описывается длинным разреженным битовым вектором свойств. В начале
программа анализирует документы, составляя их векторы свойств и поль-
зуясь изменяющим интерфейсом битового вектора (установить/сбросить
бит). Затем, при вычислении матрицы попарных расстояний между доку-
ментами выполняется лишь две операции: вычисление мощности пере-
сечения и мощности объединения двух векторов. Эти операции можно
реализовать очень эффективно, если «подготовить» векторы, построив на
них «пирамиду» (не будем углубляться в подробности), однако обновлять
пирамиду при вставках в битовый вектор слишком дорого. Поэтому пи-
рамида строится для каждого вектора сразу после вычисления векторов

© 2009 «Практика функционального программирования» 62

3.4. Борьба

и перед вычислением матрицы попарных похожестей, и матрица затем

строится очень быстро (ускорение в рассматриваемой задаче достигло
двух порядков).
Поскольку объекты с двухфазным циклом жизни легко использовать
корректно, то стоит попытаться разглядеть их в своей задаче или свести
ее к ним; вовсе не обязательно при этом даже использовать заморозку —
само наличие двухфазности вносит в программу стройную структуру.

3.4.4. Превращение изменяемой настройки в аргумент

Довольно часто бывает так, что изменяемые данные используются для
«настройки» объекта: объект настраивается с помощью нескольких сетте-
ров, а затем выполняет работу. Это похоже на двухфазный цикл жизни, од-
нако процесс настройки сконцентрирован в одном месте кода и в одном
коротком промежутке времени, известное количество настроек подают-
ся одна за другой.
В некоторых случаях это не является проблемой, однако представим
себе такой класс:
Пример: Подсоединение к базе данных.
class Database {
void setLogin ( String login ) ;
void setPassword ( String password ) ;
Connection connect () throws
InvalidCredentialsException ;
}
Наличие такого класса может поначалу выглядеть оправданным, если
он используется, скажем, из графического интерфейса, который сначала
запрашивает у пользователя логин (и, запросив, вызывает setLogin), за-
тем запрашивает пароль (и вызывает setPassword), а затем по нажатию
кнопки «Connect» вызывает connect.
Однако если объект Database окажется разделяемым между несколь-
кими пользователями, то вызовы setLogin, setPassword, connect начнут
путаться между собой, пользователи будут получать чужие соединения, и
т. п. — такая ситуация совершенно недопустима.
Гораздо лучше избавиться от изменяемости в интерфейсе Database:

© 2009 «Практика функционального программирования» 63

3.4. Борьба

class Database {
Connection connect ( String login , String password )
throws InvalidCredentialsException ;
}
При этом, конечно, клиенту придется управлять хранением значений
login и password самостоятельно, однако путаница будет устранена.
Для ситуаций, когда хранение данных нежелательно (например, дол-
гое хранение пароля в памяти может быть нежелательно по соображени-
ям безопасности), пригодится, в частности, паттерн «Curried Object» («Кар-
рированный объект»), о котором речь пойдет позже.

3.4.5. Концентрация изменений во времени

Родственный предыдущему метод — концентрирование изменений
во времени. Он заключается в том, чтобы вместо последовательности
мелких изменений выполнять одно большое, тем самым убивая сразу
двух зайцев:

1) Избавление от промежуточных состояний между мелкими измене-

ниями.

2) Избавление от необходимости устанавливать протокол последова-

тельности внесения изменений.

П.1 позволяет решить проблемы, сходные с описанными в предыду-

щем разделе (путаницу между клиентами).
П.2 полезен в случаях, когда мелкие изменения в определенном смыс-
ле взаимозависимы, и не всякая последовательность мелких изменений
является корректной, поэтому приходится навязывать клиенту протокол,
предписывающий, в каком порядке нужно вносить изменения. Это может
быть чрезвычайно неудобно.
Пример: Библиотека бизнес-правил. Рассмотрим библиотеку, позво-
ляющую пользователю задать ряд бизнес-правил для вычисления некото-
рых величин. Правила (формулы) могут быть взаимозависимы.
Интерфейс библиотеки выглядит так:

© 2009 «Практика функционального программирования» 64

3.4. Борьба

interface RuleEngine {
void addRule ( String varName , String formula )
throws ParseException ,
UndefinedVariableException ;

double computeValue ( String varName ) ;

}
В каждый момент правила должны быть целостными, поэтому addRule
бросает UndefinedVariableException в случае, когда formula ссылает-
ся на переменную, для которой еще нет правила.
Большой минус такой библиотеки — в том, что если клиенту необхо-
димо задать сразу несколько взаимозависимых правил (скажем, считать
их из файла или электронной таблицы), то клиент должен сам заботиться
о том, чтобы подавать правила в порядке топологической сортировки, т.е.
добавлять зависимое правило только после добавления всех, от которых
оно зависит!
Лучше перепроектировать интерфейс так:
interface RuleParser {
RuleSet parseRules ( Map < String , String >
var2formula )
throws ParseException ,
CircularDependencyException ;
}
interface RuleSet {
double computeValue ( String varName ) ;
}
Теперь конструирование набора взаимозависимых правил инкапсу-
лировано в методе parseRules. Он сам выполняет топологическую сор-
тировку передаваемых ему пар «переменная/формула» и детектирует
циклические зависимости.

3.4.6. Концентрация изменений в пространстве объектов

Эта методика призвана устранить необходимость в поддержании ин-
вариантов, охватывающих сразу несколько объектов: чем меньше объек-

© 2009 «Практика функционального программирования» 65

3.4. Борьба

тов охватывает инвариант, тем проще его сохранять, и тем меньше шан-
сов, что кто-то разрушит инвариант, изменив один из составляющих его
объектов, но не изменив и ничего не зная о другом.
К примеру, сложность реализации двусвязных списков в значитель-
ной степени проистекает из того, что каждая операция, затрагивающая
определенный узел, должна позаботиться о двух его соседних узлах и о
самом списке (ссылках на первый/последний узел).
Методика состоит в том, чтобы минимизировать количество объек-
тов, охватываемых инвариантами. Зачастую она сводится к разрыву за-
висимостей между объектами и, особенно, разрыву циклических зависи-
мостей. К сожалению, с двусвязными списками, по-видимому, ничего не
поделать; мы рассмотрим другой пример.
Пример: Многопользовательская ролевая игра. В рассматриваемой
игре есть понятие «артефакта», и характеристики артефакта могут зави-
сеть от характеристик игрока, носящего его. Поэтому в артефакт включа-
ется информация о его владельце:
class Artifact {
Player getOwner () ;
void setOwner ( Player player ) ;

Picture getPicture () ;

int getStrengthBoost () ;
int getHealthBoost () ;
int getDexterityBoost () ;
int getManaBoost () ;
}
class Player {
List < Artifact > getArtifacts () ;
void addArtifact ( Artifact a ) ;
void dropArtifact ( Artifact a ) ;
void passArtifact ( Artifact a , Player toWhom ) ;
}
Должен выполняться следующий инвариант: «если a.getOwner()==p,
то p.getArtifacts().contains(a), и наоборот».

© 2009 «Практика функционального программирования» 66

3.4. Борьба

Все 4 метода get∗Boost() учитывают расу игрока

(getOwner().getRace()): у великанов умножается на 2 значение
getStrengthBoost любого артефакта, у гномов — getHealthBoost, у
эльфов — getDexterityBoost, у друидов — getManaBoost.
Пока артефакт лежит на земле, его getOwner() равен null. Когда иг-
рок подбирает, роняет или передает артефакт, вызывается setPlayer.
Для каждого артефакта, присутствующего на карте мира, нужен
отдельный экземпляр класса Artifact, хранящий в себе Picture,
strengthBoost, healthBoost, dexterityBoost и manaBoost — исполь-
зовать один и тот же экземпляр даже для совершенно одинаковых арте-
фактов нельзя, т.к. экземплярами могут владеть разные игроки. Учитывая,
что артефактов на карте может быть очень много, а характеристик у них
может быть гораздо больше, чем указано здесь — имеет место лишний
расход памяти.
Ситуацию можно улучшить, если сделать класс Artifact неиз-
меняемым и разорвать зависимость от игрока (убрать методы
getPlayer/setPlayer), тем самым избавившись полностью от необ-
ходимости поддерживать указанный инвариант, позволив использовать
один и тот же экземпляр класса Artifact в рюкзаках разных игроков и
существенно сократив потребление памяти.
Встает, конечно, вопрос — как же теперь быть с методами
get∗Boost()? Ведь метод без аргументов у артефакта больше не
может давать правильный ответ.
Ответов несколько, и все они очень просты:

• Добавить аргумент типа Player к методам get∗Boost().

• Перенести методы в класс Player:

Player.getStrengthBoost(Artifact a).

• Переименовать методы в getBaseStrenghBoost и

т. п., и вынести логику определения действия арте-
факта в отдельный класс ArtifactRules, в методы
getStrengthBoost(Artifact a, Player p). К таким методам
можно будет легко добавить обработку и других условий: погоды,
наличия вокруг других игроков и т. п.

© 2009 «Практика функционального программирования» 67

3.4. Борьба

Этот прием — избавление от изменяемых данных благодаря разрыву

зависимостей — используется в чисто функциональных структурах дан-
ных и позволяет разделять значительную часть информации между дву-
мя мало отличающимися структурами. Благодаря этому бывает возмож-
на огромная экономия памяти (в задаче из практики автора, где требова-
лось хранить большое количество не очень сильно различающихся цело-
численных множеств, переход от изменяемого красно-черного дерева к
неизменяемому позволил сократить потребляемую память примерно на
два порядка).

3.4.7. Каррирование
Название этой методики связано с аналогичным понятием из функци-
онального программирования: при каррировании функции с нескольки-
ми аргументами некоторые из этих аргументов фиксируются, и получает-
ся функция от оставшихся.
Методика описана в статье [4] и предназначена для упрощения слож-
ных протоколов, где каждый вызов требует большого количества аргу-
ментов, некоторые из которых меняются редко или не меняются вовсе.
Эта методика прекрасно подходит для разрыва зависимости по состо-
янию между несколькими клиентами, использующими объект, и попутно
дает еще несколько преимуществ.
Можно сказать, что паттерн Curried Object — это частный случай инкап-
суляции состояния; более точно, он предписывает выделить часть объек-
та, позволяющую хорошую инкапсуляцию состояния, в самостоятельный
объект.
Пример: Улучшение безопасности подсоединения к БД. Рассмот-
рим упомянутый выше пример с подсоединением к базе данных. Про-
блема изначальной версии заключалась в том, что вызовы разных клиен-
тов setLogin, setPassword, connect переплетались, а исправленной —
в том, что программа могла долго хранить в памяти пароль. Фиксирован-
ным (хотя и неявным) аргументом в данном случае является то, какой кли-
ент производит вызовы. Применим паттерн Curried Object и выделим каж-
дому клиенту его личный объект для обработки протокола соединения.
class Database {

© 2009 «Практика функционального программирования» 68

3.4. Борьба

Connector makeConnector () ;
}
class Connector {
void sendLogin ( String login ) ;
void sendPassword ( String password ) ;
Connection connect ()
throws InvalidCredentialsException ;
}
В такой реализации makeConnector будет создавать новый независи-
мый объект, производящий сетевое соединение с базой данных и в мето-
дах sendLogin, sendPassword сразу отсылающий логин и пароль по сети.
У каждого клиента объект Connector будет свой, поэтому клиенты не бу-
дут мешать друг другу.
Рассмотрим еще одну иллюстрацию паттерна «Curried Object».
Пример: Загрузчик данных. Программа предназначена для загруз-
ки в базу большого количества данных от разных клиентов: клиент под-
ключается к программе и загружает большое количество данных, затем
отключается. Программа обязана обеспечить транзакционность загруз-
ки данных от каждого клиента. Изначально API программы проектируется
так:
class DataLoader {
ClientToken beginLoad ( Client client ) ;
void writeData ( ClientToken token , Data data ) ;
void commit ( ClientToken token ) ;
void rollback ( ClientToken token ) ;
}
Клиент вызывает beginLoad и с помощью полученного ClientToken
многократно вызывает writeData, затем вызывает commit или rollback.
Эта программа избавлена от проблем переплетения запросов между кли-
ентами, однако код DataLoader довольно сложен: он хранит таблицу со-
ответствия клиентов и транзакций и соединений БД, и в каждом из мето-
дов пользуется соответствующими элементами таблицы.
В некоторых задачах клиенты сами по себе могут быть многопоточны-
ми: скажем, клиент может в несколько потоков вычислять данные и вы-
полнять их запись. Если метод writeData не обладает потокобезопасно-

© 2009 «Практика функционального программирования» 69

3.4. Борьба

стью при фиксированном token, то код еще усложнится: добавится таб-

лица соответствия «клиент / объект синхронизации», и метод writeData
будет синхронизироваться по соответствующему ее элементу.
Нельзя забывать и о том, что доступ к таблицам также должен быть
синхронизирован.
Существенно упростить код можно, если перепроектировать
DataLoader, применив Curried Object:
class DataLoader {
PerClientLoader beginLoad ( Client client ) ;
}
class PerClientLoader {
void writeData ( Data data ) ;
void commit () ;
void rollback () ;
}
Теперь класс DataLoader полностью избавлен от изменяемого со-
стояния! В классе PerClientLoader нет никаких таблиц, и синхрониза-
ция выполняется тривиально — достаточно объявить все три метода как
synchronized. Клиенты также никак не могут помешать друг другу. Код
получился простым и безопасным.

3.4.8. Многопоточные техники

Как уже было сказано, трудности с написанием корректных многопо-
точных программ проистекают от большого количества возможных сов-
местных трасс выполнения нескольких процессов. Корректность необхо-
димо гарантировать на всех трассах, в связи с чем приходится рассмат-
ривать большое количество возможных переплетений трасс и проверять
на корректность каждое из них. Напомним, что количество трасс при N
потоках, у каждого из которых K состояний, можно оценить как K N .
Возможные пути уменьшения числа трасс, которые необходимо учи-
тывать, таковы:

Использование критических секций для синхронизации. Охватыва-

ние критической секцией блока кода, содержащего M состояний, умень-

© 2009 «Практика функционального программирования» 70

3.4. Борьба

шает число состояний на M −1, превращая весь блок в один переход меж-
ду двумя состояниями. Благодаря этому соответственно уменьшается ко-
личество совместных трасс.

Использование атомарных операций. Это двоякий совет. С одной сто-

роны, речь идет о том, чтобы пользоваться эффективными аппаратно реа-
лизованными операциями, такими как «прочитать-и-увеличить» (get-and-
add), «сравнить-и-поменять» (compare-and-exchange) и т. п. С другой сто-
роны, что более важно, речь идет о том, чтобы предоставлять API в терми-
нах атомарных, соответствующих предметной области, операций:
• «Перевести деньги с одного счета на другой» (помимо «снять день-
ги, положить деньги»).

• «Добавить элемент, если он еще отсутствует» (помимо «добавить

элемент, проверить наличие») — кстати, сюда же относятся SQL-
команды MERGE и INSERT IGNORE.

• «Выполнить соединение с данным логином и паролем» (помимо

«установить логин, установить пароль, выполнить соединение»).

• и т. п.

Локализация изменяемого состояния. Вместо применения несколь-

ких изменений к глобально видимому объекту — вычисление большого
изменения в локальной области видимости и его атомарное применение.
Этот прием уже был рассмотрен выше в разделе «Концентрация измене-
ний во времени».

Навязывание эквивалентности трасс. Кардинально иной подход к

уменьшению числа различных трасс — стирание различий между некото-
рыми из них. Для этого можно использовать следующие два алгебраиче-
ских свойства некоторых операций (а если операции ими не обладают —
попытаться перепроектировать их так, чтобы обладали):
• Идемпотентность: Операция, будучи выполненной несколько раз,
имеет тот же эффект, что и при однократном выполнении.

© 2009 «Практика функционального программирования» 71

3.4. Борьба

• Коммутативность: Порядок последовательности из нескольких

операций различного типа или с различными аргументами не имеет
значения.
Такие операции особенно важны в распределенном и асинхронном про-
граммировании, когда синхронизация может быть крайне неэффективна
или просто-напросто невозможна.
Пример: Покупка в интернет-магазине. Рассмотрим простой интер-
фейс оформления покупки в интернет-магазине: пользователь логинится,
выбирает продукт, количество, и жмет кнопку «купить». При этом на сер-
вере вызывается следующий API:
class Shop {
void buy ( Request request , int productId , int
quantity ) {
Session session = request . getSession () ;
Order order = new Order (
session . getCustomer () , productId ,
quantity ) ;
database . saveHistory ( order ) ;
billing . bill ( order ) ;
}
}
Представим себе ситуацию, когда закупиться хочет пользователь с
нестабильным соединением с интернетом. Он нажимает кнопку «Купить»,
однако ответный TCP-пакет от сервера теряется и браузер в течение 5 ми-
нут показывает «Идет соединение…». Наконец, пользователю надоедает
ждать и он нажимает кнопку «Купить» еще раз. На этот раз все проходит
нормально, однако через неделю пользователю приходит два экземпля-
ра товара и он с удивлением обнаруживает, что деньги с его кредитной
карты также сняты два раза.
Это произошло потому, что операция buy не была идемпотентна —
многократное ее выполнение не было равносильно однократному. Ко-
нечно, нельзя говорить об идемпотентности операции покупки товара —
ведь купить телевизор два раза — не то же самое, что купить его один раз!
Можно, однако, говорить об идемпотентности операции нажатия кнопки
«Купить» на некоторой странице.

© 2009 «Практика функционального программирования» 72

3.4. Борьба

class Session {
int stateToken ;

void advance () {
++ stateToken ;
}
int getStateToken () {
return stateToken ;
}
}
class Shop {
Page generateOrderPage ( Request request ) {
Session session = request . getSession () ;
session . advance () ;
... < INPUT type = ’hidden’
value = ’”+session.getStateToken()+”’ >...
}

void buy ( Request request , int productId , int

quantity ) {
Session session = request . getSession () ;
if ( session . currentStateToken () !=
request . getParamAsLong ( ”stateToken” ) )
{
return ;
}
Order order = new Order (
session . getCustomer () , productId ,
quantity ) ;
database . saveHistory ( order ) ;
billing . bill ( order ) ;

session . advance () ;
}
}
Таким образом, каждая страница заказа помечается целым числом;
при каждой загрузке страницы заказа или покупке это число увеличивает-

© 2009 «Практика функционального программирования» 73

3.5. Заключение Литература

ся. Нажать кнопку «Купить» несколько раз с одной страницы нельзя — это
обеспечивается тем, что после того, как покупка уже была произведена,
stateToken у сессии увеличивается и перестает совпадать со stateToken
в запросе.
Операция стала идемпотентной, а ситуации, подобные описанной,
невозможными.

3.5. Заключение
Тот факт, что обеспечение корректности программ, использующих из-
меняемое состояние, особенно многопоточно — нелегкая задача, осо-
знают почти все программисты. Программистский фольклор включает
множество описанных и неописанных приемов рефакторинга таких про-
грамм в более простую и корректную форму. В этой статье автор пред-
принял попытку собрать вместе и описать эти приемы, а также выделить
их общие идеи.
Идеи, как оказалось, сводятся к избавлению от изменяемого состоя-
ния, приведению кода в более декларативную и близкую к предметной
области форму, инкапсуляции и локализации объектов с состоянием, на-
лаганию на код определенных алгебраических свойств — все то, что зна-
комо функциональным программистам, ценящим возможность легко рас-
суждать о свойствах программ математически.
Автор выражает надежду, что данная статья послужит как полезным
справочником для программистов на объектно-ориентированных и про-
цедурных языках, так и мотивирует их погрузиться в интереснейший мир
функциональных языков, откуда многие из описанных идей почерпнуты
и где изменяемое состояние — скорее исключение, чем правило, благо-
даря чему код легко тестируем и настолько корректен, что бытует лишь
наполовину шуточное утверждение «компилируется — значит работает».

Литература
[1] Effect system. — Статья в Wikipedia, URL: http://en.wikipedia.
org/wiki/Effect_system (дата обращения: 20 июля 2009 г.).

© 2009 «Практика функционального программирования» 74

Литература Литература

[2] Johnson S. — Комментарий на форуме Lambda-the-Ultimate,

URL: http://lambda-the-ultimate.org/node/724#
comment-6621 (дата обращения: 20 июля 2009 г.).

[3] Liskov B. H., Wing J. M. Behavioural subtyping using invariants and con-
straints // Formal methods for distributed processing: a survey of object-
oriented approaches. — New York, NY, USA: Cambridge University Press,
2001. — Pp. 254–280.

[4] Noble J. Arguments and results // In PLOP Proceedings. — 1997.

[5] Okasaki C. Purely Functional Data Structures. — Cambridge University

Press, 1998.

© 2009 «Практика функционального программирования» 75

 Давно не брал я в руки шашек

Дмитрий Астапов
[email protected]

Аннотация

Функциональные языки обладают рядом полезных

свойств, позволяющих ускорить прототипирование и раз-
работку программ. В частности, функциональные языки
существенно облегчают разработку программ методом
«сверху вниз», позволяя программисту сосредоточиться на
высокоуровневом проектировании системы до того, как он
углубится в детали реализации.
Данная статья на практическом примере демонстрирует
процесс проектирования и разработки «сверху вниз» про-
грамм на языке Haskell. Она рассчитана на программистов, ко-
торые уже начали знакомство с функциональным программи-
рованием и языком Haskell, но испытывают нехватку практи-
ческих примеров того, как проектируются и разрабатываются
программы на Haskell и функциональных языках.
4.1. Введение

4.1. Введение
Начиная реализацию нового проекта, программист зачастую уже об-
ладает определенным набором библиотек, которые он хочет (или дол-
жен) использовать. Очень часто можно наблюдать, как работа при этом
строится «снизу вверх» — отталкиваясь от предлагаемых библиотеками
функций, программист пишет свой код, постепенно повышая уровень аб-
стракции и переходя ко все более высокоуровневым компонентам систе-
мы.
В то же время, существует целый ряд причин, по которым подход к раз-
работке в противоположном направлении — «сверху вниз» — может ока-
заться предпочтительнее:

Контекст всегда понятен. Проектирование высокоуровневой структу-

ры системы дает контекст для проектирования более мелких ком-
понентов — будь то подсистемы, классы или функции — повышая
вероятность того, что они будут правильно абстрагированы, а ин-
терфейсы между ними будут качественно построены. При проекти-
ровании «снизу вверх», напротив, легко потерять общий контекст и
упустить из виду какой-то аспект решаемой задачи.

Идентификация рисков. Построение системы «от общего к частному»

дает дополнительные возможности по идентификации рисков. По-
сле того, как основные подсистемы и компоненты реализованы
(пусть даже в виде «пустышек»), появляется возможность оценить
сложность их реализации и заранее предотвратить возможные рис-
ки, например, изменив дизайн системы.

Управление временем. Когда основные модули системы уже написа-

ны (или спроектированы), у разработчика появляется возможность
примерно оценить сложность и время, требуемое на разработку то-
го или иного компонента. В дальнейшем разработчик, скорее всего,
будет стремиться рационально распределять свои усилия и не тра-
тить слишком много времени на углубление в какой-то один аспект
системы. В то же время, при разработке «снизу вверх» велик риск

© 2009 «Практика функционального программирования» 77

4.2. Постановка задачи и функция main

потратить слишком много времени на «вылизывание» одного мел-

кого участка в ущерб общему качеству продукта.
Функциональные языки способствуют тому, чтобы использовать под-
ход к проектированию «сверху вниз» в повседневной работе. Развитые
возможности композиции сложных программных функций из более про-
стых и статическая типизация с автоматическим выводом типов позволя-
ют программисту писать код итеративно, постепенно уменьшая уровень
абстракции и продвигаясь от прототипа к работающей реализации. При
этом программист может опираться на компилятор или интерпретатор
функционального языка как на техническое средство проверки внутрен-
ней непротиворечивости уже написанного кода.
Впрочем, лучше один раз увидеть, чем сто раз услышать. Данная ста-
тья покажет на практическом примере, как выполняется дизайн и пишет-
ся «сверху вниз» программный код на функциональном языке програм-
мирования Haskell.
Предполагается, что читатель уже ознакомился с синтаксисом языка
Haskell при помощи книг (например, [7] и [11]) или учебников (например,
[12], [10] или [4]). Характерные приемы написания кода, использованные
в примерах, будут указываться в сносках, начинающихся со слова Haskell.
Предполагается, что читатель сам сможет углубленно ознакомиться с ука-
занными темами, используя свободно доступные в сети ресурсы.

4.2. Постановка задачи и функция main

Практической задачей, которая будет решена в рамках этой статьи,
будет реализация программы, позволяющей играть в шашки. Определим
высокоуровневые требования таким образом: программа должна позво-
лять играть в шашки (русские или международные) двум игрокам, причем
в роли каждого игрока может быть человек или «искусственный интел-
лект».
Таким образом, программа должна сначала определять конфигура-
цию партии (при помощи файла с настройками, через пользовательский
¹Для этого язык должен быть статически типизирован, а его компилятор — обладать
возможностью выведения типов выражений. Примеры подобных языков: Haskell, OCaml.

© 2009 «Практика функционального программирования» 78

4.2. Постановка задачи и функция main

интерфейс или как-то иначе), затем проводить партию и по ее заверше-

нии прекращать работу.
Соответствующий код на Haskell выглядит так :
main = do
( newBoard , playerA , playerB ) ← getConfig
play newBoard playerA playerB
Поскольку устройство функций getConfig и play пока еще не рас-
сматривается, их определение временно будет состоять из вызова функ-
ции undefined:
getConfig = undefined
play = undefined
Вызов функции undefined приводит к генерации ошибки во время ис-
полнения программы и выводу сообщения «Prelude: undefined». Однако у
этой функции есть одно примечательное свойство, позволяющее исполь-
зовать ее в качестве универсального маркера «TODO» при написании ко-
да: компилятор считает, что тип результата этой функции — это самый об-
щий, самый глобальный тип, который только может быть. Все остальные
типы, с точки зрения компилятора, являются подтипами этого общего ти-
па. Некоторой аналогией подобной концепции может служить тип Object
в языке Java или void ∗ в языке C.
На практике это означает, что программист может осуществлять про-
ектирование «сверху вниз» планомерно, не углубляясь в детали реали-
зации вводимых функций сразу же после первого их упоминания, и при
этом поддерживать код в компилируемом состоянии. Да, запуск подоб-
ной программы будет невозможен, но в ходе компиляции будет выпол-
нена проверка типов в уже написанном коде, и программист будет уве-
домлен об обнаруженных ошибках. Поскольку в случае Haskell успешно
скомпилированный код с большой вероятностью будет корректно рабо-
тать, это очень ценный результат.
Безусловно, в программах на Java/C/C++ тоже можно описывать мето-
ды или функции с пустым телом для достижения подобной цели. Однако
²Haskell: в функции main используется «синтаксический сахар» под названием «do-
нотация» для упрощения записи операций ввода/вывода. См. [3] и [7, глава 7].
³Детальное описание этого примечательного факта см. в [1].

© 2009 «Практика функционального программирования» 79

4.3. Формализация правил игры

при этом программисту необходимо будет сразу указать полную сигнату-

ру метода или функции: количество и тип аргументов, тип возвращаемо-
го результата. Если же в ходе проектирования высокоуровневые функции
или методы будут изменены, программисту с большой вероятностью по-
требуется изменить сигнатуры многих пустых методов, прежде чем код
сможет снова быть скомпилирован. Charles Petzold считает [9], что подоб-
ные особенности императивных языков, вкупе с технологиями интеллек-
туального дополнения кода (Intellisense), опирающимися на информацию
о типах объявленных функций и методов, приводят к практической невоз-
можности заниматься разработкой «сверху вниз», вынуждая программи-
ста работать «снизу вверх».
Чтобы убедиться, что написанный код на Haskell действительно ком-
пилируется, его можно сохранить в файл (допустим, «checkers01.hs») и за-
грузить в интерпретатор Haskell :

% ghci checkers01.hs
GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main ( checkers01.hs, interpreted )
Ok, modules loaded: Main.

4.3. Формализация правил игры

Поскольку способ настройки программы и конкретный вид настроек
сильно зависят от деталей реализации игры, разумно временно забыть
про функцию getConfig и сосредоточить внимание на функции play, от-
вечающей за проведение одной игровой партии.
Как известно, партия в шашки начинается с расстановки фигур, после
чего стороны поочередно делают ход до тех пор, пока один из игроков не
⁴Автор множества книг по программированию под Windows.
⁵В статье демонстрируются примеры с использованием интерпретатора ghci под OS
Linux, но с таким же успехом можно использовать и любой другой интерпретатор — на-
пример, hugs — в привычной операционной среде.

© 2009 «Практика функционального программирования» 80

4.3. Формализация правил игры

устранит с доски все фигуры противника, либо пока игра не завершится

ничьей. Чтобы упростить код и описание, будем считать, что партия может
завершиться только победой одной из сторон.
Данное описание фактически дословно переводится в код на Haskell :
play newBoard playerA playerB = do
displayBoard newBoard
makeMove newBoard White
where
makeMove board side = do
nextBoard ← undefined
displayBoard nextBoard
if isVictory side nextBoard
then return ( ”Winner is ” ++ show side )
else makeMove nextBoard ( otherSide side )

isVictory = undefined

data Side = White ∣ Black deriving Show

otherSide White = Black
otherSide Black = White

displayBoard = undefined
Разумно предположить, что сведения об игроке/цвете фигур потребу-
ются не только в этой части кода — например, для описания расположе-
ния фигур на доске. До проектирования этих частей системы еще далеко,
но уже сейчас можно ввести отдельный тип данных Side для кодирования
сведений об игроке.
Новое расширенное определение функции play включает в себя две
«заглушки»: функцию isVictory, используемую для определения конца
⁶Haskell: функция makeMove производит обновление состояния доски без исполь-
зования переменных — новое состояние передается в рекурсивный вызов функции
makeMove.
Объявление deriving Show просит компилятор автоматически реализовать для ука-
занного типа данных функцию show, используемую при объявлении победителя.
Так как функция displayBoard производит вывод на экран, для записи функции
makeMove также используется do-нотация.

© 2009 «Практика функционального программирования» 81

4.3. Формализация правил игры

партии, и код генерации нового состояния доски newBoard на основании

хода игрока. Поскольку правила игры в шашки жестко регламентируют
приоритет и очередность всех действий игрока в течении хода, их можно
(и нужно) запрограммировать.
Во-первых, если игрок имеет возможность взять фигуру противника,
он обязан это сделать, в противном случае он может сделать ход любой
(имеющей на то возможность) фигурой. Если игрок может взять несколь-
ко фигур подряд — он также обязан это сделать. Для упрощения кода и
изложения будем считать, что шашки ходят и берут исключительно впе-
ред (не назад), и игрок не обязан делать ход именно той фигурой, которая
способна взять максимальное количество фигур противника.
Если по окончании хода шашка игрока оказалась на самом дальнем
от него ряду игрового поля, она превращается в «дамку» и получает воз-
можность ходить (и бить) на произвольное количество полей по диагона-
ли как вперед, так и назад. Расширенное определение локальной функции
makeMove, реализующей эти правила, выглядит так:
makeMove board side = do
afterMove ← if canAttack board side
then undefined −− do attack
else undefined −− do move
let nextBoard = upgradeToKings afterMove
displayBoard nextBoard
if isVictory side nextBoard
then ...

upgradeToKings = undefined
canAttack = undefined
Выбор фигуры, которая будет ходить или выполнять взятие, должен
выполняться функцией playerA (или playerB, в зависимости от того, чей
ход). В качестве результата эти функции должны возвращать обновленное
состояние доски после завершения хода.
⁷Подобные соглашения приняты, в частности, в английском варианте игры в шашки.
⁸По-английски «дамка» называется «king», и именно так она будет именоваться в коде
программы.

© 2009 «Практика функционального программирования» 82

4.3. Формализация правил игры

Очевидно, что для принятия правильного решения эти функции долж-

ны получить, как минимум, информацию о:

1) текущем состоянии доски (фигур);

2) цвете фигур, которыми играет игрок;

3) том, какого рода ход надо сделать — простой или со взятием.

Для кодирования типа хода будет введен тип данных MoveType:

data MoveType = Move ∣ Attack
Теперь пробелы в определении функции makeMove могут быть запол-
нены таким образом :
makeMove board side = do
let player = getPlayer side
afterMove ← if canAttack board side
then attackLoop player board side
else player Move board side
...
getPlayer = undefined
Функция getPlayer, выбирающая правильную функцию-реализацию
поведения игрока в зависимости от того, чей сейчас ход, выглядит при
этом так :
getPlayer White = playerA
getPlayer Black = playerB
Осталось описать вспомогательную функцию attackLoop, реализую-
щую взятие фигур до тех пор, пока это возможно:
⁹Haskell: этот пример хорошо иллюстрирует отсутствие какого-либо особого стату-
са у функций по сравнению со всеми прочими типами данных. Видно, что player —
это результат работы функции getPlayer. При этом player используется в выражении
player Move board side. То есть, player — это функция; как функция, она может быть
возвращена в качестве результата работы других функций. В то же время, player пере-
дается в качестве аргумента в функцию attackLoop.
¹⁰Haskell: поскольку функция getPlayer определена локально в where-блоке функции
play, ей непосредственно доступны все аргументы функции play и их не нужно явно
передавать при вызове getPlayer.

© 2009 «Практика функционального программирования» 83

4.4. Компьютерный игрок с примитивной стратегией

attackLoop player board side = do

board ’ ← player Attack board side
if canAttack board ’ side
then attackLoop player board ’ side
else return board ’
Полная версия кода, получившегося в результате, приведена на ри-
сунке 4.1. Она также находится в файле «checkers02.hs», расположенном в
архиве с примерами кода.

4.4. Компьютерный игрок с примитивной стра-

тегией
Очевидно, что код программы должен включать в себя некоторый API
для доступа к состоянию доски и его модификации. Этим API будут пользо-
ваться, к примеру, функции, реализующие поведение компьютерных иг-
роков.
В рамках подхода к проектированию «сверху вниз» это означает, что
сначала будет написан код, реализующий поведение компьютерных иг-
роков, а в процессе его написания будут выработаны требования к тому,
какие функции должны входить в это API, и определена их функциональ-
ность.
Простейший компьютерный игрок — это игрок со случайным пове-
дением. На каждом ходе он выбирает один из доступных ходов, без вся-
кой стратегии, и делает его. Чтобы иметь возможность выбрать случай-
ный ход из списка доступных, надо каким-то образом этот список полу-
чить. В принципе, возможность получить список допустимых ходов и взя-
тий черезвычайно полезна для реализации как компьютерных игроков,
так и интерфейса с игроком-человеком.
Таким образом, можно сформулировать следующую подзадачу: необ-
ходимо реализовать функции, возвращающие список доступных ходов
и взятий, а потом на их основе построить реализацию компьютер-
ного игрока. Естественно, что поведение этих функций (назовем их
availableMoves и availableAttacks соответственно) должно зависеть
от текущего состояния доски и того, какая сторона делает ход.

© 2009 «Практика функционального программирования» 84

4.4. Компьютерный игрок с примитивной стратегией

module Main where

main = do
( newBoard , playerA , playerB ) ← getConfig
play newBoard playerA playerB

play newBoard playerA playerB = do

let board = newBoard
displayBoard board
makeMove board White
where
makeMove board side = do
let player = getPlayer side
afterMove ← if canAttack board side
then attackLoop player board side
else player Move board side
let nextBoard = upgradeToKings afterMove side
displayBoard nextBoard
if isVictory side nextBoard
then return ( ”Winner is ” ++ show side )
else makeMove nextBoard ( otherSide side )

attackLoop player board side = do

board ’ ← player Attack board side
if canAttack board ’ side
then attackLoop player board ’ side
else return board ’

getPlayer White = playerA

getPlayer Black = playerB

isVictory = undefined
canAttack = undefined

data Side = White ∣ Black deriving Show

otherSide White = Black
otherSide Black = White

data MoveType = Move ∣ Attack

© 2009 «Практика функционального программирования» 85
4.4. Компьютерный игрок с примитивной стратегией

Код, реализующий выбор хода компьютерным игроком, может быть

записан с использованием функции availableMoves так :
randomComputer Move board side =
case availableMoves board side of
[] → return board
variants → do v ← getRandom variants
return $ move board side v
Тут функция move — это (еще не реализованная) функция из API рабо-
ты с доской, выполняющая манипуляции по перемещению фигуры в ре-
зультате хода.
По аналогии, функция выбора атакующего кода будет записана так:
randomComputer Attack board side = do
v ← getRandom ( availableAttacks board side )
return $ attack board side v
Компьютерный игрок будет выполнять выбор атакующего кода толь-
ко в том случае, если функция play проверила потенциальную возмож-
ность выполнения взятия этим игроком. Соответственно, нет необходи-
мости проверять, вернула ли функция availableAttacks хотя бы один
вариант хода — его наличие гарантируется. С другой стороны, функция
availableMoves вполне может возвратить пустое множество доступных
ходов — в этом случае компьютерный игрок пропускает ход (возвращает
состояние доски без изменений).
Несмотря на довольно большой список нереализованных функ-
ций (isVictory, getConfig, displayBoard, canAttack, upgradeToKings,
availableMoves, availableAttacks, move, attack, getRandom), написан-
ный код компилируется — то есть он синтаксически корректен.
Читатели, самостоятельно пишущие код в процессе чтения статьи, мо-
гут сравнить свой вариант с файлом «checkers03.hs», расположенным в ар-
хиве с примерами кода.
¹¹Haskell: функция $ может использоваться для уменьшения количества круг-
лых скобок в коде. (print (process (parse (read x)))) — то же самое, что и
(print $ process $ parse $ read x).

© 2009 «Практика функционального программирования» 86

4.5. Сбор информации о доступных ходах со взятием

4.5. Сбор информации о доступных ходах со

взятием
Чтобы выяснить, какие еще функции должны входить в API работы с
состоянием доски, приступим к реализации функции availableAttacks,
которой потребуется всесторонне анализировать информацию о расста-
новке фигур обоих игроков.
Как известно, шашки могут «бить» вражеские фигуры, перепрыгивая
через них на следующую по диагонали клетку, если она свободна. При
этом шашка может двигаться только вперед. Соответственно, перебрав
все шашки игрока и проверив для каждой из них возможность атаковать
по обоим диагональным направлениям, можно собрать информацию о
всех доступных игроку атакующих ходах.
Диагонали, проходящие через клетку, на которой находится шашка,
можно задать, изменяя номер ряда и столбца клетки одновременно на
единицу (с нужным знаком). В принципе, уже можно приступать к напи-
санию кода availableAttacks :
availableAttacks board side =
concatMap ( checkDiagonals board side ) ( pieces side board
where
checkDiagonals board side ( piece , coords ) =
if isChecker piece
then checkerAttack coords forward left
++ checkerAttack coords forward right
else kingAttack coords forward left
++ kingAttack coords forward right
++ kingAttack coords ( − forward ) left

¹²Haskell: Из определения функции checkDiagonals следует, что она принимает три

аргумента. В то же время, в строке concatMap (checkDiagonals board side) эта функ-
ция применена к двум аргументам. Результатом такого частичного применения (partial
application, см. [8]) является функция одного аргумента, принимающая на вход пару
(piece,coords). Именно такая функция требуется для обработки списка фигур с помо-
щью функции concatMap.
В определении функций checkerAttack и kingAttack использованы охранные выра-
жения (guards, см. [2]), позволяющие выбирать тот или иной вариант поведения в зави-
симости от истинности указанных условий.

© 2009 «Практика функционального программирования» 87

4.5. Сбор информации о доступных ходах со взятием

++ kingAttack coords ( − forward ) right

( forward , left , right ) =

if side == White then ( − 1, − 1, 1) else (1 ,1 , − 1)

checkerAttack coords deltaRow deltaColumn

∣ hasTargetAndEmptySquareBehind squares =
undefined
∣ otherwise = []
where
squares = diagonal board coords deltaRow deltaColu

kingAttack coords deltaRow deltaColumn

∣ emptyS qr sThen Ta rg et An d Em ptySqrBehind squares =
undefined
∣ otherwise
= []
where
squares = diagonal board coords deltaRow deltaColu

isChecker = undefined
diagonal = undefined
hasTargetAndEmptySquareBehind = undefined
empty Sq rsThe nTar ge tAndE mp ty Sq r Be hind = undefined
Предполагается, что функция diagonal возвращает список координат
клеток, лежащих по диагонали от клетки с координатами coords в направ-
лении, указанном при помощи (deltaRow, deltaColumn).
Функция availableAttacks, даже не будучи реализованной в пол-
ном объеме, получается достаточно громоздкой. Кроме того, если за-
думаться о реализации функции availableMoves, то станет понят-
но, что ее код будет практически полностью повторять код функ-
ции availableAttacks. Отличие будет заключаться в том, что вместо
hasTargetAndEmptySquareBehind будет использована другая функция,
проверяющая наличие перед шашкой пустой клетки, на которую можно
будет сделать ход.
Аналогичное изменение будет сделано для обработки «дамок», но

© 2009 «Практика функционального программирования» 88

4.6. Сбор информации о доступных ходах: вторая попытка

весь остальной код, осуществляющий последовательный перебор фигур,

объединение результатов работы checkDiagonals, генерацию списков
клеток, лежащих на диагонали и т. п., останется без изменений.
Разумно вынести общий алгоритм работы availableMoves и
availableAttacks в отдельную функцию collectOpportunities.
Эта функция будет заниматься сбором информации о «возможностях»,
доступных игроку в текущем игровом состоянии, где под «возможно-
стями» понимаются ходы со взятием или без него. В качестве аргумента
ей будет передаваться функция, проверяющая, подходит ли данное
диагональное направление для того, чтобы осуществить данной фи-
гурой ход нужного типа (со взятием или без). Кроме того, аргументом
collectOpportunities должна быть еще одна функция, которая сфор-
мирует данные о «возможности» (возможном ходе) и вернет их в качестве
результата работы checkerAttack или kingAttack.

4.6. Сбор информации о доступных ходах: вто-

рая попытка
В процессе написания функции collectOpportunities можно сде-
лать еще несколько упрощений имеющегося кода.
Поскольку, согласно оговоренным правилам, шашки ходят и бьют
только вперед-влево и вперед-вправо, а «дамки» — еще и назад-влево
и назад-вправо, можно создать функцию validDirections, которая бу-
дет возвращать список допустимых направления движения для указан-
ной фигуры.
Кроме того, можно объединить функции checkerAttack и
kingAttack в одну, вынеся функциональность, реализующую раз-
ное поведение фигуры в зависимости от ее типа за пределы
collectOpportunities.
Теперь сама функция collectOpportunities может быть записана
следующим образом:
collectOpportunities board side canAct describeAction =
concatMap checkDiagonals ( pieces side board )
where

© 2009 «Практика функционального программирования» 89

4.6. Сбор информации о доступных ходах: вторая попытка

checkDiagonals ( coords , piece ) =

concatMap ( checkDirection coords piece ) ( validDirect

checkDirection coords piece direction

∣ canAct piece squares =
describeAction piece coords squares
∣ otherwise = []
where squares = diagonal coords direction

validDirections = undefined
diagonal = undefined

pieces = undefined
Тут функция checkDirection выполняет проверку хода фигуры piece
в направлении direction. Если набор клеток на нужной диагонали бу-
дет признан подходящим функцией canAct, то будет вызвана функция
describeAction для генерации информации о возможном ходе фигуры
в этом направлении.
Функция checkDiagonals выполняет обработку всех возможных на-
правлений движения одной фигуры, а функция collectOpportunities
просто применяет checkDiagonals ко всем фигурам конкретного игро-
ка. Реализация функции pieces, возвращающей список фигур, отложена
на будущее.
Непосредственная работа с направлениями будет реализована в
функциях validDirections и diagonal, которые, скорее всего, бу-
дут содержать код, похожий на использованный в первом варианте
availableAttacks. Но так как функция collectOpportunities получи-
лась более высокоуровневой, можно сейчас не углубляться в детали их
реализации.
Теперь можно свести функции availableAttacks и availableMoves
к вызову collectOpportunities с правильными аргументами:
availableAttacks board side =
collectOpportunities board side canTake genAttackInfo
where
canTake = undefined

© 2009 «Практика функционального программирования» 90

4.7. Передвижение фигур

genAttackInfo = undefined

availableMoves board side =

collectOpportunities board side canMove genMoveInfo
where
canMove = undefined
genMoveInfo = undefined
Получившийся код находится в файле «checkers04.hs» в архиве с при-
мерами кода. На рисунке 4.2 можно видеть иерархию функций, описанных
в этом файле, пунктиром обозначены еще не реализованные функции.

4.7. Передвижение фигур

К настоящему моменту в коде насчитывается пятнадцать функций-
«заглушек», определенных как undefined. Несмотря на это, компилятор
уже может делать определенные выводы о том, какие значения будут при-
нимать и возвращать описанные функции. Если загрузить код в интерпре-
татор Haskell и поинтересоваться, какой тип был автоматически опреде-
лен для функции availableAttacks, можно получить вполне конкретный
ответ:

*Main> :load checkers04.hs

[1 of 1] Compiling Main ( checkers04.hs, interpreted )
Ok, modules loaded: Main.

*Main> :type availableAttacks

availableAttacks :: t -> t1 -> [alpha]

Хотя компилятор еще не знает, какие конкретно типы данных будут

использованы для описания игровой доски и допустимых ходов, он уже
может сделать вывод о том, что функция availableAttacks будет возвра-
щать список значений.
Список будет пуст, если допустимых ходов со взятием нет. Зная это,
можно реализовать одну из функций-«заглушек»:
canAttack board side = not $ null $ availableAttacks board

© 2009 «Практика функционального программирования» 91

4.7. Передвижение фигур

main

getConfig play

play where-block

makeMove

attackLoop getPlayer displayBoard

canAttack isVictory otherSide

randomComputer Attack ... randomComputer Move ... upgradeToKings

availableAttacks getRandom availableMoves

attack collect move

collect where-block

pieces checkDiagonals

checkDirection validDirections

diagonal

canTake canMove genAttackInfo genMoveInfo

Рис. 4.2. Дерево вызовов функций в файле checkers04.hs

© 2009 «Практика функционального программирования» 92
4.7. Передвижение фигур

Теперь самое время углубится в детали, которые помогут связать

друг с другом разные части кода. По дизайну, компьютерный игрок
randomComputer будет выбирать один из элементов списка, возвращае-
мого функциями availableAttacks или availableMoves, и без измене-
ний передавать его в функции attack или move.
Какого же типа должны быть эти значения, и какие данные они долж-
ны содержать? Чтобы функция move могла обновить информацию о состо-
янии доски, ей потребуются сведения о том:

1) что за фигура (шашка или «дамка») ходит;

2) с какой клетки;

3) на какую клетку.

Для функции attack перечень будет таким же, плюс дополнительно

потребуются сведения о том, на какой клетке находится «битая» фигура.
Теперь можно описать соответствующий тип данных и уточнить реализа-
цию функций attack и move :
data MoveInfo = MoveInfo { piece :: Piece
, from :: Coords
, to :: Coords
}
∣ AttackInfo { piece :: Piece
, from :: Coords
, victim :: Coords
, to :: Coords
}
Детали реализации типов Piece и Coords пока обсуждать рано, можно
временно описать их как «типы без данных» (аналог трюка с undefined
для описания типов данных):
¹³Haskell: описание типа MoveInfo выполнено с использованием record syntax, что-
бы компилятор автоматически генерировал функции piece :: MoveInfo → Coords,
from :: MoveInfo → Coords и т. п. для доступа к компонентам данных.
Имя типа данных MoveInfo совпадает с именем одного из его конструкторов. Это до-
вольно распространенная практика. При употреблении MoveInfo компилятор (и про-
граммист) из контекста в любой момент может легко понять, что именно имеется в виду.

© 2009 «Практика функционального программирования» 93

4.8. Доска, фигуры, координаты

data Piece = Piece

data Coords = Coords
Модификация доски при ходе фигуры piece с клетки from на клетку
to заключается в том, чтобы убрать фигуру указанного цвета со старых
координат и разместить ее на новых:
move board side ( MoveInfo piece from to ) =
replace ( from , piece ) ( to , piece ) side board

replace = undefined
При ходе со взятием фигура piece выполняет передвижение с клет-
ки from на клетку to, перепрыгивая через «жертву», стоящую на клетке
victim. По окончании хода «жертва» убирается с доски:
attack board side ( AttackInfo piece from victim to ) =
remove victim ( otherSide side ) $ replace ( from , piece ) (

remove = undefined
Получившийся код находится в файле «checkers05.hs» в архиве с при-
мерами кода.

4.8. Доска, фигуры, координаты

Функции replace и remove будут работать со списком фигур, хра-
нящимся в описании игрового поля. Функция pieces для получения те-
кущего значения этого списка уже упоминалась при описании функции
collectOpportunities (см. 4.6). Если предположить, что для обновления
информации о списке фигур имеется парная функция setPieces, то мож-
но реализовать функции replace и remove с помощью стандартных опе-
раций работы со списками:
replace ( from , piece ) ( to , piece ’) side board =
let pcs = pieces side board
pcs ’ = ( to , piece ’):( filter ( ≠ ( from , piece )) pcs )
in setPieces side board pcs ’

© 2009 «Практика функционального программирования» 94

4.8. Доска, фигуры, координаты

remove coords side board =

let pcs = pieces side board
pcs ’ = filter (( ≠ coords ). getCoords ) pcs
in setPieces side board pcs ’
В принципе, для описания типа данных, хранящего информацию о со-
стоянии доски, уже все готово. Информация о фигурах может храниться
либо в виде списка троек (координата, фигура, цвет), либо в виде двух от-
дельных списков пар (координаты, фигура): в одном списке будет инфор-
мация о черных фигурах, во втором — о белых. Вариант с двумя списками
лучше соответствует уже написанному коду — до сих пор везде происхо-
дила обработка фигур одного конкретного цвета, и все написанные функ-
ции рассчитывают, что функция pieces будет возвращать именно список
пар (координаты, фигура). А при использовании одного списка для хра-
нения всех фигур функции pieces придется при каждом вызове отфиль-
тровывать из него информацию о фигурах ненужного цвета.
Осталось решить вопрос с тем, как хранить информацию о коорди-
натах клеток доски. Самый простой способ — пронумеровать строки и
столбцы доски, и хранить координаты в виде пар (строка, столбец):
type Coords = ( Int , Int )
Тип данных, описывающий фигуру — это простое перечисление (на-
бор констант) из двух значений: «шашка» и «дамка»:
data Piece = Checker ∣ King
Теперь описание доски будет выглядеть так :
data Board = Board { height :: Int
, width :: Int
, whites :: [( Coords , Piece )]
, blacks :: [( Coords , Piece )]
}
Для удобства работы с компонентами типа Board можно определить
вспомогательные функции pieces, setPieces и getCoords:
¹⁴Автору неизвестны варианты игры в шашки на прямоугольных досках, но тем не ме-
нее возможность создания прямоугольной доски была оставлена.

© 2009 «Практика функционального программирования» 95

4.9. Выход в «дамки» и отображение состояния доски

pieces White = whites

pieces Black = blacks
setPieces White board ws = board { whites = ws }
setPieces Black board bs = board { blacks = bs }

getCoords ( coords , p ) = coords

Получившийся код находится в файле «checkers06.hs» в архиве с при-
мерами кода.

4.9. Выход в «дамки» и отображение состояния

доски
Теперь можно реализовать часть функций-«заглушек», которым требу-
ется доступ к деталям реализации состояния о доске. Например, превра-
щение шашек в «дамки» по окончании хода. Необходимо проверить, нет
ли на доске шашек, стоящих на самом дальнем от игрока ряду. Для белых
это ряд номер один, для черных — ряд с номером, равным высоте дос-
ки. Если такие шашки найдены — они меняются на «дамки» при помощи
функции replace :
upgradeToKings board side = newBoard
where
kingRow White = 1
kingRow Black = height board
newBoard =
in case filter ( upgradeableChecker ( kingRow side
( coords , Checker ): _ →
replace ( coords , Checker ) ( coords , King ) side
_ →
board

¹⁵Haskell: В выражении case использован шаблон _, сопоставляемый с произволь-

ным выражением; таким образом реализуется семантика «для всех прочих выраже-
ний — результат такой-то». Подобный прием можно видеть и в определении функции
upgradeableChecker.

© 2009 «Практика функционального программирования» 96

4.9. Выход в «дамки» и отображение состояния доски

upgradeableChecker targetRow (( row , col ) , Checker ) =

row == targetRow
upgradeableChecker _ _ = False
Еще одна функция, реализация которой требует информации о ши-
рине и высоте доски — это displayBoard. Доска будет отображаться
алфавитно-цифровыми символами, в стиле фильмов о компьютерах кон-
ца прошлого века. Чтобы таким образом отобразить всю доску, надо отоб-
разить каждый её ряд на отдельной строке. Чтобы отобразить ряд клеток
доски, надо разобраться, занята ли клетка фигурой, и вывести либо обо-
значение фигуры, либо какой-то символ, обозначающий цвет этой клет-
ки :
displayBoard board = putStrLn ( boardToString board )
where
boardToString board = unlines rows
rows = [ row r ∣ r ← [1.. height board ] ]
row r = [ square r c ∣ c ← [1.. width board ] ]
square r c = case lookup (r , c ) allPieces of
Just ( Checker , White ) → ’w ’
Just ( King , White ) → ’W ’
Just ( Checker , Black ) → ’b ’
Just ( King , Black ) → ’B ’
Nothing → if isBlackSquare r c
then ’. ’
else ’ ’
allPieces =
[ ( coords ,( piece , side )) ∣ side ←
[ Black , White ]
, ( coords , piece ) ←
pieces side board ]

isBlackSquare r c = odd ( r + c )

¹⁶Haskell: В определениях rows, row и allPieces используется «синтаксический сахар»

для определения списков, позволяющий обойтись без циклов for (см. [5], раздел «list
comprehensions»).

© 2009 «Практика функционального программирования» 97

4.10. Создание доски

Получившийся код находится в файле «checkers08.hs» в архиве с при-

мерами кода. Загрузив его в интерпретатор Haskell, можно убедиться, что
функция displayBoard может отобразить доску без расставленных фи-
гур:

Prelude> :l ./checkers08.hs
[1 of 1] Compiling Main ( checkers08.hs, interpreted )
Ok, modules loaded: Main.
*Main> displayBoard (Board 8 8 [] [])
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .

*Main>

4.10. Создание доски

Прежде чем будет возможно проверить работу displayBoard для
доски с расставленными фигурами, необходимо реализовать функцию со-
здания описания доски с расставленными фигурами. Точнее, потребуется
несколько функций, ведь по требованиям программа должна реализовы-
вать игру как в русские, так и в международные шашки.
Варианты игры в шашки отличаются как размером доски, так и коли-
чеством шашек у каждого игрока. Доска для классических (русских) ша-
шек — размером 8×8, у каждого игрока по 12 фигур:
checkers8x8 = newBoard 8 8 12
Доска для международных шашек — 10×10, у каждого игрока по 20
фигур:
checkers10x10 = newBoard 10 10 20

© 2009 «Практика функционального программирования» 98

4.10. Создание доски

Фигуры расставляются на черных клетках доски. Если иметь упорядо-

ченный в порядке возрастания рядов список координат черных клеток, то
можно сказать, что черные фигуры занимают 12 (или 20) первых клеток из
этого списка, а белые — такое же количество последних :
newBoard h w numPieces = Board h w whitePieces blackPieces
where
coords = [ ( row , column ) ∣ row ←
[1.. h ] , column ← [1.. w ]
, isBlackSquare row column ]
blackPieces = zip ( take numPieces coords )
( repeat Checker )
whitePieces = zip ( take numPieces ( reverse coords )) (
Для упрощения реализации конфигурация программы будет описы-
ваться прямо в коде. Читатель может реализовать ввод конфигурации с
клавиатуры или из внешнего файла в качестве самостоятельного упраж-
нения:
getConfig = return ( checkers8x8 , randomComputer , randomCom
Получившийся код (с некоторыми сокращениями) приведен на рисун-
ке 4.3. Полный текст находится в файле «checkers09.hs» в архиве с приме-
рами кода.
Теперь можно убедиться, что функция displayBoard корректно рабо-
тает для доски с расставленными фигурами:

[1 of 1] Compiling Main ( checkers09.hs, interpreted )

Ok, modules loaded: Main.
*Main> displayBoard ( checkers8x8 )
b b b b
b b b b
b b b b
. . . .

¹⁷Haskell: определение coords использует «конструктор списка» (list comprehension,

см. [5]) с предикатом, при этом в результат попадают только пары (row,column), удо-
влетворяющие условию isBlackSquare.
Хотя функция repeat и генерирует бесконечный список значений, результат работы
zip будет ограничен длиной более короткого аргумента, и будет иметь длину numPieces.

© 2009 «Практика функционального программирования» 99

4.11. Диагонали

. . . .
w w w w
w w w w
w w w w

*Main>

4.11. Диагонали
Судя по всему, дизайн решения можно считать завершенным. Для того
чтобы программа заработала, необходимо всего лишь заменить оставши-
еся undefined подходящими функциями.
Так, чтобы завершить описание функции collectOpportunities,
определим функции validDirections и diagonal.
Как уже говорилось ранее (см. 4.5), функция diagonal должна воз-
вращать список клеток, лежащих по диагонали от данной в указанном
направлении. Направление можно задавать, указывая, как именно из-
меняются номера строк и столбцов клеток, лежащих на диагонали —
они либо уменьшаются, либо увеличиваются на единицу для каждой сле-
дующей клетки. Другими словами, диагональ, начинающаяся в клетке
с координатами (row,column) и идущая в направлении (dr, dc) —
это последовательность клеток с координатами (row+dr,column+dc),
(row+dr+dr,column+dc+dc), и так далее, не выходящая за пределы дос-
ки :
diagonal ( row , column ) ( dr , dc ) =
[ (r , c ) ∣ (r , c ) ← zip rows columns
, inside board r c ]
where

¹⁸Haskell: определения rows и columns используют «синтаксический сахар» (..) для

генерации координат диагонали. Получившиеся списки — бесконечные. Чтобы гаран-
тировать завершение функции diagonal, списки ограничиваются при помощи функции
take.
В генераторах списков (list comprehensions, см. [5]) возможно использование не только
явно заданных списков, но и результатов применения функций. Например, пары коор-
динат в определении diagonal берутся из результата работы функции zip.

© 2009 «Практика функционального программирования» 100

4.11. Диагонали

module Main where ∣ AttackInfo { piece :: Piece , from :: Coords ,

main = do replace ( from , piece ) ( to , piece ’) side board =

( newBoard , playerA , playerB ) ← getConfig let pcs = pieces side board
play newBoard playerA playerB pcs ’ = ( to , piece ’):( filter ( ≠( from , piece )) pcs )
in setPieces side board pcs ’
play newBoard playerA playerB = ...
remove coords side board =
data Side = White ∣ Black let pcs = pieces side board
otherSide White = Black pcs ’ = filter (( ≠ coords ). getCoords ) pcs
otherSide Black = White in setPieces side board pcs ’

data MoveType = Move ∣ Attack data Piece = Checker ∣ King deriving Eq

randomComputer Move board side = ... type Coords = ( Int , Int )

data Board = Board { height :: Int
randomComputer Attack board side = ... , width :: Int
, whites :: [( Coords , Piece )]
availableAttacks board side = , blacks :: [( Coords , Piece )]
collectOpportunities board side canTake genAttackInfo }
where
canTake = undefined pieces White = whites
genAttackInfo = undefined pieces Black = blacks
setPieces White board ws = board { whites = ws }
availableMoves board side = setPieces Black board bs = board { blacks = bs }
collectOpportunities board side canMove genMoveInfo
where getCoords ( coords , p ) = coords
canMove = undefined
genMoveInfo = undefined upgradeToKings board side = ...

collectOpportunities board side canAct describeActiondisplayBoard

= board = ....
concatMap checkDiagonals ( pieces side board )
where isBlackSquare r c = odd ( r + c )
checkDiagonals ( coords , piece ) =
concatMap ( checkDirection coords piece ) ( validDirections
getConfig = piece
return
) ( checkers8x8 , randomComputer , randomCom

checkDirection coords piece direction checkers8x8 = newBoard 8 8 12

∣ canAct piece squares = describeAction piece coords squares
∣ otherwise = [] checkers10x10 = newBoard 10 10 20
where squares = diagonal coords direction
newBoard h w numPieces = Board h w whitePieces blackPieces
validDirections = undefined where
diagonal = undefined coords = [ ( row , column ) ∣ row ← [1.. h ] , column ←
[1.. w ]
move board side ( MoveInfo piece from to ) = , isBlackSquare row column ]
replace ( from , piece ) ( to , piece ) side board blackPieces = zip ( take numPieces coords )
( repeat Checker )
attack board side ( AttackInfo piece from victim to ) = whitePieces = zip ( take numPieces ( reverse coords )) (
remove victim ( otherSide side ) $ replace ( from , piece ) ( to , piece ) side board
getRandom = undefined
data MoveInfo = MoveInfo { piece :: Piece , from :: Coords , to :: Coords }

Рис. 4.3. Листинг checkers09.hs

© 2009 «Практика функционального программирования» 101

4.12. Реализация availableAttacks и availableMoves

rows = take ( height board ) [ row + dr , row + dr + dr ..]

columns = take ( width board ) [ column + dc , column + dc + dc .
inside board r c =
r ≥ 1 && c ≥ 1
&& r ≤ height board && c ≤ width board
Диагональные направления, которые будут обрабатываться при по-
мощи функции diagonal, генерируются функцией validDirections. Те-
перь уже видно, что функция validDirections должна просто возвра-
щать список вида [(−1,1),(−1,−1),...], в зависимости от того, о какой
фигуре идет речь, и какая сторона (черные или белые) делает ход.
Допустимые направления движения и взятия для шашки — вперед-
влево или вперед-вправо:
validDirections Checker = [ ( forward , left ) , ( forward , right
Для «дамки» добавляются еще и аналогичные движения назад-влево
и назад-вправо:
validDirections King = [ ( forward , left ) , ( forward , right )
, ( backward , left ) , ( backward , righ
Конкретные значения forward, backward, left и right изменяются в
зависимости от того, с какой стороны доски смотреть на игровую ситуа-
цию:
( forward , backward , left , right ) =
if side == White
then ( − 1, 1 , − 1, 1)
else ( 1, − 1, 1 , − 1)
Получившийся код находится в файле «checkers10.hs» в архиве с при-
мерами кода.

4.12. Реализация availableAttacks и

availableMoves
Было бы неплохо проверить работоспособность функции
collectOpportunities в интерпретаторе Haskell так же, как это де-
лалось для функции displayBoard. Однако в своем нынешнем виде

© 2009 «Практика функционального программирования» 102

4.12. Реализация availableAttacks и availableMoves

функция collectOpportunities неработоспособна — для генерации

результата она вызывает функции, передаваемые из availableAttacks
и availableMoves в качестве аргументов canAct и describeAction.
Необходимо завершить реализацию функций availableAttacks и
availableMoves, чтобы в collectOpportunities передавались не
«заглушки» undefined, а нечто более осмысленное.
Начать можно с функций, передаваемых в качестве параметра
canAct — это функции canMove и canTake. Правила ходов (со взятием и
без) описываются в терминах свободных и занятых клеток доски. Пред-
положив, что для проверки занятости конкретной клетки реализованы
функции empty и hasPiece, можно приступать к написанию кода.
Шашка может сделать ход только в том случае, если непосредственно
перед ней есть пустая клетка:
canMove Checker ( inFront : _ ) = empty board inFront
«Дамка» может сделать ход, если по диагонали с ней соседствуют одна
или более пустых клеток:
canMove King diagonal = not $ null $ squaresToObstacle di

squaresToObstacle diagonal = takeWhile ( empty board ) diago

Во всех прочих случаях ход фигуры невозможен :
canMove _ _ = False
Правила выполнения ходов со взятием описываются так же просто.
Шашка может выполнить взятие, если перед ней стоит фигура противни-
ка, а за этой фигурой находится пустая клетка:
canTake Checker ( inFront : behindIt : _ ) =
hasPiece board ( otherSide side ) inFront && empty board
«Дамка» может выполнить взятие, если перед ней 0..n пустых клеток,
за которыми находится вражеская фигура, а за ней — пустая клетка. Фак-
тически, если пропустить первые пустые клетки, можно повторно исполь-
зовать правило для шашек:
¹⁹Haskell: в объявлении функции canMove использовано сопоставление с образцом _,
который совпадает с любым значением аргумента. Таким образом реализуется поведе-
ние «во всех прочих случаях — делать так-то».

© 2009 «Практика функционального программирования» 103

4.12. Реализация availableAttacks и availableMoves

canTake King diagonal = canTake Checker nearestPiece

where nearestPiece = dropWhile ( empty board ) diagonal
Во всех прочих случаях ход со взятием невозможен:
canTake _ _ = False
После того, как возможность совершить ход (со взятием или без) под-
тверждена, необходимо составить описание этого хода в виде данных
типа MoveInfo. Для этого в свое время были предусмотрены функции
genMoveInfo и genAttackInfo.
Шашка может пойти только на ближайшее пустое поле вдоль диагона-
ли :
genMoveInfo Checker coords diagonal =
[ MoveInfo { piece = Checker , from = coords , to = ( head diagon
«Дамка» может пойти на любое свободное поле диагонали, вплоть до
ближайшего препятствия. Таким образом, для «дамки» необходимо гене-
рировать список элементов MoveInfo, по одному на каждый возможный
ход:
genMoveInfo King coords diagonal =
map moveTo $ squaresToObstacle
diagonal
where moveTo square = MoveInfo { piece = King , from = coords
Похожим образом записывается и функция genAttackInfo. Шашка
выполняет взятие, перепрыгивая через ближайшую по диагонали клетку
на следующую за ней:
genAttackInfo Checker coords diagonal =
[ AttackInfo { piece = Checker , from = coords ,
victim = ( diagonal !!0) ,
to = ( diagonal !!1) } ]
«Дамка» выполняет взятие, перепрыгивая через ближайшую по диа-
гонали фигуру на любую следующую за ней пустую клетку :
²⁰Haskell: использование структур с именованными полями (record syntax, см. [6]) по-
вышает читаемость кода.
²¹Haskell: в where-блоке используется сопоставление с образцом, чтобы сразу раз-

© 2009 «Практика функционального программирования» 104

4.13. Финальные штрихи

genAttackInfo King coords diagonal =

map leapOverNearestPiece landingPlaces
where
leapOverNearestPiece square =
AttackInfo { piece = King ,
from = coords ,
victim = nearestPiece , to = square }
( nearestPiece : behindNearestPiece ) =
dropWhile ( empty board ) diagonal
landingPlaces = takeWhile ( empty board ) behindNearestP
Получившийся код находится в файле «checkers11.hs» в архиве с при-
мерами кода. Чтобы функции availableAttacks и availableMoves зара-
ботали, необходимо дать определение функций empty и hasPiece, но уже
сейчас можно проверить, что компилятор правильно вывел типы:

Prelude> :load checkers11.hs

[1 of 1] Compiling Main ( checkers11.hs, interpreted )
Ok, modules loaded: Main.

*Main> :type availableMoves

availableMoves :: Board -> Side -> [MoveInfo]

*Main> :type availableAttacks

availableAttacks :: Board -> Side -> [MoveInfo]

4.13. Финальные штрихи

Чтобы завершить написание программы игры в шашки, осталось
определить четыре функции: hasPiece, empty, isVictory и getRandom.
Проверка наличия фигуры указанного цвета в точке с указанными ко-
ординатами реализуется просто. Если в списке фигур игрока есть запись
с такими координатами, значит есть и фигура:
hasPiece board side coords =

бить результат работы dropWhile на первый элемент списка nearestPiece и «хвост»

behindNearestPiece.

© 2009 «Практика функционального программирования» 105

4.13. Финальные штрихи

case lookup coords ( pieces side board ) of

Nothing → False
_ → True
Клетка доски считается пустой, если она не занята фигурой ни одного
из игроков:
empty board coords =
not ( hasPiece board White coords ∣ ∣
hasPiece board Black coords )
Игрок считается победителем, если на доске не осталось фигур про-
тивника:
isVictory side board = null $ pieces ( otherSide side ) b
И, наконец, «интеллект» компьютерного игрока — функция, выбираю-
щая случайный элемент из списка:
import System . Random

getRandom lst = do
idx ← randomRIO (0 , length lst − 1)
return ( lst !! idx )
Получившийся код находится в файле «checkers11.hs» в архиве с при-
мерами кода.
Теперь можно проверить правильность работы функций
availableAttacks и availableMoves. Из начального положения
доски для игры в русски шашки игроку доступно семь обычных ходов и
ни одного хода со взятием:

Prelude> :l checkers12.hs
[1 of 1] Compiling Main ( checkers12.hs, interpreted )
Ok, modules loaded: Main.

*Main> length (availableMoves checkers8x8 White)

7

*Main> availableAttacks checkers8x8 White

[]

© 2009 «Практика функционального программирования» 106

4.13. Финальные штрихи

Запустив программу при помощи команды «runhaskell checkers12.hs»,

можно увидеть сражение двух компьютерных игроков друг с другом.
На рисунке 4.4 можно увидеть, как взаимодействуют друг с другом все
высокоуровневые функции финальной программы. Функции, определен-
ные локально (в let- и where-блоках) не включены в диаграмму, чтобы по-
высить ее читаемость.

main

play getConfig

randomComputer checkers8x8

getRandom displayBoard newBoard

availableMoves availableAttacks isBlackSquare

upgradeToKings move attack empty

replace remove otherSide hasPiece

getCoords setPieces collect

pieces

Рис. 4.4. Дерево вызовов функций программы checkers12.hs

© 2009 «Практика функционального программирования» 107

4.14. Разбиение программного кода на модули

4.14. Разбиение программного кода на модули

Изучив схему взаимодействия функций получившегося кода, можно
прийти к выводу, что читаемость программы и удобство ее развития мо-
гут быть существенно улучшены путем разбиения кода на независимые
модули.
Например, можно отделить описания всех используемых структур
данных и разместить их в отдельном модуле Types. Можно выделить в
отдельный модуль Board все функции, работающие с состоянием дос-
ки, а в модуль Checkers — реализацию собственно игры в шашки. Если
дополнительно вычленить реализацию компьютерного игрока в модуль
RandomComputer, то окажется, что главный модуль программы состоит
буквально из нескольких строк:
module Main where

import Board ( checkers8x8 )

import Checkers ( play )
import RandomComputer ( randomComputer )

main = do
( newBoard , playerA , playerB ) ← getConfig
play newBoard playerA playerB

getConfig = return ( checkers8x8 , randomComputer , randomCom

Подобное разбиение на модули позволит скрыть часть деталей реали-
зации. Функции collectOpportunities, hasPiece, empty и им подобные
можно не экспортировать за пределы модулей, в которых они определя-
ются и используются. На рисунке 4.5 видно, как сильно упрощается в ре-
зультате схема взаимодействия разных частей программы.
Окончательный код программы находится в директории «checkers13»
в архиве с примерами кода. Взяв его за основу, читатель может попробо-
вать в качестве самостоятельного упражнения решить такие задачи:

• Модифицировать displayBoard так, чтобы рядом с изображением

доски указывались номера строк и столбцов.

© 2009 «Практика функционального программирования» 108

4.14. Разбиение программного кода на модули

Main.hs
main

RandomComputer.hs Checkers.hs
randomComputer play

Board.hs
availableAttacks availableMoves
attack move
displayBoard upgradeToKings
checkers8x8 checkers10x10

Types.hs
Side otherSide
MoveType MoveInfo
Piece Coords Board
pieces setPieces getCoords

Рис. 4.5. Зависимости между модулями и перечень экспортируемых функ-

ций программы checkers13

© 2009 «Практика функционального программирования» 109

4.15. Заключение

• Определить функцию, которая будет запрашивать с клавиатуры ко-

ординаты передвигаемой фигуры, валидировать их и делать ход;
затем использовать ее вместо randomComputer в вызове функции
play для игры человека против компьютера.

• Для варианта игры «человек против компьютера» реализовать

«undo» — возможность вернуть состояние на один или несколько
ходов назад.

• Написать более интеллектуального компьютерного игрока, кото-

рый предпочитает делать ходы, не подставляющие свои фигуры под
ответный удар.

4.15. Заключение
В начале статьи было сделано утверждение о том, что функциональ-
ные языки со статической типизацией хорошо подходят для прототипи-
рования программ и разработки методом «сверху вниз». Примеры, при-
веденные в статье, должны убедительно проиллюстрировать это.
В самом деле, легко видеть, что словесное описание функций всегда
было более объемным, чем соответствующая реализация на Haskell, да-
же в случае сложных функций вроде collectOpportunities. Использо-
вание функций высших порядков и возможность передавать функции в
качестве аргументов позволили радикально сократить количество вспо-
могательного кода и сосредоточиться на реализации нужной функцио-
нальности.
Статическая типизированность языка Haskell, требующая, чтобы типы
всех выражений были известны на этапе компиляции, не требовала от
программиста дополнительного приложения сил. Скорее наоборот: авто-
матический вывод типов позволил не тратить время на проработку и опи-
сание сигнатур функций, а использование функции undefined позволило
быстро получить пусть и не полностью реализованный, но уже компили-
руемый вариант кода и постепенно его развивать.

© 2009 «Практика функционального программирования» 110

Литература Литература

Литература
[1] Bottom. — Статья в Haskell Wiki, URL: http://www.haskell.org/
haskellwiki/Bottom (дата обращения: 20 июля 2009 г.).

[2] Control structures. — Статья в Wiki-книге Haskell, URL: http://en.

wikibooks.org/wiki/Haskell/Control_structures (дата
обращения: 20 июля 2009 г.).

[3] Introduction to io. — Статья в Haskell Wiki, URL: http://www.

haskell.org/haskellwiki/Introduction_to_IO (дата об-
ращения: 20 июля 2009 г.).

[4] Learn you a haskell for great good. — Учебник, URL: http://
learnyouahaskell.com/ (дата обращения: 20 июля 2009 г.).

[5] More about lists. — Статья в Wiki-книге Haskell, URL: http://en.

wikibooks.org/wiki/Haskell/More_about_lists (дата об-
ращения: 20 июля 2009 г.).

[6] More on datatypes. — Статья в Wiki-книге Haskell, URL: http:

//en.wikibooks.org/wiki/Haskell/More_on_datatypes
(дата обращения: 20 июля 2009 г.).

[7] O’Sullivan B., Stewart D., Goerzen J. Real World Haskell. — O’Reilly Media,
Inc., 2008. http://book.realworldhaskell.org/read/.

[8] Partial application. — Статья в Haskell Wiki, URL: http://www.

haskell.org/haskellwiki/Partial_application (дата об-
ращения: 20 июля 2009 г.).

[9] Petzold C. Does visual studio rot the mind? — Статья в

блоге, URL: http://www.charlespetzold.com/etc/
DoesVisualStudioRotTheMind.html (дата обращения: 20 июля
2009 г.).

[10] Yet another haskell tutorial. — Учебник, URL: http://darcs.

haskell.org/yaht/yaht.pdf (дата обращения: 20 июля 2009 г.).

© 2009 «Практика функционального программирования» 111

Литература Литература

[11] Душкин Р. В. Функциональное программирование на языке Haskell. —

М.: ДМК Пресс, 2007.

[12] Мягкое введение в haskell. — Учебник, URL: http://www.rsdn.

ru/article/haskell/haskell_part1.xml (дата обращения:
20 июля 2009 г.).

© 2009 «Практика функционального программирования» 112

Моноиды в Haskell и их использование
(Haskell Monoids and their Uses [2])

Dan Piponi
(Перевод Кирилла Заборского)

Аннотация

Haskell — замечательный язык для модульного конструи-

рования кода из небольших ортогональных друг другу бло-
ков. Одним из таких блоков является моноид. Несмотря на
то, что моноиды родом из математики (точнее, из алгебры),
они применяются повсюду в программировании. На каком бы
языке вы ни программировали, вы почти наверняка неявно
используете один или два моноида в каждой строке кода, са-
ми о том пока не подозревая. Используя их явно, мы находим
новые способы построения кода — в частности, способы, поз-
воляющие облегчить написание и улучшить читаемость кода.
Предлагаемая статья является введением в моноиды на
Haskell. Предполагается знакомство читателя с классами ти-
пов, так как моноиды в Haskell являются классом типов. Также
предполагается хотя бы поверхностное знакомство с монада-
ми.
5.1. Определение моноидов

5.1. Определение моноидов

Моноид в Haskell — это тип, для которого задано правило комбини-
рования двух элементов этого типа для получения нового элемента этого
же типа. Для задания моноида необходимо также определить нейтраль-
ный элемент, комбинирование с которым любого другого элемента даёт
результат, равный этому другому элементу.
Замечательным примером являются списки. Два списка — предполо-
жим [1,2] и [3,4] — могут быть объединены оператором ++ в единый
список [1,2,3,4]. Существует также пустой список [], при комбиниро-
вании с которым мы получаем второй список в неизменном виде — на-
пример, []++[1,2,3,4]==[1,2,3,4].
Другим примером является тип целых чисел Integer. Два элемента —
например, 3 и 4 — могут быть скомбинированы оператором +, давая в ре-
зультате сумму — 7. У нас также есть элемент 0, при сложении с которым
любое целое число остаётся неизменным.
Вот пример определения класса типов Monoid:
class Monoid m where
mappend :: m → m → m
mempty :: m
Функция mappend используется для комбинирования пар элементов,
а mempty представляет собой нейтральный элемент. Мы можем сделать
списки моноидами, включив их в этот класс:
instance Monoid [ ] where
mappend = ( ++ )
mempty = []
Поскольку мы хотим, чтобы mempty не модифицировал комбинируе-
мый с ним элемент, мы требуем, чтобы моноиды удовлеворяли следую-
щей паре правил:
a ‘ mappend ‘ mempty = a
и
mempty ‘ mappend ‘ a = a .

© 2009 «Практика функционального программирования» 114

5.2. Некоторые применения моноидов

Заметьте, что существует два способа скомбинировать a и b с

использованием mappend. Мы можем написать a ‘ mappend‘ b или
b ‘ mappend‘ a. От моноида не требуется совпадения результатов этих
двух операций (эта тема обсуждается далее в статье), в то же время, мо-
ноиды должны обладать еще одним свойством. Предположим, у нас име-
ется список [3,4]. Мы хотим объединить его со списком [1,2] слева и
со списком [5,6] справа. Мы можем выполнить объединение слева и по-
лучить [1,2]++[3,4], а затем сформировать ([1,2]++[3,4])++[5,6]. Мы
можем также начать справа и получить [1,2]++([3,4]++[5,6]). Посколь-
ку мы присоединяем списки с разных концов, эти операции не влияют
друг на друга, и не имеет значения, которая из них выполнится первой.
Это приводит нас к третьему и последнему требованию, которому долж-
ны удовлетворять моноиды:
( a ‘ mappend ‘ b ) ‘ mappend ‘ c ==
a ‘ mappend ‘ ( b ‘ mappend ‘ c )
Сформулируем это требование: «комбинирование слева и справа не
мешают друг другу». Обратите внимание, что целые числа, комбинируе-
мые операцией +, также удовлетворяют этому требованию. Это очень по-
лезное свойство называется «ассоциативность».
Таково полное определение моноида. Haskell не принуждает к соблю-
дению приведенных трёх правил, но читая код, в котором присутствует
моноид, мы всегда ожидаем, что эти правила соблюдены.

5.2. Некоторые применения моноидов

Почему нам может понадобиться использовать mappend, когда мы уже
имеем в наличии такие функции, как ++ и +?
Одна из причин заключается в том, что моноиды автомати-
чески предоставляют еще одну функцию — mconcat. Эта функ-
ция принимает на вход список значений в моноиде и комбини-
рует их вместе. Например, mconcat [a,b,c] будет эквивалентно
a ‘ mappend‘ (b ‘ mappend‘ c). Таким образом, в любом монои-
де существует легкий способ скомбинировать вместе целый список.
Стоит отметить, что в идее mconcat заключается некоторая двусмыс-

© 2009 «Практика функционального программирования» 115

5.2. Некоторые применения моноидов

ленность. Какой порядок должен быть выбран, чтобы вычислить

mconcat [a,b,...,c,d]? Должны ли мы выполнять операции сле-
ва направо, или начать с c ‘ mappend‘ d? Здесь вступает в силу правило
ассоциативности: порядок не имеет значения.
Моноиды также будут к месту, если вам необходимо, чтобы ваш код
был применим вне зависимости от способа комбинирования элементов.
Вы можете написать код, который подобно mconcat будет работать с лю-
бым моноидом.
Явное использование класса типов Monoid в сигнатуре функции по-
могает читающему код понять замысел автора. Если функция имеет сиг-
натуру типа [ ] → , мы знаем о ней только то, что она принима-
ет на вход список и создаёт из него объект типа . Внутри она может
делать со списком все, что угодно. Если же мы видим функцию типа
(Monoid ) ⇒ → , то даже если она применяется исключительно к
спискам, мы имеем примерное представление о том, что происходит со
списком внутри функции. Например, мы знаем, что функция может доба-
вить новые элементы к списку, но не удалить элемент из списка.
Один и от же тип данных может служить основой разных моноидов.
Например, как я уже упоминал, целые числа могут образовывать моноид,
который определяется так:
instance Monoid Integer where
mappend = ( + )
mempty = 0
В то же время, существует и другой естественный способ сделать мо-
ноид из целых чисел:
instance Monoid Integer where
mappend = (×)
mempty = 1
Мы не можем использовать оба эти определения одновременно. По-
этому библиотека Data.Monoid не создаёт моноид напрямую из Integer.
Вместо этого, она оборачивает его в Sum (сумму) и Product (произведе-
ние). К тому же, библиотека делает это в более общем виде, позволяя пре-
вратить любые типы из класса Num в один из двух видов моноидов:
Num ⇒ Monoid ( Sum )

© 2009 «Практика функционального программирования» 116

5.3. Монада Writer

и
Num ⇒ Monoid ( Product )
Чтобы воспользоваться описанными функциями моноида, необхо-
димо представить наши данные соответствующим образом. Напри-
мер, mconcat [Sum 2, Sum 3, Sum 4] — это Sum 9, в то время как
mconcat [Product 2, Product 3, Product 4] — это Product 24.
Использование Sum и Product кажется явным усложнением обычных
операций сложения и умножения. Зачем же так делать?

5.3. Монада Writer

Моноиды можно представлять как накопители. Имея промежуточную
сумму n и текущее значение a, мы можем получить новую промежуточ-
ную сумму n’ = n ‘ mappend‘ a. Накопление итогов часто применяется
в программировании, поэтому остановимся на этой идее подробнее. Мо-
нада Writer предназначена специально для этого. Мы можем написать
монадический код, который в качестве «побочного эффекта»будет накап-
ливать некоторые значения. Функция, выполняющая накопление, называ-
ется несколько странно — tell. Следующий пример демонстрирует реа-
лизацию трассировки совершаемых действий.
1 import Data . Monoid
2 import Data . Foldable
3 import Control . Monad . Writer
4 import Control . Monad . State
5

6 fact1 :: Integer → Writer String Integer

7 fact1 0 = return 1
8 fact1 n = do
9 let n ’ = n − 1
10 tell $ ”We’ve taken one away from ” ++ show n ++
”\n”
11 m ← fact1 n ’
12 tell $ ”We’ve called f ” ++ show m ++ ”\n”
13 let r = n × m

© 2009 «Практика функционального программирования» 117

5.3. Монада Writer

14 tell $ ”We’ve multiplied ” ++ show n

15 ++ ” and ” ++ show m ++ ”\n”
16 return r
В этом примере реализована функция вычисления факториала, сооб-
щающая нам о выполняемых вычислениях. Каждый раз, когда вызывается
функция tell, мы комбинируем её аргумент с промежуточным журналом
вычислений, который был накоплен в результате предыдущих вызовов
этой функции. Для извлечения журнала мы используем runWriter. Запу-
стив следующий код:
17 ex1 = runWriter ( fact1 10)
мы получаем значение 10!, а вместе с ним — список шагов, которые
потребовались для вычисления этого значения.
Writer позволяет накапливать не только строки. Мы можем использо-
вать эту монаду с любым моноидом. Например, мы можем использовать
её для подсчета количества операций сложения и умножения, необходи-
мых для вычисления факториала числа. Для этого мы должны передать в
tell значение соответствующего типа. В данном случае мы будем скла-
дывать значения, воспользовавшись моноидом для сложения — Sum. Мы
можем написать:
18 fact2 :: Integer → Writer ( Sum Integer ) Integer
19 fact2 0 = return 1
20 fact2 n = do
21 let n ’ = n − 1
22 tell $ Sum 1
23 m ← fact2 n ’
24 let r = n × m
25 tell $ Sum 1
26 return r
27

28 ex2 = runWriter ( fact2 10)

Эту задачу мы могли бы выполнить другим способом, примененив мо-
наду State:
29 fact3 :: Integer → State Integer Integer
30 fact3 0 = return 1

© 2009 «Практика функционального программирования» 118

5.3. Монада Writer

31 fact3 n = do
32 let n ’ = n − 1
33 modify ( + 1)
34 m ← fact3 n ’
35 let r = n × m
36 modify ( + 1)
37 return r
38

39 ex3 = runState ( fact3 10) 0

Результат такой реализации идентичен предыдущему, но версия с
использованием Writer имеет большое преимущество. Из её типа —
f :: Integer → Writer (Sum Integer) Integer — можно сразу по-
нять, что наша функция имеет побочный эффект, заключающийся в адди-
тивном накопении некоторого целого числа. Мы точно знаем, что она не
перемножает накапливаемые значения. Не прочитав ни одной строчки
кода функции, мы можем понять, что происходит у неё внутри, благодаря
информации, содержащейся в её типе. Версия реализации функции, ис-
пользующая State, вольна делать с накапливаемым значением все, что
угодно, поэтому её назначение понять сложнее.
Data.Monoid также даёт нам моноид Any. Это тип Bool с заданной на
нем операцией дизъюнкции, более известной как ∣ ∣ . Такое название да-
но специально, чтобы показать, что при комбинировании любого набо-
ра элементов типа Any, наличие в наборе элемента со значением «исти-
на» (Any True) даёт результат, выражающийся как «некоторый элемент
является истинным» (Any True). Таким образом, мы получаем своего ро-
да односторонний переключатель. Мы начинаем накопление с memempty,
то есть Any False, что соответствует выключенному положению пере-
ключателя. Как только к нашему промежуточному результату добавляет-
ся значение Any True, переключатель переводится во включенное состо-
яние. Вне зависимости от того, какие значения будут добавлены позже,
переключатель уже не выключится. Этот процесс соответствует часто ис-
пользуемому в программировании шаблону: флаг, который в качестве по-
бочного эффекта включается в случае выполнения некоторого условия.
40 fact4 :: Integer → Writer Any Integer
41 fact4 0 = return 1

© 2009 «Практика функционального программирования» 119

5.4. Коммутативные моноиды, некоммутативные моноиды и дуальные
моноиды
42 fact4 n = do
43 let n ’ = n − 1
44 m ← fact4 n ’
45 let r = n × m
46 tell ( Any ( r == 120))
47 return r
48

49 ex4 = runWriter ( fact4 10)

В приведенном выше примере по окончании вычисления мы получа-
ем значение n!, при этом нам также сообщается, если в процессе вычис-
ления было выполнено умножение, результат которого был равен 120.
Вызов функции tell практически повторяет словесное описание задачи
на английском языке: «сообщи вызвавшему меня, если значение r когда-
либо станет равно 120». Помимо того, что реализация этого флага требует
минимального количества кода, существует еще одно перимущество. До-
статочно взглянуть на тип этой версии функции, чтобы понять, что в ней
происходит. Мы сразу видим, что эта функция в качестве побочного эф-
фекта вычисляет флаг, который может включиться, но не может быть вы-
ключен. Для сигнатуры типа это большой объем информации. Во многих
других языках программирования мы можем встретить булевый тип в сиг-
натуре, но нам придётся читать код, чтобы понять, как именно он исполь-
зуется.

5.4. Коммутативные моноиды, некоммутатив-

ные моноиды и дуальные моноиды
Говорят, что два элемента моноида x и y можно поменять местами, ес-
ли x ‘ mappend‘ y == y ‘ mappend‘ x. Моноид называется коммута-
тивным, если все его элементы можно менять местами. Хорошим приме-
ром коммутативного моноида является тип целых чисел. Для любой пары
целых чисел a+b == b+a.
Если моноид не является коммутативным, то его называют некомму-
тативным. Если он некоммутативен, то существует пара элементов x и
y, для которой x ‘ mappend‘ y не равно y ‘ mappend‘ x, и следова-

© 2009 «Практика функционального программирования» 120

5.5. Произведение моноидов

тельно функции mappend и flip mappend не равнозначны. Например,

[1,2]++[3,4] отличается от [3,4]++ [1,2]. Интересным следствием этой
особенности является то, что мы можем создать другой моноид, в кото-
ром функцией комбинирования будет flip mappend. Мы по-прежнему
можем использовать тот же элемент mempty, таким образом два первых
правила для моноидов будут соблюдаться. Будет неплохим упражнени-
ем доказать, что и третье правило при этом также будет выполнено. Та-
кой «перевёрнутый» моноид называется дуальным, и Data.Monoid предо-
ставляет конструктор типов Dual для построения дуальных моноидов. Он
может быть использован для инвертирования порядка накопления дан-
ных монадой Writer. К примеру, следующий код собирает трассировку
выполненных действий в обратном порядке:
50 fact5 :: Integer → Writer ( Dual String ) Integer
51 fact5 0 = return 1
52 fact5 n = do
53 let n ’ = n − 1
54 tell $ Dual $ ”We’ve taken one away from ” ++
show n ++ ”\n”
55 m ← fact5 n ’
56 tell $ Dual $ ”We’ve called f ” ++ show m ++ ”\n”
57 let r = n × m
58 tell $ Dual $ ”We’ve multiplied ” ++ show n
59 ++ ” and ” ++ show m ++
”\n”
60 return r
61

62 ex5 = runWriter ( fact5 10)

5.5. Произведение моноидов

Предположим, что мы хотим получать два побочных эффекта одновре-
менно. Например, мы хотим вести подсчет числа выполняемых инструк-
ций, а также получать словесную трассировку всех вычислений. Для ком-
бинирования двух монад Writer мы могли бы воспользоваться преобра-
зователями монад, но есть способ проще — мы можем скомбинировать

© 2009 «Практика функционального программирования» 121

5.5. Произведение моноидов

два моноида в «произведение» моноидов. Определяется оно следующим

образом:
instance ( Monoid , Monoid ) ⇒ Monoid ( , ) where
mempty = ( mempty , mempty )
mappend (u , v ) (w , x ) = ( u ‘ mappend ‘ w , v ‘ mappend ‘ x )
Каждый раз, применяя mappend к произведению, мы на самом деле
применяем пару mappend отдельно к каждому элементу пары. С помощью
следующих вспомогательных функций:
63 tellFst a = tell $ (a , mempty )
64 tellSnd b = tell $ ( mempty , b )
мы можем использовать два моноида одновременно:
65 tellFst a = tell $ (a , mempty )
66 fact6 :: Integer → Writer ( String , Sum Integer ) Integer
67 fact6 0 = return 1
68 fact6 n = do
69 let n ’ = n − 1
70 tellSnd ( Sum 1)
71 tellFst $ ”We’ve taken one away from ” ++
show n ++ ”\n”
72 m ← fact6 n ’
73 let r = n × m
74 tellSnd ( Sum 1)
75 tellFst $ ”We’ve multiplied ” ++ show n
76 ++ ” and ” ++ show m ++ ”\n”
77 return r
78

79 ex6 = runWriter ( fact6 5)

Если бы мы имплементировали наш код с использованием одного спе-
цифического моноида, скажем, моноида для списков, применимость на-
шего кода была бы очень ограничена. Используя же обобщённый класс
типов Monoid, мы обеспечиваем возможность повторного использова-
ния не только отдельных моноидов из нашего кода, но и наборов моно-
идов. Это способствует эффективности кода, поскольку мы можем соби-
рать различные значения за один обход структуры данных. При этом мы

© 2009 «Практика функционального программирования» 122

5.6. «Сворачиваемые» данные

обеспечиваем читаемость кода — наши алгоритмы легко читаются, по-

скольку код использует интерфейс к единственному моноиду.

5.6. «Сворачиваемые» данные

Последним примером применения моноидов в данной статье будет
библиотека Data.Foldable. Она предоставляет обобщённый подход к
обходу структур данных и сборке необходимых значений в процессе.
Функция foldMap применяет соответствующую функцию к каждому эле-
менту структуры и собирает результаты. Ниже следует пример реализа-
ции foldMap для деревьев:
80 data Tree = Empty ∣ Leaf ∣
Node ( Tree ) ( Tree )
81

82 instance Foldable Tree where

83 foldMap f Empty = mempty
84 foldMap f ( Leaf x) = f x
85 foldMap f ( Node l k r ) = foldMap f l
86 ‘ mappend ‘ f k
87 ‘ mappend ‘ foldMap f r
Теперь мы можем использовать любой из рассмотренных выше моно-
идов для вычисления свойств деревьев. Например, мы можем использо-
вать функцию (==1) для проверки равенства каждого элемента единице
или использовать моноид Any, чтобы выяснить, существует ли в дереве
элемент, равный единице. Вот пара примеров: один выясняет, существует
ли в дереве элемент, равный 1, а другой — проверяет, каждый ли элемент
дерева имеет значение больше 5.
88 tree = Node ( Leaf 1) 7 ( Leaf 2)
89

90 ex7 = foldMap ( Any ⋅ ( == 1)) tree

91 ex8 = foldMap ( All ⋅ ( > 5)) tree
Заметьте, что эти выражения без изменений могут быть использованы
с любым сворачиваемым типом, не только с деревьями.

© 2009 «Практика функционального программирования» 123

5.7. Заключение

Надеюсь, вы согласитесь, что наши намерения представлены в коде в

удобной для прочтения форме.
Тут же напрашивается еще одно упражнение: напишите подобный код
для нахождения минимального и максимального элемента дерева. Для
этого вам может понадобиться сконструировать новый моноид наподо-
бие Any или All. Попробуйте найти оба элемента за один обход дерева,
используя произведение моноидов.
Пример со «сворачиваемыми» данными иллюстрирует еще один мо-
мент. Программисту, реализующему foldMap для дерева, нет нужды за-
ботиться о том, должно ли левое поддерево присоединяться к централь-
ному элементу до правого или после. Ассоциативность гарантирует, что
функция даст одинаковый результат вне зависимости от способа.

5.7. Заключение
Моноиды предоставляют общий подход к комбинированию и сбору
значений. Они позволяют нам писать такой код, для которого неважно,
каким образом мы комбинируем значения, что делает его более удоб-
ным для повторного использования. Используя именованные моноиды,
мы можем указывать сингатуры типов так, чтобы читающим код были по-
нятны наши намерения: например, используя Any вместо Bool, мы пояс-
няем, как именно будет использовано булево значение. Мы можем ком-
бинировать основанные на моноидах блоки, предоставляемые библио-
теками Haskell, для построения полезных и легко читаемых алгоритмов с
минимумом усилий.
Заключительные заметки: математики часто называют mappend «би-
нарным оператором» или «умножением». Так же как и в обычной алгеб-
ре, его часто записывают знаком умножения (a × b) или даже слитно (ab).
Подробнее о моноидах можно прочитать на Википедии [6]. К сожалению,
у меня не хватает времени написать о морфизмах моноидов, о том, поче-
му списочные моноиды являются свободными (и какие возможности это
даёт при написании кода), а также как альфа-композиция изображений
¹О том, что такое свободные моноиды, смотрите определение в Википедии: http:
//en.wikipedia.org/wiki/Free_monoid Прим. пер.

© 2009 «Практика функционального программирования» 124

Литература Литература

выражается в моноидах, и о многом другом.

Литература
[1] Control.Monad.Writer.Lazy. — Online документация к GHC, URL:
http://hackage.haskell.org/packages/archive/mtl/
latest/doc/html/Control-Monad-Writer-Lazy.html (дата
обращения: 20 июля 2009 г.).

[2] Dan Piponi. Haskell Monoids and their Uses. — Запись

в блоге: URL: http://blog.sigfpe.com/2009/01/
haskell-monoids-and-their-uses.html (дата обращения:
20 июля 2009 г.). — 2009.

[3] Data.Monoid. — Online документация к GHC, URL: http:

//www.haskell.org/ghc/docs/latest/html/libraries/
base/Data-Monoid.html (дата обращения: 20 июля 2009 г.).

[4] Hurt B. Random thoughts on haskell. — Запись в блоге,

URL: http://enfranchisedmind.com/blog/posts/
random-thoughts-on-haskell/ (дата обращения: 20 июля
2009 г.).

[5] Jones M. P. Functional programming with overloading and higher-order

polymorphism. — 1995.

[6] Monoid. — Статья в Wikipedia, URL: http://en.wikipedia.org/

wiki/Monoid (дата обращения: 20 июля 2009 г.).

© 2009 «Практика функционального программирования» 125

Обзор литературы о функциональном
программировании

Алексей Отт
[email protected]

Аннотация

За долгую историю развития функционального и деклара-

тивного программирования в мире было издано большое ко-
личество книг, посвященных теоретическим и практическим
аспектам этих тематик, включая описания конкретных языков
программирования. Достаточно много книг было издано так-
же и на русском языке.
В данной статье сделана попытка провести обзор имею-
щейся русскоязычной литературы. Кроме того, представлен
небольшой обзор существующей англоязычной литературы,
имеющей отношение к данным темам. В конце статьи приво-
дится список рекомендуемой литературы как по теоретиче-
ским вопросам ФП, так и по конкретным языкам программи-
рования.
6.1. Литература на русском языке

6.1. Литература на русском языке

В 70—80-е гг. в СССР было выпущено достаточно большое количество
литературы, касающейся функционального и декларативного програм-
мирования. Список книг включает не только переводные книги, но и кни-
ги и учебники отечественных авторов, работавших в данных областях. В
90-е годы издание такой литературы практически сошло на нет, но в по-
следние годы эта ситуация стала исправляться — появились переводы хо-
роших зарубежных книг, а также вышло несколько книг русскоязычных
авторов, в том числе и учебники, разработанные специально для вузов.
Важно отметить, что большая часть описанных ниже старых книг
доступна в электронном виде, что облегчает возможность использова-
ния их при изучении соответствующих языков программирования.

6.1.1. Общие вопросы ФП

В данном разделе рассматриваются книги и учебники, не посвящен-
ные конкретным языкам программирования, но дающие читателю воз-
можность получить представление о функциональном программирова-
нии, его теоретических основах, и часто — о реализации языков.

«Функциональное программирование» (Харрисон/Филд)

В 1993 году издательство «Мир» выпустило перевод достаточно из-
вестной книги Functional Programming [16], написанной Петером Харри-
соном (Peter G. Harrison) и Антони Филдом (Anthony J. Field) в 1988 го-
ду. На русском языке она называется «Функциональное программирова-
ние» [92].
Данная книга начинается с рассмотрения функций как таковых и ис-
пользования функций высшего порядка, а также рассматривает виды вы-
числений, используемые при функциональном стиле программирования.
¹Очень часто они переводились силами энтузиастов функционального программи-
рования.
²Тут необходимо отметить серию учебников и учебных курсов проекта Интуит, опи-
санных ниже.

© 2009 «Практика функционального программирования» 127

6.1. Литература на русском языке

Для демонстрации приемов программирования в книге вводится язык

Hope. Помимо Hope, кратко описываются и другие языки программиро-
вания: Lisp, Miranda, FP.
За введением в ФП (функциональное программирование) следует ос-
новная часть книги, посвященная вопросам реализации языков програм-
мирования, начиная с основ лямбда-исчисления, системы вывода и про-
верки типов, вопросов интерпретации и компиляции кода, представле-
ния данных, сборки мусора, и заканчивая вопросами оптимизации про-
грамм (преобразование кода во время компиляции, оптимизация лени-
вого вычисления данных и т. п.).
Эту книгу можно рекомендовать всем тем, кто хочет не только доско-
нально освоить ФП, но и разобраться во внутреннем устройстве языков
программирования.

«Введение в функциональное программирование» (Харрисон)

Данный проект является переводом курса Introduction to Functional
Programming [25] Джона Харрисона (John Harrison). Этот курс может ис-
пользоваться для быстрого ознакомления с основами ФП и семейством
языков ML. Он содержит в себе как описание теоретических основ ФП (от
лямбда-исчисления до систем типов), так и примеры применения пара-
дигм ФП для решения конкретных задач.
В данном курсе используется язык программирования Caml Light, вхо-
дящий в семейство языков ML. По мере прохождения данного курса чита-
тель получает набор знаний, необходимый для освоения данного языка и
написания на нем достаточно сложных программ.
Перевод может использоваться как основа курса лекций по ФП — по-
мимо конспектов лекций (lecture notes) в нем содержатся переводы всех
сопутствующих слайдов. Последняя версия перевода может быть загру-
жена с сайта проекта.
³Хочется отметить, что ведется работа над версией курса лекций, адаптированной
для языка OCaml, который является развитием Caml Light, но не полностью совместим с
ним.

© 2009 «Практика функционального программирования» 128

6.1. Литература на русском языке

«Структура и интерпретация компьютерных программ»

В 2006 году был выпущен перевод на русский язык классического
учебника MIT по основам программирования «Структура и интерпрета-
ция компьютерных программ» [68] (Structure & Interpretation of Computer
Programs, SICP[1]). Перевод был выполнен Георгием Бронниковым.
Данная книга содержит материалы по основам программирования;
показывает, как с помощью композиции несложных процедур програм-
мист может строить сложные программные системы. Особый упор де-
лается на показ преимуществ использования абстракций и модульности
программ, а в качестве примеров рассматриваются построение языка
программирования, включая компиляцию, обработка символьных дан-
ных, бесконечные потоки данных и т. п.
Книга отличается от других учебников тем, что в ней описываются раз-
ные подходы к композиции программ, демонстрируются преимущества
функционального подхода к построению программ, использование функ-
ций высшего порядка и т. п., а в качестве основного языка программиро-
вания используется язык Scheme.
Качество перевода книги очень высокое, однако имеются недостатки,
связанные с изданием самой книги: она вышла в мягком переплете, и ее не
очень удобно читать, имеются проблемы верстки и опечатки, а главное —
малый тираж (всего 1000 экземпляров), в связи с чем книгу уже тяжело
найти в магазинах. В то же время, ее можно найти в электронном виде.

Учебные курсы проекта «Интуит»

Среди учебных курсов проекта «Интуит» имеется несколько курсов,
которые посвящены вопросам функционального и декларативного про-
граммирования. Некоторые из них предлагают теоретическое изложение
принципов ФП, другие посвящены конкретным языкам программирова-
ния. Эти курсы могут стать хорошим подспорьем при изучении ФП, по-
скольку материал рассчитан на людей, только начинающих знакомиться
с соответствующими темами. Практически все курсы содержат задачи и
упражнения, выполняя которые можно приобрести практический опыт
применения полученных знаний.
В настоящее время опубликованы следующие курсы (материалы неко-

© 2009 «Практика функционального программирования» 129

6.1. Литература на русском языке

торых курсов доступны также в печатном виде — книги можно заказать с

сайта проекта):
• «Стили и методы программирования» [88] — учебный курс, в кото-
ром систематически излагаются сведения о стилях программирования и
их методах, а также обсуждаются вопросы сочетаемости различных мето-
дов в разработке программ.
• «Язык и библиотеки Haskell 98» — перевод известного учебни-
ка A Gentle Introduction To Haskell, описанного ниже, в разделе про
Haskell (6.1.2).
• «Введение в программирование на Лиспе» [75] — вводный курс по
программированию на языке Lisp с примерами решения задач на этом
языке.
• «Основы функционального программирования» [73] — учебник по
практическому программированию на языке Lisp.
• «Парадигмы программирования» [74] — курс, рассматриваю-
щий различные парадигмы программирования — функциональное,
объектно-ориентированное, императивное и другие.
• «Введение в теорию программирования. Функциональный подход»
[80] — еще один учебник по ФП. Здесь для примеров используется язык
Standard ML.
• «Основы программирования на языке Пролог» [97] — учебный курс
по логическому программированию и языку Пролог.
Стоит отметить, что материалы некоторых курсов пересекаются меж-
ду собой, и некоторые курсы написаны достаточно сложно для самостоя-
тельного изучения.

«Типы в языках программирования» (Пирс)

Эта книга является переводом известной книги Types and
Programming Languages Бенджамина Пирса (Benjamin C. Pierce) [55].
В книге рассматриваются различные аспекты использования типов в
языках программирования: математические основы, различные типовые
системы, вывод типов и т. д.
⁴Это, к сожалению, беда многих советских и российских учебников.

© 2009 «Практика функционального программирования» 130

6.1. Литература на русском языке

Этот перевод, также как и SICP, осуществляется Георгием Броннико-

вым. Бета-версии книги доступны в электронном виде, текущую версию
вы можете найти на сайте проекта. Выход книги в печатном виде планиру-
ется после завершения работы над переводом, скорее всего в следующем
году.

Другие книги, имеющие отношение к ФП

Помимо описанных выше, на русском языке было издано еще некото-
рое количество книг, имеющих отношение к функциональному програм-
мированию — о математических основах ФП, реализации языков и т. д.
Ниже приведен краткий (и, вероятно, неполный) их список:
• В 1992 году был выпущен перевод известной книги Implementing
functional languages: a tutorial [38], написанной Simon Peyton Jones & David
Lester. На русском языке она называется «Реализация функциональных
языков» [76]. Книга посвящена практическим вопросам реализации функ-
циональных языков программирования. К сожалению, в настоящее время
найти эту книгу ни в электронном, ни в бумажном виде не удаётся, поэто-
му доступным остаётся только английский оригинал.
• Перевод книги Питера Хендерсона «Функциональное програм-
мирование. Применение и реализация» [93] (Functional Programming:
Application and Implementation [28]), вышедший в 1983 году. Книга не
только знакомит с основами ФП, но и охватывает более сложные темы,
включая тонкости реализации языков программирования (сборка мусо-
ра, компиляция кода и т. д.).
• В 1985 году был выпущен перевод книги Х. Барендрегта «Ламбда-
исчисление: его синтаксис и семантика» [70] (The Lambda Calculus.
Its Syntax and Semantics [3]). Книга посвящена теоретическим аспек-
там лямбда-исчисления, в ней рассматриваются классическое лямбда-
исчисление, различные виды редукций и связанные с ними темы.
• Книга С. Маклейна «Категории для работающего математика» [86]
(Categories for the Working Mathematician [44]), выпущенная в 2004 году,
посвящена теории категорий, в рамках которой дается определение мо-
над и других понятий и абстракций, нашедших применение в ФП. В кни-
ге всесторонне рассматриваются положения и концепции теории катего-

© 2009 «Практика функционального программирования» 131

6.1. Литература на русском языке

рий.
• Учебное пособие В.М. Зюзькова «Математическое введение в де-
кларативное программирование» [81] рассматривает математические ос-
новы декларативного и функционального программирования, лямбда-
исчисление и методы доказательства теорем. Для примеров используют-
ся языки Prolog и Haskell.

6.1.2. О конкретных языках

Наряду с книгами, описывающими общие вопросы программиро-
вания на функциональных языках и математические основы лямбда-
исчисления, в СССР и России издавались и книги по конкретным функци-
ональным и декларативным языкам программирования. Достаточно ши-
роко представлена информация о языках Lisp, Haskell и Prolog, но к сожа-
лению практически отсутствует литература по языку Erlang.

Lisp
Языку Lisp, являющемуся самым старым функциональным языком, в
СССР было посвящено несколько публикаций (хотя их не так много, по
сравнению с языком Пролог).
В 70-х гг. было выпущено сразу несколько книг по Лиспу:
• В 1976 году вышел перевод книги У. Маурера «Введение в програм-
мирование на языке ЛИСП» (Maurer W. D., The Programmer’s Introduction
to LISP [47]), содержавшей описания языка Лисп и множество примеров и
задач на его использование.
• Через год Московским Энергетическим Институтом было издано
учебное пособие по программированию на языке Lisp 1.5, написанное Е.
Семеновой. Пособие содержит описание языка Lisp 1.5 и примеры его ис-
пользования для решения учебных задач.
• И в 1978 году была выпущена книга С.С. Лаврова и Г.С. Силагадзе «Ав-
томатическая обработка данных. Язык ЛИСП и его реализация» [84], опи-
сывающая язык Лисп и рассматривающая вопросы реализации этого язы-
ка.
В 1990 году вышел в свет широко известный двухтомник «Мир Лис-
па» [95], являющийся переводом одноименной книги финских авторов

© 2009 «Практика функционального программирования» 132

6.1. Литература на русском языке

Prolog, 1972

Erlang, 1987

Lisp, 1958 Common Lisp, 1984 ANSI Common Lisp, 1994

Arc, 2008

Scheme, 1975

F#, 2005

OCaml, 1996

Caml, 1985

Caml Light, 1991 Scala, 2003

ML, 1973 SML, 1984

Miranda, 1985

Haskell, 1987

1960 1965 1970 1975 1980 1985 1990 1995 2000 2005

Рис. 6.1. Генеалогическое дерево семейств функциональных и деклара-

тивных языков

Э. Хювёнен и И. Сеппянен. В первом томе содержится описание язы-

ка Common Lisp, включая типы данных и наиболее часто используемые
функции, ввод и вывод данных, обработку символьных данных и т. п. Кро-
ме того, часть первого тома посвящена введению в методы ФП: использо-
вание рекурсии, функций высшего порядка, замыканий и макросов. Вто-
рой том содержит введение в другие методы программирования — ло-
гическое и объектное, описание среды программирования Лисп, а так-
же большое количество примеров программ на этом языке, включая про-
стой интерпретатор Лиспа.

Логическое программирование и язык Пролог

За последние тридцать лет в СССР (а затем и в России) было выпущено
достаточно большое количество книг на темы логического программиро-

© 2009 «Практика функционального программирования» 133

6.1. Литература на русском языке

вания и искусственного интеллекта вообще и языка Пролог в частности

(особенно много их было издано в 80-х гг.). Этот далеко не полный список
включает следующие книги:
• Иван Братко. «Программирование на языке Пролог для искусствен-
ного интеллекта». Первое издание на русском языке вышло в 1990 году
[71] . В настоящее время в магазинах доступно третье издание этой кни-
ги [72], выпущенное в 2004 году. Первая часть книги полностью посвяще-
на языку Пролог и методам работы с ним, а во второй части рассматри-
ваются прикладные вопросы использования данного языка: построение
экспертных систем, решение задач поиска, обучение машин, обработка
лингвистической информации и т. п.
• Клоксин У., Меллиш К. «Программирование на языке пролог» [83]. Эта
книга, изданная в 1987 году, содержит только описание языка Пролог и
особенностей его использования.
• А. Адаменко, А. Кучуков. «Логическое программирование и Visual
Prolog» [69]. Книга издана в 2003 году и содержит небольшое введение
в логическое программирование, в то время как основная часть книги
посвящена вопросам программирования на Прологе с учетом особенно-
стей Visual Prolog.
• Дж. Малпас. «Реляционный язык Пролог и его применение» [87]. Дан-
ная книга является подробным описанием языка Пролог и различных
приемов программирования на этом языке (обработка текстов, представ-
ление знаний); содержит много примеров.
• С. Чери, Г. Готлоб, Л. Танка «Логическое программирование и базы дан-
ных» [96]. Книга рассматривает вопросы организации баз данных логиче-
ских высказываний, включая краткое описание основ логического про-
граммирования и языков Пролог и Дейталог.
• Л. Стерлинг, Э. Шапиро. «Искусство программирования на языке Про-
лог» [90] (The Art of Prolog: Advanced Programming Techniques [62]). Вы-
пущенная в 1990 году, книга английских ученых содержит материалы по
теории логического программирования, достаточно подробно описыва-
ет язык Пролог и содержит большое количество примеров программиро-
вания на этом языке, включая систему для решения уравнений и компи-
лятор простого языка программирования.
• Ц. Ин, Д. Соломон. «Использование турбо-пролога» [82]. Книга содер-

© 2009 «Практика функционального программирования» 134

6.1. Литература на русском языке

жит описание принципов работы со средой программирования Турбо-

Пролог, включая такие вопросы как использование машинной графики,
создание многооконного интерфейса и т. п.
• Дж. Макаллистер. «Искусственный интеллект и Пролог на микро-
ЭВМ» [85]. Книга в краткой форме содержит сведения по языку Пролог,
логике, базам знаний и экспертным системам. В первую очередь предна-
значалась для владельцев небольших компьютеров серии Спектрум и т. п.
• Дж. Стобо. «Язык программирования Пролог» [91]. Данная книга яв-
ляется переводом книги «Problem Solving with Prolog» [63] () и описывает
язык Пролог и его применение для решения различных задач — постро-
ения баз знаний, системы решения задач и других.
• Дж. Доорс, А.Р. Рейблейн, С. Вадера. «Пролог — язык программирова-
ния будущего» [77]. Книга содержит краткое описание языка Пролог, прак-
тических приемов работы с ним, а также решения некоторых логических
задач.

Haskell
В настоящее время количество русскоязычных материалов по язы-
ку Haskell невелико. Только в последние годы стали появляться книги об
этом языке (упомянутые далее в статье книги Р. Душкина и Н. Рогановой,
курсы проекта «Интуит») и появились энтузиасты, работающие над пере-
водом англоязычных книг и статей на русский язык в целях популяриза-
ции Haskell среди русскоязычных программистов.

Книги о Haskell Романа Душкина В 2006—2007 гг. Роман Душкин, читав-

ший в МИФИ в 2001—2006 гг. курсы по ФП, выпустил две книги, посвящен-
ные языку программирования Haskell.
Первая из них называется «Функциональное программирование на
языке Haskell» [78] и является учебником по ФП, с примерами на языке
Haskell, и используется в ряде вузов в качестве учебного пособия по ФП.
В книге рассматриваются основы лямбда-исчисления, принципы постро-
ения программ на функциональных языках, а также описывается круг ти-
повых задач, для которых использование функциональных языков явля-
ется целесообразным. Использование монад, ввод/вывод данных, классы

© 2009 «Практика функционального программирования» 135

6.1. Литература на русском языке

типов (включая стандартные классы языка Haskell) и другие вопросы ил-

люстрируются примерами на языке Haskell. В последних двух главах рас-
сматриваются вопросы построения трансляторов и имеющиеся в Haskell
средства для этого, а также обсуждаются подходы к решению некоторых
задач искусственного интеллекта на языке Haskell.
Стоит отметить, что книга содержит достаточно большое количество
математики и написана суховатым языком, что делает ее излишне тео-
ретизированой с точки зрения программиста-практика и затрудняет вос-
приятие. Кроме того, в книге не так много примеров, которые показыва-
ли бы применимость языка в повседневной разработке (если сравнивать
с книгой Real World Haskell, которая является хорошим образцом в этом
деле). Еще одной вещью, затрудняющей чтение книги является качество
издания — верстки самой книги и бумаги, на которой она напечатана.
Вторая книга этого же автора называется «Справочник по языку
Haskell» [79] и является дополнением к первой. Книга предназначена для
читателей, уже знакомых с основами языка Haskell, поэтому она не должна
рассматриваться как учебник по этому языку. Она содержит краткое опи-
сание синтаксиса языка Haskell, основных типов данных, а также (что важ-
но!) основные приемы программирования на этом языке — использова-
ние различных видов рекурсии, функций высшего порядка и анонимных
функций, защитных выражений и т. д.
Основная часть книги посвящена стандартным библиотекам, входя-
щим в состав Hugs98 & GHC: начиная с Prelude и включая основные биб-
лиотеки (Control, System, Data, Text). Для каждой библиотеки приводит-
ся описание определенных в ней типов, классов и функций. Приводимые
в справочнике определения функций могут использоваться в качестве
примеров по написанию «правильного» кода на Haskell и являются хоро-
шим подспорьем в работе.

«Функциональное программирование» (Роганова) В 2002 году Инсти-

тут ИНФО издал учебное пособие Н.А. Рогановой под названием «Функци-
ональное программирование» [89]. В данном пособии основной упор де-
лается на практическое применение ФП для решения конкретных задач
(автор выбрала задачи обработки структур данных и различные матема-
тические задачи). В нем практически нет теории, изобилующей математи-

© 2009 «Практика функционального программирования» 136

6.1. Литература на русском языке

кой, что отличает его от других учебников по ФП. Все вводимые понятия
иллюстрируются примерами на языке Haskell, который описан достаточ-
но подробно, поэтому данное учебное пособие можно рассматривать в
качестве начального по данному языку.
К недостаткам пособия можно отнести то, что отсутствие материала по
теоретическим основам ФП (лямбда-исчисление и т. п.) требует изучения
дополнительных материалов (которые, к сожалению, не указаны в списке
литературы). Кроме того, в части описания языка Haskell мало внимания
уделено таким вопросам, как ввод/вывод данных, разбор данных и т. п.

Переводы документации М. Ландина и В. Роганов в 2005 году выпол-

нили перевод The Haskell 98 Report [39] — основного документа, который
определяет синтаксис языка Haskell, а также состав основных библиотек
этого языка. Перевод этого документа доступен с сервера haskell.ru как в
варианте для печати, так и в online-версии.
Еще одна группа энтузиастов выполнила перевод на русский язык
хорошо известного учебника по языку Haskell — Gentle Introduction To
Haskell [33]. Данный учебник описывает основные возможности языка
Haskell и наиболее часто используемые функции стандартных библиотек,
включая ввод и вывод, и может использоваться для изучения основ язы-
ка. Перевод учебника доступен с сервера RSDN [94] и состоит из двух ча-
стей — часть 1 и часть 2.

Семейство языков ML
О семействе языков ML (Standard ML, Objective Caml, Caml Light) на
русском языке существует сравнительно немного литературы. В качестве
небольшого введения в программирование на языке Caml Light можно
использовать курс лекций «Введение в функциональное программирова-
ние», описанный выше (6.1.1).
Кроме того, существует незаконченный перевод книги Developing
Applications With Objective Caml [7] — переведено 11 глав, описывающих
сам язык OCaml и базовые библиотеки, их можно использовать в качестве
учебника по данному языку.

© 2009 «Практика функционального программирования» 137

6.2. Англоязычная литература

6.1.3. Планируется выпустить

Книга Сергиевского и Волчёнкова «Декларативное программирова-
ние» в настоящее время находится в процессе издания и должна появить-
ся к концу этого года. Книга предназначена для использования в учебных
заведениях. Она рассматривает вопросы функционального и логического
программирования, включая теоретические вопросы ФП, доказательство
свойств программ и т. д. Для примеров используются языки Lisp и Haskell.
Отдельная часть учебника посвящена вопросам логического программи-
рования с использованием языка Prolog.
Другие авторы также ведут работу над несколькими книгами, посвя-
щенными Haskell. Одна из них касается вопросов создания специализиро-
ванных языков программирования (DSL) средствами языка Haskell, вклю-
чая создание синтаксических анализаторов, а также ряда связаных с этим
тем. Еще одна книга будет посвящена практическим аспектам использо-
вания Haskell с целью показать применимость языка Haskell для решения
«реальных» задач.
Также в последнее время ведется работа над переводом на русский
язык книги Practical Common Lisp. Книга содержит достаточно подробное
введение в язык Common Lisp и содержит большое количество практи-
ческих примеров, которые помогают начать использование этого языка
в повседневной работе. Работа над переводом находится в заключитель-
ной стадии, а переведенный материал доступен на сайте проекта.

6.2. Англоязычная литература

На английском языке издано большое количество книг по ФП, его тео-
ретическим основам, а также функциональным языкам программирова-
ния. Хотя некоторые книги и были переведены на русский, количество
публикаций на английском языке гораздо больше. Краткие рецензии на
некоторые из них приведены в этом разделе.

© 2009 «Практика функционального программирования» 138

6.2. Англоязычная литература

6.2.1. Общие вопросы ФП

В данном списке собраны книги, посвященные общим вопросам раз-
работки ПО на функциональных языках, а также теоретическим вопросам
ФП:
• Книга Programming Languages: Application and Interpretation [42] яв-
ляется учебником для курса «Языки программирования». В ней рассмат-
риваются различные аспекты проектирования и разработки языков про-
граммирования. Для примеров используется язык Scheme.
• Purely Functional Data Structures [50] — отличная книга Криса Ока-
саки (Chris Okasaki) в которой описываются методы работы со сложными
структурами данных в «чистых» функциональных языках.
• Книга The Functional Approach to Programming (Guy Cousineau,
Michel Mauny) [11], описывающая все основные вопросы ФП, может ис-
пользоваться в качестве учебника по ФП. Для примеров используется
язык Caml.
• В книге Algorithms: A Functional Programming Approach [57] рассмат-
риваются вопросы реализации различных алгоритмов на «чистых» функ-
циональных языках, включая некоторые темы, описанные в книге «Purely
Functional Data Structures». Для примеров используется Haskell.
• Книга Advanced Programming Language Design [17] (online-версия)
содержит информацию о разных подходах к программированию, в том
числе и несколько глав о функциональном и логическом программиро-
вании.
• Книга How to Design Programs: An Introduction to Programming and
Computing [30] (имеющаяся в свободном доступе и поставляемая вместе
с PLT Scheme), является учебником по программированию, демонстриру-
ющим различные подходы к разработке программ. Для примеров в книге
используется язык Scheme.
• Basic Category Theory for Computer Scientists [54] — данная книга рас-
сматривает теорию категорий, лежащую в основе некоторых приемов, ис-
пользуемых в ФП (в частности, монад в языке Haskell).

© 2009 «Практика функционального программирования» 139

6.2. Англоязычная литература

6.2.2. Реализация языков программирования

Вопросы реализации функциональных языков программирования
рассматриваются в некоторых описанных выше книгах, посвященных тео-
рии ФП, но кроме этого, существуют книги, посвященные исключительно
вопросам реализации таких языков программирования:
• Книга Design Concepts in Programming Languages [66] посвящена
теоретическим и практическим аспектам разработки языков программи-
рования.
• Книга The Implementation of Functional Programming Languages [37],
написанная Simon Peyton Jones и изданная в 1987 году, описывает такие
темы, как лямбда-исчисление, вывод и проверка типов, сопоставление с
образцом (pattern-matching), и использование этих приемов при реали-
зации функциональных языков программирования.
• Книга Implementing functional languages: a tutorial [38], написанная
Simon Peyton Jones & David Lester и изданная в 1992 году, рассматрива-
ет вопросы реализации функциональных языков программирования на
примере реализации простого языка.
• Книга Garbage Collection: Algorithms for Automatic Dynamic Memory
Management [36] посвящена описанию применяемых в функциональных
языках программирования технологий «сборки мусора».

6.2.3. Конкретные языки ФП

Ниже перечислены наиболее интересные книги на английском языке,
посвященные конкретным функциональным языкам программирования.

Haskell
Среди публикаций, посвященных языку Haskell, я хотел бы отметить
следующие:
• Introduction to Functional Programming using Haskell Ричарда Бёр-
да [4] является учебником ФП, использующим Haskell в качестве основ-
ного языка. В нем рассмотрены базовые концепции ФП и их применение
в Haskell. Книга содержит много примеров и упражнений для самостоя-
тельного решения.

© 2009 «Практика функционального программирования» 140

6.2. Англоязычная литература

• Real World Haskell [51] является отличной книгой по языку Haskell, по-
скольку, кроме описания самого языка, содержит множество примеров,
показывающих применение Haskell в реальной жизни: программирова-
ние баз данных и графических интерфейсов, разбор данных, тестирова-
ние приложений и многое другое. Эта книга находится в свободном до-
ступе на официальном сайте.
• The Haskell Road To Logic, Maths And Programming [13] показывает
применение Haskell в математике и логике.
• Programming in Haskell [34], написанная Graham Hutton, описывает
язык Haskell немного суховато, но может использоваться в качестве спра-
вочника теми, кто уже знаком с этим или другими функциональными язы-
ками, например, OCaml или Standard ML.
• Книга Haskell: The Craft of Functional Programming [65] посвящена
описанию языка Haskell и принципов программирования на нем и вклю-
чает отдельные главы по работе с типами данных, классами типов и т. п.
• The Haskell School of Expression: Learning Functional Programming
through Multimedia [32] показывает практические аспекты применения
Haskell, при этом описывает достаточно сложные темы, такие как взаимо-
действие с внешним миром, проектирование программ на Haskell и т. д.
Кроме напечатанных книг и учебников, имеются и материалы, доступ-
ные online. К наиболее интересным можно отнести:
• Раздел на сайте проекта Wikibooks, посвященный Haskell, содержит
очень большое количество материалов различной степени сложности.
• A Gentle Introduction to Haskell 98 [33] — учебник по языку Haskell 98.
• Yet Another Haskell Tutorial [35] — еще один учебник по Haskell, со-
держащий примеры использования языка и упражнения для самостоя-
тельного решения.
• Write Yourself a Scheme in 48 Hours — данный учебник позволяет по-
лучить навыки программирования на Haskell на практическом примере
написания интерпретатора языка Scheme.
• All About Monads — учебник, посвященный теории и вопросам прак-
тического применения монад в Haskell.

© 2009 «Практика функционального программирования» 141

6.2. Англоязычная литература

Erlang
Книга Programming Erlang. Software for a Concurrent World [2], написан-
ная Джо Армстронгом (Joe Armstrong), является практически единствен-
ным доступным печатным изданием, посвященным языку Erlang, посколь-
ку выпущенная ранее книга «Concurrent Programming in Erlang» [10] ста-
ла уже библиографической редкостью (в интернете можно найти первую
часть этой книги). «Programming Erlang» описывает язык простым языком
и знакомит читателя с его основным функционалом. Кроме самого языка,
книга описывает более сложные темы: базы данных, использование OTP
и т. п.
Кроме того, в этом году планируется выпуск следующих книг, посвя-
щенных как самому языку Erlang, так и применению его в конкретных за-
дачах:
• Erlang Programming [6],
• Concurrent Programming with Erlang/OTP [46],
• Erlang Web Applications: Problem-Design-Solution [22].

Caml & Objective Caml

Вопросам программирования на языке Objective Caml (OCaml) посвя-
щено несколько книг.
Наиболее известной является свободно доступная книга Developing
Applications with Objective Caml [7], которая не только описывает сам язык
OCaml, но и рассматривает различные вопросы программирования с его
использованием.
Недавно также появилась свободно распространяемая книга
Introduction to Objective Caml [29], которая содержит достаточно по-
дробное описание языка и примеры его применения.
Книга OCaml for Scientists [26] посвящена вопросам использования
OCaml для «научного программирования» — обработки данных, матема-
тических вычислений, визуализации данных и оптимизации кода для луч-
шей производительности.
Еще одна книга — Practical OCaml [60], описывает язык OCaml и прие-
мы программирования на нем. К сожалению, по многочисленными отзы-
вами читателей, книга написана не очень хорошо.

© 2009 «Практика функционального программирования» 142

6.2. Англоязычная литература

Технический отчет The ZINC experiment: an economical implementation

of the ML language [45], написанный Xavier Leroy в 1990 году, представляет
собой подробное описание реализации языка ML и может быть интересен
тем, кто интересуется внутренним устройством Caml & OCaml.

F#
В настоящее время по языку F# написана серия книг.
Foundations of F# [53] описывает основы языка и показывает разные
методы программирования на нем, включая создание пользовательских
интерфейсов и работу с базами данных.
Книга Expert F# [64] в свою очередь посвящена более сложным вопро-
сам применения F# для разработки программ, таким как взаимодействие
с кодом, написанным на других языках, использование библиотек .Net,
разбор данных, асинхронное программирование и т. д.
F# for Scientists [27] является версией книги «OCaml for Scientists», адап-
тированной для языка F#, и содержит информацию по разным аспектам
применения F# в «научном программировании» — визуализации данных,
работе с базами данных, обработке данных и т. д.
Также в скором времени планируется выпуск еще нескольких книг, по-
священных программированию на языке F# : Beginning F#, The Definitive
Guide to F# и Functional Programming for the Real World: With Examples in
F# and C#.

Standard ML
По языку Standard ML также выпущено достаточно большое количе-
ство книг.
Книга ML for the Working Programmer [52] является практическим вве-
дением в этот язык, описывающим сам язык и демонстрирующим некото-
рые приемы программирования на нем.
Книга The Little MLer [15] является кратким справочником по языку с
примерами программ.
Книга «Unix System programming with Standard ML» [59] посвящена де-
монстрации применимости функциональных языков в повседневной ра-
боте.

© 2009 «Практика функционального программирования» 143

6.2. Англоязычная литература

Книга Elements of ML Programming, ML97 Edition [67], также описываю-

щая сам язык и методы программирования на нем, может использоваться
как введение в язык Standard ML.
Несколько книг посвящены изложению стандарта языка. К ним мож-
но отнести книги The Definition of Standard ML [48] и The Standard ML Basis
Library [21], которые содержат подробную информацию о языке и стан-
дартной библиотеке.

Lisp
Кроме описанных ранее русскоязычных книг по языку Lisp, существует
большое количество книг на английском языке, посвященных Lisp и его
диалектам:
• Paradigms of Artificial Intelligence Programming: Case Studies in
Common LISP [49] — классическая книга Питера Норвига (Peter Norvig),
посвященная вопросам искусственного интеллекта, показывает приме-
нение языка Common Lisp для решения некоторых задач искусственного
интеллекта.
• ANSI Common Lisp [24], написанная Полом Гремом (Paul Graham),
предназначена для начинающих программировать на Common Lisp. Кни-
га содержит описание языка и примеры его использования.
• On Lisp [23], также написанная Полом Гремом, раскрывает более
сложные вопросы программирования на Common Lisp: создание макро-
сов, использование макросов для построения domain-specific languages
(DSL) и т. п.
• Книги Object-Oriented Programming in Common Lisp: A Programmer’s
Guide to CLOS [40] и The Art of Metaobject Protocol [41] содержат по-
дробную информацию о программировании с использованием Common
Lisp Object System. При этом, вторая книга в большей степени по-
священа вопросам реализации Metaobject Protocol, лежащего в осно-
ве CLOS, и рекомендуется всем, кто интересуется вопросами объектно-
ориентированного программирования (ООП).
• Книга Let Over Lambda [31] посвящена рассмотрению сложных тем
программирования на Common Lisp — созданию и использованию мак-
росов, правильному проектированию программ и т. п.

© 2009 «Практика функционального программирования» 144

6.2. Англоязычная литература

• Книга Common Lisp: The Language, 2ed [61] (также доступна online)
является полным справочником по языку Common Lisp.
• Successful Lisp: How to Understand and Use Common Lisp [43] — еще
одна книга для начинающих программировать на Lisp’е. Книга также име-
ет online версию.
• Lisp in Small Pieces [56] — достаточно известная книга по Lisp. В ней
рассматриваются реализации языков Lisp и Scheme, включая программи-
рование с использованием продолжений, построение интерпретатора и
компилятора этих языков, поддержку макросов и многое другое.

Scheme
По языку программирования Scheme также выпущено несколько книг,
в настоящее время можно купить следующие из них:
• The Little Schemer [20],
• The Reasoned Schemer [18],
• The Seasoned Schemer [19],
• The Scheme Programming Language, 3ed [14].
Книги описывают как сам язык, так и различные аспекты его исполь-
зования. Эти книги могут использоваться как справочники по языку и
являются хорошим дополнением к книгам Structure and Interpretation of
Computer Programs [1] и How to Design Programs [30], в которых язык
Scheme использован для примеров.

Prolog
Количество англоязычных книг по Прологу достаточно велико. Ниже
приведен лишь небольшой список имеющейся литературы — я старался
отобрать наиболее интересные книги:
• Logic Programming with Prolog [5] — хорошая книга по Prolog началь-
ного уровня. В ней описываются основные принципы программирования
на Prolog вместе с примерами решения конкретных задач.
• Книга The Art of Prolog, Second Edition: Advanced Programming
Techniques [62] посвящена вопросам использования языка, которые
⁵Продолжение — continutation.

© 2009 «Практика функционального программирования» 145

6.3. Рекомендации

обычно не рассматриваются в книгах, предназначенных для изучения са-

мого языка: построение интерпретаторов и компиляторов, преобразова-
ние программ, теории логического программирования.
• Programming in Prolog: Using the ISO Standard [8] — еще один учебник
по Прологу, демонстрирующий основные принципы программирования
на этом языке.
• Clause and Effect: Prolog Programming for the Working Programmer [9]
является небольшим введением в Пролог для программистов, владею-
щих другими языками.
• Prolog Programming in Depth [12] — еще одна книга, посвящен-
ная «сложным» аспектам применения Пролога: взаимодействию с внеш-
ним миром, императивному программированиму на Прологе, построе-
нию экспертных систем и т. п.

6.3. Рекомендации
Если вы хотите познакомиться с принципами создания функциональ-
ных языков программирования, то на русском языке базовую информа-
цию вы почерпнете из книг «Функциональное программирование» [92],
«Функциональное программирование. Применение и реализация» (Хен-
дерсон) и «Реализация функциональных языков». Из книг на английском
языке я могу порекомендовать книги, перечисленные в разделе «Реали-
зация функциональных языков программирования (6.2.1)».
Заинтересовавшиеся Common Lisp могут начать его изучение с кни-
ги Practical Common Lisp [58] (существующей и на русском языке), которая
даст информацию по основным аспектам языка. Более сложные аспекты
работы с Lisp описаны в On Lisp [23], The Art of Metaobject Protocol [41],
Let Over Lambda [31], Lisp in Small Pieces [56] и других англоязычных кни-
гах (6.2.3).
Для обучения функциональному программированию на языке Haskell
можно порекомендовать книгу «Introduction to Functional Programming
using Haskell» Ричарда Бёрда [4]. Для желающих узнать о практическом
применении Haskell хорошим выбором будет книга Real World Haskell [51],
в которой приводятся практические примеры использования Haskell.

© 2009 «Практика функционального программирования» 146

6.4. Заключение

Среди учебников можно отметить Yet another Haskell tutorial [35] и A

Gentle Introduction to Haskell 98 [33] (также доступный на русском языке),
ну и конечно раздел о Haskell в проекте Wikibooks.
В настоящее время по языку Erlang доступно не так уж много литерату-
ры — только книга Programming Erlang. Software for a Concurrent World [2]
и официальная документация. Книга может быть использована для озна-
комления с языком и концепциями, лежащими в основе OTP, после чего
можно переходить к изучению библиотек и фреймворков, входящих в со-
став дистрибутива языка. Хочется надеяться, что ситуация с литературой
по данному языку улучшится с выходом новых книг (6.2.3).
Для ознакомления с языками семейства ML существует достаточно
много литературы. Выбравшим OCaml лучше начать с книги Introduction
to Objective Caml [29], используя её вместе со справочником по язы-
ку, а потом переходить к Developing Applications with Objective Caml [7]
и другим книгам из списка выше (6.2.3). А изучение F# стоит начать
с Foundations of F# [53] и продолжить чтением Expert F# [64] и F# for
Scientists [27].
Для Prologа выбор книг достаточно велик — начать можно с книги
Братко «Программирование на языке Пролог для искусственного интел-
лекта» [72], а затем переходить к книгам на английском языке, перечис-
ленным выше (6.2.3).

6.4. Заключение
Хотелось бы отметить, что появившаяся тенденция к изданию на рус-
ском языке книг по тематике функционального/декларативного програм-
мирования не может не радовать. В печати появляются как переводы от-
личных зарубежных книг, так и публикации отечественных авторов. Неко-
торые книги зарубежных авторов переводятся силами энтузиастов, что
часто позволяет получить очень качественный с технической точки зре-
ния перевод.

© 2009 «Практика функционального программирования» 147

Литература Литература

Литература
[1] Abelson H., Sussman G. J. Structure and Interpretation of Computer Pro-
grams, 2nd Edition. — The MIT Press, 1996. http://mitpress.mit.
edu/sicp/.

[2] Armstrong J. Programming Erlang: Software for a Concurrent World. —

Pragmatic Programmers, 2007.

[3] Barendregt H. P. The Lambda Calculus: its Syntax and Semantics. — North-
Holland, 1981.

[4] Bird R. S. Introduction to Functional Programming Using Haskell, 2nd Edi-

tion. — 2nd edition. — Prentice-Hall, 1998.

[5] Bramer M. Logic Programming with Prolog. — Springer, 2005.

[6] Cesarini F., Thompson S. Erlang Programming. — O’Reilly, 2009.

[7] Chailloux E., Manoury P., Pagano B. Developing Applications With Objec-
tive Caml. — O’Reilly, 2000. — 757 pp. http://caml.inria.fr/
pub/docs/oreilly-book/.

[8] Clocksin W., Mellish C. Programming in Prolog: Using the ISO Standard, 5th
Edition. — Springer, 2003.

[9] Clocksin W. F. Clause and Effect: Prolog Programming for the Working Pro-
grammer. — Springer, 2003.

[10] Concurrent Programming in Erlang, Second Edition / J. Armstrong,

R. Virding, C. Wikström, M. Williams. — Prentice-Hall, 1996.

[11] Cousineau G., Mauny M. The Functional Approach to Programming. —

Cambridge University Press, 1998.

[12] Covington M. A., Nute D., Vellino A. Prolog Programming in Depth. — Pren-
tice Hall, 1996.

© 2009 «Практика функционального программирования» 148

Литература Литература

[13] Doets K., van Eijck J. The Haskell Road to Logic, Maths and Program-
ming. — College Publications, 2004.

[14] Dybvig R. The Scheme Programming Language. — 3rd edition. — The

MIT Press, 2003.

[15] Felleisen M., Friedman D. P. The Little MLer. — The MIT Press, 1997.

[16] Field A. J., Harrison P. G. Functional Programming. — Addison-Wesley,

1988.

[17] Finkel R. Advanced Programming Language Design. — Addison Wesley,

1995.

[18] Friedman D. P., Byrd W. E., Kiselyov O. The Reasoned Schemer. — The MIT
Press, 2005.

[19] Friedman D. P., Felleisen M. The Seasoned Schemer. — The MIT Press, 1995.

[20] Friedman D. P., Felleisen M., Sussman G. J. The Little Schemer, 4th Edition. —
The MIT Press, 1995.

[21] Gansner E. R., Reppy J. H. The Standard ML Basis Library. — Cambridge

University Press, 2002.

[22] Gerakines N. Erlang Web Applications: Problem-Design-Solution. — John

Wiley and Sons, 2009.

[23] Graham P. On Lisp. — Prentice Hall, 1993. http://www.paulgraham.

com/onlisp.html.

[24] Graham P. ANSI Common LISP. — Prentice Hall, 1995.

[25] Harrison J. Introduction to functional programming. — Lecture notes. —

1997. http://www.cl.cam.ac.uk/teaching/Lectures/
funprog-jrh-1996/.

[26] Harrop J. OCaml for Scientists. — 2007.

[27] Harrop J. F# for Scientists. — Wiley-Interscience, 2008.

© 2009 «Практика функционального программирования» 149

Литература Литература

[28] Henderson P. Functional Programming: Application and Implementa-

tion. — Prentice-Hall, 1980.

[29] Hickey J. Introduction to objective caml. —

2008. http://www.freetechbooks.com/
introduction-to-objective-caml-t698.html.

[30] How to Design Programs: An Introduction to Programming and Comput-

ing / M. Felleisen, R. B. Findler, M. Flatt, S. Krishnamurthi. — The MIT Press,
2001. http://htdp.org/.

[31] Hoyte D. Let Over Lambda. — Lulu.com, 2008.

[32] Hudak P. The Haskell School of Expression: Learning Functional Program-

ming through Multimedia. — Cambridge University Press, 2000.

[33] Hudak P., Peterson J., Fasel J. A gentle introduction to haskell, version 98.
http://haskell.cs.yale.edu/tutorial/.

[34] Hutton G. Programming in Haskell. — Cambridge University Press, 2007.

[35] III H. D. Yet another haskell tutorial. — Учебник, URL: http://darcs.

haskell.org/yaht/yaht.pdf (дата обращения: 20 июля 2009 г.).
http://darcs.haskell.org/yaht/yaht.pdf.

[36] Jones R., Lins R. Garbage Collection: Algorithms for Automatic Dynamic
Memory Management. — Wiley, 1996.

[37] Jones S. L. P. The Implementation of Functional Program-

ming Languages. Computer Science. — Prentice-Hall, 1987.
http://research.microsoft.com/en-us/um/people/
simonpj/papers/slpj-book-1987/.

[38] Jones S. L. P., Lester D. Implementing functional languages: a tutori-

al. — 1992. http://research.microsoft.com/en-us/um/
people/simonpj/papers/pj-lester-book/.

[39] Jones S. P. Haskell 98 language and libraries. the revised report. — 2002.
http://haskell.org/haskellwiki/Definition.

© 2009 «Практика функционального программирования» 150

Литература Литература

[40] Keene S. E. Object-Oriented Programming in Common Lisp: A Program-

mer’s Guide to CLOS. — Addison-Wesley Professional, 1989.

[41] Kiczales G., des Rivieres J., Bobrow D. G. The Art of the Metaobject Proto-
col. — The MIT Press, 1991.

[42] Krishnamurthi S. Programming Languages: Application and In-

terpretation. — 2003. http://www.cs.brown.edu/~sk/
Publications/Books/ProgLangs/.

[43] Lamkins D. B. Successful Lisp: How to Understand and Use Common

Lisp. — bookfix.com, 2004. http://psg.com/~dlamkins/sl/
contents.html.

[44] Lane S. M. Categories for the Working Mathematician. — Springer Verlag,

1998.

[45] Leroy X. The zinc experiment: an economical implementation of the

ml language: Technical report 117: INRIA, 1990. http://gallium.
inria.fr/~xleroy/publi/ZINC.pdf.

[46] Logan M., Merritt E., Carlsson R. Concurrent Programming with Er-
lang/OTP. — Manning, 2009.

[47] Maurer W. D. The programmer’s introduction to LISP. — London, Mac-

donald, 1972.

[48] Milner R., Tofte M., Harper B. The Definition of Standard ML. — MIT Press,
1990.

[49] Norvig P. Paradigms of Artificial Intelligence Programming: Case Studies

in Common Lisp. — Morgan Kaufmann, 1991.

[50] Okasaki C. Purely Functional Data Structures. — Cambridge University

Press, 1998.

[51] O’Sullivan B., Stewart D., Goerzen J. Real World Haskell. — O’Reilly Media,
Inc., 2008. http://book.realworldhaskell.org/read/.

© 2009 «Практика функционального программирования» 151

Литература Литература

[52] Paulson L. C. ML for the Working Programmer, 2ed. — Cambridge Univer-

sity Press, 1996.

[53] Pickering R. Foundations of F#. — Apress, 2007.

[54] Pierce B. C. Basic Category Theory for Computer Scientists. — The MIT
Press, 1991.

[55] Pierce B. C. Types and Programming Languages. — MIT Press, 2002.

http://www.cis.upenn.edu/~bcpierce/tapl.

[56] Queinnec C. Lisp in Small Pieces. — Cambridge University Press, 2003.

[57] Rabhi F. A., Lapalme G. Algorithms: A Functional Programming Ap-

proach. — Addison Wesley, 1999.

[58] Seibel P. Practical Common Lisp. — Apress, 2005. http://www.

gigamonkeys.com/book/.

[59] Shipman A. L. Unix System Programming with Standard ML. — 2001.

http://web.archive.org/web/20030302003837/http:
//web.access.net.au/felixadv/files/output/book/.

[60] Smith J. B. Practical OCaml. — Apress, 2006.

[61] Steele G. Common LISP. The Language, 2ed. — Digital Press, 1990. http:
//www.cs.cmu.edu/Groups/AI/html/cltl/cltl2.html.

[62] Sterling L., Shapiro E. The Art of Prolog: Advanced Programming Tech-
niques. — The MIT Press, 1986.

[63] Stobo J. Problem Solving with Prolog. — Pitman, 1989.

[64] Syme D., Granicz A., Cisternino A. Expert F#. — Apress, 2007.

[65] Thompson S. Haskell: The Craft of Functional Programming, 2nd Edi-

tion. — Addison-Wesley, 1999.

[66] Turbak F. A., Gifford D. K. Design Concepts in Programming Languages. —

The MIT Press, 2008.

© 2009 «Практика функционального программирования» 152

Литература Литература

[67] Ullman J. D. Elements of ML Programming, ML97 Edition, 2ed. — Prentice

Hall, 1998.

[68] Харольд Абельсон, Джеральд Джей Сассман. Структура и интерпрета-

ция компьютерных программ. — М.: Добросвет, 2006.

[69] А. Адаменко, А. Кучуков. Логическое программирование и Visual

Prolog. — БХВ-Петербург, 2003.

[70] Х. Барендрегт. Ламбда-исчисление. Его синтаксис и семантика. — М.:

Мир, 1985.

[71] И. Братко. Программирование на языке PROLOG для искусственного

интеллекта. — М.: Мир, 1990.

[72] И. Братко. Алгоритмы искусственного интеллекта на языке Prolog. —

Вильямс, 2004.

[73] Л. В. Городняя. Основы функционального программирования. http:

//www.intuit.ru/department/pl/funcpl/.

[74] Л. В. Городняя. Парадигмы программирования. http://www.

intuit.ru/department/se/paradigms/.

[75] Л. В. Городняя, Н.А. Березин. Введение в программирование на Лиспе.

http://www.intuit.ru/department/pl/lisp/.

[76] С. П. Джонс, Д. Лестер. Реализация функциональных языков. — 1992.

[77] Дж. Доорс, А. Р. Рейблейн, С. Вадера. Пролог - язык программирования

будущего. — М.: Финансы и статистика, 1990.

[78] Р. В. Душкин. Функциональное программирование на языке

Haskell. — М.: ДМК Пресс, 2007.

[79] Р. В. Душкин. Справочник по языку Haskell. — М.: ДМК Пресс, 2008.

[80] С. В. Зыков. Введение в теорию программирования. Функциональный

подход. http://www.intuit.ru/department/se/tppfunc/.

© 2009 «Практика функционального программирования» 153

Литература Литература

[81] В. М. Зюзьков. Математическое введение в декларативное про-

граммирование. — 2003. http://window.edu.ru/window/
library?p_rid=46691.

[82] Ц. Ин, Д. Соломон. Использование Турбо-Пролога. — М.: Мир, 1990.

[83] Клоксин У. and Меллиш К. Программирование на языке пролог. — М.:

Мир, 1987.

[84] С. С. Лаврова, Г. С. Силагадзе. Автоматическая обработка данных. Язык

ЛИСП и его реализация. — М.: Наука, 1978.

[85] Дж. Макаллистер. Искусственный интеллект и Пролог на микро-

ЭВМ. — М.: Машиностроение, 1990.

[86] С. Маклейн. Категории для работающего математика. — Физматлит,

2004.

[87] Дж. Малпас. Реляционный язык Пролог и его применение. — М.: На-
ука, 1990.

[88] Н. Н. Непейвода. Стили и методы программирования. http://www.

intuit.ru/department/se/progstyles/.

[89] Н. А. Роганова. Функциональное программирование. — 2002.

[90] Л. Стерлинг, Э. Шапиро. Искусство программирования на языке Про-

лог. — М.: Мир, 1990.

[91] Дж. Стобо. Язык программирования Пролог. — М.: Радио и связь,

1993.

[92] А. Филд, П. Харрисон. Функциональное программирование. — М.:

Мир, 1993.

[93] П. Хендерсон. Функциональное программирование. Применение и

реализация. — М.: Мир, 1983.

© 2009 «Практика функционального программирования» 154

Литература Литература

[94] Пол Хьюдак, Джон Петерсон, Джозеф Фасел. Мягкое введение в

haskell. — Учебник. http://www.rsdn.ru/article/haskell/
haskell_part1.xml.

[95] Э. Хювёнен, И. Сеппянен. Мир Лиспа. — М.: Мир, 1990.

[96] С. Чери, Г. Готлоб, Л. Танка. Логическое программирование и базы

данных. — М.: Мир, 1992.

[97] П. А. Шрайнер. Основы программирования на языке Пролог. http:

//www.intuit.ru/department/pl/plprolog/.

© 2009 «Практика функционального программирования» 155