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

http://www.ibm.com/developerworks/java/library/j-ft2/index.html
  • Перевод

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

First-class functions and control


Используя библиотеку Functional Java, в прошлый раз я продемонстрировал реализацию классификатора чисел с написанными в функциональном стиле методами isFactor() и factorsOf(), как показано в Листинге 1:

Listing 1. Functional version of the number classifier
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() и factorOf() я делегировал алгоритм обхода фреймворку, который сам решает как лучше обойти диапазон чисел. Если фреймворк (или непосредственно язык, если вы используете к примеру функциональные языки Clojure и Scala) способен оптимизировать лежащую в основе реализацию, то Вы автоматически выигрываете от этого. И хотя на первых порах Вам не захочется перекладывать эту функциональность на чужие плечи, все же заметьте, что это следует основной тенденции в языках программирования и средах. С течением времени, разработчик все больше абстрагируется от деталей, которые платформа может обрабатывать более эффективно. Я никогда не забочусь об управлении памятью в JVM, потому что платформа позволяет мне забыть про это. Конечно, временами, это делает некоторые вещи более сложными, но это хороший компромисс для преимуществ, которые Вы получаете в повседневном написании кода. Конструкции функционального языка такие как: функции высшего порядка и функции — объекты, позволяют мне подняться еще на одну ступень выше в лестнице абстракции и сфокусироваться на том что должен делать код, а не как он должен это делать.

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

Classifier in Clojure

Clojure — это функциональный Lisp, спроектированный для JVM. Посмотрите на классификатор чисел, написанный на Clojure — Листинг 2

Listing 2. Clojure implementation of the number classifier
(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? принимает два параметра и проверяет на равенство нулю остатка от деления после умножения number на factor. Подобно этому методы perfect?, abundunt? и deficient? также должны оказаться простыми для понимания, особенно если Вы глянете на Листинг 1 с реализацией на Java.

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

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

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

Optimization

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

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

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

Я могу переформулировать исходную проблему в функциональном стиле: отфильтровать все делители от 1 до заданного числа, оставляя только те, которые удовлетворяют предикату isFactor. Это сделано в листинге 3:

Listing 3. The isFactor() method
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;
        }
    });
}

Несмотря на свою элегантность, код в Листинге 3 не очень эффективен так как проверяет каждое число. Однако поняв оптимизацию (собирать делители парами от 1 до квадратного корня) я могу переформулировать проблему:
  1. Отфильтровать все числа от 1 до квадратного корня заданного числа.
  2. Делить заданное число на каждый из этих делителей для получения парного делителя и добавлять его в список делителей.

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

Listing 4. Optimized factors-finding method
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 (чтобы быть уверенным, что я получу все делители). Затем, также как и в предыдущей версии, я фильтрую результат с помощью оператора модуля, завёрнутого в блок кода. Я сохраняю этот отфильтрованный результат в переменной factors. Далее (если читать изнутри) я беру этот список делителей и выполняю функцию map(), которая создаёт новый список, выполняя мой блок кода для каждого элемента (отображая каждый элемент в новое значение). Мой список делителей содержит все делители заданного числа меньше квадратного корня; теперь я должен разделить заданное число на каждый из них чтобы получить список симметричных делителей и соединить его с исходным списком. На последнем шаге я должен учесть, что я храню делители в списке, а не во множестве. Методы списка удобны для манипуляций, которые выполнялись ранее, но мой алгоритм имеет побочный эффект: один элемент повторяется дважды если среди делителей появляется квадратный корень. Например, если число 16, квадратный корень из него 4 появится в списке делителей дважды. Чтобы и дальше пользоваться удобными методами списка, я должен вызвать метод nub() в конце для удаления всех повторений.

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

Во всём коде, что я привёл выше визуально доминирует синтаксис блоков, который использует обощения и анонимные вложенные классы как псевдо блоки кода. Замыкания — это одна из самых общих черт функциональных языков. Что же делает их настолько полезными в функциональном мире?

What's so special about closures?


Замыкание (closure) — это функция, cохраняющая неявные ссылки на переменные, на которые ссылается. Иными словами, функция (или метод), захватывающая и сохраняющая окружающий её контекст *. Замыкания используются довольно часто в качестве портативного механизма исполнения в функциональных языках и фреймворках, передающегося в функции высшего порядка, например в map() для трансформации. Functional Java использует анонимные внутренние классы для имитации некоторого поведения “настоящих” замыканий, но они не в состоянии предоставить всю полноту функциональности последних, потому как в Java нет поддержки замыканий. Что это означает?

Листинг 5 показывает пример того, что делает замыкания особенными. Он написан на Groovy — языке, поддерживающем замыкания непосредственно.

Listing 5. Groovy code illustrating closures
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

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

Чтобы показать в действии метод makeCounter(), я присвоил ссылку на блок переменной c1, затем вызвал ее 3 раза. Я использую синтаксический сахар Groovy для выполнения блока кода, состоящий в размещении скобок вслед за переменной. Затем я вызываю makeCounter() снова, присваивая новый экземпляр блока кода переменной C2. В заключение, я выполняю C1 снова вместе с C2. Заметьте, что каждый блок кода ссылается на отдельный экземпляр переменной very_local_variable. Это именно то, что я имел в виду, говоря о захвате контекста. Несмотря на кажущуюся локальность определения переменной внутри метода, замыкание все равно связано с ней и хранит состояние."

Наибольшее приближение к такому поведению, реализованное на Java представлено в Листинге 6:

Listing 6. MakeCounter in Java
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 и его близких родственниках с описанием карринга(currying) и частичного применения метода(partial method application).

Примечания

* — Здесь автор видимо излишне старательно уходит от академической терминологии. Речь идёт о свободных переменных в лямбда-выражении. Хорошую интуицию о поведении замыканий в разных реализациях можно получить из статьи в ПФП. Достаточно понятное формальное определение свободных и связанных переменных приведено в статье википедии.

P.S. Спасибо CheatEx за оказанную помощь при переводе
  • +36
  • 3,8k
  • 7
Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 7
  • +2
    На clojure можно и без «for» чисто функционально написать:

    (defn factors [number]
    (filter #(is-factor? % number) (range 1 number)))

    Также можно «удешевить» sum-factors:

    (defn sum-factors [number]
    (apply + (factors number)))
    • +4
      Неужто сложно поставить ссылку на первую часть?
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        А можете чуть подробнее и конструктивнее осветить проблемы?
      • 0
        По сравнению с Clojure джава совершенно нечитаема.
        • 0
          (= number (- (sum-factors number) number)))


          А разве не

          (= number (sum-factors number)))

          ?

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