Функциональное мышление
Часть 1. Разработка программ в функциональном стиле
Научитесь думать как функциональный программист
Серия контента:
Этот контент является частью # из серии # статей: Функциональное мышление
Этот контент является частью серии:Функциональное мышление
Следите за выходом новых статей этой серии.
Представьте себя на минуту на месте лесоруба, имеющего самый лучший топор в лесу, который делает вас самым продуктивным лесорубом в артели. Но в один прекрасный день появляется некто, восхваляющий достоинства новой парадигмы рубки леса – бензопилы. Благодаря его убеждениям вы покупаете пилу, но при этом не знаете, как она работает. Поэтому вы пытаетесь использовать её в рамках уже знакомой и работающей парадигмы рубки леса, т.е. пытаетесь свалить дерево ударами бензопилой по стволу. Довольно скоро вы придете к выводу, что расхваленная бензопила – на самом деле ерунда, и вернетесь к верному топору. И только потом кто-нибудь покажет вам, как заводить бензопилу и работать ею.
Чтобы приблизить эту историю к области разработки ПО, достаточно заменить бензопилу функциональным программированием. Проблема с абсолютно новыми стилями программирования заключается не в изучении языка. Синтаксис языка – это детали, а самое сложное– это научиться мыслить по-новому. И здесь на помощь читателю приходит данная серия статей, показывающая как «завести» нашу бензопилу.
Добро пожаловать в "Функциональное мышление". Эта серия изучает предмет функционального программирования, но не зацикливается на языках функционального программирования. Как будет показано, написание кода в функциональном стиле затрагивает дизайн, требует компромиссов, другого выбора блоков для повторного использования и умения "зреть в корень". По мере возможности принципы функционального программирования будут демонстрироваться на Java-примерах (или других языках, близких к Java), но будут рассмотрены и другие языки, обладающие возможностями, отсутствующими в Java. В статьях не будет развернутого теоретического обоснования и рассмотрения таких сущностей, как монады (см. раздел "Ресурсы") - по крайней мере вначале. Читателю будет продемонстрирован новый способ мышления (который вы наверняка уже применяли где-нибудь, но просто не осознавали этого).
Эта и следующие две статьи служат введением в некоторые аспекты, связанные с функциональным программированием, включая его базовые принципы. Некоторые вопросы будут обсуждаться более подробно в последующих статьях серии, по мере накопления необходимых знаний и погружения в контекст. В качестве отправной точки для знакомства я рекомендую взглянуть на две различные реализации одной задачи, одна из которых написана в императивном стиле (на основе команд-инструкций), а другая – в функциональном стиле.
Классификация чисел
Чтобы говорить о различных стилях программирования, необходимо иметь код для сравнения двух подходов. Первый пример является вариантом проблемы, рассматривавшейся в моей книге The Productive Programmer (см. раздел "Ресурсы"), и в статьях "Test-driven Design, Part 1" и "Test-driven design, Part 2" из прошлой серии статей Evolutionary architecture and emergent design, также опубликованной на портале developerWorks. Этот пример был выбран еще и потому, что в этих статьях очень подробно описывается дизайн кода. Дизайн, представленный в этих статьях, является абсолютно нормальным, но в этой статье будут представлены аргументы в пользу более функционально-ориентированного варианта.
Задача, которую должна решить программа, состоит в определении типа целого и положительного (больше 1) числа. Число может принадлежать к одному из трех типов:
- совершенное (perfect): число равно сумме собственных делителей (за исключением самого числа);
- избыточное (abundant): сумма делителей числа (за исключением его самого) превышает само число;
- недостаточное (deficient): сумма делителей числа (за исключением его самого) меньше самого числа;
Императивная программа-классификатор
В листинге 1 приведен класс, решающий эту задачу в императивном стиле:
Листинг 1. NumberClassifier
, императивное решение задачи
public class Classifier6 { private Set<Integer> _factors; private int _number; public Classifier6(int number) { if (number < 1) throw new InvalidNumberException( "отрицательные числа не классифицируются"); _number = number; _factors = new HashSet<Integer>>(); _factors.add(1); _factors.add(_number); } private boolean isFactor(int factor) { return _number % factor == 0; } public Set<Integer> getFactors() { return _factors; } private void calculateFactors() { for (int i = 1; i <= sqrt(_number) + 1; i++) if (isFactor(i)) addFactor(i); } private void addFactor(int factor) { _factors.add(factor); _factors.add(_number / factor); } private int sumOfFactors() { calculateFactors(); int sum = 0; for (int i : _factors) sum += i; return sum; } public boolean isPerfect() { return sumOfFactors() - _number == _number; } public boolean isAbundant() { return sumOfFactors() - _number > _number; } public boolean isDeficient() { return sumOfFactors() - _number < _number; } public static boolean isPerfect(int number) { return new Classifier6(number).isPerfect(); } }
В этом коде следует выделить несколько моментов:
- он полностью покрыт unit-тестами (частично это связано с тем, что он писался для обсуждения разработки, основанной на тестах – test driven development).
- класс состоит из множества внутренне связанных (cohesive) методов, что обусловлено использованием разработки, основанной на тестах.
- в метод
calculateFactors()
встроена оптимизация производительности. Основная задача класса заключается в вычислении делителей, чтобы потом можно было их сложить и определить тип числа. Делители можно собирать по парам, например, если исследуется число 16, то, определив делитель 2, можно найти делитель 8, т.к. 2 * 8 = 16. Если собирать делители попарно, то достаточно проверять делители не больше квадратного корня из целевого числа, что и делается в методеcalculateFactors()
.
Более функциональная программа-классификатор
Используя тот же самый основанных на тестах подход, можно создать альтернативную реализацию программы, представленную в листинге 2.
Листинг 2. Более функциональная версия классификатора чисел
public class NumberClassifier { static public boolean isFactor(int number, int potential_factor) { return number % potential_factor == 0; } static public Set<Integer> factors(int number) { HashSet<Integer> factors = new HashSet<Integer>(); for (int i = 1; i <= sqrt(number); i++) if (isFactor(number, i)) { factors.add(i); factors.add(number / i); } return factors; } static public int sum(Set<Integer> factors) { Iterator it = factors.iterator(); int sum = 0; while (it.hasNext()) sum += (Integer) it.next(); return sum; } static public boolean isPerfect(int number) { return sum(factors(number)) - number == number; } static public boolean isAbundant(int number) { return sum(factors(number)) - number > number; } static public boolean isDeficient(int number) { return sum(factors(number)) - number < number; } }
Хотя различия между этими двумя версиями и трудно уловимы, но они крайне важны. Основное отличие заключается в намеренном отказе от «общего» состояния в листинге 2. Устранение (или, по меньшей мере, уменьшение) "общего" состояния – это одна из абстракций, наиболее часто применяемых в функциональном программировании. Вместо того чтобы передавать состояние между методами в виде промежуточных результатов (см. поле factors
в листинге 1), методы вызываются напрямую, минуя обращения к состоянию. С точки зрения дизайна это удлиняет метод factors()
, но зато предотвращает "утечку" поля factors
из метода. Стоит также отметить, что листинг 2 состоит только из static
-методов. Поскольку не существует данных, совместно используемых методами, можно меньше заботиться и об инкапсуляции данных с помощью модификаторов доступа. Все эти методы будут превосходно работать, если просто передавать им входные параметры ожидаемых типов. (Это пример "чистой" функции – понятия, которое будет исследоваться в следующей статье).
Функции
Функциональное программирование – это обширная область компьютерных технологий, переживающая резкий всплеск популярности. На сцену (см. раздел "Ресурсы") выходят новые функциональные языки на основе JVM (такие как Scala и Clojure) и инфраструктуры (такие как Functional Java и Akka), которые, как обычно, обещают снижение количества дефектов и рост продуктивности, улучшение перспектив и рост доходов и т.д. Вместо того чтобы пытаться охватить всю область функционального программирования, я сосредоточусь на нескольких ключевых концепциях и выведу из них несколько интересных заключений.
Ядром функционального программирования является функция, подобно тому, как классы являются главной абстракцией в объектно-ориентированных языках. Функции образуют строительные блоки для обработки данных и имеют дополнительные возможности, не встречающиеся в традиционных императивных языках.
Функции высших порядков
Функции высших порядков могут принимать другие функции в качестве аргументов или возвращать их в виде результатов. В языке Java подобные конструкции не допускаются. В качестве ближайшего аналога можно рассмотреть использование класса (обычно анонимного) в качестве "контейнера" для функции, которую необходимо выполнить. В Java не существует самостоятельных функций или методов, так что их невозможно возвращать из функций или передавать в качестве параметров.
Такая способность важна для функциональных языков по меньшей мере по двум причинам. Во-первых, наличие функций высшего порядка позволяет делать предположения о том, как элементы сочетаются вместе. Например, можно отказаться от целой категории методов в иерархии классов, если построить общий механизм, просматривающий список и применяющий к каждому его элементу одну или несколько функций высшего порядка. (Пример подобной конструкции будет продемонстрирован ниже.) Во-вторых, возможность использовать функции в качестве возвращаемых значений позволяет строить динамические адаптируемые системы.
Проблемы, связанные с использованием функций высшего порядка, не являются уникальными только для функциональных языков. Тем не менее при использовании функционального решения появляется альтернативный способ решения этих проблем. В листинге 3 приведен пример метода, который обеспечивает защищенный доступ к данным (это пример взят из большего фрагмента кода).
Листинг 3. Фрагмент исходного кода, потенциально пригодный для повторного использования
public void addOrderFrom(ShoppingCart cart, String userName, Order order) throws Exception { setupDataInfrastructure(); try { add(order, userKeyBasedOn(userName)); addLineItemsFrom(cart, order.getOrderKey()); completeTransaction(); } catch (Exception condition) { rollbackTransaction(); throw condition; } finally { cleanUp(); } }
Код из листинга 3 выполняет инициализацию, а затем определенные действия. Код завершает транзакцию, если всё прошло успешно, или откатывает её в противном случае, а в конце освобождает все ресурсы. Очевидно, что "каркас" этого кода можно использовать неоднократно, и в объектно-ориентированных языках это обычно делается путем создания структуры. В данном случае я использую сочетание двух шаблонов из арсенала "Банды Четырех" (книга Design Patterns – см. раздел "Ресурсы"): Template Method (шаблонный метод) и Command (команда). Шаблон Template Method предлагает поместить "каркас" общего кода в иерархию наследования, отложив алгоритмические подробности для дочерних классов. Шаблон Command предлагает способ инкапсулировать поведение в классе с хорошо известной семантикой исполнения. В листинге 4 приведен результат применения этих двух шаблонов к коду из листинга 3.
Листинг 4. Код после рефакторинга
public void wrapInTransaction(Command c) throws Exception { setupDataInfrastructure(); try { c.execute(); completeTransaction(); } catch (Exception condition) { rollbackTransaction(); throw condition; } finally { cleanUp(); } } public void addOrderFrom(final ShoppingCart cart, final String userName, final Order order) throws Exception { wrapInTransaction(new Command() { public void execute() { add(order, userKeyBasedOn(userName)); addLineItemsFrom(cart, order.getOrderKey()); } }); }
В листинге 4 "общие" фрагменты кода помещены в метод wrapInTransaction()
(можно заметить, что его семантика – это упрощенная версия TransactionTemplate
– шаблона инфраструктуры Spring), а объект Command
передается в этот метод в качестве "рабочей единицы" (unit-of-work). Метод addOrderFrom()
ужимается до определения анонимного вложенного класса, используемого для создания команды, содержащей два обрабатываемых элемента.
Оформление необходимой функциональности в виде класса-«команды» связано с особенностью языка Java, который не предполагает никакой "самостоятельной" функциональности. В Java вся функциональность должна находиться внутри класса. Если оглянуться назад, то даже сами разработчики языка быстро заметили "пробел" в таком дизайне, так как наивно предполагать, что НИКОГДА не потребуется функциональность, не подключенная ни к одному классу. В JDK 1.1 это упущение было исправлено добавлением анонимных вложенных классов, которые обеспечили синтаксическую основу для создания множества маленьких классов всего с несколькими методами, которые являются исключительно функциональными, а не структурирующими. Интересное эссе об этом аспекте языка Java можно прочитать в статье Стива Йегга (Steve Yegge) "Execution in the Kingdom of Nouns" (см. раздел "Похожие темы").
Методология Java заставила меня создать объект класса Command
, хотя на самом деле мне просто был необходим метод, находящийся внутри этого класса. Сам по себе класс не предоставляет никаких преимуществ: у него нет полей, конструкторов (кроме конструктора по умолчанию, генерируемого самой Java) и нет состояния. Он используется только в качестве "оболочки" для функциональности, заключенной внутри метода. В функциональном языке для этого бы использовался метод высшего порядка.
Если на секунду "отказаться" от языка программирования Java, то с помощью замыканий (closures) можно получить код, семантически близкий к идеалу функционального программирования. В листинге 5 приведен тот же пример, подвергшийся рефакторингу, но уже с помощью языка Groovy (см. раздел "Ресурсы").
Листинг 5. Использование Groovy-замыканий вместо классов-команд
def wrapInTransaction(command) { setupDataInfrastructure() try { command() completeTransaction() } catch (Exception ex) { rollbackTransaction() throw ex } finally { cleanUp() } } def addOrderFrom(cart, userName, order) { wrapInTransaction { add order, userKeyBasedOn(userName) addLineItemsFrom cart, order.getOrderKey() } }
В Groovy всё находящееся внутри фигурных скобок {} представляет собой блок кода (closure), и эти блоки кода могут передаваться в качестве параметров, имитируя поведение функций высшего порядка. Но "за кулисами" Groovy просто реализует шаблон Command вместо самого программиста. Каждый блок с замыканием в Groovy – это объект типа closure
, который включает в себя метод call()
, автоматически вызываемый при указании пустых круглых скобок после переменной, содержащей объект замыкания. В Groovy определенные возможности, похожие на функциональное программирование, реализуются за счет построения соответствующих структур данных на синтаксической основе, встроенной в сам язык. Как будет показано в следующих статьях, Groovy также включает другие возможности функционального программирования, которые уже выходят за рамки Java. В одной из следующих статей мы вернемся к этому сравнению замыканий и функций высшего порядка.
Функции первого класса
В функциональном языке программирования функции являются сущностями "первого класса", что означает, что они могут встречаться в таких местах, где в других языках программирования используются другие конструкции (например, переменные). Наличие функций «первого класса» позволяет использовать их нестандартными способами и по-новому взглянуть на решения, предлагаемые для общих (за исключением отдельных нюансов) операций, применяемых к стандартным структурам данных. Это приводит к фундаментальному сдвигу в мышлении: "фокусироваться на результатах, а не на отдельных действиях".
В императивных языках программирования необходимо продумывать каждый отдельный шаг в разрабатываемом алгоритме. Этот подход продемонстрирован в листинге 1. Для решения задачи о классификации чисел необходимо точно определить, как вычислять делители, что в свою очередь, требует написания специального кода для итерирования по числам с целью поиска делителей. Но итерирование по списку и выполнение определенных действий с каждым элементом – это довольно стандартный прием. Рассмотрим альтернативную реализацию классификатора чисел, выполненную с помощью инфраструктуры Functional Java; см. листинг 6.
Листинг 6. Функционально-ориентированный классификатор чисел
public class FNumberClassifier { public boolean isFactor(int number, int potential_factor) { return number % potential_factor == 0; } public List<Integer> factors(final int number) { return range(1, number+1).filter(new F<Integer, Boolean>() { public Boolean f(final Integer i) { return isFactor(number, i); } }); } public int sum(List<Integer> factors) { return factors.foldLeft(fj.function.Integers.add, 0); } public boolean isPerfect(int number) { return sum(factors(number)) - number == number; } public boolean isAbundant(int number) { return sum(factors(number)) - number > number; } public boolean isDeficiend(int number) { return sum(factors(number)) - number < number; } }
Ключевые различия между листингами 2 и 6 заключаются в методах sum()
и factors()
. Метод sum()
использует возможности метода foldLeft()
, относящегося к классу List
инфраструктуры Functional Java. Это специальная реализация приема catamorphism из области манипулирования списками (catamorhism – это обобщение приемов для работы со списком). В данном случае операция "fold left" (свертывание влево) означает:
- взять исходное значение и соединить его с первым элементом списка с помощью определенного действия;
- взять полученный результат и выполнить эту же операцию для следующего элемента;
- повторять пункты 1 и 2 до тех пор, пока список не закончится.
Очевидно, это те же самые действия, которые выполняются при суммировании чисел: начать с нуля и добавить первый элемент, взять результат и сложить его со вторым, продолжать, пока список не исчерпается. Инфраструктура Functional Java предоставляет функции высшего порядка (Integers.add
и enumeration
) и берет на себя все операции по их применению. (Конечно, в действительности в Java нет функций высшего порядка, но можно создать неплохой аналог, если ограничить его отдельной структурой и типом данных).
Другой интересный метод в листинге 6 – это метод factors()
, иллюстрирующий совет "фокусироваться на результатах, а не на действиях". В чем суть проблемы поиска делителей числа? Если сформулировать её другим способом, то задача выглядит так: имея список чисел, предшествующих целевому числу, определить, какие из них являются делителями. Для этого можно воспользоваться фильтрацией – профильтровать полный список, удалив из него числа, не соответствующие критерию. Простыми словами такой метод можно описать так: взять диапазон чисел от 1 до искомого (само число в этот диапазон не входит); отфильтровать список на основе кода из метода f()
(таким способом Functional Java позволяет создавать классы с определенными типами данных); возвратить оставшиеся значения.
Этот код также иллюстрирует более важную тенденцию, являющуюся общей для разных языков программирования. Поначалу программистам приходилось заниматься выделением памяти, «сборкой мусора» и работой с указателями. Со временем языки программирования взяли на себя большую часть этих забот. По мере того как росла Так мощность компьютеров, все больше и больше автоматизируемых задач перекладывалось на языки и среды исполнения. В Java все операции по работе с памятью берет на себя язык программирования. Со временем мы будем тратить все меньше времени на продумывание действий, необходимых для решения проблемы, и все больше думать в терминах процессов. Примеры подобного подхода будут продемонстрированы в следующих статьях серии.
Заключение
Функциональное программирование – это скорее образ мысли, нежели набор инструментов и языков. В этой первой статье серии рассматривались некоторые вопросы функционального программирования - от простых дизайнерских решений до радикального переосмысления задач. Мы переписали простой Java-класс, сделав его более функциональным, вместо того чтобы тщательно исследовать теоретические различия между функциональным программированием и стандартными императивными языками.
В этой статье впервые были представлены две важные концепции. Первая – "фокусироваться на результатах, а не действиях". Функциональное программирование пытается представить проблемы в другом свете, так как в нём используются другие строительные блоки, упрощающие реализацию решений. Вторая концепция, которая будет демонстрироваться на протяжении всей серии, - это перенос низкоуровневых задач на языки программирования или среды исполнения, что позволяет нам фокусироваться на уникальных особенностях решаемой проблемы. В следующей статье мы продолжим изучать общие аспекты функционального программирования и их применение в современной разработке ПО.
Ресурсы для скачивания
Похожие темы
- Functional thinking: Thinking functionally, Part 1: оригинал статьи (EN).
- Monads: монады (ключевой субъект в функциональных языках программирования) будут рассмотрены в одной из будущих статей.
- The Productive Programmer (Neal Ford, O'Reilly Media, 2008): новая книга Нила Форда, в которой более подробно рассматриваются некоторые вопросы из данной серии статей.
- Monads: монады (ключевой субъект в функциональных языках программирования) будут рассмотрены в одной из будущих статей.
- Scala: современный функциональный язык программирования на основе JVM.
- Clojure: современная функциональная реализация Lisp, работающая поверх JVM.
- Podcast: Stuart Halloway on Clojure: узнайте больше о Clojure и двух основных причинах, способствующих его широкому распространению и росту его популярности.
- Akka: Java-инфраструктура для организации параллельного выполнения на основе взаимодействующих субъектов (actors).
- Functional Java: инфраструктура, добавляющая в Java конструкции из арсенала функционального программирования.
- Design Patterns: Elements of Reusable Object-Oriented Software (Erich Gamma et al., Addison-Wesley, 1994): классическая книга о шаблонах проектирования.
- "Execution in the Kingdom of Nouns" (Steve Yegge, март 2006): статья, в развлекательном стиле описывающая отдельные аспекты дизайна языка программирования Java.