Знакомство с функциональным программированием

  • Article

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

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

Экскурс в историю

Функциональное программирование является практической реализацией лямбда-исчисления, разработанного в 30-х годах прошлого века американским математиком Алонзо Чёрчем. В отличие от императивной парадигмы, родившейся для ad-hoc поддержки доступного железа, ФП долго оставалась чисто научной дисциплиной (первые практические функциональные языки программирования были разработаны лишь в начале 70-х годов, их эффективные реализации появились значительно позже).

Такая история имеет и плюсы, и минусы. С одной стороны, отдаленность концепции от мейнстримного железа и ad-hoc понимания программирования обусловила ее невысокую доступность и недостаточное к ней внимание. С другой стороны, разработчики ФП, не будучи скованными ориентацией на низкий уровень ассемблера, смогли воплотить в жизнь такие замечательные концепции как сборку мусора и метапрограммирование.

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

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

Рассмотрим пример

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

Если императивная версия более-менее понятна, то по для понимания функциональной могут понадобиться некоторые пояснения.

  1. Функция qsort объявлена при помощи техники сопоставления с образцом (pattern matching), которую можно рассматривать как аналог набора условных операторов. В данном случае аргументы функции сопоставляются с одним из двух вариантов - пустым списком и всем остальным.
  2. Операторы ":" и "++" применяются для работы со списками - первый создает список из головы (первого элемента) и хвоста (списка, содержащего остальные элементы), второй объединяет список из двух более мелких.
  3. Функция filter по некоторому списку и определенному критерию формирует новый список, который состоит только из элементов, которые удовлетворяют критерию.
  4. Критерии фильтрации списков заданы в интересном виде - "< x" и ">= x". Такой способ записи интересен двумя особенностями. Во-первых, критерии фильтрации захватывают свой параметр x из лексического контекста родителя, а, во-вторых, эти критерии представляют собой частичное применение соответствующей функции "<" или ">=".

Быстрая сортировка на языке C

Быстрая сортировка на языке Haskell

 
 void qsort(int a[], int lo, int hi)
 {
   int h, l, p, t;
  
   if (lo < hi) {
     l = lo;
     h = hi;
     p = a[hi];
  
     do {
       while ((l < h) && (a[l] <= p)) 
           l = l+1;
       while ((h > l) && (a[h] >= p))
           h = h-1;
       if (l < h) {
           t = a[l];
           a[l] = a[h];
           a[h] = t;
       }
     } while (l < h);
  
     a[hi] = a[l];
     a[l] = p;
  
     qsort(a, lo, l-1);
     qsort(a, l+1, hi);
   }
 }
 
 qsort [] = []
 qsort (x:xs) = 
     qsort(filter (< x) xs) ++ 
     [x] ++ 
     qsort(filter (>= x) xs)

Первые впечатления

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

1. В варианте слева алгоритм представляет собой последовательность действий, в то время как в варианте справа алгоритм задается деревом вложенных функций. Ко всему прочему, это значит то, что в отличие от императивных программ, которые декомпозируются in-the-large до уровня процедур, функциональные программы декомпозируются также in-the-small до уровня отдельных выражений (это свойство называется функциональная композиция).

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

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

4. Можно отметить, что функциональная реализация удобнее в разработке и поддержке, но это достигается определенной ценой. Так, императивная версия не требует дополнительной памяти и выполняет in-place сортировку, в то время как реализация на Хаскелле на каждом шаге рекурсии выделяет память для создания и объединения списков.

Заключение

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

Материалы для чтения по темам следующих постов

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

1. "Why Functional Programming Matters", John Hughes, 1984

2. "How does functional programming affect the structure of your code?", Brian McNamara, 2008

3. "The Anti-For Campaign", Matthew Podwysocki, 2009

Читателям, уже знакомым с ФП, в ожидании будущих постов о продолжениях и монадах, предлагаем познакомиться с прекрасной статьей Филипа Вадлера "The essence of functional programming".