Функциональное мышление: Часть 2. Разработка программ в функциональном стиле

Исследование возможностей функционального программирования

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

Нил Форд, Архитектор приложений, ThoughtWorks

Нил Форд (Neal Ford) работает архитектором приложений в ThoughtWorks, революционной компании, предоставляющей профессиональные IT-услуги и помогающей талантливым людям по всему миру эффективнее использовать программное обеспечение. Он также является проектировщиком и разработчиком приложений, учебных материалов, журнальных статей, учебных курсов, видео/DVD-презентаций и автором книг "Разработка с Delphi: Объектно-ориентированный подход", "JBuilder 3 Unleashed" и "Искусство разработки Web-приложений на Java". Он специализируется на консультациях по построению широкомасштабных корпоративных приложений. Он также является общепризнанным докладчиком и выступал на многочисленных конференциях разработчиков по всему миру. С ним можно связаться по адресу: nford@thoughtworks.com.



31.05.2011

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

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

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

Функции первого класса и управление

В листинге 1 показана реализация классификатора чисел с функциональными методами isFactor() и factorsOf(), основанных на возможностях библиотеки Functional Java (см. раздел "Ресурсы").

Листинг 1. Функциональная версия классификатора чисел
import fj.F;
import fj.data.List;
import static fj.data.List.range;
import static fj.function.Integers.add;
import static java.lang.Math.round;
import static java.lang.Math.sqrt;

public class FNumberClassifier {

    public boolean isFactor(int number, int potential_factor) {
        return number % potential_factor == 0;
    }

    public List<Integer> factorsOf(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(factorsOf(number)) - number == number;
    }

    public boolean isAbundant(int number) {
        return sum(factorsOf(number)) - number > number;
    }

    public boolean isDeficiend(int number) {
        return sum(factorsOf(number)) - number < number;
    }
}

В методе isFactor() и factorsOf() управление циклическим алгоритмом передается инфраструктуре, и она решает, как лучше выполнить итерирование по диапазону чисел. Если инфраструктура (или язык, если используется функциональный язык, такой как Clojure и Scala) может оптимизировать нижележащую реализацию, то вы автоматически оказываетесь в выигрыше. Хотя на первых порах вы неохотно будете расставаться с управлением, следует отметить, что этот подход находится в русле общих тенденций в языках программирования и средах исполнения. Со временем разработчик абстрагируется от вопросов, с которыми платформа может справляться более эффективно. Я не переживаю об управлении памятью на платформе Java, так как платформа позволяет мне забыть об этом. Конечно, иногда некоторые вещи из-за этого усложняются, но это допустимая плата за преимущества, получаемые в процессе повседневного написания кода. Конструкции функциональных языков программирования, такие как функции высших порядков и функции первого класса, позволяют подняться на более высокий уровень абстракции и сфокусироваться на том, что именно делает код, а не на том, как он это делает.

Даже с помощью инфраструктуры Functional Java создание кода в таком стиле на языке Java может показаться сложным, так как на самом деле в этом языке отсутствуют подходящие конструкции. Как же выглядит функционально-ориентированный код в языках, обладающих всеми необходимыми возможностями?

Классификатор в Clojure

Clojure – это функциональная реализация LISP, исполняемая на JVM (см. раздел "Ресурсы"). Рассмотрим классификатор чисел на языке Clojure, представленный в листинге 2.

Листинг 2. Реализация классификатора чисел на языке Clojure
(ns nealford.perfectnumbers)
(use '[clojure.contrib.import-static :only (import-static)])
(import-static java.lang.Math sqrt)

(defn is-factor? [factor number]
  (= 0 (rem number factor)))

(defn factors [number] 
  (set (for [n (range 1 (inc number)) :when (is-factor? n number)] n)))

(defn sum-factors [number] 
    (reduce + (factors number)))

(defn perfect? [number]
  (= number (- (sum-factors number) number)))

(defn abundant? [number]
  (< number (- (sum-factors number) number)))

(defn deficient? [number]
  (> number (- (sum-factors number) number)))

Большую часть кода, представленного в листинге 2, легко понять, даже не будучи опытным Lisp-разработчиком, особенно если вы научитесь читать код "изнутри наружу". Например, метод is-factor? принимает на вход два параметра (factor и number), и если остаток от деления number на factor равен 0, то factor является делителем number. Таким же образом можно расшифровать методы perfect?, abundant? и deficient?, особенно если сравнить с Java-реализацией, приведенной в листинге 1.

Метод sum-factors использует встроенный метод reduce. Метод sum-factors последовательно удаляет элементы из списка, применяя функцию (в данном случае "+") к каждому элементу списка. Метод reduce встречается в различных языках программирования и инфраструктурах, в листинге 1 была приведена реализация этого метода в инфраструктуре Functional Java – метод foldLeft(). Метод factors возвращает список чисел, по которому выполняется итерирование, при этом каждый элемент суммируется с общей суммой, которая затем и возвращается из метода reduce. Хотелось бы отметить, что как только вы привыкнете думать в терминах функций высших порядков и первого класса, то сможете сократить количество "шума" (кода, не относящегося к основной бизнес-задаче) в разрабатываемом коде.

Метод factors может показаться случайным набором символов. Но он сразу приобретет смысл, как только вы познакомитесь со списочными выражениями (list comprehension - одна из самых мощных возможностей для манипулирования списками, доступная в Clojure). Как и раньше, проще всего понять метод factors «изнутри наружу». Не стоит пугаться противоречивой терминологии, так как ключевое слово for в Clojure не используется для создания цикла for. Напротив, его надо рассматривать как основу конструкции, служащей для фильтрации и преобразования элементов. В данном случае, мы хотим отфильтровать диапазон чисел от 1 до number + 1, используя предикат is-factor? (этот метод, использующий функции первого класса, также объявлен в листинге 2 и уже рассматривался выше), и вернуть только числа, соответствующие критерию. Этот метод возвращает список чисел, соответствующих условию фильтрации, который затем преобразуется во множество (set) для устранения дублирующихся элементов.

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

Оптимизация

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

В "предыдущей статье" были представлены две реализации классификатора чисел на основе Java, в которых была выполнена оптимизация кода, вычисляющего делители. В исходной реализации использовалась крайне неэффективная операция взятия остатка от деления (%), при помощи которой все числа начиная с 2 до указанного проверялись на то, являются они делителем указанного числа или нет. Этот алгоритм можно оптимизировать, если учесть тот факт, что делители всегда встречаются "попарно". Например, если искать делители числа 28 и найти делитель 2, то можно вычислить и "парный" ему делитель — 14. Поэтому, если искать делители сразу "по парам", достаточно проверить все числа начиная с 2 и заканчивая квадратным корнем из целевого числа.

Подобную оптимизацию, легко реализуемую в Java, кажется невозможным реализовать в версии на Functional Java, так как в ней мы не можем напрямую управлять работой алгоритма для итерации по списку. Но в процессе обучения «функциональному мышлению» следует отказаться от подобного типа управления и использовать другие предлагаемые возможности.

Попробуем переформулировать исходную проблему в функциональном стиле: необходимо отфильтровать все числа, начиная с 1 до целевого числа, оставив из них только делители, соответствующие предикату isFactor(). В листинге 3 показано, как это можно реализовать в Functional Java.

Листинг 3. Метод isFactor()
public List<Integer> factorsOf(final int number) {
    return range(1, number+1).filter(new F<Integer, Boolean>() {
        public Boolean f(final Integer i) {
            return number % i == 0;
        }
    });
}

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

  1. найти все делители указанного числа из диапазона чисел от 1 до квадратного корня из исследуемого числа.
  2. разделить исследуемое число на каждый из найденных делителей, чтобы найти другой, "симметричный" ему, делитель, и добавить его в список.

Переформулировав проблему, можно написать оптимизированную версию метода factorsOf(), используя средства Functional Java, как показано в листинге 4.

Листинг 4. Оптимизация метода для поиска делителей
public List<Integer> factorsOfOptimzied(final int number) {
    List<Integer> factors = 
        range(1, (int) round(sqrt(number)+1))
        .filter(new F<Integer, Boolean>() {
            public Boolean f(final Integer i) {
                return number % i == 0;
            }});
    return factors.append(factors.map(new F<Integer, Integer>() {
                                      public Integer f(final Integer i) {
                                          return number / i;
                                      }}))
                                      .nub();
}

Код в листинге 4 основан на описанном выше алгоритме с добавлением специального синтаксиса, необходимого для инфраструктуры Functional Java. Сначала берется диапазон чисел от 1 до квадратного корня из целевого числа + 1 (чтобы гарантировать, что будут "охвачены" все делители). Далее, как и в предыдущих версиях, результаты фильтруются с помощью оператора "остаток от деления", но внутри блока кода Functional Java. Этот отфильтрованный список сохраняется в переменной factors. После этого (напоминаю, что код следует читать "изнутри наружу") берется список делителей и к нему применяется функция map, порождающая новый список за счет применения указанного блока кода к каждому элементу ("привязывая" каждый элемент к новому значению). Первоначальный список содержит все делители указанного числа от 1 до квадратного корня из самого числа, поэтому необходимо разделить целевое число на каждый делитель, чтобы найти "пару" текущему делителю, как раз это и делает блок кода, передаваемый в функцию map(). Теперь полученный список "симметричных" нужно присоединить к первоначальному списку. На последнем шаге следует учесть, что делители хранятся в коллекции типа List, а не Set. Методы интерфейса List лучше подходят для подобных манипуляций, но побочным эффектом от алгоритма будет дублирование значений, когда квадратный корень из числа является целым числом. Например, для числа 16 квадратный корень равен целому числу 4, что приведет к дублированию этого делителя в списке. Поэтому, чтобы продолжать пользоваться удобными методами интерфейса List, необходимо вызвать метод nub() для удаления дублирующихся значений.

Хотя мы обычно и отказываемся от изучения низкоуровневых особенностей реализации при использовании высокоуровневых абстракций, таких как функциональное программирование, это не означает, что мы не можем при необходимости к ним обратиться. Платформа Java в основном освобождает программистов от низкоуровневых задач, но, если нужно, можно "спуститься" на более низкие уровни. Аналогичным образом в конструкциях функционального программирования желательно оставлять подробности реализации на откуп абстракциям, экономя время для более важных задач.

Самой заметной особенностью кода, основанного на Functional Java, является использование синтаксиса, в котором параметризованные типы (generics) и анонимные вложенные классы используются в качестве блоков "псевдокода" или замыканий. Замыкания – это одна из стандартных возможностей функциональных языков. В чем же состоят их преимущества?


Замыкания

Замыкание – это функция, которая неявно привязана ко всем переменным, используемым внутри неё. Другими словами, такая функция формирует замкнутый контекст вокруг сущностей, на которые она ссылается. В функциональных языках и библиотеках замыкания часто используются как переносимые конструкции для кода, который необходимо выполнить. Впоследствии замыкания передаются в функции высших порядков, например, в функцию map() в примере с преобразованием списка. В Functional Java для имитации поведения "настоящих" замыканий используются анонимные вложенные классы, но они не могут полностью их заменить, так как в Java отсутствует поддержка замыканий. Что все это значит?

В листинге 5 приведен пример, демонстрирующий возможности замыканий. Он написан на языке Groovy, который поддерживает замыкания благодаря собственному механизму блоков кода.

Листинг 5. Groovy-код, демонстрирующий использование замыканий
def makeCounter() {
  def very_local_variable = 0
  return { return very_local_variable += 1 }
}

c1 = makeCounter()
c1()
c1()
c1()
c2 = makeCounter()

println "C1 = ${c1()}, C2 = ${c2()}"
// output: C1 = 4, C2 = 1

Метод makeCounter() сначала определяет локальную переменную с подходящим именем, а затем возвращает блок кода, использующий эту переменную. Важно отметить, что метод makeCounter() возвращает блок кода, а не значение. Этот блок кода не выполняет никаких действий, только инкрементирует значение локальной переменой и возвращает его. Я добавил в этот код явные вызовы return; на самом деле оба этих вызова в Groovy не являются обязательными, но без них код бы стал выглядеть еще запутаннее!

Вызвав метод makeCounter(), я сохраняю полученный блок кода в переменную C1, а затем вызываю эту переменную три раза. Для исполнения блока кода используется упрощенный синтаксис Groovy, в котором, чтобы вызвать блок кода, достаточно просто поместить пустые круглые скобки за переменной, указывающей на него. Далее метод makeCounter() вызывается еще раз, и возвращенный экземпляр блока кода сохраняется в переменной C2. На последней строке мы еще раз вызываем обе переменные: C1 и С2. Как видно по результату запуска программы, в каждом из блоков кода хранится собственный экземпляр very_local_variable. Это и называется "замкнутым" контекстом: хотя локальная переменная объявлена внутри метода, но блок кода привязан к этой переменной, так как ссылается на неё. Это значит, что блок кода должен отслеживать значение "своей" переменной всё время, пока он считается "живым".

Ближайший аналог подобного поведения, реализованный на языке Java, представлен в листинге 6.

Листинг 6. Java реализация функции makeCounter
public class Counter {
    private int varField;

    public Counter(int var) {
        varField = var;
    }

    public static Counter makeCounter() {
        return new Counter(0);
    }

    public int execute() {
        return ++varField;
    }
}

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

В итоге замыкания всё-таки появятся в следующей версии Java (хотя обсуждение этого вопроса и выходит за рамки данной статьи). Их появление в Java принесет два важных преимущества. Во-первых, замыкания значительно облегчат работу разработчикам инфраструктур и библиотек, так как обеспечат им более удобный синтаксис. Во-вторых, это обеспечит общую низкоуровневую базу для поддержки замыканий во всех языках, работающих поверх JVM. Хотя многие языки, работающие поверх JVM, уже поддерживают замыкания, но все они реализуют их собственными способами, что затрудняет передачу замыканий из одного языка в другой. Так что если в языке Java появится стандартизованный формат замыканий, то другие языки смогут воспользоваться им.


Заключение

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

В следующей статье мы продолжим изучение конструкций функционального программирования в языке Java и его близких родственниках и познакомимся с приемами преобразования функций currying (карринг) и partial method application (частичное применение метода).

Ресурсы

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=809196
ArticleTitle=Функциональное мышление: Часть 2. Разработка программ в функциональном стиле
publish-date=05312011