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

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

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

This article provides a comprehensive description of all the basic concepts usually attributed to functional languages, such as algebraic data types, closures or point-free style. Historical roots of all concepts are explained, their essence is illustrated, typical usage is displayed along with ways of imitating the concepts in languages that do not support them natively.

The article is targeted at professional programmers using mainstream programming languages, even if they do not plan to switch to functional languages. We aim to equip them with ideas from the world of functional programming.

Обсуждение статьи ведется по адресу
http://community.livejournal.com/fprog/5223.html.

1  Введение

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

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

В статье намеренно не затронуты две чрезвычайно важных темы: типовый полиморфизм, а также ленивые вычисления. Обе темы настолько широки, что достойное их рассмотрение увеличило бы и без того немалый размер статьи в полтора–два раза, а рассмотреть их кратко — значило бы лишить читателя удовольствия и обмануть относительно многогранности и красоты их применений. Эти темы будут рассмотрены в ближайших номерах. Кроме того, в данном номере опубликована статья Романа Душкина о полиморфизме в языке Haskell: она прекрасно подойдет для подготовки к знакомству со всем многообразием проявлений полиморфизма в программировании.

Структура всех глав примерно одинакова и состоит из следующих пунктов:

1. Суть: описание концепции, изложенное в одном предложении.
2. Краткая история, предпосылки и контекст возникновения концепции.
3. Интуиция: пример, подготавливающий читателя к восприятию концепции; в идеале при прочтении этой секции читатель должен изобрести концепцию самостоятельно :)
4. Более или менее подробное описание сущности концепции; однако, все сложные или длинные объяснения заменены ссылками на внешние источники.
5. Применение: задачи, для решения которых концепция может оказаться полезной, а также указание на существующие программы, использующие данную концепцию.
6. Реализации: перечисление языков, инструментов, библиотек, реализующих данную концепцию.
7. Схожие концепции из других парадигм (императивной, логической, объектно-ориентированной) и языков, по сути своей схожие с данной, а также способы реализации или имитации данной концепции в рамках этих парадигм и языков.

2  Вывод типов
(Type inference)

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

История
Вывод типов также называется «неявной типизацией», или же «типизацией по Карри», в честь логика Хаскелла Карри. Роджер Хиндли в письме [76] утверждает, что алгоритм вывода типов при помощи унификации множество раз переоткрывался, в основном в период 1950—1960-х гг, или даже 1920—1930-х гг. Возможно, это объясняется чрезвычайной простотой, элегантностью и универсальностью общей схемы алгоритма: вероятно, авторы работали в разных областях математики и информатики, не знали о работах друг друга и не считали нужным публиковать данный алгоритм отдельно.

Интуиция
Рассмотрим написанную на псевдокоде программу для вычисления скалярного произведения двух двумерных векторов:

Очевидно, что на входе этой программы — два числовых массива, а на выходе — число. Посмотрим, какие рассуждения могут привести к такому результату:

• Выполняется обращение к v1[0], v2[0],v1[1],v2[1] — значит, v1 и v2 — массивы чего-то.
• Выполняется сложение v1[0]*v2[0] и v1[1]*v2[1] — значит, v1[0]*v2[0] и v1[1]*v2[1] — числа, и результат dot(v1,v2) — также число.
• Раз v1[0]*v2[0] — число, то и v1[0], и v2[0] — числа. Следовательно, v1 и v2 — массивы чисел.

В этом рассуждении были использованы типы операций «+», «*», «[]», с помощью которых была составлена система ограничений, решение которой позволило выяснить типы dot, v1, v2.

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

Алгоритм и сама возможность вывода типов целиком зависят от используемой системы типов.

Исходная информация для алгоритма вывода типов — сама программа, способ присваивания типов литералам (таким как 42.0f, “hello”, и т. п.), типы некоторых функций и значений, а также правила типизации синтаксических конструкций (типы встроенных арифметических операций, типы операций доступа к структурам данных, взятые из определений этих структур, и т. п.). Правила типизации синтаксических конструкций и литералов обычно фиксированы в рамках одного алгоритма вывода типов.

Наиболее известный, простой и широко применяющийся алгоритм вывода типов — алгоритм Хиндли—Милнера (описан в Wikipedia в статье «Type inference» [21]), пригодный для таких систем, как просто типизированное лямбда-исчисление, System F (ее ограниченное подмножество) и некоторых других. System F является основой систем типов большинства современных функциональных языков, таких как OCaml и Haskell. Она описана, например, в презентации Александра Микеля «An introduction to System F» [118], учебнике Жирара, Лафонта и Тейлора «Proofs and types» [71], и в классическом учебнике Бенджамина Пирса «Types and programming languages» [139].

Мы не будем приводить этот алгоритм здесь, так как он описан в многочисленных публикациях, доступных в Интернете.

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

В качестве примера полезности вывода типов лучше подойдет Java: начиная с версии 5 в этом языке появились «дженерики» (generics: классы и методы, параметризованные типами), и в некоторых случаях компилятор способен вывести конкретные значения типовых параметров при вызове метода, например:

вместо

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

В программах на языках с мощной системой типов, скажем, языках семейства ML, лаконичность кода во многом обусловлена именно тем, что программист может не указывать типы большинства выражений. Обычно типы указывают только для объявлений верхнего уровня, в качестве документации. Например, вот фрагмент кода из библиотеки для чтения tar-архивов [46] на Haskell:

В этом фрагменте кода не указаны типы checksum' и header', типы x и y в выражении \\x y -> x + ord y, а также тип значения, возвращаемого этой анонимной функцией.

Вывод типов вкупе с классами типов (см. 13) зачастую позволяет добиться огромной экономии кода, которая была бы невозможна даже в языке без статической системы типов. Рассмотрим пример из статьи о классах типов и полюбуемся, что с ним станет, если отказаться от вывода типов; в частности, от вывода аргументов полиморфных (параметрических) типов (то, чего не умеет делать компилятор Java 6)¹:

До:

После: (это не совсем Haskell: в Haskell более сложный синтаксис явного указания типов)

Реализация
Большинство современных языков программирования обладают элементами вывода типов в той или иной форме.

• Все используемые на практике статически типизированные языки способны производить вывод типов выражений «снизу вверх», позволяя программисту писать выражения вида order.getCustomer().getName() (тут из типа order автоматически выводится тип выражения order.getCustomer() и компилятор убеждается, что для этого типа определена операция getName()).
• C++ может выводить типы шаблонных аргументов шаблонных функций из типов их фактических параметров («снизу вверх»). В C++0x появится ключевое слово auto, позволяющее автоматически выводить тип выражения, стоящего в правой части, при объявлении переменной.
• В C# начиная с версии 3.0 также доступен вывод типов инициализирующих выражений при объявлении переменных при помощи ключевого слова var.
• Java, аналогично, позволяет в некоторых простых случаях выводить типовые аргументы методов-дженериков, но не классов и, как ни странно, не конструкторов (до Java 7).
• В Scala присутствует механизм вывода типов выражений и типовых аргументов дженериков, однако вывод типов является локальным, т. е. полные типы выражений выводятся из контекста, в котором эти выражения упоминаются, без составления какой-либо системы ограничений между выражениями в разных местах программы (например, между типами двух методов класса); как следствие, явное указание типа довольно часто все же оказывается необходимым.
• В Haskell, OCaml и F# (представляющем собой подмножество OCaml, расширенное в сторону совместимости с объектной системой .NET и т. п.) вывод типов основан на алгоритме Хиндли — Милнера; в случае Haskell алгоритм дополнен обработкой специфических особенностей системы типов Haskell (классов типов (см. 13), «семейств типов» и т. п.)
• Coq (язык формулировки математических теорий и программирования, основанный на зависимых типах — [7], описан в книге «Coq’art: Interactive theorem proving and program development» [40], а также в презентации Евгения Кирпичёва [181]) отчасти использует алгоритм Хиндли — Милнера с определенным количеством эвристик, однако его система типов настолько сложна и мощна, что вывод типов в ней является вычислительно неразрешимой задачей, поэтому очень часто типы приходится указывать вручную.

3  Функция высшего порядка (ФВП)
(Higher-order function (HOF))

Суть
Функция, принимающая на вход или возвращающая функцию.

История
В некоторых областях математики (например, в функциональном анализе) функции высшего порядка называются операторами или функционалами. Скажем, оператор вычисления производной является функцией высшего порядка: он действует над функциями, и к тому же, его результатом является также функция. В программировании самые ранние из объектов, схожих с функциями высшего порядка — это «комбинаторы» в комбинаторной логике и термы в нетипизированном лямбда-исчислении. Обе этих области науки на самом деле появились задолго до возникновения программирования, в районе 1920—1930-х гг., однако со временем стали его неотъемлемыми элементами. Первым языком программирования с поддержкой функций высшего порядка оказался появившийся еще в 1958 году LISP, изначально являвшийся в первую очередь реализацией лямбда-исчисления. Эта возможность оказалась настолько удобна для программирования, что стала одной из основных составляющих функциональных языков как таковых и одним из самых мощных инструментов абстракции. Тем не менее, в течение очень долгого времени в силу ряда трудностей реализации (см. секции «Имитация» и «Реализация») «промышленные»-языки предоставляли крайне ограниченную поддержку функций высшего порядка. В последние годы их полезность была осознана и оценена широким сообществом программистов по достоинству, и в настоящее время они поддерживаются в той или иной форме практически всеми языками уровня выше Си.

Интуиция
Рассмотрим два отчасти взаимосвязанных примера:

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

С другой стороны, в движке СУБД процедура анализа секции ORDER BY должна принимать на вход ее синтаксическое дерево и возвращать способ сравнения строк таблицы согласно заданным в ней параметрам. В данном случае результатом одного вычислительного процесса является описание другого.

Отметим, что описать (задать) вычислительный процесс можно несколькими способами, различающимися по удобству и универсальности:

• Зафиксировать способ описания (задания) вычислительных процессов, подходящий для конкретной задачи. Например, в задаче сортировки рядов базы данных по полям это может быть структура данных, соответствующая конструкции ORDER BY в SQL. Очевиден недостаток такого подхода: необходимо в каждой очередной задаче организовывать подобную инфраструктуру интерпретации встроенного языка. Тем не менее, в отдельных случаях он вполне оправдан: например, может быть необходимо в целях эффективности ограничить класс возможных вычислительных процессов. Самый яркий пример такой ситуации: большинство графических библиотек ограничивают возможные преобразования изображений аффинными и перспективными, поскольку они допускают чрезвычайно эффективное в реализации и удобное для манипуляций матричное представление.
• Заставить программиста описать все возможные происходящие в программе вычислительные процессы заранее (а именно, описать все процедуры) и разрешить манипуляцию указателями на функции. Этот подход применяется в языках Си, Pascal и многих других. Недостаток такого подхода в том, что число возможных манипулируемых процессов конечно и ограничено числом процедур в программе. К примеру, трудно динамически создать процедуру сравнения двух документов согласно их релевантности относительно пользовательского запроса, поскольку на этапе разработки программы пользовательский запрос неизвестен и невозможно заранее написать процедуру сравнения, уже содержащую его. Этим недостатком обладает процедура qsort из стандартной библиотеки Си: она позволяет задавать способ сравнения всего лишь при помощи указателя на функцию. Конечно, можно сохранить пользовательский запрос в глобальной переменной, и пользоваться ей в процедуре, переданной qsort, но этот способ обладает множеством очевидных недостатков, связанных с многопоточностью и реентерабельностью (reentrancy).
• Принять описанный в предыдущем пункте подход и разрешить лишь манипуляцию указателями на функции, однако задавать вычислительные процессы парами из указателя на функцию и произвольных данных. Теперь достаточно описать процедурами лишь типы принципиально различных происходящих в программе процессов, а конфигурирование их вынести в данные. Такой подход общепринят в языках, не реализующих замыкания (см. 4), в т. ч. в Си, Pascal и т. п. Приведем пример использования такого подхода:
  // pthread.h int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void*), void *arg); // main.c #include <pthread.h> typedef struct our_data { ... } our_data; void *our_thread(void *arg) { our_data *data = (our_data*)arg; ... } ... pthread_create(..., our_thread, (void*)some_data); ...

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

  Несколько подробнее этот подход описан в статье о замыканиях (см. 4).

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

Описание
Функция называется функцией высшего порядка, если один из её аргументов — это функция, либо её возвращаемое значение — это функция.

Например:

1. процедура сортировки принимает на вход список данных и функцию сравнения элементов;
2. в движке базы данных процедура анализа секции ORDER BY принимает на вход ее синтаксическое дерево и возвращает соответствующую процедуру сравнения строк таблицы;
3. процедура численного дифференцирования принимает на вход спецификацию требуемой точности и вещественную функцию одного аргумента f, а возвращает также вещественную функцию, отображающую x в f′(x), вычисленное с указанной точностью;
4. процедура вычисления композиции функций принимает на вход две функции f и g, а возвращает функцию h, отображающую x в f(g(x))

Вот несколько примеров типов функций высшего порядка на Haskell:

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

Из-за некоторой путаницы с тем, что понимать под порядком функции при наличии каррирования (считать ли isAsubstringOfB функцией второго порядка из-за того, что результат ее применения к одному аргументу — функция первого порядка типа String -> Bool?), иногда порядком функции считают глубину самой вложенной слева стрелки: ниже приведены три типа, соответствующих функциям первого, второго и третьего порядков.

Здесь foldr — процедура правой списочной свертки (см. 11).

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

В статье «Functional pearl: Why would anyone ever want to use a sixth-order function?» [126] Крис Окасаки показывает, какое практическое применение может быть у функций чрезвычайно высоких порядков, вплоть до шестого.

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

• Оператор отображения списка map:
  map :: (α -> β) -> [α] -> [β] > map toUpper ["Hello", "World"] ["HELLO", "WORLD"]
• Оператор фильтрации списка filter:
  filter :: (α -> Bool) -> [α] -> [α] > filter even [1..10] [2,4,6,8,10]

Операторы отображения, фильтрации и списочной свертки есть не только в функциональных языках, но и, например, в Python и Ruby.

• Оператор обращения к массиву (списку) или к словарю: входом оператора является массив (список) или словарь, а выходом — функция из индекса (соответственно целого числа или ключа словаря) в соответствующий элемент коллекции. Данный оператор очень удобно использовать вместе с оператором отображения: скажем, можно «одним махом» получить из списка ключей список соответствующих им значений, преобразовав с помощью функции map список функцией обращения к словарю.
• Оператор построения словаря из списка ключей и функции: к каждому ключу применяется функция построения значения, и из полученных пар составляется словарь.
• Оператор построения списка при помощи порождающей функции: на входе задается размер списка n и процедура с одним аргументом, и ответ составляется из результатов применения процедуры к числам в диапазоне 0 … n−1.

Многие функции высшего порядка оперируют на более абстрактном уровне, не над данными, но над другими функциями:

• Оператор смены базиса бинарной операции on:
  on :: (β -> β -> gamma) -> (α -> β) -> (α -> α -> gamma) g `on` f = \x y -> g (f x) (f y) equalsIgnoreCase = (==) `on` toUpper
• Оператор смены порядка аргументов бинарной операции flip:
  flip :: (α -> β -> gamma) -> (β -> α -> gamma) flip f = \b a -> f a b
• Оператор вычисления в заданной точке at:
  at :: α -> (α -> β) -> β at x = \f -> f x -- Alternative definition: ($) f x = f x at = flip ($)
• Имея функцию из X в значение обнуляемого² типа Y, и «значение по умолчанию», можно получить функцию из X в Y, заменяющую нулевой результат первой функции на значение по умолчанию.

Существует множество полезных функций высшего порядка для работы с парами:

• Имея функцию из X в Y, можно естественным образом получить функцию из X в пару (X,Y).
• Имея функцию из X в Y, можно получить функцию из (Z,X) в (Z,Y) или из (X,Z) в (Y,Z).
• Имея функцию из X в Y и из X в Z, можно получить функцию из X в (Y,Z).
• Имея X, можно получить функцию из Y в (X,Y) или в (Y,X).
• Существуют функции взятия первого и второго компонентов пары, удобные для использования с вышеупомянутыми.

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

Функции высшего порядка часто используются вместе с бесточечным стилем (см. 6).

Функции высшего порядка позволяют уменьшить избыточность в программе и сократить код, что положительно влияет на корректность (меньше мест для совершения ошибки — меньше ошибок) и поддерживаемость (не надо делать изменения во множестве похожих мест в коде: достаточно изменить код, абстрагирующий их сходство). Особенно остро это проявляется в многопоточном программировании, где необходимо управлять несколькими процессами — скажем, «периодически выполнять заданное действие, не допуская, чтобы оно выполнялось одновременно два раза», или «параллельно применить функцию к каждому элементу списка», или «выполнить набор заданий, пользуясь не более чем 10 нитями», или «асинхронно выполнить заданное действие и в случае успеха передать его результат следующему действию» и т. п. Корректная реализация многопоточных алгоритмов — чрезвычайно трудоемкое дело со множеством нюансов. Этим объясняется тот факт, что библиотеки многопоточного программирования даже в императивных языках буквально напичканы функциями высшего порядка. Скажем, рассмотрим стандартную библиотеку Java; в ней процедуры (равно как и процедуры высшего порядка) моделируются при помощи объектов:

• java.util.concurrent.Callable<V> — процедура без аргументов, возвращающая V.
• java.util.concurrent.ExecutorService — класс, позволяющий асинхронно выполнять задания и дожидаться их результатов. Задания задаются в виде процедур типа Callable или Runnable.
• java.util.TimerTask содержит в себе процедуру без аргументов и без возвращаемого значения.
• java.util.Timer периодически выполняет процедуры типа TimerTask.
• В Java 7 появится ParallelArray – средство для параллельной обработки массивов. API этой библиотеки целиком построен на функциях высшего порядка. Вот пример его использования:
  ParallelArray<Student> students = new ParallelArray<Student>(fjPool, data); double bestGpa = students .withFilter(isSenior).withMapping(selectGpa).max(); static final Ops.Predicate<Student> isSenior = new Ops.Predicate<Student>() { public boolean op(Student s) { return s.graduationYear == Student.THIS_YEAR; } }; static final Ops.ObjectToDouble<Student> selectGpa = new Ops.ObjectToDouble<Student>() { public double op(Student student) { return student.gpa; } };
  В нотации замыканий (см. 4), которую, однако, не планируется включать в Java 7 (планируется включить несколько иную нотацию), этот пример выглядел бы так:
  double bestGpa = students .withFilter ({ Student s => (s.graduationYear == THIS_YEAR) }) .withMapping({ Student s => s.gpa }) .max();

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

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

Реализация
Многие современные языки общего назначения (C, Pascal) позволяют манипулировать указателями на функции (многие компиляторы Fortran не позволяют даже этого).

Все функциональные языки (Haskell, OCaml, Scheme, Clean, ...) и большинство динамически типизированных языков (Python, Ruby, Javascript) позволяют манипулировать функциями как полноценными значениями, позволяют использовать замыкания (см. 4), анонимные функции (лямбда-выражения).

Функциональные языки с мощной системой статической типизации (Haskell, OCaml, Clean, ...) поощряют обильное использование функций высшего порядка.

Имитация
Способ имитации полноценных функций высшего порядка в языках семейства Си описан в секции «Интуиция».

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

В стандартной библиотеке Java объекты, схожие по свойствам и назначению с функциями, и использующие их объекты, схожие, таким образом, с ФВП, встречаются достаточно часто:

• Описанные выше многопоточные средства.
• Класс TreeMap и процедура сортировки Collections.sort параметризуются процедурой сравнения, моделируемой классом Comparator.
• Метод Collections.reverseOrder(Comparator<T>) принимает на вход функцию сравнения и возвращает функцию сравнения в обратном порядке.
• Паттерны Visitor и Listener, описанные в классической книге «банды четырех» о шаблонах проектирования ([68]) имеют явное сходство с ФВП; последний используется, например, в оконной библиотеке Swing.

4  Замыкание
(Closure)

Суть
Функция, использующая переменные из области видимости, в которой была создана.

История
Правила вычисления в лямбда-исчислении таковы, что лямбда-выражение может использовать переменные, связанные какой-нибудь из окружающих его лямбда-абстракций. Возьмем, например, ((λ x.(λ y.x))42)37 =⇒ (λ y.42)37 =⇒ 42: здесь выражение λ y.x «запоминает» значение определенного во внешней области видимости идентификатора x. Таким образом, идея замыканий появилась еще до появления программирования, в момент создания лямбда-исчисления — в 1930 гг. Термин «замыкание» был введен в 1964 г. Питером Ландиным. Замыкание — это пара из лямбда-выражения («кода») со свободными переменными и окружения, связывающего их. Внутри замыкания все переменные связаны, т. е. оно замкнуто. Первая полноценная реализация лексических замыканий относится к языку Scheme (диалект LISP, 1975 г.). В настоящее время они поддерживаются в той или иной форме почти всеми популярными языками общего назначения, кроме низкоуровневых, таких как C или C++ до версии C++0x (не считая эмуляции замыканий, например, при помощи boost::function — впрочем, надо отдать должное, достаточно удобной).

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

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

Рассмотрим пример ее применения: напишем процедуру, которая принимает в качестве аргумента словарь и возвращает функцию поиска в этом словаре по ключу.

Затем при помощи этой функции достанем из словаря по списку ключей список значений.

Как видно, функция fetch использует значение аргумента dict функции values, потому объявлена в теле values.

Переменная dict не является аргументом или локальной переменной fetch — она является свободной относительно определения fetch. Однако, она является аргументом fetcher и потому связана относительно определения fetcher.

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

Представим, как выглядел бы этот код, если бы Python, как стандартный Си, разрешал объявлять функции только на верхнем уровне файла, и, таким образом, свободными переменными в определении функции могли бы быть только глобальные переменные программы.

Если объявлять процедуру fetch на верхнем уровне, то в контексте ее тела неоткуда взять dict, т. к. он не является и не может являться глобальной переменной.

К счастью, Python разрешает объявлять одни процедуры внутри других. В менее мощных языках можно попробовать применить «лямбда-поднятие (lambda lifting)» или «преобразование замыканий». Этот подход описан в статье об ФВП (см. 3). Представим n-аргументную функцию как пару из n+1-аргументной и значения вспомогательного n+1-го аргумента. При n=1 подход выглядит так:

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

Как видно, для использования ФВП необходима поддержка замыканий со стороны языка.

Описание
Итак, замыкание — это значение (обычно процедура), имеющее доступ к переменным из области видимости, в которой оно было создано. В некоторых языках (в функциональных языках, в Python, Ruby, Javascript, …) нет разницы между замыканиями и обычными процедурами. В других же языках замыкания приходится эмулировать.

Замыкания жизненно важны для использования функций высшего порядка; без замыканий становится невозможно использовать сколько-нибудь полезную ФВП (как мы видели выше на примере map, написать полезную ФВП возможно, однако нетривиальные варианты ее использования оказываются недостижимыми).

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

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

Реализация замыканий связана с двумя вопросами, называемыми вместе «проблемой функционального аргумента (фунарг-проблемой)»⁴:

• Upward funarg problem (наружняя фунарг-проблема)⁵: как реализовать возврат замыкания в качестве результата? Поскольку замыкание использует переменные, связанные в области видимости, где оно было создано (или еще выше), то цикл жизни этих переменных должен продлиться, по крайней мере, до последнего использования этого замыкания — возможно, даже после выхода из создавшей их области видимости (например, после возврата из процедуры, возвратившей это замыкание).

  Скажем, стратегия выделения переменных на стеке уже не подходит, поскольку они уничтожатся при выходе из процеруры, и замыкание, ссылавшееся на них, испортится. Таким образом, все переменные, используемые замыканиями, должны либо подвергаться глубокому копированию (копия не должна зависеть от существования исходных переменных), либо создаваться в куче и уничтожаться при помощи какого-либо механизма сборки мусора (во всяком случае, нужна какая-то договоренность относительно того, кто и в какой момент уничтожает такие переменные). Стратегия с копированием лишает замыкания некоторых интересных вариантов использования, описанных далее. Поэтому полноценная поддержка замыканий (и полноценное решение upward funarg problem) присутствует почти исключительно в языках со сборщиком мусора. Существуют, впрочем, и другие решения, основанные на статическом анализе кода: т. н. escape analysis (анализ времени жизни), region inference (вывод регионов), ownership types (типы владения) и т. п., однако они пока не получили широкого распространения.

• Downward funarg problem (внутренняя фунарг-проблема): как реализовать возможность передачи замыкания в качестве аргумента процедуре? Проблема в данном случае состоит лишь в том, как обеспечить одинаковое представление обычных процедур и замыканий, так, чтобы процедура могла принимать в качестве аргумента другую процедуру, не заботясь о том, является ли она замыканием. В отличие от upward funarg problem, в данном случае предполагается, что передаваемое замыкание не сохраняется процедурой в глобальных переменных, и, таким образом, оно существует лишь во время ее вызова: благодаря этому исчезают проблемы управления памятью. Решения downward funarg problem существуют даже в языках без сборки мусора: так, компилятор GCC поддерживает (в качестве нестандартного расширения языка Си) передачу указателей на «вложенные функции» в другие функции при помощи техники «трамплинов» — маленьких динамически генерируемых и компонуемых фрагментов кода. Эта возможность также поддерживается языком Pascal (но, как и в случае GCC, без решения наружней фунарг-проблемы). Можно считать решением внутренней фунарг-проблемы и перегрузку оператора () в C++: язык позволяет в некоторых ситуациях одинаковым образом работать с функциями, указателями на функции и объектами, для чьих классов переопределен оператор (), а объекты, в свою очередь, позволяют эмулировать замыкания.

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

В Scheme разрешено изменять значения переменных из родительской области видимости. Для реализации этой функциональности используется «модель окружений»:

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

За подробным описанием модели окружений предлагается обратиться в один из авторитетных источников: например, в книгу «Структура и интерпретация компьютерных программ» [32] (глава 3.2).

В классической работе Стрейчи «Fundamental concepts in programming languages» [161] в секции 3.4.3 «Modes of free variables» также обсуждается вопрос изменяемости захваченных переменных.

Использование
Чаще всего замыкания появляются при использовании функций высшего порядка (см. 3); см. соответствующий раздел. Однако у замыканий есть два других интересных свойства, открывающих совершенно иные и очень интересные варианты использования:

• Замыкание может использовать изменяемые данные (если язык это позволяет).
• Несколько замыканий могут совместно использовать переменные из одной и той же области видимости.

Рассмотрим их по очереди.

Вот код на Scheme, реализующий счетчик при помощи замыкания:

В этом примере x и y — два замыкания, каждое со своим собственным состоянием.

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

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

Значительно более интересный пример использования замыканий с изменяемым состоянием для эмуляции объектов можно найти в главах 3.3.4 и 3.3.5 книги «Структура и интерпретация компьютерных программ» [32]: в них строится симулятор цифровых схем и симулятор схем с распространением ограничений.

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

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

Например, можно взять вместо вещественных чисел логические значения, вместо умножения — операцию «И», вместо сложения — операцию «ИЛИ», а вместо нуля — False.

Матрицы над этим полукольцом полезны, в том числе, для поиска компонент связности графа (при возведении матрицы инцидентности в n-ю степень получится матрица, в чьем (i,j)-м компоненте стоит True, если и только если вершины i и j связаны путем длиной в n−1 шаг). Если же рассмотреть матрицы над вещественными числами и полукольцом, где вместо сложения и умножения — операции взятия сложения и минимума (это полукольцо называется «тропическим»), то такие матрицы можно использовать для поиска кратчайших путей в графах. У них есть и другие применения: см., например, статью Дэна Пипони «An Approach to Algorithm Parallelization» [140].

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

В данном случае make-linalg принимает на вход функцию сложения, функцию умножения и нейтральный элемент по сложению, и возвращает набор процедур линейной алгебры над этими операциями. Как видно, возвращается процедура, принимающая на вход произвольный запрос, сопоставляющая (см. 10) его с несколькими образцами и вызывающая одну из «рабочих» процедур, определенных внутри make-linalg. Эти процедуры являются замыканиями и используют данные из semiring и из локальных переменных @+@, @*@, +0+.

Данный пример также иллюстрирует имитацию классов типов (см. 13) при помощи «dictionary-passing style» (см. в статье о классах типов): имитируется класс типов «Полукольцо» примерно следующего вида:

Реализация
Практически все появляющиеся в последнее время языки поддерживают замыкания. Замыкания реализованы в той или иной форме в большом количестве функциональных (Haskell, OCaml, Lisp, F# и др.), динамических (Python, Ruby и др.) и императивных (C# и др.) языков.

«Классический» и наиболее интуитивно понятный вариант поддержки замыканий с моделью окружений реализован в языке Scheme.

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

Javascript известен своими неочевидными правилами, связанными с областями видимости (см. блог-пост «A huge gotcha with Javascript closures and loops» Кейта Ли [108]); эти же проблемы есть также и в C# (см. пост на StackOverflow «Problem with delegates in C#» [16] с примером такой проблемы, а также статью «The Beauty of Closures» [155] о различиях в стратегиях захвата переменных в C# и Java).

Замыкания можно ограниченно смоделировать при помощи анонимных классов в Java. Существуют планы включить более удобную синтаксическую поддержку замыканий в Java 7. Из-за отсутствия общей точки зрения на детали реализации и синтаксиса эта возможность была отложена, однако в ноябре 2009 г. ситуация неожиданно изменилась ([146]), и, возможно, замыкания все же будут включены в язык (впрочем, в предложенном варианте имеется множество проблем, описанных Нилом Гафтером в письме [67]).

Замыкания также планируется включить в стандарт C++0x (однако без автоматического управления памятью их полезность несколько снижается; в частности, стандарт обязывает программиста явно указывать, желает ли он копировать значения свободных переменных или же использовать их по ссылке — но в этом случае их время жизни ограничено временем жизни области видимости, создавшей их, а за ее пределами обращение к такой переменной порождает «неопределенное поведение»).

Python реализует замыкания сходным с Java образом: модифицировать захваченные переменные запрещено (хоть это и проверяется во время выполнения, а не во время компиляции).

Имитация
Часть способов имитации замыканий описана в статье о функциях высшего порядка (см. 3).

Процесс устранения замыканий с помощью введения вспомогательных аргументов называется преобразованием замыканий (closure conversion), или лямбда-поднятием (lambda lifting) и применяется в качестве стадии компиляции во многих компиляторах функциональных языков. Это преобразование было предложено Томасом Джонсоном в статье «Lambda lifting: transforming programs to recursive equations».

В объектно-ориентированных языках замыкания и лямбда-выражения можно имитировать с помощью объектов, объектных литералов или анонимных классов.

Также существует техника дефункционализации — способ преобразования программы, использующей функции высшего порядка («программы высшего порядка») в программу первого порядка, использующую только функции первого порядка и дополнительные структуры данных. Дефункционализация хорошо описана в статье «Defunctionalization at work» Оливье Дэнви и Лассе Нильсена [58], а также в потрясающей диссертации Нила Митчелла «Transformation and analysis of functional programs» [119] и в его отдельной статье [120] и слайдах [121] о дефункционализаторе firstify «Losing functions without gaining data».

При дефункционализации программ высшего порядка зачастую получаются знакомые и несколько неожиданные алгоритмы: к примеру, из программы, составляющей список узлов дерева при помощи разностных списков, получается программа, использующая хвосторекурсивный алгоритм (см. 7) с аккумулятором. Разностные списки были предложены Джоном Хьюзом в статье «A novel representation of lists and its application to the function reverse».

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

Дефункционализация также используется и для оптимизации программ высшего порядка, поскольку часто производительность дефункционализованной программы оказывается выше за счет использования более простых, эффективных и «близких к железу» операций. Дефункционализация не решает проблемы управления памятью под свободные переменные замыканий и по-прежнему требует сборки мусора либо ручного управления. Однако существуют другие техники, позволяющие частично или полностью решить проблемы управления памятью: например, т. н. типы владения (ownership types) (описаны в статье «Ownership types for object encapsulation» [44], один из авторов которой — Барбара Лисков), вывод регионов (region inference) (описан в статье «Region-based memory management» Мэдса Тофте и Жана-Пьера Талпена [167] и в книге «Design concepts in programming languages» [169]).

5  Частичное применение, карринг и сечения
(Partial application, currying and sections)

Суть
Фиксацией некоторых аргументов из функции получается новая функция с меньшим числом аргументов.

История
Согласно классическому труду Хенка Барендрегта «Lambda calculi with types» [36] и статье Хиндли и Кардоне «History of lambda-calculus and combinatory logic» [47], понятие карринга было введено Шейнфинкелем в 1924 г. при создании комбинáторной логики (статья «Über die Bausteine der mathematischen Logik» [151], перевод на английский язык «On the building blocks of mathematical logic» [152]) для избавления от нужды в функциях с несколькими аргументами — как один из этапов перехода от «традиционного» математического языка к языку комбинаторной логики, где понятие аргумента и функции вовсе отсутствуют. Позднее (в 1930 гг. и далее) это понятие использовалось Хаскеллом Карри (он, однако, много раз явно указывал на роль Шейнфинкеля как «первооткрывателя»), и было названо по его имени «каррингом» уже Кристофером Стрейчи в 1967 г. в его знаменитой работе «Fundamental concepts in programming languages» [161]⁷.

Интуиция
Рассмотрим процедуру, определяющую, удовлетворяет ли строка регулярному выражению.

Применим ее, скажем, для валидации целых чисел:

Получается: «Число — это такая строка s, что s удовлетворяет регулярному выражению -?[-0-9]+». Но почему бы не сказать покороче? «Число — это то, что удовлетворяет регулярному выражению -?[0-9]+»:

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

Наличие процедуры makeMatcher позволяет не плодить вспомогательные функции и лямбда-абстракции вида \s -> matchesRegexp “-?[0-9]+” s или isNumber s = matchesRegexp “-?[0-9]+” s⁸.

Описание
Рассматриваемые термины (частичное применение, карринг) имеют смысл только в языке, где функции могут обладать несколькими аргументами (арностью более 1). Поэтому будем считать, что речь идет именно о таком языке.

Частичным применением n-арной функции f называется конструкция, значением которой является (n−k)-арная функция, соответствующая f при фиксированных значениях некоторых k из n аргументов. Например, в гипотетическом языке программирования частичное применение функции drawLine может выглядеть вот так:

В данном случае фиксируются 2 аргумента 5-арной функции drawLine и получается 3-арная функция thinSolidLine.

У термина «карринг» есть три взаимосвязанных значения.

Первое из них — частный случай частичного применения, при котором фиксируется несколько первых аргументов функции:

В этом примере thinLine получен фиксацией первого аргумента drawLine⁹.

Второе — превращение функции F над 2-местным кортежем (парой с типами компонентов X и Y) в функцию над X, возвращающую функцию над Y (такая функция называется «каррированной» версией F):

В этом примере matchesRegexpCurried называется каррированной версией matchesRegexpUncurried, а сам процесс выражения matchesRegexpCurried через matchesRegexpUncurried называется каррингом.

Такое преобразование легко выразить в общем виде и оно оказывается достаточно полезным, чтобы быть включенным, например, в стандартную библиотеку Haskell¹⁰:

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

Третье значение термина «карринг» — применение каррированной функции к аргументам:

В таком случае говорят, что процедура isNumber получена каррированием процедуры matchesRegexpCurried.

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

Для бинарных операций примерно одинаково часто встречается необходимость зафиксировать их левый и правый аргумент, поэтому, к примеру, Haskell предоставляет одинаковый синтаксис для обоих вариантов:

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

Эти варианты применения называются соответственно левым и правым сечениями функции.

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

Из игры «Space invaders» (hinvaders) [143]:

В этом примере используется карринг функции moveSprite.

Из утилиты «Bookshelf» [33] для каталогизации документов:

В строках (1), (2) и (3) используются сечения: соответственно левое, правое и снова правое.

Из библиотеки для работы с zip-потоками zlib [56]:

Функции decompressWith и decompress определены через друг друга при помощи карринга и втроем предоставляют различные уровни настраиваемости декомпрессии.

Карринг играет очень большую роль в удобстве пользования функциями высшего порядка (см. 3) и бесточечным стилем (см. 6). Это видно, например, в приведенном выше фрагменте кода из Bookshelf.

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

При другом порядке аргументов такая оптимизация была бы затруднена.

Реализация
Карринг реализован почти во всех языках семейства ML, в частности в Haskell, OCaml, F#, Scala (однако в Scala синтаксис объявления каррируемых и не-каррируемых функций различается), Coq и других. В языке OCaml реализован более удобный вариант частичного применения за счет поддержки именованных параметров; см. блог-пост «Curried function and labeled arguments in Ocaml» Педро дель Галлего [59]. В Scala также реализован довольно удобный вариант частичного применения: неявный аргумент обозначается за \_, например, goodThings.contains(\_) обозначает функцию, по x возвращающую goodThings.contains(x).

С точки зрения компиляции в эффективный код поддержка карринга в языке имеет свои тонкости: см., например, статью «Making a fast curry: push/enter vs. eval/apply for higher-order languages» [112] от авторов компилятора GHC Саймона Марлоу и Саймона Пейтона-Джонса, однако существуют техники преобразования программ (дефункционализация: см. ссылки в главе о функциях высшего порядка (см. 3), в секции «Имитация»), позволяющие получить из программы эквивалентную ей программу, не использующую карринг и функции высшего порядка и, вследствие этого, лучше поддающуюся компиляции в эффективный код.

В языках, поддерживающих процедуры с нефиксированным числом параметров, карринг в общем случае реализовать невозможно, т. к. если foo — процедура с произвольным числом параметров, то непонятно, как интерпретировать, скажем, foo a b c: как применение foo к трем аргументам a,b,c, или же как функцию от оставшихся аргументов (по-прежнему произвольного количества)? Например, к таким языкам относятся диалекты Lisp, в частности, Scheme, а также Ruby, Python, Perl и т. п. Впрочем, в таких языках, конечно же, остается возможность использовать карринг для процедур, число аргументов которых известно. Например, вот процедура curry на Scheme, аналогичная приведенной выше процедуре на Haskell:

Имитация
Имитация карринга возможна при помощи процедур, аналогичных определенной выше процедуре curry. Для этого, очевидно, необходимо, чтобы язык поддерживал замыкания (см. 4) (поскольку замыкание, возвращаемое curry, использует аргумент curry, т. е. «замыкается» над каррируемой процедурой) и функции высшего порядка (см. 3) (т. к. процедура curry, принимая на вход функцию и возвращая функцию, является ФВП).

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

Существует также интересный паттерн проектирования «Curried Object» (описан в статье Джеймса Нобла «Arguments and results» [123]). Одно из его применений для облегчения многопоточной работы с изменяемым состоянием рассмотрено в статье «Изменяемое состояние: опасности и борьба с ними» Евгения Кирпичёва ([185]).

6  Бесточечный стиль
(Point-free style)

Суть
Сборка функций из других функций при помощи комбинаторов, без явного упоминания аргументов.

История
Идея описания функций без обращения к их аргументам берет свои корни из математики. Скажем, оператор Гамильтона («набла») определяется так:

.

В 1924 г., еще до создания лямбда-исчисления, Шейнфинкель создал комбинáторную логику — формализм, подобный лямбда-исчислению, однако не содержащий лямбда-абстракции, и, таким образом, избегающий необходимости в использовании переменных. Вместо лямбда-абстракции комбинаторная логика предоставляет набор базовых комбинаторов и правил редукции; в результате получается также Тьюринг-полный вычислительный формализм (при этом следует помнить, что комбинаторная логика создавалась до формализма Тьюринга и до появления компьютеров как таковых). Комбинаторная логика оказала огромное влияние на современные функциональные языки программирования семейства ML, такие как Haskell.

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

В современном понимании этого слова бесточечный стиль был, вероятно, впервые описан Джоном Бэкусом в его знаменитой лекции «Can programming be liberated from the Von Neumann style?» ([35]), прочтенной им на церемонии вручении премии Тьюринга в 1977 году. Бесточечный стиль описывается в ней на примере манипуляций со списками, векторами и матрицами. Таким образом демонстрируется удобство формального манипулирования бесточечными определениями для доказательства свойств определенных подобным образом функций.

Практическое применение бесточечный стиль нашел в вышеупомянутых языках семейства ML, развивавшихся с начала 1970 гг.

Пожалуй, последнее из существенных событий в истории бесточечного стиля — появление в начале 1990 гг. языка J, наследника APL. О нем см. ниже в секции «Реализация».

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

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

Такой стиль часто позволяет уменьшить количество лишней информации в определении функции, делая его более лаконичным и читаемым (см. пример в предыдущей секции), хотя и требует определенного привыкания. С другой стороны, злоупотребление бесточечным стилем влияет на читаемость крайне негативно: ср.  \\f g x y -> f (g x y) против (.).(.).

Использование
Бесточечный стиль в основном применяется в языках, поддерживающих каррирование (см. 5), функции высшего порядка (см. 3) и обладающих мощной системой типов — таких, как Haskell, Clean, OCaml, F#. Однако, из соображений читаемости, бесточечные определения целых функций используются очень редко. Несравнимо чаще выражения в бесточечном стиле используются как часть определения. Рассмотрим несколько реальных примеров использования бесточечного стиля в программах на Haskell (намеренно выбраны очень простые примеры).

Пример из аркады «Monadius» [166]:

Код, отмеченный (1), (2), означает: При приходе сигнала нажатия клавиши key произвести над ячейкой keystate модификацию «добавить key и удалить дубликаты (nub)»; при сигнале отпускания — модификацию «убрать key». Первый из отмеченных фрагментов с использованием «точечного» стиля выглядел бы как \\s -> nub (s ++ [key]), второй — как \\s -> filter (\\k -> k /= key) s.

Пример из комбинаторной библиотеки graphics-drawingcombinators [130]:

Процедура colorFunc принимает на вход функцию преобразования цвета (например, увеличение прозрачности в 2 раза выглядело бы как \\(r,g,b,a) -> (r,g,b,a/2)) и картинку, а возвращает картинку, где цвет каждой точки изменен соответствующим образом. Процедура color закрашивает всю картинку одним цветом, подставляя в colorFunc функцию, везде равную заданному цвету. В «точечном» стиле процедура color выглядела бы так:

А в «еще более бесточечном» — так:

Пример из программы «jarfind» для поиска по jar-файлам [101]:

parseDataSource по описанию источника данных возвращает поток разобранных class-файлов. search по спецификации того, в каких классах искать (задается с помощью searchSource), что именно искать (сами классы или же методы/поля — searchTarget) и class-файлу возвращает список результатов (пар из найденного элемента и пути к файлу, содержащему его). В последней строчке данного примера написано: «Выполнить поиск во всех class-файлах из classes, сложить результаты, отформатировать и отобразить каждый из них».

И, наконец, пример использования бесточечного стиля на Java, из практики автора: фрагмент кода обнаружения DoS-атак по логам веб-сервера (см. также статью о комбинаторных библиотеках (см. 14)):

«Сессией» называется удовлетворяющий особым условиям участок последовательности запросов от одного IP-адреса. LogFunction<T> — «функция из лога в значение типа T», аналогично SessionFunction. Данный фрагмент кода манипулирует различными примитивными функциями и комбинаторами (к примеру, комбинатор moving соответствует применению заданной функции к временным подокнам определенной длительности) и собирает из них функцию, вычисляющую по логу скорость самой быстрой последовательности запросов.

И несколько воображаемых примеров:

• Ширина окна = наибольшая ширина составляющих:
  frameWidth = maximum . map componentWidth . windowContents
• Товар дорогой, если его цена превышает 100:
  isExpensive = (>100) . price
• Технари — те, у кого средняя оценка как по физике, так и по математике, превышает 4.5:

Реализация
Как уже говорилось выше, бесточечный стиль в основном применяется в языках семейства ML: Haskell, F# и т. п. Поддержка системы типов необходима для контроля за корректностью программ с использованием ФВП; ФВП необходимы в роли комбинаторов, собирающих более сложные функции из более простых; частичное применение избавляет от нужды в имитирующих его комбинаторах (к примеру, не будь карринга — понадобился бы комбинатор «зафиксировать первый из двух аргументов»: bind1st f x = \\y -> f x y — что и имеет место, к примеру, в C++ STL).

Также бесточечный стиль обильно используется в языках семейства APL, в т. ч. J (сайт [12]) и K ([13]). Чрезвычайно интересны и самобытны средства, предоставляемые для бесточечного программирования в языке J, где подавляющее большинство функций принято определять бесточечно. Язык J вводит понятия монадных (не путать с монадами из Haskell) и диадных глаголов (унарных и бинарных операций), «наречий» (модификаторов, применяемых к монаде или диаде для образования новой) а также вилок и крючков — особых синтаксических комбинаций нескольких монад или диад, образующих вместе новую монаду или диаду. Так, классический пример использования «вилки» и вообще краткости и стиля языка J — вычисление арифметического среднего:

Эту фразу следует читать как «среднее есть сумма, поделенная на длину», и она образована вилкой из монады суммирования списка +/ (где / — наречие свертки (см. 11)), диады деления \% и монады взятия длины \#. Описание разнообразных видов вилок и крючков можно найти, например, в онлайн-книге Роджера Стокса «Learning J», в главе 8 «Composing verbs» ([160]).

Наконец, стековые (конкатенативные) языки, такие как FORTH или Factor, также по своей сути располагают к бесточечному программированию.

Имитация
Использование бесточечного стиля в нефункциональных языках, не поддерживающих функции высшего порядка и частичное применение, сводится к имитации функций высшего порядка (например, с помощью объектов) и к имитации частичного применения (например, при помощи паттерна «Curried Object» (описан в статье Джеймса Нобла «Arguments and results» [123]). Пример использования бесточечного стиля на Java можно найти в статье и презентации «Функциональное программирование в Java» Евгения Кирпичёва ([183], [184]). Однако такое использование оправдано лишь в специфических случаях, когда действительно необходима крайне низкая синтаксическая нагрузка на конструирование функций при помощи комбинаторов (в основном, задачи сложной обработки данных).

7  Хвостовой вызов
(Tail call)

Суть
Применение функции, соответствующее замене одной вычислительной задачи на другую, вместо сведения одной задачи к другой.

История
Первый вычислительный формализм, в котором вообще можно говорить о «вызовах» — лямбда-исчисление. Семантика бета-редукций (аналог «вызова функции») в лямбда-исчислении основана на подстановке, а не на, скажем, операциях над стеком параметров и адресов возврата, поэтому можно сказать, что вычислители, основанные на лямбда-исчислении, поддерживают оптимизацию хвостовых вызовов в изложенном далее по тексту смысле. Несмотря на то, что язык LISP был фактически реализацией лямбда-исчисления, стандарт Common LISP не обязывает оптимизировать хвостовые вызовы. Первый язык программирования, поддерживающий оптимизацию хвостовых вызовов — Scheme (1975). Оптимизация хвостовых вызовов была впервые описана в статье «Lambda: The Ultimate GOTO» [95] из серии фундаментальных статей «Lambda Papers» Гая Стила и Джеральда Сассмана [159]. Статья описывает и способ реализации этой возможности языка, и ее применения¹¹.

Интуиция
Рассмотрим две простые процедуры над двоичными деревьями: поиск в двоичном дереве поиска и свертку (см. 11).

Будем считать, что деревья определены как алгебраический тип (см. 9) data Tree α = Leaf | Fork α (Tree α) (Tree α).

Структура решения такова: есть два «крайних» случая (пустое дерево Leaf и «вилка» Fork с искомым значением), а в каждом из двух оставшихся случаев задача поиска в дереве t заменяется на задачу поиска в другом дереве — в левой или правой ветке t. Если x < y, то отыскать x в Fork y l r — то же самое, что и отыскать x в l, и аналогично при x > y, то есть, ответ к исходной задаче совпадает с ответом к другой задаче.

Теперь рассмотрим свертку и небольшой пример ее применения — вычисление высоты дерева.

Структура решения такова: есть «крайний» случай — пустое дерево — и случай, требующий вычисления свертки в левом и правом поддереве и комбинирования результатов. Задача вычисления свертки над Fork x l r сводится к вычислению сверток над l и над r, то есть, ее ответ выражается через ответы других задач.

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

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

---

Рис. 1: Бинарное дерево, высота которого вычисляется в примере.

---

Вычисление высоты дерева на рис. 1 будет протекать так:

Запишем этот же вычислительный процесс в другой форме: будем указывать аргументы текущего вызова, а также то, как выражается окончательный результат через результат текущего вызова (то есть, «продолжение» текущего результата). Для краткости будем писать h вместо height.

Как видно, в данном процессе форма выражения окончательного результата через результат текущего вызова все усложняется по мере «погружения» рекурсивных вызовов в структуру данных. Представить такое продолжение можно в виде композиции стека «локальных» продолжений, имеющих в данной программе вид 1+max • (height …) или 1+max … • (продолжение текущего вызова относительно вызывающей процедуры).

Теперь рассмотрим поиск в дереве. Согласно системе уравнений (см. 10), задающих memberOf, можно записать следующую цепочку равенств:

И то же в форме с «продолжениями»:

Как видно, в этом вычислительном процессе на каждом шаге меняется лишь формулировка задачи, а ответ остается постоянным, и ответ на исходную задачу постоянно равен ответу на текущую, поэтому выражается через него как «•».

Итак, вызов называется хвостовым, если его продолжение в контексте вызывающей процедуры — «•». Эта точная формулировка соответствует принятым туманным определениям, вроде «вызов — последнее предложение (statement) в теле функции и является непосредственным аргументом return» и т. п.

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

При хвостовой рекурсии хвостовой вызов процедуры происходит из этой же самой процедуры. Это имеет место, например, в приведенной процедуре memberOf.

При взаимной рекурсии известна и фиксирована система процедур P₁,…,P_n такая, что во всякой из них вызов каждой из остальных является хвостовым. Вот чисто иллюстративный пример взаимно рекурсивной системы функций, задающих крайне неэффективный способ проверки неотрицательных целых на четность и нечетность:

Наконец, отметим, что любая программа может быть переписана так, чтобы в ней содержались только хвостовые вызовы. Для того, чтобы сделать все вызовы функции f хвостовыми, достаточно передавать этой функции ее продолжение в явном виде («реифицировать» (reify), или овеществить его). Это преобразование называется «преобразование в стиль передачи продолжений». Запишем преобразование для функции height в явном виде, для наглядности не выражая ее через свертку:

Здесь функции foldTree' в явной форме передается продолжение для ее результата. Рассмотрим для примера вычисление высоты более простого, чем рассмотрено выше, дерева: Fork 2 (Fork 1 Leaf Leaf) Leaf.

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

Добиться дальнейшего увеличения производительности или возможностей для преобразования или анализа можно, изменив представление передаваемого продолжения. Рассмотрим этот прием на примере вычисления высоты дерева. Как уже говорилось, продолжения рекурсивного вызова относительно вызывающей процедуры в данном случае имеют вид 1+max • (height …) или 1+max … •, а продолжение вызова относительно вызова верхнего уровня имеет вид списка из таких элементов. Определим соответствующую структуру данных явно.

Если внимательно проследить соответствие между этим фрагментом кода и предыдущим, то видно, что один получен из другого чисто механической трансляцией. Каждой из трех разновидностей замыканий (см. 4), использованных в качестве аргумента k в предыдущем фрагменте кода, сопоставлен свой конструктор типа Context, а аргументами являются свободные переменные этого замыкания. Использованная техника (дефункционализация) подробно описана в статье «Defunctionalization at work» Оливье Дэнви и Лассе Нильсена ([58]), а также в диссертации Нила Митчелла «Transformation and analysis of functional programs», один из разделов которой посвящен дефункционализатору firstify ([119], а также в статье «Losing functions without gaining data» [120], презентации [121]), и статье Митчелла Ванда «Continuation-based program transformation strategies» ([175]).

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

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

На самом деле в функциональных программах принято избегать рекурсии, а вместо этого абстрагировать ее в рекурсивные комбинаторы общего назначения, написанные раз и навсегда. Например, идиоматический вариант данной программы на Haskell выглядел бы так: mySum a b = sum [a..b] (где sum — встроенная функция в Haskell).

Система взаимнорекурсивных функций применяется для реализации конечных автоматов, причем реализация обычно получается значительно элегантнее, чем реализация при помощи цикла и switch или goto. Каждая функция соответствует одному состоянию. Рассмотрим, например, конечный автомат, подсчитывающий количество слов в тексте.

На рис. 2 приведена диаграмма состояний конечного автомата, соответствующего этой программе; сравните их.

---

Рис. 2: Конечный автомат для подсчета слов

---

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

Возможна ситуация, когда заранее неизвестно, какая именно функция вызывается хвостовым вызовом (например, происходит вызов функции, хранившейся в переменной или переданной в качестве аргумента). В первую очередь речь идет о конечных автоматах с заранее неизвестным набором состояний и о стиле передачи продолжений (CPS). См. также обширную и интересную серию постов Джо Маршалла «You knew I’d say something» на тему хвостовых вызовов, их роли и отличия от обычной «хвостовой рекурсии» и циклов [113].

Кроме того, аналогичная ситуация (отсутствие информации о том, какая функция вызывается хвостовым вызовом) возникает и при вызове виртуального метода в программе на объектно-ориентированном языке! См. «Why object-oriended languages need tail calls» Гая Стила ([158]) и «Functional objects» Маттиаса Феллайзена ([63]). В этих двух источниках приводятся аргументы, почему объектно-ориентированным языкам особенно необходима эффективная поддержка хвостовых вызовов. На форуме Lambda the Ultimate есть обсуждение этих двух статей ([156]).

Рассмотрим иной пример: поиск самого первого элемента в дереве, удовлетворяющего предикату.

Спецификация процедуры такова: Возвратить результат выполнения процедуры with-found над самым первым (в порядке обхода в глубину слева направо) элементом в дереве tree, удовлетворяющим предикату p; если же такого элемента нет, то возвратить результат выполнения процедуры when-notfound.

Идея решения состоит в том, что:

• если дерево пустое — надо возвратить результат «обработчика неудачи»;
• если дерево удовлетворяет предикату — надо выполнить над ним действие удачи;
• иначе — надо посмотреть в левом поддереве, причем если в нем нужного элемента не нашлось, то посмотреть в правом (а уж если там не нашлось, то выполнить обработчик неудачи). NB: это — вычисление для левого поддерева задачи, абсолютно аналогичной исходной, но всего лишь с другим «обработчиком неудачи»: оно отмечено курсивом.

Это и написано в приведенном коде на Scheme. Код написан с использованием стиля передачи продолжений: процедуре search передается дерево и «продолжение неудачи».

Заметим, что вызовы, отмеченные «(*)» — хвостовые. Посмотрим, что следует из того, что язык Scheme поддерживает полноценную оптимизацию хвостовых вызовов.

• Глубина стека вызовов при выполнении with-first будет постоянной.
• Потребление памяти, однако, не будет постоянным — в аргументе процедуры when-notfound будет выстраиваться неявный стек из заданий на обработку правых веток. Размер этого аргумента не будет превышать высоту дерева по левым веткам (т. е. максимальное количество левых поворотов по всем возможным путям в дереве).
• Если само дерево tree не удовлетворяет предикату, то задача сведется к вызову (search (left tree) search-right), для которого уже не требуется сам объект tree, и он может быть собран сборщиком мусора! Это неочевидное обстоятельство превращает поддержку хвостовых вызовов из простой «оптимизации, превращающей рекурсию в цикл» в мощное средство, способное кардинальным образом уменьшить потребление памяти некоторыми типами программ и упростить разработку программ, для которых своевременное освобождение памяти (в данном случае — данных узла) в подобных ситуациях критично (описано в «Proper tail recursion and space efficiency» Виллиама Клингера [55] и в серии постов Джо Маршалла «You knew I’d say something» [113]).

Поддержка оптимизации хвостовых вызовов обладает одним недостатком: трудно сохранить отладочную информацию о стеке вызовов. Существуют различные способы борьбы с этим: см.,  например, «A tail-recursive machine with stack inspection» Джона Клементса и Маттиаса Феллайзена ([54]), а также по ссылкам из упомянутой серии постов Джо Маршалла [113].

Еще одно применение поддержки TCO — возможность реализации очень необычных структур управления через преобразование всего кода в CPS на этапе компиляции. В этом случае все без исключения вызовы становятся хвостовыми, однако программа очень сильно усложняется и замедляется; требуются дополнительные этапы обработки кода, чтобы восстановить производительность. Плюс этого подхода — становятся возможными такие нестандартные структуры управления, как, например, call/cc, shift/reset («ограниченные продолжения», delimited continuations) и другие, реализовать которые без CPS-преобразования намного труднее. call/cc имеет множество интересных применений, многие из которых описаны в статье «Call with current continuation patterns» Даррелла Фергюссона и Деуго Дуайта [64]; огромное количество информации об этой и других разновидностях продолжений содержится на странице-библиографии «Continuations and Continuation Passing Style» [5]. CPS-преобразование кода используется в некоторых реализациях Scheme в качестве промежуточного этапа компиляции.

Реализация
Впервые полноценная поддержка оптимизации хвостовых вызовов (далее TCO) была реализована в языке Scheme; более того, это требуется стандартом языка.

Как ни удивительно, стандарт Common Lisp не требует TCO, хотя ряд реализаций ее все же предоставляют. В похожем на Lisp языке Mathematica она отсутствует.

TCO реализована в OCaml, в Prolog (насколько это понятие там вообще применимо), в Haskell (опять же, насколько это понятие там применимо).

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

В языках Scala (смесь Java и ML) и Clojure (диалект Lisp), компилирующихся в код для JVM, поддержка TCO также отсутствует, однако были придуманы обходные решения, пригодные в определенных ситуациях. Эти решения обсуждаются в соответствующих списках рассылки: сначала произошло обсуждение в рассылке Clojure (ветка «Trampoline for mutual recursion» [75], начатая самим Ричем Хикки), которое спровоцировало дискуссию в рассылке Scala (ветка «Tail calls via trampolining and an explicit instruction», начатая Джеймсом Айри [90]).

Существуют следующие подходы к реализации TCO в языке (первые два из них были предложены именно в статье Гая Стила «Lambda: the Ultimate GOTO» [95]):

• Изменение кода, генерируемого для вызовов, стоящих «в хвостовой позиции», т. е. таких, чье продолжение — •: при таком вызове после инструкций передачи аргументов вместо инструкции вызова (кладущей в стек адрес возврата) просто используется инструкция безусловного перехода. Простота этого подхода в низкоуровневых языках типа Си — лишь кажущаяся; на деле же имеющиеся попытки его реализации в компиляторе GCC (основная часть работы произведена Андреасом Бауэром в работе «Compilation of Functional Programming Languages using GCC — Tail Calls» [37]) до сих пор недостаточно успешны (см. баг 513007 в Debian Bug Database [92]), чтобы применять эту возможность широко и без каких-либо ограничений.
• Изменение кода, генерируемого для всех вызовов процедур: вместо того, чтобы класть в стек аргументы, а затем адрес возврата, поступают наоборот — сначала кладут адрес возврата, а затем аргументы, и выполняют безусловный переход по адресу начала вызываемой процедуры.
• Трамплины. Эта техника очень похожа на стандартный способ реализации конечного автомата при помощи цикла следующего вида:
  while(state != DONE) { state = state.workAndNext(); }
  Она подразумевает, что функция, вместо того, чтобы производить хвостовой вызов другой функции, лишь возвращает, какую функцию надо вызвать и с какими аргументами. Фактически же вызовы производятся в «основном цикле» указанного вида. Пример использования этой техники для имитации TCO можно найти в блог-посте Олега Царёва о парсере заголовочных файлов Си на Python ([188]).
• «Сборка мусора» над фреймами стека вызовов. В этом случае изменяется сам способ реализации вызовов процедур: стек вызовов организуется не в виде последовательной области памяти, а в виде фреймов, содержащих связывания формальных параметров с фактическими и указатель на родительский фрейм. Таким образом получается «спагетти-стек (spaghetti stack)», поскольку один и тот же фрейм может быть родительским для нескольких других. Основное преимущество этой техники — в том, что остается возможность получить доступ к стеку вызовов для отладочных и прочих целей. Подробнее прочитать об этой технике можно в статье «Tail-recursive stack disciplines for an interpreter» Ричарда Келси ([97]) — более того, в этой статье произведен довольно-таки полный, но понятный разбор существующих техник реализации хвостовой рекурсии. Техника сборки мусора используется в SISC Scheme (реализация Scheme для JVM) и Scheme48.

Имитация
Хвостовую рекурсию и взаимную рекурсию (т. е. ситуации, когда функция, чей вызов является хвостовым, известна статически) легко преобразовать в цикл. Схемы и примеры преобразований описаны в лекции 2 «Язык Scheme. Рекурсия и итерация» курса «Функциональное программирование» Евгения Кирпичёва [186] (также там описаны и некоторые другие приемы удаления или уменьшения кратности рекурсии).

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

Выше была описана еще одна техника — преобразование в CPS и последующая дефункционализация. Чтобы применить эту технику в императивном языке (где CPS-форма будет слишком трудна для представления), придется, скорее всего, временно переписать алгоритм на языке вроде Haskell, OCaml или Scheme, соптимизировать его и затем переписать результат на исходном языке.

8  Чисто функциональная структура данных
(Purely functional data structure)

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

История
В истории развития неизменяемых структур данных можно отметить следующие важные вехи:

• Давно и широко известна техника Copy-on-Write («COW») (описана в Wikipedia: [6]), использующая неизменяемость для оптимизации производительности и потребления памяти.
• В языке LISP, появившемся в 1958 г., одна из основных структур данных — обычный односвязный список, реализованный при помощи т. н. изменяемых «cons-пар». Подавляющее большинство стандартных процедур обработки списков не используют возможность изменения списка и предполагают, что список, по крайней мере в процессе их работы, не изменяется ¹². В языке Scheme в стандарте версии 6 (R6RS [18]) процедуры изменения cons-пар убраны из базовых и вынесены в отдельную библиотеку. В диалекте PLT Scheme 4.0 (2007 г.) типы изменяемых и неизменяемых пар были окончательно разделены, и для изменяемых пар введен свой набор примитивов mcons, mcar, mcdr, set-mcar! и set-mcdr!.
• В 1989 г. вышла работа Дрисколла, Сарнака, Слетора и Тарьяна «Making data structures persistent» [62], посвященная тому, как превратить обычную структуру данных в чисто функциональную.
• В 1997 г. Крис Окасаки опубликовал большую работу «Purely Functional Data Structures» [127], целиком посвященную чисто функциональным структурам данных, их реализации (на ML и Haskell) и анализу производительности. Эта книга в настоящий момент является основным источником информации на данную тему.
• В 2003 г. Мартин Хольтерс продолжил дело Криса Окасаки работой «Efficient data structures in a lazy functional language» [80], где описано несколько новых структур данных и проведен более подробный, чем у Окасаки, анализ производительности некоторых известных структур.
• Вышедшая в 2009 г. книга Питера Брасса «Advanced data structures» [45] в одной из глав рассказывает о превращении обычных структур данных в чисто функциональные.

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

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

• Откатить ход:
  findBestMove(Position initial, int lookahead) { for(Move move : getPossibleMoves(initial)) { initial.makeMove(move); ...findBestMove(initial, lookahead-1)... initial.undoMove(move); } }
• Не производить изменение в самой позиции initial, а создавать копию:
  findBestMove(Position initial, int lookahead) { for(Move move : getPossibleMoves(initial)) { Position pos = initial.clone(); pos.makeMove(move); ...findBestMove(pos, lookahead-1)... } }
  В этом случае не надо отменять ход, зато надо клонировать позицию.

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

Решение, используемое типичной чисто функциональной структурой данных, ближе ко второму варианту:

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

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

Пример: Односвязные списки (стеки)

Приведем реализацию чисто функционального стека на Java.

Как видно, все стековые операции выполняются за время O(1) и не используют изменяемых данных. Такой стек может использоваться, к примеру, для эффективного хранения текущего стека вызовов в интерпретаторе языка или в библиотеке журналирования: при входе в процедуру он будет заменяться новым стеком, который длиннее на один элемент, а при выходе — на предыдущий стек. Во время процедуры можно получить текущее значение стека вызовов и куда-нибудь его при необходимости сохранить (оно останется в первозданном виде и не «испортится»). Например, это нужно затем, чтобы вывести в асинхронный лог отладочное сообщение (из-за асинхронности лога использование изменяемого стека недопустимо), или даже затем, чтобы вернуться в предыдущую точку программы. В качестве примера реального использования такого стека см. исходный код профайлера antro [180] для сборочных скриптов Ant. Данная структура данных также называется «спагетти-стек (spaghetti stack)»

На рис. 3 приведена диаграмма связей между объектами, образующихся в результате выполнения следующего кода:

---

Рис. 3: Диаграмма объектов к коду примера со стеками

---

Пример: Бинарные деревья
Большинство разновидностей бинарных деревьев поиска (используемых для представления множеств, словарей, приоритетных очередей и т. п.) также допускают чисто функциональную реализацию. В типичной ситуации результат выполнения какой-либо простой операции над деревом (скажем, вставка/удаление элемента) отличается от исходного дерева на относительно небольшое количество элементов, пропорциональное высоте дерева, т. е. «меняются» лишь элементы, расположенные неподалеку от пути к затронутой точке дерева. В качестве примера на рис. 4 на одной диаграмме объектов приведены два бинарных дерева поиска — a, образованное значениями 0, 1, 3, 4, 6, 8, 10, 11, 13, 14, и b, образованное добавлением к a значения 7. Как видно, большая часть узлов (например, все левое поддерево) у них общая, однако эти деревья могут быть использованы независимо — опять же, благодаря неизменяемости обоих деревьев.

---

Рис. 4: Чисто функциональные деревья

---

Существует множество различных чисто функциональных структур данных, основные из которых описаны в книге Окасаки ([127]). Нередко такие структуры используют ленивые вычисления, что затрудняет анализ производительности; в книге Окасаки акцентируется внимание на таком анализе.

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

Использование
Один из примеров использования чисто функциональных структур данных уже был показан выше: они чрезвычайно удобны для реализации комбинаторного перебора с откатами.

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

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

Так как при реализации чисто функциональных структур программист избавлен от проблем, связанных с изменяемым состоянием, то корректно реализовать и оттестировать такую структуру также проще, чем «обычную» (см. статью «Изменяемое состояние: опасности и борьба с ним» Евгения Кирпичёва [185]).

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

Реализация
В языке Java, C# и многих других разработчиками стандартных библиотек было принято решение сделать класс строки неизменяемым. Это позволило представлять строки как отрезки неизменяемого массива символов и, как следствие, разделять ссылку на такой массив между несколькими строками, что позволило реализовать очень эффективную операцию взятия подстроки, а также уничтожило как класс ошибки, связанные с неявным изменением строк, достаточно частые в таких языках, как C++. История показала, что это решение оказалось очень удачным и не наложило существенных ограничений на использование строк: в ситуациях, где необходима строка как изменяемая структура данных, используются другие классы (например, в Java используется StringBuilder), которые, однако, используются только для промежуточного представления текста, а не как основной класс строк. Такое же решение (отрезок разделяемого неизменяемого массива) используется в языке Erlang для представления «binaries» (байтовых массивов).

Стандартная библиотека языка Haskell по большей части содержит именно чисто функциональные структуры данных: к примеру, это стандартные списки (модуль Data.List), словари (Data.Map), множества (Data.Set), последовательности с быстрой конкатенацией (Data.Sequence) и другие.

Структуры, описанные в книге Окасаки [127], реализованы в его библиотеке «Edison» (существует на hackage [125]). Большое количество других структур данных можно найти на hackage ([20]) в разделе «Data Structures», хотя и не все из них чисто функциональные.

Стандартная библиотека языка Scala (пакет scala.collections.immutable) содержит несколько функциональных структур данных.

Стандартная библиотека языка Clojure содержит в основном чисто функциональные структуры данных и реализует таким образом даже хэш-словари и множества (с временем доступа порядка O(log₃₂n)).

Стандартные библиотеки практически всех функциональных языков содержат те или иные функциональные структуры.

В библиотеке functionaljava ([23]) реализованы некоторые функциональные структуры, в частности, красно-черные деревья.

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

9  Алгебраический (индуктивный) тип данных
(Algebraic (inductive) datatype)

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

История
Среди языков программирования первым поддерживать простейший аналог алгебраических типов стал, судя по всему, Algol 68, в форме «united modes». Затем в форме «variant records» поддержка схожей и достаточно примитивной возможности появилась в Pascal и других языках. В конце 1970 гг. появился язык ML, поддерживавший современную форму алгебраических типов, включая рекурсивные и полиморфные алгебраические типы; эта же форма (с другим синтаксисом и с небольшими, но важными расширениями) используется в стандарте Haskell’98. ML положил начало другим статически типизированным функциональным языкам. Практически все они сейчас поддерживают алгебраические типы.

В большинстве языков процедурного и объектно-ориентированного программирования (наследниках Си и Smalltalk) их поддержка так и не появилась, и пользователи этих языков довольствуются различными имитациями или стараются избежать их. В некоторых динамических языках с богатыми возможностями метапрограммирования (Lisp, Ruby и т. п.) можно реализовать абстрактные типы данных, схожие по возможностям с алгебраическими типами, как, например, сделано в языке Scheme (пакет «struct.ss» [28]).

В 1992 г. появился язык Coq [7], а с ним и «исчисление индуктивных конструкций» (Calculus of Inductive Constructions, CIC) и чрезвычайно мощное и общее понятие индуктивного типа. Сама концепция алгебраических типов не развивалась существенным образом с момента появления индуктивных типов в CIC, однако находились новые применения некоторым их частным случаям. Так, в 2003 г. в статье «Guarded recursive datatype constructors» [178] была предложена несколько менее общая конструкция, ныне известная под названием «обобщенный алгебраический тип» (Generalized Algebraic Datatype (GADT)). Первым языком программирования общего назначения, в котором появилась полноценная поддержка обобщенных алгебраических типов, был Haskell (начиная с компилятора GHC 6.4, выпущенного в 2005 г.).

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

Итак, существует 3 типа фигур:

Прямоугольник определяется левым верхним и правым нижним углом:

Круг — центром и радиусом:

Треугольник — тремя точками.

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

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

Первый способ, приходящий на ум программисту, имеющему опыт разработки на Си, Java и т. п. таков: воспользоваться составной структурой данных, хранящей и форму, и параметры. К сожалению, почти все наиболее распространенные современные языки программирования допускают, в сущности, только один способ комбинирования двух элементов данных в одной сущности — помещение их в поля одной и той же структуры или класса. Но при таком способе нельзя учесть, что для формы CIRCLE осмыслен только набор параметров типа Circle, и т. п.

Другой способ заключается в том, чтобы отказаться от разделения на «форму» и «параметры», и описать тип данных явно и безызбыточно: «либо прямоугольник (задаваемый двумя точками), либо круг (задаваемый точкой и числом), либо треугольник (задаваемый тремя точками)». Вот код на Haskell:

Далее в статье мы будем в основном пользоваться несколько иной нотацией. В этой нотации тип Shape определяется не как набор способов сконструировать значение типа Shape, а как набор заявлений «Терм такого-то вида имеет тип Shape»; отличие довольно тонкое и в данном примере вовсе не проявляется, но оно станет ясно позднее.

Например:

Описание
Рассмотрим различные аспекты понятия алгебраического типа по отдельности.

Алгебраические типы позволяют определять типы-произведения (кортежи).

Как видно, тип FileInfo задается утверждением «Если n — строка, ar — целое число, lm — дата, то FileInfo \{ name=n, accessRights=ar, lastModified=lm \} (сокращенно FileInfo n ar lm) имеет тип FileInfo». Такой тип соответствует обыкновенной «структуре» в языках семейства Си.

Под термином «тип-произведение» в данном случае имеется в виду, что тип FileInfo соответствует декартову произведению множеств, соответствующих его компонентам.

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

Как видно, тип Color задается утверждениями «Red — цвет», «Orange — цвет», «Yellow — цвет» и т. п. Такой тип соответствует «перечислению» (enumeration) в языках семейства Си.

Под термином «тип-сумма» в данном случае имеется в виду, что множество термов, имеющих тип Color, складывается из термов вида «Red», «Green», «Blue», «Yellow».

Алгебраические типы позволяют определять типы вида «сумма произведений».

Этот пример сочетает в себе две предыдущих возможности: тип Shape складывается из термов вида Rectangle ... ... и т. п.

Важно понимать, что Rectangle, Circle, Triangle сами по себе не являются типами в языке Haskell и в большинстве других языков с поддержкой алгебраических типов — это лишь подмножества значений типа Shape, так же как, скажем, чётные числа — подмножество значений типа int в Java. Фундаментальных теоретических препятствий для этого нет, однако если бы Rectangle был сам по себе типом, то значение Rectangle p1 p2 имело бы сразу два типа: Rectangle и Shape, что существенно затрудняло бы вывод типов (см. 2) и усложняло язык в целом.

Определения алгебраических типов могут быть рекурсивны и взаимно рекурсивны.

Как видно, в этом примере тип Document задан так:

• Если s::String, то Paragraph s — документ;
• Если p::Image, то Picture p — документ;
• Если ds::[Document], то Sequence ds — документ;
• Если rh::[String], ch::[String], c::[[Document]], то Table rh ch c — документ.

Таким образом, например, следующий терм — документ:

В этом примере тип Document определен через самого себя, т. е. рекурсивен.

Картинка определена как «картинка из файла», «автофигура», «композиция нескольких картинок» или же «встроенный документ» (например, MS Office позволяет использовать большинство средств форматирования текста внутри текстовых элементов картинок). Как видно, типы Document и Picture определены друг через друга, т. е., взаимно рекурсивны.

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

В этом примере задан тип «Бинарное дерево со значениями типа α в узлах (сокращенно: дерево α)». Он задан так: «Leaf — дерево α (заметьте: независимо от α)», «если x::α, t1::Tree α, t2::Tree α, то Fork x t1 t2 — дерево α». Например, Leaf::Tree Int (пустое дерево является деревом со значениями типа Int (как, впрочем, и любого другого) в узлах), а также:

В этом примере задан тип «Хэш-таблица из k в v с хэшами типа h». Если k,h,v — типы, f::k->h, e::k->k->Bool, t::Array h [(k,v)] (что означает: массив с индексами типа h и значениями типа «список пар (k,v)»), то Hash f e t — хэш-таблица из k в v с хэшами типа h.

Интуитивно хочется избавиться от упоминания типа h в типе Hash k h v: он не имеет отношения к интерфейсу хэш-таблицы как отображения из ключа в значение. Вскоре мы увидим, что это возможно.

Алгебраические типы допускают неоднородную рекурсию: аргумент рекурсивного применения конструктора типа может быть сложным.

Здесь определен хитроумный способ задания структуры данных «список с произвольным доступом (random-access list)» при помощи так называемых «вложенных», или «полиморфно рекурсивных» типов. За алгоритмическими подробностями предлагается обратиться в книгу Криса Окасаки «Purely functional data structures» ([127]) и презентацию Евгения Кирпичёва по теме книги ([182], слайды 37—39).

Как видно, конструктор OneCons, конструирующий терм типа RAList α, имеет одним из аргументов значение типа RAList (α,alpha). Например, OneCons 5 (ZeroCons (OneCons ((6,2),(4,3)) Nil)) :: RAList Int. Применения этой разновидности алгебраических типов см. в секции «Применение».

Конструкторы алгебраического типа T могут упоминать не только те типовые переменные, по которым параметризован тип T.

В этом примере задан тип «Хэш-таблица из k в v». Если k,h,v — типы, f::k->h, e::k->k->Bool, t::Array h [(k,v)], то Hash f e t — хэш-таблица из k в v. Обратите внимание на разницу между этим объяснением и объяснением, данным выше: она заключается в том и только том, что из типа хэш-таблицы убрано упоминание о внутренне используемом ею типе хэшей. Таким образом, имея значение типа Hash k v, уже невозможно узнать, какой именно тип эта таблица использует для хэшей, однако же известно, что какой-то — использует, и если обозначить этот тип за h, то поле hash этой таблицы будет иметь тип k -> h и т. п. Это позволяет реализовать все операции над хэш-таблицей без знания конкретного типа h.

Такой тип называется «экзистенциальным (existential)», поскольку множество его значений составляют термы, квантифицированные квантором существования:

Экзистенциальные типы играют огромную роль при реализации абстрактных типов данных, поскольку, в общем-то, и являются воплощением абстракции как процесса «забывания» чего-то конкретного (в данном случае — конкретного типа h). В этом смысле они тесно связаны с понятием инкапсуляции в ООП. Хороший обзор применения экзистенциальных типов для реализации абстрактных типов можно найти в первой половине статьи Мартина Одерски и Константина Лойфера «Polymorphic type inference and abstract data types » ([107]). В особенности интересными и полезными экзистенциальные типы становятся в комбинации с классами типов (см. 13); см. статью Лойфера «Type classes with existential types» [106]. Также см. страницы «Existential type» [30] и «OOP vs type classes» [31] в Haskell wiki.

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

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

Например:

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

Тогда вычисление описанного выражения interp (IfThenElse ...) даст True.

Специфика данного примера, как видно, в том, что типовый параметр α конструируемого терма у разных конструкторов был разным: у Add — Int, у Equal — Bool, у Const он был полиморфен, а у Equal — даже ограниченно полиморфен по типам, принадлежащим к классу (см. 13) Eq.

Большинство примеров, использующих данную возможность алгебраических типов, также реализуют тот или иной «язык» (с другой стороны, любая структура данных — своего рода язык). Это существенно увеличивает возможности системы типов по обеспечению корректности (иначе очень трудно определить алгебраический тип Expr, гарантируя, что значения типа Expr a не имеют ошибок типизации, например IfThenElse (Const 1) ....

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

Типы же, использующие эти возможности, называются обобщенными алгебраическими (Generalized Algebraic Data Type, GADT).

Возможностями GADT разнообразие и мощь концепции алгебраического типа не исчерпывается: в языке Coq, поддерживающем т. н. зависимые типы, алгебраические типы называются «индуктивными» (используется система типов «Calculus of Inductive Constructions» — она хорошо описана в книге Ива Берто и Пьера Кастеррана о системе Coq «Coq’art: Interactive theorem proving and program development» [40], а формально задана в статье Кристины Паулин-Моринг «Inductive definitions in the system Coq — Rules and properties» [131]) и обладают фактически неограниченной выразительной мощью, позволяя в т. ч. выражать сколь угодно сложные классы структур данных с инвариантами. Мы не будем подробно останавливаться на них в этой статье — краткий обзор приведен в презентации Евгения Кирпичёва [181], а более полный можно найти в источниках, указанных в ней.

Для всякого алгебраического типа определена чрезвычайно общая операция свертки (см. 11), абстрагирующая способ вычисления «по индукции» (снизу вверх) над значениями такого типа. Предлагается обратиться за разъяснениями к соответствующей подстатье. Для обычных алгебраических типов составление процедуры свертки тривиально. Кроме того, существуют обобщения понятия свертки и на вложенные и обобщенные алгебраические типы; их автоматическое порождение реализовано в языке Coq под названием «принципов индукции» (induction principles).

У алгебраических типов есть и недостатки:

• Расширить алгебраический тип можно только путем редактирования его определения. Положительная сторона этого ограничения — то, что компилятор всегда может проверить, все ли случаи учитываются при сопоставлении с образцом.
• Алгебраические типы иногда раскрывают слишком много «частных» подробностей реализации структуры данных. Смена представления алгебраического типа, переименование конструктора, добавление или удаление конструкторов обычно ведут к тому, что клиентский код перестает компилироваться (отчасти тут помогают экзистенциальные типы). Поэтому довольно часто при программировании на Haskell вместо алгебраических типов используются абстрактные типы (типы, с которыми клиент может работать исключительно в терминах вспомогательных функций, ничего не зная об их реализации). Разработчик библиотеки не экспортирует из модуля конструкторы алгебраического типа, а вместо этого предоставляет различные вспомогательные функции. Примеры см. в секции «Использование».

Использование
«Обычные» (не обобщенные) алгебраические типы используются в поддерживающих их языках (Haskell, OCaml, F#, Scala и т. п.) повсюду: например, в Haskell все определяемые пользователем типы данных — алгебраические; вообще говоря, алгебраические типы намного лучше подходят для описания структур данных и позволяют намного естесственнее записывать алгоритмы их обработки (при помощи сопоставления с образцом (см. 10)), чем структуры (записи) или объекты. Хотя чаще других используются «тривиальные» алгебраические типы, которые могли бы быть записаны при помощи структуры или перечисления, но примеры, когда тривиальным типом не обойтись, имеются в изобилии. Приведем несколько совершенно произвольных отрывков из библиотек языка Haskell, опуская тривиальные типы.

Определение типа JSON-выражений из библиотеки json [65]:

Определение типа SQL-значений из библиотеки HDBC [72]:

Определение типа «Игровой объект» из игры Monadius [166] (фрагмент):

Абстрактные типы используются вместо алгебраических очень часто: например, в стандартном модуле словарей языка Haskell Data.Map (документация: [26]), в модуле приоритетных очередей heap [10], в библиотеке «идеального хэширования» PerfectHash [15], обильно используются в модуле-привязке к физическому движку «Hipmunk» [11], в библиотеке для построения графиков Chart [3] (например, в модуле Grid) и т. д.

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

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

Вложенные типы данных и полиморфная рекурсия в основном применяются для задания структур данных со сложными инвариантами. Они используются во многих структурах данных в фундаментальном труде Криса Окасаки «Purely functional data structures» [127]. Одна из таких структур описана в статье того же автора «Binomial queues as a nested type» ([124]). Еще один экзотический, но интересный пример — циклические структуры данных, позволяющие при реализации операций над ними учитывать зацикленность в явном виде (статья «Representing cyclic structures as nested datatypes» [69]).

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

• Ralph Hinze, «Fun with Phantom Types» ([78]): превосходный обзор, описывающий: язык выражений, подобный рассмотренному выше; обобщенные функции, в определенном смысле эмулирующие динамическую типизацию; улучшение класса Show; нормализацию типизированных лямбда-термов; типизированный аналог printf.
• Ralf Hinze, Johan Jeuring, и Andres Löh, «Typed Contracts for Functional Programming» ([79]): интереснейшая статья, предлагающая реализованную с помощью GADT библиотеку, позволяющую упростить поиск первопричин нарушения «контрактов» функций в программе.
• Ganesh Sittampalam, «Darcs and GADTs»: в статье рассказано, как применение GADT для представления «патчей» в системе контроля версий darcs позволило упростить код и обнаружить ошибку в старом коде.
• Andrew Kennedy, Claudio V. Russo, «Generalized Algebraic Datatypes and Object-Oriented Programming» ([99]): эта обширная статья демонстрирует параллели между GADT и некоторыми паттернами ООП.

Реализация
Алгебраические типы реализованы в различных формах во множестве языков:

• Haskell реализует их в представленном в данной статье объеме.
• OCaml реализует обычные (не обобщенные) алгебраические типы, но не поддерживает ни вложенные типы, ни необходимую для обращения с ними полиморфную рекурсию (впрочем, существует синтаксическое расширение, реализующее полиморфную рекурсию).
• Scala реализует обычные и обобщенные алгебраические типы.
• Для Scheme существуют пакеты макросов, позволяющие использовать для задания «типов» и для сопоставления с образцом синтаксис, схожий с синтаксисом алгебраических типов и сопоставления с образцом в других языках; впрочем, за отсутствием у Scheme статической системы типов нельзя говорить о поддержке алгебраических типов в этом языке.
• F# как надмножество OCaml реализует обычные алгебраические типы.
• Coq, Agda, Epigram реализуют индуктивные типы (индуктивные типы Coq описаны в книге «Coq’art: Interactive theorem proving and program development» [40] и в презентации Евгения Кирпичёва [181]).

Имитация
Задачи, решаемые алгебраическими типами, возникают на практике постоянно. В программистском фольклоре существует множество (неудобных) способов их решения без поддержки АТД. Вот некоторые из них.

Использование одной структуры/класса с обнуляемыми полями.

Например:

Этот способ особенно часто используется в языках типа Java или C#, не поддерживающих конструкцию union. Недостатки очевидны:

• Код, оперирующий такого рода структурами, уродлив (сравните функцию интерпретации схожего типа на Haskell выше, и представьте себе реализацию такой функции для этого типа на Си).
• Код хрупок и подвержен ошибкам. Например, написав et_unop вместо et_binop в одной из веток switch(exp->type), программист обрекает себя на ошибку доступа к полю op2.
• При заполнении и изменении подобных структур очень легко забыть проинициализировать какое-либо поле.
• Хранение таких структур неэффективно в плане потребляемой памяти: например, при хранении значения типа et_const_bool зря занимают место в памяти три лишних поля: operation, op1, op2.

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

Использование одной структуры/класса с union.

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

Неявный union.

Здесь подразумевается, что если type==et_unop, то в памяти непосредственно после type расположена структура типа unop, и т. п.

Этот подход довольно часто используется, например, в WinAPI, в частности, в Security API ([2]). Из его достоинств можно назвать оптимальное использование памяти, из недостатков — по уродливости кода, трудоемкости и подверженности ошибкам он многократно превосходит оба предыдущих способа вместе взятых.

Объектно-ориентированная имитация при помощи наследования и диспетчеризации по типу

При этом подходе для алгебраического типа создается базовый абстрактный класс, а для каждого конструктора создается по наследнику. Обработка значений такого типа осуществляется либо через операторы проверки и приведения типов ( expr instanceof Unop, (Unop)expr), либо при помощи приема, описанного далее. Минусы этого подхода: а) по-прежнему отсутствует проверка полноты разбора случаев; б) код, написанный в стиле ExpressionUtils.eval и выполняющий диспетчеризацию по типу или полю, имитирующему тип, в ООП считается антипаттерном и его рекомендуется заменять на использование виртуальных функций, паттерна Visitor и т. п. Использование виртуальных функций в классе Expression в такой ситуации не всегда оправдано, т. к. на этапе его проектирования может быть неизвестно, какие именно операции понадобятся. Обильное использование такой техники может легко привести к замусориванию класса разнородным кодом. Отчасти решает эту проблему паттерн Visitor, описанный в классической книге о паттернах проектирования ([68]), предназначенный для реализации двойной диспетчеризации.

Кодировка Чёрча и паттерн Visitor

Паттерн Visitor подробно описан в книге о шаблонах проектирования ([68]) и в огромном количестве других источников, в основном в варианте, приведенном в комментариях («Or:...»).

Раскомментированный вариант visitUnop и visitBinop — частный случай кодировки Чёрча (см. статью о ней в Wikipedia [4], и главы об алгебраических типах в книге «Design concepts in programming languages» [169], см. также статью Янсена, Коопмана и Пласмейера «Efficient interpretation by transforming data types and patterns to functions» [91], где реализуется небольшой язык программирования с поддержкой алгебраических типов и сопоставления с образцом при помощи кодировки Чёрча, и эта реализация оказывается чрезвычайно эффективной). Этот прием позволяет представлять структуры данных и сопоставление с образцом при помощи одних лишь функций. В блог-посте «Structural pattern matching in Java» Оли Рунара [129] можно найти пример кода на Java, иллюстрирующего представление структур данных в кодировке Чёрча. Помимо имитации алгебраических типов кодировка Чёрча иногда используется и для их реализации, в качестве промежуточной стадии компиляции или оптимизации (такое применение описано в книге «Design concepts in programming languages»).

Использование абстрактного типа данных

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

• Интерфейс, подобный классу ExpressionVisitor и функции match выше. Например, вот как можно реализовать match при представлении с помощью конструкторов:
  module Trees ( Tree(), -- Do not export constructors! match ) where data Tree α = Leaf | Fork α (Tree α) (Tree α) match lf fk Leaf = lf match lf fk (Fork a t1 t2) = fk t1 t2
• Интерфейс, основанный на т. н. абстракции конструкторов, селекторов и предикатов. Конструкторы — это функции, позволяющие создать значение данного типа. Селекторы обеспечивают доступ к индивидуальным компонентам значений. Предикаты используются для различения разновидностей значений (например, чтобы отличить дерево-«лист» от дерева-«вилки»). Иногда к этой классификации добавляют еще «мутаторы» (процедуры, изменяющие структуру данных) и «запросы» (нетривиальные процедуры, вычисляющие определенные свойства структуры данных, например, высоту дерева или принадлежность ключа к словарю).
  module Trees ( Tree(), leaf,fork, value,left,right, isLeaf,isFork ) -- Constructors leaf = Leaf fork a t1 t2 = Fork a t1 t2 -- Selectors (none for Leaf in this case) value (Fork a l r) = a left (Fork a l r) = l right (Fork a l r) = r -- Predicates isLeaf Leaf = True ; isLeaf _ = False isFork Leaf = False ; isFork _ = True

10  Сопоставление с образцом
(Pattern matching)

Суть
Сопоставление формы структуры данных с формой образца и заполнение переменных-«дырок» в образце значениями в соответствующих местах структуры данных.

История
Первые языки с поддержкой сопоставления с образцом появились в 1960—1970-е гг; самым первым из них был SNOBOL — язык для обработки текста. Он предоставлял чрезвычайно богатые возможности по манипулированию образцами, а также позволял обращаться с ними как с объектами первого класса. Однако SNOBOL — очень экзотический язык. Согласно книге Саймона Пейтона-Джонса «Implementation of functional programming languages» [137], из более современных языков «первопроходцами» были ISWIM (абстрактный язык без реализации, представленный Петром Ландиным в его знаменитой статье «The Next 700 Programming Languages» [105]), SASL, NPL (далее эволюционировавший в Hope — предшественника Miranda и Haskell). В развитие технологии сопоставления с образцом внесли свой вклад такие языки, как РЕФАЛ (1968), Prolog (1972) и Mathematica (1988).

В конце 1980-х появились различные вариации на тему «представлений» (views), позволяющих решить некоторые проблемы расширяемости кода с использованием алгебраических типов, повысить его уровень абстракции и близости к предметной области, и т.д (см. конец секции «Описание»). Так, в 1987 г. вышла статья Филипа Вадлера на эту тему «Views: a way for pattern matching to cohabit with data abstraction» ([172]). Более сложная, но и более удобная в использовании (на взгляд автора) идея «активных образцов» нашла реализацию в работе «F# active patterns» Дона Сайма ([165], 2007 г). Возможность первоклассного манипулирования образцами в языке без встроенной поддержки такой возможности была предложена в 2000 г. Марком Таллсеном в статье «First class patterns» ([168]) и развита до удобного в использовании уровня совсем недавно — в 2008 году (Мортен Райгер, статья «Type-safe pattern combinators» [147]).

Интуиция

---

Рис. 5: Обращение списка

---

На рис. 5 графически декларативно записан алгоритм вычисления обращения списка, сведенный к задаче «приписать обращение списка xs к списку r» (изначально полагается r=[]). Алгоритм reverse' последовательно «откусывает» от списка голову и приписывает ее к результату. В алгоритме разбираются два случая, которые вместе описывают все множество входных списков:

• xs — пустой список. В этом случае результат — r.
• xs — список с головой h и хвостом t. В этом случае задача заменяется на приписывание обращения t к списку, составленному из головы h и хвоста r.

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

На Haskell описанная функция будет выглядеть так:

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

Для сравнения, вот реализация, не использующая в явной форме сопоставление с образцом:

Описание
Оператор сопоставления с образцом, с точностью до синтаксиса конкретного языка, выглядит так:

Здесь EXPRESSION — произвольное выражение, обладающее значением (обычно принадлежащим к алгебраическому типу (см. 9)), VALUE — выражения или операторы (statement), а PATTERN — собственно образцы. Пары PATTERN -> VALUE называются уравнениями (clause), иногда — «клозами».

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

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

---

Рис. 6: Правый поворот дерева

---

Вот соответствующий код на Haskell:

Неформальная семантика case-выражения такова: «Значением выражения case E of P1 -> V1; ...; Pn -> Vn является значение правой части V_i первого из уравнений P_i → V_i, такого, что E сопоставимо с P_i».

В некоторых языках case-оператор — не единственная форма сопоставления с образцом. Например, Haskell позволяет непосредственно определять функции в таком стиле:

Или (перепишем пример reverse):

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

В этом случае каждый подобный элемент определения функции называется уравнением.

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

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

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

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

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

Язык Mathematica, пожалуй, можно считать образцовой реализацией техники сопоставления с образцом. В Mathematica само понятие вычисления основано на переписывании термов в соответствии с определеннами правилами в форме уравнений. Mathematica предоставляет большое количество разновидностей образцов. Рассмотрим некоторые из них.

• «обычные» образцы: заменим все фрукты красного цвета на символ «красный фрукт». «foo_» — обычная метапеременная, обозначающая «произвольное выражение в данном месте образца назовем именем foo».
  > {apple[red], apple[green], blueberry, orange[red]} /. fruit_[red] :> redFruit {redFruit, apple[green], blueberry, redFruit}
• Нелинейные образцы: заменим выражения вида d(aⁿ)/da на n aⁿ⁻¹.
  > d[x^3, x] /. d[a_^n_, a_] :> n a^(n-1) 3 x^2
• Повторения (последовательность из выражений, подходящих под образец): обернем последовательности яблок символом «яблоки». «P..» обозначает «последовательность выражений, подходящих под образец P».
  > {blueberry, {apple[red], apple[green]}, orange[red]} /. x:{apple[_]..} :> apples[x] {blueberry, apples[{apple[red], apple[green]}], orange[red]}
• Образцы-последовательности, сопоставляемые с подсписками: определим функцию принадлежности элемента к списку. «__» обозначает «произвольный подотрезок списка».
  > Elem[x_, {___, x_, ___}] := True; > Elem[_, _] := False; > Elem[1, {2,2,1,4}] True
• Образцы с условием: заменим числа меньше 3 на символ tooSmall, а числа больше 5 на tooBig.
  > {1,2,3,4,5,6,7} /. {x_/;x<3 :> tooSmall, x_/;x>5 :> tooBig} {tooSmall,tooSmall,3,4,5,tooBig,tooBig}
• Отрицание образца: выберем из списка все значения, кроме тех, что больше 4.
  > Cases[{1,2,5,3,4,2,6,3,1}, Except[x_/;x>4]] {1,2,3,4,2,3,1}
• Строковые образцы: заменим подстроку «ab» на «X».
  > StringReplace["abc abcb abdc", "ab" ~~ _ -> "X"] "X Xb Xc"
• Определение функций при помощи образцов: определим детерминант матрицы 2 × 2 как det (

  a	b
  c	d

  ) = a d − b c.
  > det[{{a_,b_}, {c_,d_}}] := a*d - b*c; > det[{{1,2}, {3,4}}] -2

Абстрактные типы данных обеспечивают легкость поддержки и развития кода, а также модульность, за счет того, что доступ к данным определен исключительно в терминах поддерживаемых операций и их свойств. Например, абстрактный тип данных «Двоичное дерево» может быть определен в терминах операций «Получить данные узла, получить левое поддерево, получить правое поддерево». При таком интерфейсе возможно, к примеру, поменять представление дерева с «обычного» (data Tree a = Leaf a | Fork a (Tree a) (Tree a)) на компактное представление в массиве (где левым ребенком k-го узла является 2k+1-й, а правым — 2k+2-й), ничего не меняя в клиентском коде.

К сожалению, сопоставление с образцом не позволяет работать с абстрактными типами данных, потому что данный способ доступа к данным напрямую связан с конкретной реализацией структуры, т. е. с тем, какие конструкторы с какими сигнатурами составляют ее тип (см. 9). Если клиентский код был написан при помощи сопоставления деревьев с образцами, состоящими из конструкторов Leaf,Fork, то при переходе к представлению при помощи массива код придется переписать.

У этой проблемы существует несколько похожих решений. Первое из них появилось под названием «views (view patterns)» («представления»; описаны в статье Вадлера «Views: a way for pattern matching to cohabit with data abstraction» [172]); со временем в Haskell стало использоваться под тем же названием несколько другое решение; через несколько лет похожие техники появились в F# («active patterns») и Scala («extractors»). Оказалось, что они не только решают проблему смены представления данных, но и позволяют писать очень красивый и компактный код во многих других случаях.

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

Рассмотрим пример: будем сопоставлять строки с форматом дат (приведен псевдокод в предположении, что существует функция parseDate).

В этом коде написано: «Если parseDate ... s является датой с полями yyyy,mm,dd,hh,mi,ss, то ответ такой-то».

Почему бы не сказать «Если str является представлением даты с полями yyyy,mm,dd,hh,mi,ss относительно формата YYYY/MM/DD hh:mi:ss, то ответ такой-то»? Вот как такая переформулировка будет выглядеть на Haskell с использованием расширения языка «ViewPatterns»:

Аналогично можно, к примеру, разбирать строки при помощи регулярных выражений:

В этих двух случаях нет большой разницы между кодом с представлениями и его аналогом с явным case, однако она становится очень явной, когда речь идет о сопоставлении одновременно нескольких значений с несколькими образцами. Например, вот гипотетический код для слияния двух приоритетных очередей (предполагается, что uncons q возвращает минимальный элемент q и остаток q). Можно представить себе, во что этот код превратится, если избавиться от «view patterns» и сделать case явным.

Очень поучительное и красивое применение алгоритмов с использованием очередей и с использованием представлений именно для абстрагирования от конкретной реализации структуры (сопоставление с образцом-представлением «Очередь с головой h и остатком t») можно найти в статье Криса Окасаки «Breadth-first numbering: lessons from a small exercise in algorithm design» ([128]).

Реализация представлений в Haskell интересна именно своей неожиданной простотой и понятностью. Однако, средства F# синтаксически чуть удобнее. Множество красивых и убедительных примеров представлений в F# приведены в статье («F# active patterns» Дона Сайма [165]).

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

Объединение сортированных списков:

Посылка команды в протоколе POP3 (библиотека HaskellNet [122]; отрывок):

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

В языке Haskell сопоставление с образцом — не просто форма определения функций или записи условного выражения case, а основная форма связывания значений с именами, употребляемая во всех контекстах, где требуется такое связывание. Например, в генераторах списков и в do-блоках (первый пример учебный, второй взят из библиотеки HSH для Haskell [73], реализующей встроенный язык, схожий с конвейером shell):

В Mathematica многие функции определяются с помощью сопоставления с образцом. Вообще, большая часть всей обработки данных там происходит через переписывание согласно образцам. Рассмотрим несколько примеров: вычисление детерминанта матрицы 2 × 2, упрощение выражения согласно правилам log(x y)=log x+log y и log(x^k)=k log x (Mathematica не производит такое упрощение самостоятельно, поскольку эти правила верны лишь для положительных аргументов), а также «устранение карринга (см. 5)».

Реализация
Сопоставление с образцом реализовано во многих языках. В первую очередь это языки семейства ML: Haskell, OCaml, F# и т. п.

В Mathematica вся концепция вычислений основана на сопоставлении с образцом; фактически, движок Mathematica — лишь чрезвычайно эффективная машина для выполнения поиска и замены на основе образцов.

Сопоставление с образцом может быть реализовано и в качестве «макроса» при отсутствии непосредственной поддержки в языке. Так, например, сделано в реализации PLT Scheme (модуль «match.ss» [24]):

Здесь определен абстрактный тип данных «выражение» — две структуры «сумма» и «произведение», и приведен отрывок функции, выполняющей «раскрытие скобок» по правилу a (b + c) = a b + a c.

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

В первом случае выражение app([1,2],[3,4],Zs) было сопоставлено с уравнениями app и обнаружилось, что это выражение подходит только под второй из них: X=1,Xs=[2],Ys=[3,4],Zs=[1|Zs'], при условии, что верно app([2],[3,4],Zs'). Это выражение также сопоставилось со вторым уравнением, а оставшееся выражение app([],[3,4],Zs'') сопоставилось с первым уравнением подстановкой Ys=[3,4],Zs''=Ys. Таким образом, получилось, что Zs=[1,2,3,4].

Во втором случае процесс протекал наоборот: выражение app(Xs,Ys,[1,2,3]) сопоставилось с обоими уравнениями; в результате сопоставления с первым было порождено решение Xs=[],Ys=[1,2,3], и т. д.

В языке многопоточного и распределенного программирования Erlang сопоставление с образцом обладает следующими интересными особенностями:

• Поддерживается сопоставление префиксов строк:
  protocol("HTTP/"++Version) -> Version; protocol(_) -> undefined.
• Поддерживается сопоставление на уровне битов, что позволяет крайне компактно и читаемо записывать разбор бинарных протоколов:
  decode(Segment) -> case Segment of << SourcePort:16, DestinationPort:16, SequenceNumber:32, AckNumber:32, DataOffset:4, _Reserved:4, Flags:8, WindowSize:16, Checksum:16, UrgentPointer:16, Payload/binary>> when DataOffset > 4 -> OptSize = (DataOffset - 5)*32, << Options:OptSize, Message/binary >> = Payload, << CWR:1, ECE:1, URG:1, ACK:1, PSH:1, RST:1, SYN:1, FIN:1 >> = << Flags:8 >>, %% Can now process the Message according to the %% Options (if any) and the flags CWR, ..., FIN. binary_to_list(Message) end.

Еще один язык, основанный целиком на сопоставлении с образцом — язык РЕФАЛ (Refal). Отличительная особенность его — в том, что основная структура данных в нем — двусвязный список, что позволяет выполнять сопоставление с более сложными образцами и делает РЕФАЛ удобным для сложных задач обработки текста или деревьев, например, XML. Вот пример программы на РЕФАЛе, проверяющей, является ли строка палиндромом, по правилам: строка вида a S a  — палиндром, если S — палиндром; строка из одного символа — палиндром; пустая строка — палиндром; остальные строки — не палиндромы.

Имитация
Сопоставление с образцом всегда можно заменить на ручной разбор случаев с использованием операций доступа к данным; при этом придется проделать работу компилятора по поиску оптимального дерева проверок и код, скорее всего, увеличится в несколько раз. Кроме того, компиляция сопоставления с образцом далеко не тривиальна, и реализованные вручную проверки, скорее всего, будут неоптимальны. Например, при компиляции сопоставления с образцом для типа с 20 конструкторами компилятор, скорее всего, сгенерирует вовсе не последовательность из двадцати if..else, а бинарное дерево проверок логарифмической высоты.

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

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

Сравнительно недавно появились техники («First class patterns» Марка Таллсена [168] и «Type-safe pattern combinators» Мортена Райгера [147]), позволяющие манипулировать образцами как первоклассными объектами, и, как следствие, позволяющие в том числе выражать образцы в виде обычных функций высшего порядка (см. 3) и писать определения в стиле сопоставления с образцом без помощи синтаксической поддержки языка.

Также недавно появилась удобная и мощная библиотека для работы с первоклассными образцами на Haskell [144] (см. также серию блог-постов Райнера Поупа об этой библиотеке, в блоге по тегу «pattern combinators» [145]). Приведем краткий пример кода с ее использованием:

Этот код эквивалентен следующему:

Основные преимущества первоклассных образцов — возможность отслеживать несовпадение значения с образцом во время выполнения (в этой ситуации при обычном сопоставлении произошла бы ошибка выполнения), возможность «дополнять» существующий образец новыми уравнениями и возможность определять принципиально новые разновидности образцов. При помощи первоклассных образцов можно, к примеру, реализовать «selective receive» (выборку сообщений по образцу из очереди процесса) в стиле Erlang. Это одна из мощных и уникальных возможностей Erlang.

11  Свёртка
(Fold)

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

История
Как утверждается в статье Грэма Хаттона «A tutorial on the universality and expressiveness of fold» ([88]), понятие свертки появилось в теории рекурсии в 1952 г. Свертки были впервые использованы в языке программирования APL (1962) для обработки списков. В 1978 г. свертки были упомянуты в работе Джона Хьюза «Why Functional Programming Matters» [84].

К произвольным структурам данных свертку впервые применил Г. Малкольм в 1990 г. в статье «Algebraic data types and program transformation» ([111]), обобщив идею свертки над списками. Эта идея получила развитие в очень известной статье Эрика Мейера, Маартена Фоккинги и Росса Патерсона «Functional programming with bananas, lenses, envelopes and barbed wire» ([117]) и многих других работах, где используется т. н. «универсальное свойство» свертки (описанное в вышеупомянутой статье Грэма Хаттона [88]). В 1998 г. в статье Ричарда Бёрда и Ламберта Меертенса «Nested datatypes» ([41]) было описано обобщение свертки на «вложенные» (полиморфно рекурсивные) алгебраические типы, а в статье Ральфа Хинзе «Efficient generalized folds» ([77]) и статье Джереми Гиббонса «Disciplined, efficient, generalized folds for nested datatypes» ([53]) это обобщение было улучшено.

Однако, шестью годами раньше, в 1992 г. появился язык Coq, исчисление индуктивных конструкций. В нём было разработано обобщение понятия свертки в качестве принципа индукции на значительно более сложный класс индуктивных типов (см. книгу «Coq’art: Interactive theorem proving and program development» [40] и статью «Inductive definitions in the system Coq: Rules and properties» [131])! Удивительно, что этот результат оставался незамеченным целых 6 лет: на первый взгляд некоторые определения сверток, предложенные, скажем, в «Nested datatypes» Бёрда и Меертенса [41], практически совпадают с теми, что автоматически генерирует Coq.

Интуиция
Рассмотрим несколько возможных операций над документами (возьмем для примера HTML):

• Подсчет количества слов или множества различных слов
• Вырезание картинок или javascript-сценариев
• Поиск абзаца, содержащего больше всего ключевых слов из заданного списка

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

• Подсчет слов: Результат алгоритма — целое число; вычисление происходит рекурсивно снизу вверх. Для текстового узла — обычный алгоритм; для комментария — 0; для иного узла — сумма результатов в его подузлах.
• Посчет множества различных слов: Результат алгоритма — множество строк; вычисление происходит рекурсивно снизу вверх. Для текстового узла — обычный алгоритм; для комментария — пустое множество; для иного узла — объединение результатов для подузлов.
• Вырезание картинок или javascript-сценариев: Результат алгоритма — узел (документ) или специальное значение «пустой узел» (на случай, если весь документ, скажем, состоял из одной-единственной картинки). Для текстового узла или комментария  — сам узел; для тега IMG или SCRIPT — пустой узел; для иного узла — узел с теми же тегом и атрибутами, чей список подузлов составлен из непустых результатов применения алгоритма к подузлам исходного узла.
• Рендеринг в формат PostScript (например, последовательность команд для принтера): результат алгоритма — последовательность команд; вычисление происходит рекурсивно снизу вверх. Для каждого из типов узлов результаты подузлов конкатенируются, возможно, перемежаясь дополнительными командами.

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

Описание
Пусть T — рекурсивно определенный алгебраический тип (см. 9), обладающий конструкторами K₁ … K_n.

Определим алгебраический тип F tau с конструкторами F₁ … F_n, где сигнатура F_i получается из сигнатуры K_j заменой аргументов типа T на аргумент типа tau. Будем называть F схемой рекурсии для T.

Рассмотрим пример — дерево следующего вида:

Для такого типа n=2, K₁=Leaf, K₂=Fork.

Схема рекурсии же для него такова:

Особенность такого типа в том, что он, будучи примененным к tau=IntTree, дает тип, эквивалентный IntTree; а при вычислении какого-либо значения снизу вверх этот тип соответствует типу «контекста» такого вычисления (известны данные текущего узла и результаты рекурсивных вызовов). Значение такого типа и является аргументом для процедуры свертки.

Итак, свёртка (вычисление снизу вверх) над типом T определяется функцией из соответствующего ему типа F tau в значение типа tau. Чтобы задать вычисление снизу вверх над типом деревьев, нужно задать функцию из IntTree' tau в tau. Например, функция для подсчета количества листьев в дереве будет выглядеть так:

Еще раз обратим внимание, что тип IntTree' сам по себе не рекурсивен, а аргументами Fork' вместо значений типа IntTree' tau являются просто значения типа tau, т. е. результаты вычисления снизу вверх в непосредственных подструктурах.

Опишем функцию, выполняюшую свертку (вычисление снизу вверх) согласно заданной процедуре:

Тогда функция, выполняющая подсчет количества листьев в дереве, будет задаваться как countLeaves = foldTree leafCountFold.

Показательно рассмотреть процедуру копирования дерева, чей тип получается, если подставить IntTree в качестве tau: в этом случае сверточная процедура имеет тип Tree' IntTree -> IntTree. С практической точки зрения процедура бесполезна, однако она иллюстрирует связь между исходным типом, его схемой рекурсии и операцией свертки.

Полностью аналогично определяется свёртка для параметрических алгебраических типов, например:

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

---

Рис. 7: Свёртка как подмена конструкторов

---

Теперь рассмотрим, во что вырождается понятие свертки в применении к спискам, задаваемым как data List α = Nil | Cons α (List α): схема рекурсии этого типа — тип data List' α tau = Nil' | Cons' α tau, поэтому тип сверточной процедуры — List' α tau -> tau; можно вместо процедуры такого типа задать две «процедуры», обрабатывающие каждый из двух возможных конструкторов, по отдельности: значение типа tau для конструктора Nil' и α -> tau -> tau для конструктора Cons'. Получающаяся процедура называется правой сверткой:

Похожая процедура, однако образованная по другой схеме, называется левой сверткой, и не имеет очевидных аналогов для других структур, кроме списков. Она как бы представляет список не как сумму головы и хвоста, а как сумму начальной части и последнего элемента. Это позволяет использовать нерекурсивный алгоритм вычисления (см. хвостовой вызов (см. 7)):

Формулы для левой и правой свертки выглядят так:

В ленивом языке левая и правая свёртка принципиально различаются. Для правой свертки, как видно, результат, независимо от элементов a₂ …, имеет вид a₁ # …, и слабая заголовочная нормальная форма (СЗНФ, WHNF) этого выражения зачастую может быть вычислена и без вычисления свертки по всему остатку списка; это позволяет в т. ч. использовать правую свертку на бесконечных списках.

Различие для ленивого языка можно увидеть на примере реализации процедуры filter:

Проиллюстрируем ленивость foldr вычислением чуть более простого примера:

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

У левой свертки есть более экзотический, но значительно более полезный аналог — строгая левая свёртка, отличающаяся лишь строгостью (энергичностью) (см. статью «Laziness» в Haskell wikibooks [14]) по «аккумулятору»:

В качестве примера алгоритма, требующего строгой левой свертки, можно привести вычисление суммы списка:

В первом случае глубокая рекурсия внутри foldr приводит к переполнению стека.

Во втором случае результат foldl вычисляется итеративно (в смысле, указанном в статье о хвостовых вызовах (см. 7)) и успешно (в чем можно убедиться на третьем примере), однако результатом оказывается невычисленный терм (((0+1)+2)+...)+1000000, и переполнение стека происходит уже при попытке форсировать его вычисление для распечатки.

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

Итак:

• Правая списочная свёртка используется, когда известно, как составить результат для всего списка из его головы и результата для хвоста, причем часть результата «известна» и без полного результата для хвоста (т. е. вычисляется лишь на основе головы — например, в случае map или filter).
• Строгая левая свёртка используется, когда алгоритм выражается в виде императивного прямого цикла по списку с аккумулятором.
• Обычная левая свёртка используется, когда алгоритм выражался бы в виде правой свертки, будь список перевернут. Эта разновидность свертки нужна исключительно редко.

Подробности, касающиеся различий левых и правых списочных сверток в отношении ленивости и строгости, описаны в статье «Foldr, Foldl, Foldl’» в Haskellwiki ([8]).

---

Рис. 8: Дерево вычисления ассоциативной свертки по сложению

---

В случае, когда тип результата свертки совпадает с типом элементов сворачиваемого списка, можно говорить о коммутативности (f x y == f y x) и ассоциативности ( f (f x y) z == f x (f y z)) сверточной операции. Если операция ассоциативна, то такая операция называется списочным гомоморфизмом, левая и правая свертки по ней совпадают, и свертку можно вычислить с помощью «дерева» (на рис. 8 изображено дерево, образующееся в процессе вычисления суммы списка), что позволяет распараллелить вычисление (вычисляя дерево «по слоям» снизу вверх и распараллеливая вычисление каждого слоя) или сделать его инкрементальным (при изменении элемента списка в дереве затрагивается лишь O(log n) узлов, лежащих на пути от корня к нему; возможны также вставка/удаление/конкатенация за логарифмическое время). Многие параллельные алгоритмы основаны на таком подходе; узнать о нем больше можно в следующих источниках:

• В книге «Vector models for data-parallel computing» Гая Блеллоха ([42]): впервые предложен и описан подход к разработке параллельных алгоритмов на основе сверток и пробегов (префиксных сумм), и приведено множество очень красивых и несложных алгоритмов.
• Статья того же автора «Prefix sums and their applications» ([43]) обрисовывает основные положения этого подхода и некоторые их применения.
• В блог-посте Хайнриха Апфельмуза «Monoids and finger trees» описана структура данных «дерево с указателем» (finger tree), позволяющая компактно и просто сформулировать, параллелизовать и инкрементализовать множество алгоритмов, и даны ссылки на дополнительную литературу.
• В блог-посте Дэна Пипони «Fast incremental regular expression matching»¹³ описано применение деревьев с указателем для реализации инкрементального (и параллельного) поиска по регулярным выражениям.
• В блог-посте Дэна Пипони «An approach to algorithm parallelisation» префиксные суммы применены для параллелизации хорошо известного и на первый взгляд вовсе не параллелизуемого решения задачи о подотрезке с максимальной суммой.

Если операция к тому же коммутативна, то результат свертки не зависит от порядка элементов в списке и можно еще увеличить степень параллелизма: фактически, достаточно в произвольном порядке объединять элементы и промежуточные результаты объединения по сверточной операции, пока не останется всего одно значение, которое и будет окончательным результатом. Все агрегатные функции SQL (MIN,MAX,SUM, DISTINCT,...) являются коммутативными свёртками.

Существует примечательная и очень полезная теорема — «третья теорема о гомоморфизмах» (описана в статье «The third homomorphism theorem» Джереми Гиббонса [70]). Она гласит, что если алгоритм можно реализовать как в виде левой свертки, так и в виде правой свертки с тем же начальным значением, то его можно реализовать и в виде ассоциативной свертки (которая поддается распараллеливанию и инкрементализации).

Использование
Чаще всего в функциональном программировании применяются списочные свертки и их аналоги. Приведем пару примеров:

В модуле Data.ByteString.Lazy байтовые потоки представляются в виде ленивого списка из байтовых массивов. Там же определена функция foldlChunks (код этого и следующего примера слегка модифицирован для лучшей понимаемости):

Эта функция применяется, например, в библиотеке digest [100] (привязка к процедурам вычисления CRC32 и Adler32 из zlib):

То есть, при вычислении CRC32 от ленивого байтового потока функция crc32_c (обновление CRC32 заданным байтовым массивов) вызывается процедурой foldlChunks для каждого байтового массива, входящего в поток.

В сервере HAppS-Server [110] определена процедура для кодирования URL-адресов:

Эта процедура группирует переданные параметры при помощи partition и для каждой последовательности параметров с одинаковым ключом при помощи foldl порождает отрезок строки вида foo=bar,baz,qux.

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

Одинаковый принцип действия сверток над любой структурой данных позволяет им обладать особыми алгебраическими свойствами, полезными для оптимизации программ: см. статью «Functional programming with bananas, lenses, envelopes and barbed wire» [117].

В языке Haskell концепция структур, поддающихся списочной свертке (даже если сама структура — не список, а, например, упорядоченное множество, реализованное с помощью дерева), выражена в классе типов (см. 13) Foldable, а более общая концепция, связанная со схемами рекурсии — в библиотеке «fixpoint» [109], реализующей (буквально в несколько строк) идеи из статьи «Functional programming with bananas …» [117], и аналогичной, но более современной и значительно более сложной библиотеке «multirec» [148].

В качестве примера применения сверток в нефункциональном языке можно привести API компилятора javac для работы с синтакическим деревом кода [25]. Класс TreeScanner представляет собой сверточную операцию почти в чистом виде: в нем есть функции для отображения листовых узлов и функция для комбинирования промежуточных результатов.

Одно из важнейших применений ассоциативных и коммутативных сверток — параллельное программирование. В статье «Prefix sums and their applications» [43] и книге «Vector models for data-parallel computing» [42] обсуждаются применения сверток и родственной им концепции «пробега» (англ. scan) к параллельному программированию. В настоящее время описанные в этих источниках алгоритмы применяются посвеместно, к примеру, при программировании графических процессоров.

Реализация
Почти все функциональные и динамические языки (Haskell, OCaml, Scala, Ruby, Python, Scheme, Perl и прочие) содержат в стандартной библиотеке аналог операции свертки над списками. Он есть даже в PHP, однако по неизвестным автору причинам поддерживаются только свертки над целыми числами (изучение исходного кода не показало каких-либо препятствий для снятия этого ограничения).

Очень интересно обобщение сверток на структуры данных с зависимыми типами, используемое в системе автоматизированного доказательства теорем Coq (сайт [7]). В Coq при определении индуктивного (алгебраического) типа автоматически генерируется соответствующий ему принцип индукции. Например, для типа списков, сортированных согласно заданному отношению порядка, получается приблизительно такой принцип индукции по отсортированным спискам:

«Если свойство P выполняется для пустого списка, для всякого одноэлементного списка, и из x ≤ y и сортированности списка y::rest, удовлетворяющего P, можно вывести P для x::y::rest, то свойство P выполняется для любого сортированного списка».

Ознакомиться с Coq и с идеологией программирования с зависимыми типами можно, например, в книге «Coq’Art: Interactive theorem proving and program development» ([40]) и в презентации ([181]).

12  Структурная / вполне обоснованная рекурсия (индукция)
(Structural / well-founded recursion (induction))

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

Интуиция
Рассмотрим функцию поиска элемента в бинарном дереве поиска (binary search tree, BST)

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

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

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

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

Описание
Будем говорить, что отношение ≺ на множестве M является вполне обоснованным (понятие описано также в статье в Wikipedia «Well-founded relation» [22]), если не существует бесконечной последовательности a₁ ≺ a₂ ≺ …. Можно переформулировать это свойство еще двумя способами: «в графе отношения ≺ нет циклов», или «в любом подмножестве M есть хотя бы один минимальный элемент относительно ≺».

Для конечных рекурсивно определенных структур данных (таких как списки, деревья и т. п.) отношение «a ≺ b, если a — подструктура b», очевидно, является вполне обоснованным.

Процедура f a b .. x .. называется структурно рекурсивной (см. также статью в Wikipedia «Structural induction» [19]) по аргументу x, где x имеет алгебраический тип (см. 9) T, если она определена для всех нерекурсивных конструкторов T (т. е. для минимальных элементов этого типа по отношению непосредственного включения) и ее определение для таких конструкторов не содержит рекурсивных вызовов, и при этом в уравнении для каждого из рекурсивных конструкторов T всякий рекурсивный вызов производятся от непосредственных аргументов этого конструктора. Если убрать из этого определения требование «процедура определена для всех конструкторов» и оставить лишь ограничение на аргументы рекурсивных вызовов, то полученное свойство будет гарантировать лишь завершаемость, но необязательно тотальность (т. е. наличие результата на всех возможных аргументах)¹⁵.

Например, вышерассмотренная процедура поиска значения в дереве структурно рекурсивна по дереву, чей тип обладает одним нерекурсивным конструктором Leaf и одним рекурсивным конструктором Fork. Вот этот тип:

Процедура была определена двумя уравнениями, первое из которых соответствует случаю Leaf и не содержит рекурсивных вызовов, а второе соответствует случаю, когда аргумент имеет форму Fork a l r, и рекурсивные вызовы производятся лишь от аргументов этого конструктора — l или r.

Из вышесказанного следует, что структурно рекурсивная процедура обязательно завершается на всех конечных аргументах. Условие конечности очень важно. Haskell, благодаря ленивым вычислениям, позволяет манипулировать бесконечными структурами данных, и свойство завершаемости, разумеется, выводимо из структурной рекурсивности лишь в случае конечных структур. Кроме того, в ленивых языках используется более тонкое понятие завершаемости, поэтому в рамках данной статьи мы будем предполагать, что речь идет о строгом (энергичном) языке с синтаксисом Haskell.

Завершимость, конечно, присутствует и в случае, когда вместо отношения «являться подструктурой» используется другое вполне обоснованное отношение между аргументами исходного и рекурсивного вызова. В этом случае говорят, что процедура определена при помощи вполне обоснованной индукции (см. также презентацию Ива Берто о вполне обоснованной индукции в Coq «Well-founded induction» [39]). В статье Лоуренса Полсона «Constructing recursion operators in intuitionistic type theory» [132] описан примененный в системе Coq способ конструктивной реализации вполне обоснованной индукции в системе типов, допускающей только структурную рекурсию.

Заметим, что натуральные числа также образуют алгебраический тип с двумя конструкторами: «ноль» и «n+1»: data Nat = Zero | Next Nat, поэтому можно считать структурно рекурсивными арифметические процедуры, определенные для n через результат для n−1.

Структурная рекурсия абстрагируется оператором свертки (см. 11).

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

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

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

Функция вычисления длины списка структурно рекурсивна по списку:

Рекурсивный вызов производится от терма xs, являющегося непосредственным аргументом конструктора (:) в терме (x:xs).

Функция вычисления факториала структурно рекурсивна по своему аргументу-натуральному числу.

Функция вставки в бинарное дерево (для простоты рассмотрим несбалансированное дерево) структурно рекурсивна по аргументу-дереву:

Рекурсивные вызовы производятся от термов l или r, являющихся непосредственными аргументами конструктора Fork в терме (Fork a l r).

Идиоматическая реализация быстрой сортировки списка¹⁷ не является структурно рекурсивной:

Как видно, здесь аргументы рекурсивных вызовов — термы вида filter (>x) xs, не являющиеся непосредственными аргументами конструктора (:) в терме (x:xs).

Впрочем, эта реализация является, например, вполне обоснованно рекурсивной, поскольку рекурсивные вызовы производятся от списков, чья длина строго меньше длины исходного списка (это рассуждение основано на таком свойстве filter, как length (filter p xs) <= length xs).

Процедура объединения двух сортированных списков является вполне обоснованно рекурсивной:

В данном случае имеет место вполне обоснованная индукция: аргументы рекурсивных вызовов merge (обозначим их xs', ys') связаны с аргументом исходного (обозначим их xs, ys) следующим вполне обоснованным отношением:

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

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

Обратим внимание, как было изменено определение merge, чтобы удовлетворить свойству структурной рекурсивности: были в явной форме выделены уравнения для каждого из конструкторов, составляющих алгебраический тип [Int] третьего аргумента.

Теперь явно имеет место структурная рекурсия по третьему аргументу (заметим, что без уравнения (X) функция не была бы структурно рекурсивной, т. к. не был бы рассмотрен базовый (минимальный) случай относительно аргумента структурной рекурсии; была бы гарантирована лишь завершимость, но не тотальность).

Рассмотрим еще один пример: вычисление наибольшего общего делителя.

Эта процедура также не является структурно рекурсивной, однако является вполне обоснованно рекурсивной по отношению между аргументами рекурсивного (a', b') и исходного (a, b) вызовов «a’+b’ < a+b», поэтому она гарантированно завершается. Вполне обоснованная индукция становится несколько более явной, если ввести дополнительный аргумент, как и в случае mergesort:

Теперь стало ясно видно, что для любого вызова gcd' a b s верно a+b == s, следовательно при a/=0 && b/=0 верно a<s && b<s, следовательно при рекурсивных вызовах аргумент s уменьшается, но становится нулем только если a==0 && b==0, а в этом случае «сработает» какое-либо из первых двух уравнений. Поэтому функция gcd является и завершающейся, и тотальной.

Примеры mergesort и gcd взяты из презентации Ива Берто «Well-founded induction» [39].

Еще одно часто применяемое в специфических областях вполне обоснованное отношение — т. н. «гомеоморфное вложение». Это — отношение над формулами, и его свойство вполне обоснованности применяется в таких областях, как системы переписывания термов (например, при упрощении выражений), суперкомпиляция и т. п. Это отношение и его приложение к суперкомпиляции описаны, например, в статье Мортена Соренсена и Роберта Глюка «An algorithm of generalization in positive supercompilation» ([157]).

Реализация
Языки Coq, Epigram, Agda допускают только структурную рекурсию, причем в Coq при введении структурно рекурсивного определения необходимо явно указывать аргумент, по которому производится структурная рекурсия; как следствие, все процедуры на этих языках завершаются (если исключить из рассмотрения присутствующую в Coq коиндукцию). В стандартной библиотеке языка Coq есть модуль «Coq.Init.Wf» ([29]), реализующий вполне обоснованную индукцию. В последних версиях реализована также экспериментальная команда Function, позволяющая непосредственно определять не-структурно рекурсивные функции и отдельно доказывать свойство вполне обоснованности отношения между аргументами исходного и рекурсивных вызовов. Кроме того, Coq при определении индуктивного типа данных (см. 9) генерирует определения, соответствующие операторам структурной рекурсии над этим типом.

13  Класс типов
(Type class)

Суть
Реализации интерфейсов для типов и их комбинаций указываются в произвольном месте программы и отдельно от определений самих типов.

История
Классы типов были предложены Филипом Вадлером в 1989 году в статье «How to make ad-hoc polymorphism less ad hoc» ([174]) в качестве варианта специального полиморфизма. Изначально предполагалось применить их для реализации перегрузки арифметических операторов и операторов сравнения. Авторы работы были недовольны сложившейся ситуацией: на тот момент среди разработчиков языков программирования отсутствовало общее мнение о том, как следует решать связанные с этим проблемы. К примеру, язык ML вводил специальное понятие «типов, сравнимых на равенство» (eqtypes), а стандарт этого языка хоть и упоминал возможность перегрузки арифметических операторов, но не уточнял, что это такое.

Классы типов оказались удачным решением и вошли в стандарт языка Haskell. С тех пор было найдено огромное множество различных применений классов типов, они стали одним из основных элементов системы типов Haskell, его «визитной карточкой», а также стали проникать в некоторые другие языки (Mercury, Coq). Кроме того, был предложен ряд расширений, увеличивающих выразительную силу и удобство пользования классами типов; вот некоторые из них:

• Многопараметрические классы типов (Саймон Пейтон-Джонс, Марк Джонс, Эрик Мейер, «Type classes: an exploration of the design space», 1997 г. [136]);
• Функциональные зависимости (Марк Джонс, «Type classes with functional dependencies», 2000 г. [93]);
• Семейства типов (две статьи Чакраварти, Келлера и Пейтона-Джонса: «Associated types with class» ([49], 2005), «Associated type synonyms» ([48], 2005), а также «Type checking with open type functions» Чакраварти, Пейтона-Джонса и других ([153], 2008)).

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

Интерфейсы позволяют:

• Применять клиентский код ко множеству различных типов, коль скоро эти типы реализуют нужные операции;
• Применять клиентский код к типам, недоступным клиенту на момент написания и компиляции.

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

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

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

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

Описание
Классом типов называется именованный набор сигнатур операций, упоминающих этот тип. Например: (все примеры в данной статье написаны на языке Haskell)

В этом примере объявлен класс Hashable: «тип, годный в качестве ключа хэш-таблицы». Класс состоит из двух сигнатур операций: операции хэширования и операции сравнения на равенство (обратите внимание на отличие сигнатуры equal от сигнатуры equals в таких ОО-языках, как Java или C#).

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

Такая форма полиморфизма называется «ограниченным параметрическим полиморфизмом».

В этом примере функция makeHashtable, требует, чтобы тип key принадлежал классу типов Hashable. Она принимает на вход список пар (key,val), а возвращает функцию поиска, отображающую ключ типа key в значение типа val или в сигнал об отсутствии значения для этого ключа.

Для того, чтобы указать реализацию класса типов для конкретного типа, необходимо объявить экземпляр этого класса типов. Например, объявим экземпляр Hashable для типа целочисленных пар.

Очень часто можно использовать при реализации класса типов реализацию других классов типов. Например, при реализации Hashable для пар типа (α,β) можно использовать реализацию Hashable для α и для β:

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

Понятие класса типов также применяется к параметрическим типам с одним или несколькими аргументами, например, Tree α; такие типы также называются «типовыми конструкторами»¹⁸. В этом случае сигнатуры операций класса могут включать в себя применение этого конструктора. В нижеприведенном примере записан класс типов, соответствующий понятию коллекции с операциями «размер», «преобразование в список и обратно», «проверка вхождения», «добавление и удаление», и определена его реализация для конструктора типа списков [α].

Использование
Выше уже был приведен один пример использования классов типов: библиотека хэш-таблиц. Приведем еще несколько примеров их использований из библиотек языка Haskell.

• Haskell определяет несколько стандартных классов типов:
  • Арифметические классы Num, Integral, Floating и т. п., соответствующие понятию чисел с определенными над ними различными операциями;
  • Eq и Ord — классы значений, сравнимых на равенство и на упорядоченность;
  • Show и Read — классы значений, обладающих строковым представлением и способом воссоздать значение из строки;
  • IArray, MArray — многопараметрические классы читаемых и изменяемых массивов (см. статью в Haskellwiki «Arrays» [1]).

  А также более «абстрактные» классы:

  • Monad — класс монад;
  • Monoid — класс типов, чьи значения образуют алгебраическую структуру «моноид» (см. статью «Моноиды в Haskell и их использование» (Дэн Пипони, перевод Кирилла Заборского) [141], а также презентацию Эдварда Кметта «Introduction to monoids» [102]), т. е. на значениях определена бинарная операция «комбинирования»:
    mappend :: (Monoid m) => m -> m -> m
    А также задан «нейтральный элемент» mempty :: (Monoid m) => m, являющийся единицей для mappend); а также похожий класс MonadPlus;
  • Foldable и Traversable — классы «Структура данных, поддающаяся свертке (см. 11)» и «Структура данных, поддающаяся обходу»;

  Существует прекрасная и очень подробная статья Брента Йорджи обо всех основных классах типов в Haskell, под названием «Typeclassopedia» [179].

• Популярная комбинаторная библиотека (см. 14) случайного тестирования QuickCheck Коэна Клэссена ([52]) основана на классе Arbitrary, соответствующему (упрощенно) понятию «тип, для которого известна процедура порождения случайных значений этого типа». В библиотеке определяются экземпляры этого класса для некоторых основных типов и вывод экземпляров для пар, списков и т. п. Пользователь библиотеки может также определить экземпляр класса Arbitrary для своих типов данных. Скажем, примерно так выглядит код порождения случайных бинарных деревьев: для порождения случайного дерева с вероятностью 2/3 порождается случайное значение и обертывается «листом», либо с вероятностью 1/3 рекурсивно порождаются два случайных дерева и обертываются «вилкой» (см. также статью об алгебраических типах (см. 9)).
  data Tree α = Leaf α | Fork (Tree α) (Tree α) instance (Arbitrary α) => Arbitary (Tree α) where arbitrary = frequency [ (2, liftM Leaf arbitrary), (1, liftM2 Fork arbitrary arbitrary) ]

  Данная библиотека интересна также тем, что портирована на множество других языков, от Erlang до Java и C++, и эти реализации тем или иным образом имитируют типы классов.

• Библиотека двоичной сериализации/десериализации «binary» также основана на классах типов. С их помощью определены способы сериализации/десериализации для базовых типов и комбинаций типов (пар, списков и т. п.). Вот пример ее использования для сериализации/десериализации арифметических выражений, взятый с сайта библиотеки:
  data Exp = IntE Int | OpE String Exp Exp instance Binary Exp where put (IntE i) = put (0 :: Word8) >> put i put (OpE s e1 e2) = put (1 :: Word8) >> put s >> put e1 >> put e2 get = do tag <- getWord8 case tag of 0 -> liftM IntE get 1 -> liftM3 OpE get get get

  Аналогичный подход используется в известной статье Эндрю Кеннеди «Pickler combinators» ([98]) из серии «жемчужины функционального программирования (functional pearls)», однако там вместо классов типов используется передача словарей (см. раздел «Имитация»).

• Классы типов могут быть использованы для частичной эмуляции зависимых типов (типов, параметризованных значениями или высказываниями: например, векторов определенной длины с гарантированно безопасным доступом без выхода индексов за границы, или сбалансированных деревьев, чье свойство сбалансированности невозможно нарушить в рамках системы типов, и т. п.). Например, см. статью Конора Мак Брайда «Faking it: Simulating dependent types in haskell» ([114]).
• Библиотека линейной алгебры фиксированной размерности «Vec» [60] целиком основана на классах типов и использует их для проведения операций над размерностями во время компиляции, что позволяет полностью избавиться от проверок выхода за границы вектора или матрицы во время исполнения.
• В статье-«жемчужине» «Generic descrimination: sorting and partitioning unshared data in linear time» Фрица Хенгляйна ([74]) при помощи классов типов описывается способ сортировки и группировки списков за линейное время, работающий для большой части часто встречающихся типов.
• Недавно появившаяся в компиляторе GHC поддержка семейств типов основана на классах типов и предоставляет множество очень интересных возможностей (упомянутые в секции «История» статьи Пейтона-Джонса и Чакраварти [49], [48], [153]). Среди практических применений этих возможностей — «самооптимизирующиеся» контейнеры (библиотека «unboxed-containers» на Hackage [104]), образцы (см. 10) как объекты первого класса (библиотека «first-class-patterns» [144]), обобщенные префиксные деревья (библиотека TrieMap [176]) и т. п.

Реализация
Наиболее распространенный язык, поддерживающий классы типов — это Haskell. Именно в нем они впервые появились в 1989 г. В 1997 г. в компиляторе GHC появилась поддержка многопараметрических классов типов, однако в стандарт Haskell98 не вошла. В 2005 г. появилась поддержка семейств типов.

На странице «Research papers/Type systems» в разделе «Type classes» [17] в Haskellwiki можно найти множество исследовательских работ, посвященных различным аспектам семантики, реализации и применения классов типов.

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

В языке OCaml есть концепция, родственная классам типов — модули. В статьях Чакраварти и других «ML modules and Haskell type classes: a constructive comparison» [177] и «Modular type classes» [61] приведено их сравнение, показаны параллели между их возможностями и стилем программирования.

«Концепты», так и не вошедшие в стандарт C++0x, также схожи по своим возможностям с классами типов. В статье «A comparison of C++ concepts and Haskell type classes» Жана-Филиппа Бернарди и других [38] приведено их сравнение. Эта статья чрезвычайно интересна и ее стоит прочитать даже тем, кто не интересуется C++, поскольку в ней само понятие класса типов «разбирается по косточкам», рассматриваются его составляющие, оси изменчивости возможностей и обсуждается роль этих возможностей в программировании.

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

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

Еще один яркий пример такого подхода — модуль Data.Monoid [27]. Однако данный прием все же предполагает, что все возможные реализации фиксированы и известны статически, и не позволяет создать реализацию класса для некоторого типа динамически: скажем, полиморфная процедура сортировки, сортирующая значения типа α, где Ord α, сгодится для сравнения элементов списка по задаваемому пользователем условию (скажем, для сортировки рядов таблицы по заданным столбцам). Поэтому процедурам сортировки приходится принимать на вход процедуру сравнения непосредственно.

Непосредственная передача функциям реализаций всех операций для типа называется стилем передачи словарей (dictionary-passing style). Например, сравним сигнатуры процедур для построения хэш-индекса с использованием классов типов и с использованием стиля передачи словарей:

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

Еще один любопытный пример использования стиля передачи словарей приведен в статье о замыканиях (см. 4), в секции «Использование».

14  Комбинáторная библиотека
(Combinator library)

Суть
Модель предметной области, выстроенная из небольшого количества «базовых» сущностей и абстрактных способов их комбинирования.

Интуиция
Рассмотрим задачу проверки пользовательского ввода: например, является ли заданная строка записью числа с плавающей точкой или, скажем, даты в формате YYYY/Mon/DD HH:MM:SS. Есть как минимум три различных подхода к решению такой задачи:

• написание специализированного кода для разбора строки: проверка строки символ за символом, использование indexOf, subString и т. п.;
• использование специализированной библиотеки для разбора строк заданного типа — например, функций scanf или strptime;
• использование регулярных выражений.

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

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

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

Именно об отличиях в характере универсальности между первым и третьим способом мы и поговорим.

Оба способа моделируют предметную область «Проверка строк на принадлежность к некоторому языку».

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

Второй способ моделирует предметную область непосредственно, хотя и более узко. Язык регулярных выражений специально заточен под комбинируемость, и из двух регулярных выражений, моделирующих языки A и B, легко собрать третье, моделирующее язык AB={a b|a ∈ A ∧ b ∈ B} и т. п. Предметная область собирается, например, из следующих элементов и способов их комбинирования:

Примитивы:

• классы символов (литералы: a, диапазоны: [0-9a-zA-Z], классы: [:space:]);
• начало и конец строки (^ и $);
• пустая последовательность (()),

и способы их комбинирования:

• последовательная композиция (E₁E₂);
• параллельная композиция (E₁|E₂);
• повторение 0 или 1 раз (жадное или нет) (E?);
• повторение 0 или более раз (жадное или нет) (E∗);
• повторение 1 или более раз (жадное или нет) (E+);
• повторение от m до n раз (жадное или нет) (E{m,n});
• заключение в скобки (это чисто синтаксический элемент: если бы регулярные выражения задавались не последовательностью символов, а собственным синтаксическим деревом, то для целей валидации в скобках необходимости бы не было) ((E));
• значимость или незначимость регистра.

Повторимся: важен не синтаксис регулярных выражений, а набор предоставляемых ими примитивов и комбинаторов.

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

Регулярные выражения — пример очень простого и понятного, но в то же время невероятно мощного и универсального приема моделирования (не только в программировании) — комбинáторной модели предметной области.

Описание
Программные библиотеки, моделирующие предметную области при помощи комбинáторной модели, называются комбинáторными библиотеками.

Для комбинаторных библиотек характерно:

• соответствие терминологии библиотеки и терминологии предметной области;
• состав: типы, примитивы, комбинаторы первого и высшего порядка;
• свойство замыкания;
• возможность эффективной реализации.

Соответствие терминологии библиотеки и терминологии предметной области.

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

Состав: типы, примитивы, комбинаторы первого порядка, комбинаторы высшего порядка.

Обычно комбинаторная библиотека состоит из «примитивов» (базовых, неделимых сущностей предметной области, таких как «регулярное выражение, распознающее один символ») и «комбинаторов» (способов комбинирования сущностей в более сложные).

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

Комбинаторы могут выражаться друг через друга: например, в случае регулярных выражений верно A? = A|() и A+ = AA∗.

Довольно часто комбинаторные библиотеки открыты для расширения: пользователь может определить свои собственные примитивы и комбинаторы, равноправные встроенным в библиотеку (впрочем, в случае регулярных выражений это не так).

Как и у любой другой программы, терминологическая основа комбинаторной библиотеки — это типы используемых в ней сущностей. Типы определяют, в частности, в каком контексте уместны какие примитивы и комбинаторы, и какие из них совместимы друг с другом. Так, логично, что в случае комбинаторной библиотеки для описания потоков данных (например, электронных схем) комбинатор «последовательная композиция блока с самим собой N раз» уместен только если типы входа и выхода блока совпадают.

Одно из современных «веяний» в типизации в комбинаторных библиотеках — использование GADT (обобщенных алгебраических типов) (см. 9). Например, см. иллюстрацию этой техники для парсеров в соответствующем разделе статьи о GADT в haskellwiki ([9]) и модель представления патчей в системе контроля версий darcs, описанную в презентации Ганеша Ситтампалама «Darcs and GADTs» ([154]).

Свойство замыкания.

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

Нарушение свойства замыкания делает язык не только сложнее (так как становится необходимо различать простые и составные сущности и помнить, в каком контексте какие из них допустимы), но и менее выразительным из-за невозможности использовать некоторые комбинаторы в некоторых контекстах. Более того, это закрывает путь к развитию концепции, навсегда ограничивая ее рамками первоначального замысла создателя. Автор данной статьи принадлежит к сторонникам мысли «Путь к выразительности языка — не добавление возможностей, а устранение искусственных ограничений» (также известна цитата: «Expressive power should be by design rather than by accident» из классической статьи Питера Ландина «The next 700 programming languages» [105]).

Пример нарушения этого свойства — типы в языке FORTRAN: FORTRAN позволяет создавать массивы из примитивных типов, однако не позволяет создавать массивы из массивов (многомерные массивы — не универсальное решение, т. к. они не позволяют использовать т. н. «зубчатые» (jagged) массивы, т. е. такие, чьи ячейки имеют разный размер).

Возможность эффективной реализации.

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

Почти всегда имеет место компромисс между эффективностью реализации и универсальностью²⁰. Например, регулярные выражения в самом простом случае можно чрезвычайно эффективно реализовать при помощи компиляции в конечный автомат (преобразование подробно описано в статье «Regular expression matching can be simple and fast» Расса Кокса [57]); в более сложных языках регулярных выражений также обычно стараются предоставить набор операторов, допускающий эффективную реализацию.

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

Однако этого удается достичь не всегда: например, в случае нелинейных преобразований точек ничего не остается, кроме как применять композицию из нескольких преобразований путем последовательного применения каждого из них, т. е. композиция тысячи преобразований будет, по меньшей мере, в тысячу раз менее эффективна, чем каждое преобразование по отдельности. Более того, свои издержки вносит и сама «инфраструктура» библиотеки; стоит проектировать библиотеку так, чтобы эти издержки были минимальны, т. е. чтобы библиотека переносила «тяжелые» операции в примитивы. Этот подход рассмотрен в упомянутой лекции 4 курса [186] по отношению к преобразованиям координат.

Джон Хьюз читал целый курс о комбинаторных библиотеках «Designing and Using Combinators: The Essence of Functional Programming»; материалы курса свободно доступны в интернете ([83]).

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

• удобная синтаксическая поддержка создания сложных структур данных;
• поощрение неизменяемых данных, что, как рассмотрено в статье «Изменяемое состояние: опасности и борьба с ними» Евгения Кирпичёва ([185]), положительно сказывается на модульности и комбинируемости;
• обилие способов комбинирования — скажем, ФВП (см. 3) и замыкания (см. 4);
• очень мощные системы типов, позволяющие удобно моделировать терминологию предметной области.

В знаменитой статье «An experiment in software prototyping productivity» [82] Пола Хьюдэка и Марка Джонса на стр. 9 описывается, как программист на Haskell разработал для решения задачи комбинаторную библиотеку (язык представления геометрических областей), благодаря чему его код оказался в 2 раза короче, чем код ближайшего конкурента (и в 13 раз короче, чем код на С++)²¹.

Аналогичный язык для представления картинок и анимаций кратко рассмотрен в очень интересной статье Пола Хьюдэка «Modular domain specific languages and tools» [81], где также рассмотрены и некоторые другие аспекты разработки комбинаторных библиотек.

Существует много библиотек для комбинаторного представления графики: [130], [3] (модуль Grid) и т. п.

Одно из самых удачных применений комбинаторных библиотек (в том числе и за пределами ФП) — это библиотеки для синтаксического анализа. Одна из лучших статей на данную тему — статья Филипа Вадлера «How to replace failure by a list of successes» [171], а также статья Грэхема Хаттона «Higher-order functions for parsing» [87] и его совместная статья с Эриком Мейером «Monadic parsing in Haskell» [89]. Данный подход оказался настолько хорош, что портированные комбинаторные библиотеки синтаксического разбора существуют для очень большого количества языков, далеко не только функциональных. Однако, пользуются ими все же почти исключительно в функциональных языках — вероятно, из-за неудобства манипулирования комбинаторами без синтаксической поддержки монад, ФВП (см. 3) и замыканий (см. 4). В презентации Эдварда Кметта «Iteratees, Parsec and monoids» [103] описан подход, позволяющий сделать комбинаторы синтаксического разбора инкрементальными, однако уровень сложности этого материала очень высокий, требуется знание некоторых других концепций, в частности, монад и т. н. iteratees.

В статье Криса Окасаки «Why would anyone ever want to use a sixth-order function?» [126] описаны, в приложении к синтаксическому разбору, примеры полезных комбинаторов чрезвычайно высоких порядков, вплоть до 6го.

В книге «Структура и интерпретация компьютерных программ» [32] в главе 2.2.4 рассмотрен игрушечный «язык картинок», выстроенный в форме комбинаторной библиотеки с комбинаторами высшего порядка.

В статье «The design of a pretty-printing library» [85] (автор которой, опять же, Джон Хьюз) рассмотрена комбинаторная библиотека для представления и «красивого» форматирования текстов. Это применение стало одной из классических иллюстраций идеи комбинаторной библиотеки, а за этой статьей позднее последовало множество других на ту же тему («A prettier printer» Филипа Вадлера [173], «Pretty printing with lazy deques» Олафа Читила [50], «A pretty printer library in Haskell» Саймона Пейтона-Джонса [135], «Beyond pretty-printing: Galley concepts in document formatting combinators» Вольфрама Каля [96], «Linear, bounded, functional pretty-printing» Доатсе Свирстры [162], «Optimal pretty-printing combinators» [34] Азеро и Свирстры, и т. п.).

Знаменитая библиотека случайного тестирования свойств QuickCheck Коэна Клэссена ([51], описана в статье «Specification based testing with QuickCheck» [52]) также представляет собой пример комбинаторной библиотеки.

Язык образцов (см. 10) в Mathematica сходен с регулярными выражениями и также основан на примитивах и комбинаторах.

В статьях «Imperative streams — a monadic combinator library for synchronous programming» [150] и «A monad of imperative streams» [149] Энно Шольца рассматривается комбинаторная библиотека для программирования, основанного на событиях (функционального реактивного программирования), ставшая базисом библиотеки для построения пользовательского интерфейса FranTk. Библиотека FranTk так и не стала широко применяться, однако идеи функционального реактивного программирования дали начало, по меньшей мере, двум гораздо более удобным, мощным и распространенным средствам:

• В языке F# поддерживаются события как первоклассные значения, и имеется комбинаторная библиотека для манипуляций над событиями, описанная в блог-посте Маттеса Подвысоцки «F# first class events — composing events until others» [142]. Так, с ее помощью можно, имея события щелчка/отпускания/передвижения мыши, составить событие «перетаскивание мыши из одной точки в другую» и подписаться на него.
• Этот подход приходит и в C#: в .NET 4.0 планируется включить мощный фреймворк для программирования интерактивных приложений: Rx Framework Эрика Мейера, использующий идеи функционального реактивного программирования и идеологически схожий с подходом к событиям в F#. Rx Framework основан на инверсии потока управления при помощи монады продолжений (впрочем, пользователям не нужно знать об этом, чтобы им пользоваться), и использует в качестве синтаксической поддержки LINQ. Вот несколько блог-постов и видео-лекций про Rx Framework: лекции Мейера [115] (часть 1) и [116] (часть 2), «Reactive programming (I.) — First class events in F#» [133] и «Reactive programming (II.) — introducing Reactive LINQ» [134] Томаша Петричека, а также «Introducing Rx (Linq to Events» [86] Джафара Хусейна.

В презентации «Функциональное программирование в Java» Евгения Кирпичёва [184] описывается комбинаторная библиотека для асинхронного программирования на Java, также использующая монаду продолжений. F# реализует похожую библиотеку («asynchronous workflows», описаны в блог-посте основного разработчика F# Дона Сайма «Introducing F# asynchronous workflows»[163], в его же видео «What’s new in F# — asynchronous workflows» [164], в статье Роберта Пикеринга «Beyond foundations of F# — asynchronous workflows» [138] и т. п.) при помощи использования монад в явной форме (workflow — термин из F#, фактически совпадающий с понятием монады).

Еще одна известная и получившая в свое время довольно широкую известность статья «Composing contracts: an adventure in financial engineering (functional pearl)» [94] описывает комбинаторную библиотеку для задания финансовых контрактов.

В статье «Функциональное программирование в Java» [183] приведено несколько примеров использования гипотетических и реальных комбинаторных библиотек на Java.

Список литературы

[1]

Arrays. Страница в haskellwiki, http://www.haskell.org/haskellwiki/Arrays.

[2]

Authorization structures. Страница MSDN, http://msdn.microsoft.com/en-us/library/aa375780(VS.85).aspx.

[3]

Chart: A library for generating 2d charts and plots. http://hackage.haskell.org/package/Chart.

[4]

Church encoding. Статья в Wikipedia, http://en.wikipedia.org/wiki/Church_encoding.

[5]

Continuations and continuation passing style. http://library.readscheme.org/page6.html.

[6]

Copy-on-write. Статья в Wikipedia, http://en.wikipedia.org/wiki/Copy-on-write.

[7]

The coq proof assistant. http://coq.inria.fr/.

[8]

Foldr, foldl, foldl’. Страница в haskellwiki, http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl'.

[9]

Generalized algebraic datatype: Parsing example. Статья в HaskellWiki, http://www.haskell.org/haskellwiki/GADT\#Parsing_Example.

[10]

heap: Heaps in haskell. http://hackage.haskell.org/package/heap.

[11]

Hipmunk: A haskell binding for chipmunk. http://hackage.haskell.org/package/Hipmunk.

[12]

J software. http://jsoftware.com.

[13]

Kx systems - fast database for streaming and historical data. http://kx.com.

[14]

Laziness. Страница в Haskell Wikibooks, http://en.wikibooks.org/wiki/Haskell/Laziness.

[15]

Perfecthash: A perfect hashing library for mapping bytestrings to values. http://hackage.haskell.org/package/PerfectHash.

[16]

Problem with delegates in c#. Вопрос на форуме Stack Overflow, http://stackoverflow.com/questions/1660483/problem-with-delegates-in-c.

[17]

Research papers/type systems/type classes. Страница в haskellwiki, http://haskell.org/haskellwiki/Research_papers/Type_systems\#Type_classes.

[18]

Revised(6) report on the algorithmic language scheme. http://www.r6rs.org/.

[19]

Structural induction. Статья в Wikipedia, http://en.wikipedia.org/wiki/Structural_induction.

[20]

hackageDB :: [Package]. http://hackage.haskell.org/packages/hackage.html.

[21]

Type inference: Hindley-milner type inference algorithm. Секция статьи в Wikipedia, http://en.wikipedia.org/wiki/Type_inference\#Hindley-Milner_type_inference_algorithm.

[22]

Well-founded relation. Статья в Wikipedia, http://en.wikipedia.org/wiki/Well-founded_relation.

[23]

Библиотека functional java. http://functionaljava.org.

[24]

Библиотека match.ss для plt scheme. http://download.plt-scheme.org/doc/372/html/mzlib/mzlib-Z-H-27.html.

[25]

Документация к классу treescanner. http://java.sun.com/javase/6/docs/jdk/api/javac/tree/com/sun/source/util/TreeScanner.html.

[26]

Документация к модулю data.map стандартной библиотеки языка haskell. http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map.html.

[27]

Документация к модулю data.monoid. http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html.

[28]

Документация к пакету struct.ss из библиотеки языка plt scheme. http://planet.plt-scheme.org/package-source/dherman/struct.plt/2/4/doc.txt.

[29]

Модуль coq.init.wf, реализующий вполне обоснованную индукцию. http://coq.inria.fr/stdlib/Coq.Init.Wf.html.

[30]

Страница в haskellwiki «existential type». http://www.haskell.org/haskellwiki/Existential_type.

[31]

Страница в haskellwiki «oop vs type classes». http://www.haskell.org/haskellwiki/OOP_vs_type_classes.

[32]

Harold Abelson and Gerald J. Sussman. Structure and Interpretation of Computer Programs - 2nd Edition (MIT Electrical Engineering and Computer Science). The MIT Press, 2 edition, July 1996.

[33]

Emil Axelsson. Bookshelf: A simple document organizer with some wiki functionality. Пакет на hackage, http://hackage.haskell.org/package/Bookshelf.

[34]

P. Azero and S. D. Swierstra. Optimal pretty-printing combinators, April 1998.

[35]

J. Backus. Can programming be liberated from the von neumann style? Communications of the ACM, 21(8):613–641, 1978.

[36]

H. P. Barendregt. Lambda calculi with types. pages 117–309, 1992.

[37]

Andreas Bauer. Compilation of functional programming languages using GCC—Tail calls. Master’s thesis, Institut für Informatik, Technische Universität München, 2003.

[38]

Jean-Philippe Bernardy, Patrik Jansson, Marcin Zalewski, Sibylle SChupp, and Andreas P. Priesnitz. A comparison of c++ concepts and haskell type classes. In Ralf Hinze and Don Syme, editors, ICFP-WGP, pages 37–48. ACM, 2008.

[39]

Yves Bertot. Well-founded induction. Слайды, http://www-sop.inria.fr/members/Yves.Bertot/tsinghua/tsinghua-5.pdf.

[40]

Yves Bertot and Pierre Castéran. Interactive Theorem Proving and Program Development. Coq’Art: The Calculus of Inductive Constructions. Texts in Theoretical Computer Science. Springer Verlag, 2004.

[41]

Richard Bird and Lambert Meertens. Nested datatypes. In MPC: 4th International Conference on Mathematics of Program Construction. LNCS, Springer-Verlag, 1998.

[42]

G. Blelloch. Vector Models for Data-Parallel Computing. The MIT Press, Cambridge, MA, 1990.

[43]

Guy E. Blelloch. Prefix sums and their applications. February 1993.

[44]

Chandrasekhar Boyapati, Barbara Liskov, and Liuba Shrira. Ownership types for object encapsulation. In In Principles of Programming Languages (POPL), pages 213–223, 2003.

[45]

Peter Brass. Advanced Data Structures. Cambridge: Cambridge University Press, 2009.

[46]

Bjorn Bringert and Duncan Coutts. tar: Reading, writing and manipulating ".tar" archive files. Пакет на hackage, http://hackage.haskell.org/package/tar, 2007–2009.

[47]

F. Cardone and J. R. Hindley. History of lambda-calculus and combinatory logic. Handbook of the History of Logic, 5.

[48]

Manuel M. T. Chakravarty, Gabriele Keller, and Simon Peyton Jones. Associated type synonyms. ACM SIGPLAN Notices, 40(9):241–253, September 2005.

[49]

Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, and Simon Marlow. Associated types with class. ACM SIGPLAN Notices, 40(1):1–13, January 2005.

[50]

Olaf Chitil. Pretty printing with lazy dequeues. ACM Trans. Program. Lang. Syst., 27(1):163–184, January 2005.

[51]

Koen Claessen. Quickcheck: Automatic testing of haskell programs. Пакет на hackage, http://hackage.haskell.org/package/QuickCheck.

[52]

Koen Claessen and John Hughes. Specification based testing with QuickCheck. In The Fun of Programming, Cornerstones of Computing, pages 17–40. Palgrave, 2003.

[53]

Martin Clare E., Jeremy Gibbons, and Ian Bayley. Disciplined, efficient, generalised folds for nested datatypes. Formal Asp. Comput, 16(1):19–35, 2004.

[54]

John Clements and Matthias Felleisen. A tail-recursive machine with stack inspection. ACM Trans. Program. Lang. Syst., 26(6):1029–1052, 2004.

[55]

William D. Clinger. Proper tail recursion and space efficiency. In Proceedings of the ACM SIGPLAN ’98 Conference on Programming Language Design and Implementation, pages 174–185, Montréal, Québec, June 1998.

[56]

Duncan Coutts. zlib: Compression and decompression in the gzip and zlib formats. Пакет на hackage, http://hackage.haskell.org/package/zlib.

[57]

Russ Cox. Regular expression matching can be simple and fast. http://swtch.com/~rsc/regexp/regexp1.html, January 2007.

[58]

Olivier Danvy and Lasse R. Nielsen. Defunctionalization at work. In PPDP ’01: Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, pages 162–174, New York, NY, USA, 2001. ACM.

[59]

Pedro Del Gallego. Curried function and labeled arguments in ocaml. Пост в блоге, http://theplana.wordpress.com/2007/04/26/curried-function-and-labeled-arguments-in-ocaml/, April 2007.

[60]

Scott E. Dillard. Vec: Fixed-length lists and low-dimensional linear algebra. Пакет на hackage, http://hackage.haskell.org/package/Vec, 2009.

[61]

Derek Dreyer, Robert Harper, Manuel M. T. Chakravarty, and Gabriele Keller. Modular type classes. In Martin Hofmann and Matthias Felleisen, editors, POPL, pages 63–70. ACM, 2007.

[62]

Driscoll, Sarnak, Sleator, and Tarjan. Making data structures persistent. JCSS: Journal of Computer and System Sciences, 38, 1989.

[63]

Matthias Felleisen. Functional objects. Слайды с выступления на ECOOP 2004, http://www.ccs.neu.edu/home/matthias/Presentations/ecoop2004.pdf.

[64]

Darrell Ferguson and Dwight Deugo. Call with current continuation patterns. In Proceedings of the 2001 Pattern Languages of Programs Conference, 2001.

[65]

Sigbjorn Finne. json: Support for serialising haskell to and from json. Пакет на hackage, http://hackage.haskell.org/package/json.

[66]

Matthew Flatt. Getting rid of set-car! and set-cdr! Пост в блоге PLT Scheme Blog, http://blog.plt-scheme.org/2007/11/getting-rid-of-set-car-and-set-cdr.html.

[67]

Neal Gafter. Comments on the straw man…. http://mail.openjdk.java.net/pipermail/lambda-dev/2009-December/000023.html.

[68]

Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Professional, 1995.

[69]

Neil Ghani, Makoto Hamana, Tarmo Uustalu, and Varmo Vene. Representing cyclic structures as nested datatypes.

[70]

Jeremy Gibbons. The Third Homomorphism Theorem. Journal of Functional Programming, 6(4):657–665, July 1996. Functional Pearls.

[71]

Jean-Yves Girard, Yves Lafont, and Paul Taylor. Proofs and Types, volume 7 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1989. This is textbook on proof theory and type systems, based on lectures by Girard. It contains an appendix by Lafont on linear logic, and also treats Girard’s polymorphic lambda calculus.

[72]

John Goerzen. Hdbc: Haskell database connectivity. Пакет на hackage, http://hackage.haskell.org/package/HDBC.

[73]

John Goerzen. Hsh: Library to mix shell scripting with haskell programs. Пакет на hackage, http://hackage.haskell.org/package/HSH.

[74]

Fritz Henglein. Generic discrimination: Sorting and paritioning unshared data in linear time. In James Hook and Peter Thiemann, editors, Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, ICFP 2008, Victoria, BC, Canada, September 20-28, 2008, pages 91–102. ACM, 2008.

[75]

Rich Hickey. Trampoline for mutual recursion. Обсуждение в рассылке clojure, http://groups.google.com/group/clojure/browse_thread/thread/6257cbc4454bcb85/3addf875319c5c10.

[76]

Roger Hindley. Сообщение об истории алгоритма вывода типов Хиндли-Милнера. Сообщение в рассылке TYPES в MIT, http://www.cis.upenn.edu/~bcpierce/types/archives/1988/msg00042.html, 1988.

[77]

Ralf Hinze. Efficient generalized folds. In Johan Jeuring, editor, Proc. of 2nd Workshop on Generic Programming, WGP’2000 (Ponte de Lima, Portugal, 6 July 2000), Tech. Report UU-CS-2000-19, Dept. of Computer Science, Utrecht Univ. June 2000.

[78]

Ralf Hinze. Fun with phantom types. In Jeremy Gibbons and Oege de Moor, editors, The Fun of Programming, pages 245–262. Palgrave Macmillan, 2003. ISBN 1-4039-0772-2 hardback, ISBN 0-333-99285-7 paperback.

[79]

Ralf Hinze, Johan Jeuring, and Andres Löh. Typed Contracts for Functional Programming, volume 3945. January 2006.

[80]

Martin Holters. Efficient data structures in a lazy functional language, November 2003.

[81]

Paul Hudak. Modular domain specific languages and tools. In Proceedings of Fifth International Conference on Software Reuse, pages 134–142, June 1998.

[82]

Paul Hudak and Mark P. Jones. Haskell vs. ada vs. c++ vs awk vs ... an experiment in software prototyping productivity. Technical report, 1994.

[83]

John Hughes. Designing and using combinators: The essence of functional programming. http://www.math.chalmers.se/~rjmh/Combinators/.

[84]

John Hughes. Why functional programming matters. Technical Report 16, Programming Methodology Group, University of Goteborg, November 1984.

[85]

John Hughes. The design of a pretty-printing library. pages 53–96. 1995.

[86]

Jafar Husain. Introducing rx (linq to events). Пост в блоге, http://themechanicalbride.blogspot.com/2009/07/introducing-rx-linq-to-events.html.

[87]

Graham Hutton. Higher-order Functions for Parsing. Journal of Functional Programming, 2(3):323–343, July 1992.

[88]

Graham Hutton. A tutorial on the universality and expressiveness of fold. J. Funct. Program, 9(4):355–372, 1999.

[89]

Graham Hutton and Erik Meijer. Monadic parsing in haskell. Journal of Functional Programming, 8(4):437–444, July 1998.

[90]

James Iry. Tail calls via trampolining and an explicit instruction. Обсуждение в рассылке Scala, http://old.nabble.com/Tail-calls-via-trampolining-and-an-explicit-instruction-td20702915.html.

[91]

Jan Martin Jansen, Pieter W. M. Koopman, and Rinus Plasmeijer. Efficient interpretation by transforming data types and tatterns to functions. In Trends in Functional Programming, pages 73–90, 2006.

[92]

Aurelien Jarno. gcc-4.3/alpha: -foptimize-sibling-calls generates wrong code. Письмо в рассылку debian-gcc, http://www.mail-archive.com/debian-gcc@lists.debian.org/msg31603.html.

[93]

Mark P. Jones. Type classes with functional dependencies. In Gert Smolka, editor, Programming Languages and Systems, 9th European Symposium on Programming, ESOP 2000, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS 2000, Berlin, Germany, March 25 - April 2, 2000, Proceedings, volume 1782 of Lecture Notes in Computer Science, pages 230–244. Springer, 2000.

[94]

Simon Peyton Jones, Jean-Marc Eber, and Julian Seward. Composing contracts: an adventure in financial engineering (functional pearl). In ICFP ’00: Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, pages 280–292, New York, NY, USA, 2000. ACM.

[95]

Guy Lewis Steele jr. Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, lambda: The ultimate goto. Report A. I. MEMO 443, Massachusetts Institute of Technology, A.I. Lab., Cambridge, Massachusetts, 1977.

[96]

Wolfram Kahl. Beyond pretty-printing: Galley concepts in document formatting combinators. In PADL ’99: Proceedings of the First International Workshop on Practical Aspects of Declarative Languages, pages 76–90, London, UK, 1998. Springer-Verlag.

[97]

Richard A. Kelsy. Tail-recursive stack disciplines for an interpreter. Technical Report NU-CCS-93-03, College of Computer Science, Northeastern University, March 1993.

[98]

Andrew Kennedy. Pickler combinators. J. Funct. Program, 14(6):727–739, 2004.

[99]

Andrew Kennedy and Claudio V. Russo. Generalized algebraic data types and object-oriented programming. SIGPLAN Not., 40(10):21–40, 2005.

[100]

Eugene Kirpichov. digest: Various cryptographic hashes for bytestrings; crc32 and adler32 for now. Пакет на hackage, http://hackage.haskell.org/package/digest.

[101]

Eugene Kirpichov. jarfind: Tool for searching java classes, members and fields in classfiles and jar archives. Пакет на hackage, http://hackage.haskell.org/package/jarfind.

[102]

Edward Kmett. Introduction to monoids (slides). Пост в блоге, http://comonad.com/reader/2009/iteratees-parsec-and-monoid/, 2009.

[103]

Edward Kmett. Iteratees, parsec and monoids. Пост в блоге, http://comonad.com/reader/2009/iteratees-parsec-and-monoid/, August 2009.

[104]

Edward A. Kmett. unboxed-containers: Self-optimizing unboxed sets using view patterns and data families. Пакет на hackage, http://hackage.haskell.org/package/unboxed-containers.

[105]

P. J. Landin. The next 700 programming languages. CACM, 9:157–166, 1966.

[106]

K. Läufer. Type classes with existential types. Journal of Functional Programming, 6(3):485–517, May 1996.

[107]

Konstantin Läufer and Martin Odersky. Polymorphic type inference and abstract data types. ACM Trans. Program. Lang. Syst., 16(5):1411–1430, 1994.

[108]

Keith Lea. A huge gotcha with javascript closures and loops. Пост в блоге, http://joust.kano.net/weblog/archive/2005/08/08/a-huge-gotcha-with-javascript-closures/.

[109]

Roman Leshchinsky. fixpoint: Data types as fixpoints. Пакет на hackage, http://hackage.haskell.org/package/fixpoint.

[110]

HAppS LLC. Happs-server: Web related tools and services. Пакет на hackage, http://hackage.haskell.org/package/HAppS-Server.

[111]

G. Malcolm. Algebraic Data Types and Program Transformation. PhD thesis, Groningen University, 1990.

[112]

Simon Marlow and Simon Peyton Jones. Making a fast curry: push/enter vs. eval/apply for higher-order languages. SIGPLAN Not., 39(9):4–15, 2004.

[113]

Joe Marshall. Серия блог-постов: http://funcall.blogspot.com/2009/04/you-knew-id-say-something.html, http://funcall.blogspot.com/2009/04/you-knew-id-say-something-part-ii.html, http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-iii.html, http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-iv.html, http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-v.html.

[114]

Conor McBride. Faking it: Simulating dependent types in haskell. J. Funct. Program, 12(4&5):375–392, 2002.

[115]

Erik Meijer and Wes Dyer. Reactive framework (rx) under the hood — 1 of 2. Видео на Channel9, http://channel9.msdn.com/shows/Going+Deep/E2E-Erik-Meijer-and-Wes-Dyer-Reactive-Framework-Rx-Under-the-Hood-1-of-2/.

[116]

Erik Meijer and Wes Dyer. Reactive framework (rx) under the hood — 2 of 2. Видео на Channel9, http://channel9.msdn.com/shows/Going+Deep/E2E-Erik-Meijer-and-Wes-Dyer-Reactive-Framework-Rx-Under-the-Hood-2-of-2/.

[117]

Erik Meijer, Maarten Fokkinga, and Ross Paterson. Functional programming with bananas, lenses, envelopes and barbed wire. Lecture Notes in Computer Science, 523:124–??, 1991.

[118]

Alexandre Miquel. An introduction to system f. Слайды доступны по ссылке http://www.pps.jussieu.fr/~miquel/slides/got03-1.pdf.

[119]

Neil Mitchell. Transformation and Analysis of Functional Programs. PhD thesis, University of York, June 2008.

[120]

Neil Mitchell and Colin Runciman. Losing functions without gaining data. In Haskell ’09: Proceedings of the second ACM SIGPLAN symposium on Haskell. ACM, September 2009.

[121]

Neil Mitchell and Colin Runciman. Losing functions without gaining data. Слайды, http://community.haskell.org/~ndm/downloads/slides-losing_functions_without_gaining_data-03_sep_2009.pdf, September 2009.

[122]

Jun Mukai. Haskellnet: network related libraries such as pop3, smtp, imap. Пакет на hackage, http://hackage.haskell.org/package/HaskellNet.

[123]

James Noble. Arguments and results. Comput. J, 43(6):439–450, 2000.

[124]

Chris Okasaki. Binomial queues as a nested type. Пост в блоге от 22 октября 2009 г., http://okasaki.blogspot.com/2009/10/binomial-queues-as-nested-type.html.

[125]

Chris Okasaki. Edisoncore: A library of efficent, purely-functional data structures (core implementations). Пакет на hackage, http://hackage.haskell.org/package/EdisonCore.

[126]

Chris Okasaki. Functional pearl: Even higher-order functions for parsing or why would anyone ever want to use a sixth-order function? Journal of Functional Programming, 8(2):195–199, 1998.

[127]

Chris Okasaki. Purely Functional Data Structures. Cambridge University Press, 1999.

[128]

Chris Okasaki. Breadth-first numbering: Lessons from a small exercise in algorithm design. In ICFP, pages 131–136, 2000.

[129]

Runar Oli. Structural pattern matching in java. Пост в блоге, http://apocalisp.wordpress.com/2009/08/21/structural-pattern-matching-in-java/.

[130]

Luke Palmer. graphics-drawingcombinators: A functional interface to 2d drawing in opengl. Пакет на hackage, http://hackage.haskell.org/package/graphics-drawingcombinators.

[131]

Christine Paulin-Mohring. Inductive definitions in the system coq — rules and properties. In TLCA ’93: Proceedings of the International Conference on Typed Lambda Calculi and Applications, pages 328–345, London, UK, 1993. Springer-Verlag.

[132]

Lawrence C. Paulson. Constructing recursion operators in intuitionistic type theory. Journal of Symbolic Computation, 2(4):325–355, December 1986.

[133]

Tomáš Petříček. Reactive programming (i.) — first class events in f#. Пост в блоге, http://tomasp.net/blog/reactive-i-fsevents.aspx.

[134]

Tomáš Petříček. Reactive programming (ii.) — introducing reactive linq. Пост в блоге, http://tomasp.net/articles/reactive-ii-csevents.aspx.

[135]

Simon Peyton Jones. A pretty printer library in haskell. Часть стандартной библиотеки GHC, http://research.microsoft.com/en-us/um/people/simonpj/downloads/pretty-printer/pretty.html.

[136]

Simon Peyton-Jones, Mark Jones, and Erik Meijer. Type classes: an exploration of the design space. In J. Launchbury, editor, Haskell workshop, Amsterdam, 1997.

[137]

Simon L. Peyton Jones. The Implementation of Functional Programming Languages. Prentice–Hall, 1987.

[138]

Robert Pickering. Beyond Foundations of F# — Asynchronous Workflows. Статья на infoq, http://www.infoq.com/articles/pickering-fsharp-async.

[139]

Benjamin C. Pierce. Types and Programming Languages. The MIT Press, Cambridge, Massachusetts, 2002.

[140]

Dan Piponi. An approach to algorithm parallelisation. Пост в блоге, http://blog.sigfpe.com/2008/11/approach-to-algorithm-parallelisation.html, November 2008.

[141]

Dan Piponi. Моноиды в haskell и их использование (перевод Кирилла Заборского). Практика функционального программирования, 1, July 2009.

[142]

Matthes Podwysocki. F# first class events — composing events until others. Пост в блоге, http://codebetter.com/blogs/matthew.podwysocki/archive/2009/10/15/f-first-class-events-composing-events-until-others.aspx.

[143]

Bernie Pope. hinvaders: Space invaders. Пакет на hackage, http://hackage.haskell.org/package/hinvaders.

[144]

Reiner Pope. first-class-patterns: First class patterns and pattern matching, using type families. Пакет на hackage, http://hackage.haskell.org/package/first-class-patterns.

[145]

Reiner Pope. Pattern combinators. Серия блог-постов, http://reinerp.wordpress.com/category/pattern-combinators/.

[146]

Mark Reinhold. Project lambda: Straw-man proposal. http://cr.openjdk.java.net/~mr/lambda/straw-man/.

[147]

Morten Rhiger. Type-safe pattern combinators. J. Funct. Program, 19(2):145–156, 2009.

[148]

Alexey Rodriguez, Stefan Holdermans, Andres Löh, and Johan Jeuring. multirec: Generic programming for families of recursive datatypes. Пакет на hackage, http://hackage.haskell.org/package/multirec.

[149]

E. Scholz. A Monad of Imperative Streams. Ullapool, Scotland, July 1996. Department of Computing Science, University of Glasgow.

[150]

Enno Scholz. Imperative streams —a monadic combinator library for synchronous programming. In ICFP ’98: Proceedings of the third ACM SIGPLAN international conference on Functional programming, pages 261–272, New York, NY, USA, 1998. ACM.

[151]

Moses Schönfinkel. Über die bausteine der mathematischen logik. Math. Annalen, 92:305–316, 1924. An English translation appears in From Frege to Godel, edited by Jean van Heijenoort (Harvard Univ. Press, 1967), pages 355-366.

[152]

Moses Schönfinkel. On the building blocks of mathematical logic. pages 355–366, 1967. A Source Book in Mathematical Logic, 1879–1931.

[153]

Tom Schrijvers, Simon L. Peyton Jones, Manuel M. T. Chakravarty, and Martin Sulzmann. Type checking with open type functions. In James Hook and Peter Thiemann, editors, Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, ICFP 2008, Victoria, BC, Canada, September 20-28, 2008, pages 51–62. ACM, 2008.

[154]

Ganesh Sittampalam. Darcs and gadts. Видео и слайды в PDF, http://www.londonhug.net/2008/02/02/video-darcs-and-gadts/.

[155]

Jon Skeet. The beauty of closures. Глава из книги «C# in depth», http://csharpindepth.com/Articles/Chapter5/Closures.aspx.

[156]

Leon P Smith. Why object-oriented languages need tail calls. Ветка на форуме Lambda the Ultimate, http://lambda-the-ultimate.org/node/3702.

[157]

Morten H. Sørensen and Robert Glück. An algorithm of generalization in positive supercompilation. In John Lloyd, editor, Proceedings of the International Symposium on Logic Programming, pages 465–479, Cambridge, December 1995. MIT Press.

[158]

Guy Steele. Why object-oriented languages need tail calls. Пост в блоге Project Fortress, http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion.

[159]

Guy Steele and Gerald Jay Sussman. Lambda papers. Серия статей, доступны по адресу http://library.readscheme.org/page1.html.

[160]

Roger Stokes. Learning j: Chapter 8. composing verbs. http://www.jsoftware.com/help/learning/08.htm.

[161]

Christopher Strachey. Fundamental concepts in programming languages. Higher Order Symbol. Comput., 13(1-2):11–49, 2000.

[162]

S. Doaitse Swierstra and Olaf Chitil. Linear, bounded, functional pretty-printing. J. Funct. Program., 19(1):1–16, 2009.

[163]

Don Syme. Introducing f# asynchronous workflows. Пост в блоге, http://blogs.msdn.com/dsyme/archive/2007/10/11/introducing-f-asynchronous-workflows.aspx.

[164]

Don Syme. What’s new in f# — asynchronous workflows. Видео на Channel9, http://channel9.msdn.com/posts/Charles/Don-Syme-Whats-new-in-F-Asynchronous-Workflows-and-welcome-to-the-NET-family/.

[165]

Don Syme. F# active patterns. http://blogs.msdn.com/dsyme/attachment/2044281.ashx, 2007.

[166]

Hideyuki Tanaka and Takayuki Muranushi. Monadius: 2-d arcade scroller. Пакет на hackage, http://hackage.haskell.org/package/Monadius.

[167]

Mads Tofte and Jean-Pierre Talpin. Region-based memory management. Inf. Comput., 132(2):109–176, 1997.

[168]

Mark Tullsen. First class patterns. Lecture Notes in Computer Science, 1753:1–??, 2000.

[169]

Franklyn A. Turbak and David K. Gifford. Design Concepts in Programming Languages. The MIT Press, 2008.

[170]

Anton van Straaten. Коан об объектах и замыканиях. http://people.csail.mit.edu/gregs/ll1-discuss-archive-html/msg03277.html.

[171]

Philip Wadler. How to replace failure by a list of successes. In Proc. of a conference on Functional programming languages and computer architecture, pages 113–128, New York, NY, USA, 1985. Springer-Verlag New York, Inc.

[172]

Philip Wadler. Views: A way for pattern matching to cohabit with data abstraction. In POPL, pages 307–313, 1987.

[173]

Philip Wadler. A prettier printer. Journal of Functional Programming, 1999.

[174]

Philip Wadler and Stephen Blott. How to make ad-hoc polymorphism less ad hoc. In 16’th ACM Symposium on Principles of Programming Languages, Austin, Texas, January 1989.

[175]

Mitchell Wand. Continuation-based program transformation strategies. Journal of the ACM, 27:164–180, 1980.

[176]

Louis Wasserman. Triemap: Automatic type inference of generalized tries. Пакет на hackage, http://hackage.haskell.org/package/TrieMap.

[177]

Stefan Wehr and Manuel M. T. Chakravarty. Ml modules and haskell type classes: A constructive comparison. In G. Ramalingam, editor, APLAS, volume 5356 of Lecture Notes in Computer Science, pages 188–204. Springer, 2008.

[178]

Hongwei Xi, Chiyan Chen, and Gang Chen. Guarded recursive datatype constructors. SIGPLAN Not., 38(1):224–235, 2003.

[179]

Brent Yorgey. Typeclassopedia. The Monad.Reader, 13, March 2009.

[180]

Кирпичёв Е. antro: a line-level profiler for ant build scripts. Проект на sourceforge, sourceforge.net/projects/antro.

[181]

Кирпичёв Е. Coq. Доклад на собрании SPb Haskell User Group, 24 октября 2008 г., http://spbhug.folding-maps.org/wiki/Coq.

[182]

Кирпичёв Е. Чисто функциональные структуры данных (ч.2). Доклад на собрании SPb Haskell User Group, 11 ноября 2007 г., http://spbhug.folding-maps.org/wiki/FunctionalDataStructures2, 2007.

[183]

Кирпичёв Е. Приемы программирования на java: Повышение читаемости кода и функциональное программирование. Доступно по адресу http://www.rsdn.ru/article/java/JavaFP.xml, 2008.

[184]

Кирпичёв Е. Функциональное программирование в java. Слайды к докладу на математическо-механическом факультете СПбГУ, http://spbhug.folding-maps.org/wiki/EugeneKirpichov?action=AttachFile&do=get&target=JavaFP_ru.ppt, 2008.

[185]

Кирпичёв Е. Изменяемое состояние: опасности и борьба с ними. Практика функционального программирования, 1, July 2009.

[186]

Кирпичёв Е. Курс лекций «Функциональное программирование» для студентов АФТУ. http://spbhug.folding-maps.org/wiki/SICP_Course, 2009.

[187]

Хювёнен, Э. и Сеппянен, Й. Мир Лиспа. 1990.

[188]

Царёв О. Парсер заголовочных файлов Си на python. Пост в блоге, http://zabivator.livejournal.com/359491.html.

1

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

2

То есть, содержащего некое «нулевое» значение, например, null.

3

Впрочем, в ряде задач переменные с динамической областью видимости бывают полезны; они поддерживаются, например, языком Common Lisp.

4

Перевод «фунарг-проблема» используется в книге «Мир Лиспа» [187].

5

Автору не известен устоявшийся перевод этого термина на русский язык, приведенный перевод придуман специально для данной статьи.

6

На эту тему существует дзен-коан [170].

7

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

8

А также позволяет «скомпилировать» регулярное выражение, так что многократные применения результата matchesRegexp “-?[0-9]+” к множеству строк s₁,s₂,…выполняются намного эффективнее, чем многократные вычисления matchesRegexp “-?[0-9]+” s1, matchesRegexp “-?[0-9]+”  s2 и т. п.

9

Конечно же, необязательно фиксировать аргументы какими-то «конкретными» значениями (литералами).

10

А также в теоретико-категорное определение декартово замкнутой категории, где при помощи curry фактически вводится определение оператора «применение функции к аргументу». К счастью, для понимания материала этой статьи знакомство с теорией категорий не требуется.

11

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

12

О том, что будет, если нарушить это требование, можно прочитать в посте Мэттью Флэтта «Getting rid of set-car! and set-cdr!» ([66]).

13

По субъективному мнению автора, этот пост можно смело причислить к шедеврам программирования.

14

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

15

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

16

Еще более хорошим тоном считается по возможности избегать явного использования рекурсии и использовать ее лишь в комбинаторах (см. 14) общего назначения, таких как map, fold и т. п. Речь идет о структурной рекурсивности этих комбинаторов.

17

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

18

Не следует путать понятие типового конструктора с понятием конструктора алгебраического типа (см. 9).

19

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

20

О том, как достичь компромисса между эффективностью и универсальностью в случае преобразований координат можно прочитать, например, в лекции номер 4 «Абстракция данных» курса «Функциональное программирование» Евгения Кирпичёва ([186]).

21

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

Этот документ был получен из L^AT_EX при помощи H^EV^EA

© 2009—2011  «Практика функционального программирования»ISSN 2075-8456