Функции высшего порядка

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

Функции высшего порядка (high-order functions)

Функцией высшего порядка (ФВП) называется функция, которая принимает в качестве параметра другую функцию или возвращает функцию в качестве результата. Например, ранее мы рассматривали реализацию быстрой сортировки на языке Haskell. В ней шаг рекурсии выражался следующей строчкой: qsort (x:xs) = qsort(filter (< x) xs) ++ [x] ++ qsort(filter (>= x) xs). В этом коде функция filter в качестве параметра принимает функцию - критерий фильтрации. Поэтому filter является функцией высшего порядка. Другими примерами типичных ФВП являются отображения, аккумуляторы и свертки.

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

Практический пример

В классической статье "Why Functional Programming Matters" Джон Хьюз приводит ряд примеров, которые показывают мощь функциональной композиции. Чтобы дополнить картину, мы приведем еще одну иллюстрацию - сравним императивную и функциональную реализации обработки абстрактного синтаксического дерева. Для краткости примера рассмотрим простой AST, состоящий из нодов Literal (объявление литерала) и Apply (применение функции).

Решение, предлагаемое на MSDN, основывается на паттерне Visitor. В рамках этого паттерна мы реализуем класс (далее будем называть его “визитор”), который для каждого типа нода содержит по одному методу, в котором задана логика обработки нода и последующего обхода его детей. Иллюстрацией этого подхода является базовый класс для визиторов (реализация упрощена в целях краткости):

 public abstract class AbstractVisitor

 {

     protected Expression Visit(Expression exp)

     {

         switch(exp.NodeType)

         {

             case ExpressionType.Literal:

                 return VisitLiteral((LiteralExpression)exp);

             case ExpressionType.Apply:

                 return VisitApply((ApplyExpression)exp);

             default:

                 throw new ArgumentException(String.Format("Unexpected node '{0}' of type '{1}'",

                     exp, exp.NodeType));

         }

     }

     protected virtual LiteralExpression VisitLiteral(LiteralExpression le)

     {

         return le;

     }

     protected virtual ApplyExpression VisitApply(ApplyExpression ae)

     {

         var args = ae.Args.Select(arg => Visit(arg));

         return Expression.Apply(ae.Function, args);

     }

 }

Функциональный подход к решению задачи представляет собой катаморфизм - ФВП, которая содержит логику обхода АСТ и принимает в качестве параметра N различных функций, реализующих обработку соответствующих типов нодов. Рассмотрим реализацию катаморфизма на языке F# (если вы не знакомы с F#, то в объеме, необходимом для понимания кода, приведенного ниже, его можно освоить, прочитав ознакомительный пост; реализация предельно упрощена в целях краткости, о ее возможных усовершенствованиях можно почитать в серии статей Брайана МакНамары).

 let fold ast literalF applyF = 

     let rec Iter ast =

         match ast with 

         | Literal(value) -> literalF value

         | Apply(name, args) -> applyF name (Seq.map Iter args)

     Iter ast

Анализ примера

Сразу же можно заметить, что конкретному визитору, который перекрывает некоторый метод VisitXXX, необходимо будет воспроизвести логику обхода детей обрабатываемого узла, в то время как при использовании функционального подхода работа с нодом четко разделяется на логику fold (обход) и логику literalF/applyF (обработки). Здесь мы наблюдаем функциональную композицию в действии - монолитный для императивной версии код мы смогли разделить на две части, каждая из которых может использоваться отдельно.

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

Кроме того, в одной из последних статей серии Брайана МакНамары про катаморфизмы можно увидеть еще один аспект функциональной декомпозиции – благодаря тому, что катаморфизм становится отложенным (lazy), у нас появляется возможность извне обрывать рекурсивное углубление в структуру данных, то есть вместо логики обхода (fold) и N обработчиков (literalF, applyF) наш алгоритм декомпозируется на обходчик, N контроллеров и N обработчиков. Конечно же, такие возможности нужны не всегда, но отметьте, насколько мелкозернистой в этом случае оказывается функциональная декомпозиция по сравнению с декомпозицией, предоставляемой ИП и ООП.

Заключение

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

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

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

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

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

1. "Referential transparency", from Wikipedia, the free encyclopedia

2. "Verifiable Functional Purity in Java", Matthew Finifter et al., 2008

3. "Code Contracts #5: Method purity", Matthias Jauernig, 2009

Для ценителей функционального программирования у нас есть еще одна отличная статья - лекция Джона Бэкуса "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs", прочитанная им на получении награды ACM Turing Award.