Pull to refresh

Functional thinking: Thinking functionally, Часть 1

Reading time 12 min
Views 15K
Original author: Neal Ford
Давайте на мгновение представим, что Вы — дровосек. И благодаря своему лучшему топору в округе, вы являетесь самым продуктивным дровосеком в лагере. Но однажды появляется некто, начинающий расхваливать достоинства новой парадигмы в рубке леса — бензопилы. В силу убедительности продавца, Вы покупаете бензопилу, но не знаете как она работает. Прилагая неимоверные усилия, пробуете вырвать или раскачать дерево, применяя на практике свою новую парадигму. И быстренько делая вывод, что эта самая новомодная бензопила — ерунда, возвращаетесь к привычному делу — рубить лес топором. А затем кто-то приходит и показывает как заводить бензопилу.

Эта история может показаться Вам знакомой, поставив функциональное программирование на место бензопилы. Проблема в совершенно новой парадигме программирования — не изучение нового языка. Более того, синтакс языка — это всего лишь детали. Вся тонкость же — научиться мыслить иначе. Это то, почему я оказался тут — заводящий бензопилы и “функциональный” программист.

Итак, добро пожаловать в Functional thinking. Эта серия исследует предмет функционального программирования, но не несет исключительной направленности описать функциональные языки. Как я покажу дальше, написание кода в функциональном стиле касается дизайна, компромиссов, разных повторно используемых кусков кода и служит основой для иных догадок. Насколько это окажется возможным, я попытаюсь показать концепции функционального программирования в Java (или близких к Java языках) и перейду к другим языкам, чтобы осветить возможности, отсутствующие на данный момент в Java. Я не полезу сразу в дебри, рассказывая о довольно необычных вещах, таких как монады (monads). Напротив, я постепенно проведу Вас через новый путь мышления.

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

Number classifier


Начиная разговор о разных стилях программирования, Вам необходим код для сравнения. В качестве первого примера я приведу вариацию одной проблемы, рассматриваемой в моей книге The Productive Programmer, а также первой и второй частях Test-driven design. Как минимум, я выбрал этот код потому, что в этих двух публикациях он рассматривается достаточно глубоко. Нет ничего дурного в дизайне, превозносимом в этих статьях, но я хочу ниже предложить разумное обоснование иному подходу.

Суть требований в том, что при поступлении на вход положительного числа больше 1, Вам нужно классифицировать его как perfect (совершенное), abundant (избыточное) или deficient (недостаточное). Совершенным является то число, чьи делители (за исключением его самого, как делителя) в сумме ему равны. Подобно тому, сумма делителей избыточного числа выше его самого, а недостаточного — меньше.

Imperative number classifier

Императивный класс, удовлетворяющий вышеуказанным требованиям представлен ниже:

Listing 1. NumberClassifier, the imperative solution to the problem
public class Classifier6 {
    private Set<Integer> _factors;
    private int _number;

    public Classifier6(int number) {
        if (number < 1)
            throw new InvalidNumberException(
            "Can't classify negative numbers");
        _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-тестов (частично из-за того, что я написал его для рассуждения в аспекте TDD)
  • класс состоит из большого числа связанных методов, что в таком виде является побочным эффектом (side effect) для использования в TDD
  • встроенная в метод calculateFactors() оптимизация производительности. Сущность этого класса составляет сбор делителей, чтобы в дальнейшем их сложить и в конечном итоге классифицировать. Делители всегда могут быть собраны в пары. Например, если число на входе — 16, то когда я определяю делитель 2, я также использую и 8, так как 2*8=16. Если я собираю делители в пары, мне всего лишь необходимо проверить на них, составляющие квадратный корень из рассматриваемого числа, что в точности и делает метод calculateFactors().

(Slightly more) functional classifier

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

Listing 2. Slightly more functional number classifier
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;
    }
}

Разница между двумя версиями классификаторов едва уловимая, но достаточно важная. Основное отличие — это осознанное удаление из кода разделяемого состояния (shared state). Избавление от него является одной из важных черт в функциональном программировании. Вместо того, чтобы разделять состояние в виде промежуточных результатов между методами (поле factors в Листинге 1), я вызываю методы напрямую, что позволяет избавится от него. С точки зрения дизайна, метод factors() становится длиннее, но препятствует утеканию поля factors за пределы метода. Также стоит отметить, что вторая версия может состоять исключительно из статических методов. Никаких аккумулирующих переменных, используемых от метода к методу, что позволяет мне избавится от необходимости инкапсуляции через области видимости (scoping). Все эти методы отлично отработают, если послать на вход параметр требуемого типа. (Это пример чистой функции (pure function), коцепции, которую я рассмотрю позже, в следующей части).

Functions


Функциональное программирование является широкой и довольно активно развивающейся областью в computer science, вызывающей все больший интерес. Появляются новые функциональные языки в JVM (такие как Scala или Clojure) и фреймворки (Functional Java или Akka) вместе с заявлениями о возникновении меньшего числа ошибок, большей продуктивности, лучшей читаемости, больших дивидендов и т.д. Вместо того, чтобы сразу охватить весь предмет функционального программирования, я сфокусируюсь на нескольких ключевых концепциях, завершая повествование некоторыми интересными выводами.

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

Higher-order functions

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

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

Проблемы, решаемые использованием функций высшего порядка не уникальны для функциональных языков. Тем не менее, подход, которым Вы решаете проблему отличается, когда начинаете думать “функционально”. Обратите внимание на пример метода в Листинге 3 (вырванный из большего куска кода), обеспечивающего безопасный доступ к данным:

Listing 3. Potentially reusable code template
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 содержит инициализацию, выполняет какую-то работу, завершает транзакцию в случае успешного выполнения, иначе совершает откат (rollback) и в завершении производит освобождение ресурсов. Безусловно, шаблонная часть этого кода может быть повторно использована, и мы, как правило, реализуем это в ООП созданием структуры. В нашем случае, я совмещу 2 паттерна “Банды четырех” (Gang of Four Design Patterns): Шаблонный метод (Template Method) и паттерн Команда (Command). Шаблонный метод предполагает, что мне нужно перенести повторяющуюся часть кода вверх по иерархии наследования, оставляя реализацию алгоритма в дочерних классах. Паттерн “Команда” позволяет инкапсулировать поведение в классе с хорошо известной семантикой выполнения. Листинг 4 демонстрирует результат применения этих двух паттернов к коду из Листинга 3:

Listing 4. Refactored order code
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 как кусок кода для выполнения. Суть метода addOrderFrom() сводится к определению анонимного внутреннего класса (anonymous inner class) для создания экземпляра класса команды, оборачивая пару выражений.

Оборачивание нужного поведения в класс команды — чистой воды артефакт дизайна Java, не содержащего возможность отделения этого поведения. Все поведение в Java должно быть размещено внутри класса. Даже проектировщики языков быстро разглядели недостаток в таком дизайне — оглядываясь в прошлое, немного наивно думать о невозможности существования поведения, не привязанного к классу. JDK 1.1 исправил этот недостаток добавлением анонимных внутренних классов, которые, как минимум, добавляют синтаксического сахара для создания большого числа мелких классов всего лишь с несколькими функциональными методами — не структурными. В качестве занятного эссе об этом аспекте в Java, могу порекомендовать «Execution in the Kingdom of Nouns» (Steve Yegge).

Java принуждает меня создавать экземпляр класса Command, даже если я хочу всего лишь определения одного метода. Сам по себе класс не предоставляет никаких преимуществ: не содержит полей, конструктор (не принимая во внимание стандартный) или какого-либо состояния. Это только оболочка для поведения, реализуемого внутри метода. В функциональном же языке, это решается использованием функцией высшего порядка.
Если я решу на момент оставить Java, то приближусь к идеалу в функциональном программировании, используя замыкания (closures). Листинг 5 демонстирует такой же отрефакторенный пример, но с использованием Groovy вместо Java:

Listing 5. Using Groovy closures instead of command classes
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 все, распологаемое внутри фигурных скобок {} является блоками кода, которые могут передаваться в качестве параметров, имитируя функции высшего порядка. За кулисами Groovy реализует для Вас паттерн “Команда”. Каждый блок замыкания в Groovy на самом деле экземпляр специального типа Closure, который содержит метод call(), автоматически выполняющийся в момент размещения круглых скобок () после переменной, указывающей на экземпляр замыкания. Groovy позволяет реализовывать некоторое, сравнимое с “функциональным”, поведение, выстраивая соответствующие структуры данных, добавляя в язык синтаксического сахара. Как я покажу в следующих частях, Groovy также содержит другие возможности функционального программирования, лежащие за границами Java. Также в дальнейшем я вернусь назад для некоторого интересного сравнения замыканий и функций высшего порядка.

First-class functions

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

В императивных языках программирования мне приходится думать о каждом элементарном шаге в алгоритме. Код в Листинге 1 наглядно демонстрирует это. Для реализации классификатора чисел мне нужно точно определить то, как собирать делители, что в свою очередь означает необходимость писать специфичный код, чтобы пройти по циклу для определения среди чисел делителей. Но обход списков с проведением операции на каждом элементе кажется довольно привычной вещью. Посмотрите в Листинге 6 на переопределенный код классификатора чисел с использованием фреймворка Functional Java:

Listing 6. Functional number classifier
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 number % i == 0;
            }
        });
    }

    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;
    }
} 

Основное отличие между Листингами 6 и 2 составляют два метода: sum() и factors(). sum() использует преимущества метода foldLeft() применительно к классу List в Functional Java. Это специфичная разновидность манипуляций со списками носит название катаморфизм (catamorphism), что является обобщением для свертывания списков (list folding). В этом случае “свертывание списка” означает:
  1. Взять начальное значение применить к нему в паре с первым элементом списка указанную операцию
  2. Получить результат и применить эту же операцию к вместе со следующим элементом
  3. Повторять действие пока не будет достигнут конец списка

Заметьте, это в точности то, что вы делаете когда суммируете список элементов: начинаете с 0, добавляете первый элемент, получая результат, добавляете второй и далее, пока не обойдете весь список. Functional Java делат возможным использование функции высшего порядка (в этом примере Integers.add) и применяет ее за Вас. (Несомненно, в Java на самом деле нет функций высшего порядка, но Вы можете написать отличный аналог на случай ограничений, накладываемых структурой данных или их типом.

Другой интригующий метод в Листинге 6 — factors(), который иллюстрирует совет “концентрируйтесь на результате, а не промежуточных шагах”. В чем суть проблемы определения делителей числа? Иначе говоря, учитывая список всех возможных чисел до рассматриваемого, как я могу выделить из них те, что являются его делителями? Это подсказывает использование операции фильтрации — я могу отфильтровать полный список чисел, исключая те, которые не удовлетворяют моему критерию. Обычно читается: берем диапазон чисел от 1 до рассматриваемого, фильтруем список кодом внутри метода f(), что является способом в Functional Java, позволяющим создавать класс со специфичными типами и возвращаемыми значениями.
Этот код иллюстрирует гораздо большее понятие — такое, как тенденцию в языках программирования в целом. В прошлом разработчикам приходилось обрабатывать большое количество раздражающих вещей, как выделение памяти, сборка мусора, указатели. С течением времени многое из этого взяли под свою опеку языки и среды выполнения. Подобно тому, как компьютеры становятся все более мощными, мы выносим обыденные, поддающиеся автоматизации задачи в языки и среды выполнения. Как Java-разработчик, я привык уступать языку все проблемы, касающиеся памяти. Функциональное программирование расширяет эти полномочия, охватывая более специфичные детали. Со временем, мы проводим все меньше времени за заботой о шагах, необходимых для решения проблемы и думаем больше в терминологии процессов. В продолжении серии я продемонстрирую множество примеров этого.

Заключение


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

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

P.S. Огромное спасибо CheatEx за review перевода. Скорее всего, продолжение следует…
Tags:
Hubs:
+58
Comments 102
Comments Comments 102

Articles