Функциональное мышление

Часть 1. Разработка программ в функциональном стиле

Научитесь думать как функциональный программист

Нил Форд
Опубликовано 09.04.2012

Серия контента:

Этот контент является частью # из серии # статей: Функциональное мышление

https://www.ibm.com/developerworks/ru/views/global/libraryview.jsp?series_title_by=Функциональное+мышление

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Функциональное мышление

Следите за выходом новых статей этой серии.

Об этой серии статей

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

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

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

Добро пожаловать в "Функциональное мышление". Эта серия изучает предмет функционального программирования, но не зацикливается на языках функционального программирования. Как будет показано, написание кода в функциональном стиле затрагивает дизайн, требует компромиссов, другого выбора блоков для повторного использования и умения "зреть в корень". По мере возможности принципы функционального программирования будут демонстрироваться на 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-класс, сделав его более функциональным, вместо того чтобы тщательно исследовать теоретические различия между функциональным программированием и стандартными императивными языками.

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

Ресурсы для скачивания

этот контент в PDF