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

Отложенное выполнение. Часть 1

Исследование отложенного выполнения в Java

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

Отложенное выполнение присутствует во многих функциональных языках программирования. Его смысл - отложить вычисление выражений настолько, насколько это возможно. "Отложенные" коллекции предоставляют свои элементы по мере необходимости, а не вычисляют их заранее, что обеспечивает некоторые преимущества. Во-первых, так можно отложить сложные вычисления до того момента, когда они действительно понадобятся. Во-вторых, можно создавать "бесконечные" коллекции, которые будут постоянно возвращать новые элементы при обращении к ним. В-третьих, "отложенное" использование таких функциональных возможностей, как отображение (map) и фильтрация (filter) позволяет создавать более эффективный код (в разделе "Ресурсы" есть ссылка на статью Брайана Гетца (Brian Goetz) с подробным обсуждением данного вопроса). Хотя Java изначально и не поддерживает отложенное выполнение, но такой возможностью обладают некоторые инфраструктуры и языки следующего поколения, которые будут рассмотрены в этой и последующих статьях.

Рассмотрим фрагмент псевдокода для вывода длины списка:

print length([2+1, 3*2, 1/0, 5-4])

Если вы попробуете выполнить данный код, то полученный результат может меняться в зависимости от типа используемого языка: строгого (strict) или нестрогого (nonstrict или lazy). В строгом языке программирования выполнение (а, возможно, даже и компиляция) этого кода приведут к возникновению исключения деления на ноль (DivByZeroException) для третьего элемента списка. В нестрогом языке результатом выполнения кода будет 4, что соответствует количеству элементов в списке. В конечном счёте я же вызываю метод length(), а не метод lengthAndThrowExceptionWhenDivByZero(). Одним из распространенных нестрогих языков является Haskell (см. раздел "Ресурсы"). Хотя Java и не поддерживает нестрогое выполнение, вы всё равно можете воспользоваться преимуществами этого подхода в своих Java-программах.

Отложенное итерирование по списку в Java

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

Листинг 1. Простой алгоритм для определения простоты числа

import java.util.HashSet;
import java.util.Set;
import static java.lang.Math.sqrt;

public class Prime {

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

    public static Set<Integer> getFactors(int number) {
        Set<Integer> factors = new HashSet<Integer>();
        factors.add(1);
        factors.add(number);
        for (int i = 2; i < sqrt(number) + 1; i++)
            if (isFactor(i, number)) {
                factors.add(i);
                factors.add(number / i);
            }
        return factors;
    }

    public static int sumFactors(int number) {
        int sum = 0;
        for (int i : getFactors(number))
            sum += i;
        return sum;
    }

    public static boolean isPrime(int number) {
        return number == 2 || sumFactors(number) == number + 1;
    }

    public static Integer nextPrimeFrom(int lastPrime) {
        lastPrime++;
        while (! isPrime(lastPrime)) lastPrime++;
        return lastPrime;
    }
}

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

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

Листинг 2. Создание объекта типа Iterator с отложенным выполнением

public class PrimeIterator implements Iterator<Integer> {
    private int lastPrime = 1;

    public boolean hasNext() {
        return true;
    }

    public Integer next() {
        return lastPrime = Prime.nextPrimeFrom(lastPrime);
    }

    public void remove() {
       throw new RuntimeException("Can't change the fundamental nature of the universe!");
    }
}

Метод hasNext() в листинге 2 всегда возвращает true, потому что множество простых чисел, как нам известно, является бесконечным. Метод remove() не может применяться в данном сценарии, так что в случае его вызова я выдаю исключение. Ключевым является метод next(), который своей единственной строкой решает сразу две задачи. Во-первых, он генерирует следующее простое число на основе предыдущего такого числа с помощью метода nextPrimeFrom(), который я добавил в листинге 1. Во-вторых, он обновляет значение внутреннего поля lastPrime, используя возможность Java, позволяющую выполнять присваивание и возврат значения в одной инструкции. В листинге 3 представлен тест для итератора с отложенным выполнением.

Листинг 3. Тестирование объекта Iterator с отложенным выполнением

public class PrimeTest {
    private ArrayList<Integer> PRIMES_BELOW_50 = new ArrayList<Integer>() {{
                add(2);  add(3);  add(5);  add(7);  add(11);  add(13);
                add(17); add(19); add(23); add(29); add(31);  add(37);
                add(41); add(43); add(47);
            }};

    @Test
    public void prime_iterator() {
        Iterator<Integer> it = new PrimeIterator();
        for (int i : PRIMES_BELOW_50) {
            assertTrue(i == it.next());
        }
    }
}

В листинге 3 я создаю объект типа PrimeIterator и проверяю, что он возвращает первые 50 простых чисел. Хотя это и не стандартное использование объектов Iterator, таким способом можно воспроизвести некоторые полезные возможности коллекций с отложенным выполнением.

Использование класса LazyList

Проект Jakarta Commons содержит класс LasyList (см. ссылку в разделе "Ресурсы"), который использует сочетание шаблонов проектирования Декоратор (Decorator) и Фабрика (Factory). Чтобы воспользоваться возможностями этого класса, следует поместить существующий список в "оболочку" из LazyList и создать фабрику для получения новых значений, как показано в листинге 4.

Листинг 4. Тестирование класса LazyList из библиотеки Commons

public class PrimeTest {
    private ArrayList<Integer> PRIMES_BELOW_50 = new ArrayList<Integer>() {{
                add(2);  add(3);  add(5);  add(7);  add(11);  add(13);
                add(17); add(19); add(23); add(29); add(31);  add(37);
                add(41); add(43); add(47);
            }};

    @Test
    public void prime_factory() {
        List<Integer> primes = new ArrayList<Integer>();
        List<Integer> lazyPrimes = LazyList.decorate(primes, new PrimeFactory());
        for (int i = 0; i < PRIMES_BELOW_50.size(); i++)
            assertEquals(PRIMES_BELOW_50.get(i), lazyPrimes.get(i));
    }
}

В листинге 4 я создаю новый пустой объект ArrayList, помещаю его в "оболочку" с помощью метода decorate() класса LazyList и передаю туда же объект типа PrimeFactory для генерации новых значений. Класс LazyList будет использовать значения, которые уже имеются в списке, но когда метод get() обратится к позиции, где ещё нет значения, LazyList обратится к фабрике (в данном случае объекту типа PrimeFactory()), чтобы создать новое значение и поместить его в соответствующее место. Класс PrimeFactory представлен в листинге 5.

Листинг 5. Класс PrimeFactory, используемый LazyList

public class PrimeFactory implements Factory {
    private int index = 0;

    @Override
    public Object create() {
        return Prime.indexedPrime(index++);
    }
}

Все списки с отложенным вычислением нуждаются в каком-либо способе для вычисления последующего значения. В листинге 2 я использую сочетание метода next() из интерфейса Iterator и метода nextPrimeFrom() из класса Prime. В случае с LazyList для этой же цели я использую объект типа PrimeFactory, как показано в листинге 4.

Одной из особенностей реализации LazyList в библиотеке Commons является передача слишком малого количества информации в метод-фабрику при запросе нового значения. Изначально LazyList не передаёт даже индекса запрошенного элемента, перекладывая контроль за текущим состоянием на класс PrimeFactory. Это создаёт нежелательную зависимость от самого списка, так как он должен быть инициализирован пустым, чтобы его индексы синхронизировались с внутренним состоянием PrimeFactory. Реализация LazyList из библиотеки Commons может рассматриваться как простейшая, так как существуют лучшие open source реализации, например, Totally Lazy.

Totally Lazy

Totally Lazy – это инфраструктура, которая добавляет в Java превосходные возможности отложенного выполнения (см. раздел "Ресурсы"). В предыдущей статье я познакомил вас с Totally Lazy, но не продемонстрировал стандартного применения возможностей этой инфраструктуры. Одной из целей этой инфраструктуры является создание понятного Java-кода c помощью комбинирования статических import-конструкций. В листинге 6 представлен простой пример кода для определения простоты числа, который полностью раскрывает эту возможность Totally Lazy.

Листинг 6. Использование статических import-конструкций в Totally Lazy

import com.googlecode.totallylazy.Predicate;
import com.googlecode.totallylazy.Sequence;

import static com.googlecode.totallylazy.Predicates.is;
import static com.googlecode.totallylazy.numbers.Numbers.equalTo;
import static com.googlecode.totallylazy.numbers.Numbers.increment;
import static com.googlecode.totallylazy.numbers.Numbers.range;
import static com.googlecode.totallylazy.numbers.Numbers.remainder;
import static com.googlecode.totallylazy.numbers.Numbers.sum;
import static com.googlecode.totallylazy.numbers.Numbers.zero;
import static com.googlecode.totallylazy.predicates.WherePredicate.where;

public class Prime {
    public static Predicate<Number> isFactor(Number n) {
        return where(remainder(n), is(zero));
    }

    public static Sequence<Number> factors(Number n){
        return range(1, n).filter(isFactor(n));
    }

    public static Number sumFactors(Number n){
        return factors(n).reduce(sum);
    }

    public static boolean isPrime(Number n){
        return equalTo(increment(n), sumFactors(n));
    }
}

Код в листинге 6, приведённый после окончания статических import-конструкций, выглядит довольно нетипично для Java, хотя и вполне понятно для пользователя. Одной из основополагающих концепций Totally Lazy является лаконичный интерфейс Hamcrest для расширения тестов JUnit (Hamcrest testing extension fluent interface for JUnit) и использование некоторых классов Hamcrest (см. раздел "Ресурсы"). Метод isFactor() превращается в вызов метода where() с помощью комбинации метода remainder() из TotallyLazy и метода is() из Hamcrest. Аналогично метод factors() превращается в вызов метода filter() для объекта, возвращённого методом range(), и я использую уже знакомый метод reduce() для определения суммы. В конце метод isPrime() использует метод equalTo() из Hamcrest для определения, равна ли сумма делителей увеличенному числу.

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

Листинг 7. Версия на основе Totally Lazy программы для определения простоты числа с поддержкой оптимизирующего алгоритма

public class PrimeFast {
    public static Predicate<Number> isFactor(Number n) {
        return where(remainder(n), is(zero));
    }

    public static Sequence<Number> getFactors(final Number n){
        Sequence<Number> lowerRange = range(1, squareRoot(n)).filter(isFactor(n));
        return lowerRange.join(lowerRange.map(divide().apply(n)));
    }

    public static Sequence<Number> factors(final Number n) {
        return getFactors(n).memorise();
    }

    public static Number sumFactors(Number n){
        return factors(n).reduce(sum);
    }

    public static boolean isPrime(Number n){
        return equalTo(increment(n), sumFactors(n));
    }
}

В листинге 7 появляются два главных изменения. Во-первых, я улучшил метод getFactors(), чтобы он собирал делители, не превышающие квадратного корня из целевого числа, а затем генерировал симметричные им делители, превосходящие квадратный корень. В Totally Lazy даже такие операции, как divide() можно выразить в более лаконичном стиле интерфейса данной инфраструктуры. Второе изменение включает мемоизацию, которая автоматически кеширует вызовы функций с повторяющимися параметрами; я изменил метод sumFactors(), чтобы в нём использовался метод factors(), который является мемоизованной версией метода getFactors(). В TotallyLazy мемоизация является частью самой инфраструктуры, так что никакого дополнительного кода для этой оптимизации не требуется; однако автор инфраструктуры назвал соответствующий метод memorise() вместо более традиционного названия memoize() как в Groovy).

В соответствии со своим названием Totally Lazy старается использовать отложенное выполнение в максимально возможном количестве мест внутри инфраструктуры. На самом деле в TotallyLazy уже содержится метод-генератор primes(), в котором с помощью встроенных возможностей инфраструктуры уже реализована бесконечная последовательность простых чисел. Рассмотрим фрагменты класса Numbers, приведённые в листинге 8.

Листинг 8. Фрагмент реализации бесконечной последовательности простых чисел в Totally Lazy

public static Function1<Number, Number> nextPrime = new Function1<Number, Number>() {
       @Override
       public Number call(Number number) throws Exception {
       	      return nextPrime(number);
      }
};

public static Computation<Number> primes = computation(2, computation(3, nextPrime));

public static Sequence<Number> primes() {
       return primes;
}
 
public static LogicalPredicate<Number> prime = new LogicalPredicate<Number>() {
    public final boolean matches(final Number candidate) {
        return isPrime(candidate);
    }

};

public static Number nextPrime(Number number) {
    return iterate(add(2), number).filter(prime).second();
}

Метод nextPrime() создаёт новый объект типа Function1 (реализацию псевдофункции высшего порядка в Totally Lazy), который принимает на вход один параметр типа Number и возвращает объект этого же типа. В данном случае возвращается результат из метода nextPrime(). Переменная primes создаётся для хранения текущего состояния коллекции простых чисел; при этом в качестве стартового значения используется 2 (первое простое число), а следующие простые числа находятся путем вычисления. Это стандартный подход, применяемый в отложенных реализациях: хранить следующий элемент и метод для генерации последующих значений. Метод prime() выступает в качестве оболочки для ранее выполненных вычислений простых чисел.

Для проверки числа в методе nextPrime() в листинге 8 создаётся новый объект prime типа LogicalPredicate для инкапсуляции проверки простоты числа, а затем создаётся сам метод nextPrime, который использует лаконичный интерфейс Totally Lazy для определения следующего простого числа.

Инфраструктура Totally Lazy позволяет эффективно использовать статические import-конструкции для создания хорошо читаемого Java-кода. Многие программисты считают, что Java плохо подходит для создания внутренних доменно-ориентированных языков, но инфраструктура Totally Lazy опровергает это мнение. При этом она агрессивно использует отложенное выполнение, стараясь отложить выполнение практически каждой операции.

Заключение

В этой статье я исследовал возможности отложенного выполнения, сначала создав "Java-копию" коллекции с отложенным выполнением с помощью интерфейса Iteraror, а затем воспользовавшись простейшим классом LazyList из библиотеки Jakarta Commons Collections. В конце я реализовал пример кода с помощью инфраструктуры Totally Lazy, используя коллекции с отложенным выполнением как "внутри" алгоритма для определения простоты числа, так и "снаружи" для организации "бесконечной" коллекции простых чисел. Инфраструктура Totally Lazy также демонстрирует выразительность лаконичного стиля интерфейса, использующего статические import-конструкции для повышения читаемости кода.

В следующей статье я продолжу исследование отложенного выполнения на примерах для Groovy, Scala и Clojure.

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

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

Похожие темы

• Functional thinking: Laziness, Part 1: оригинал статьи (EN).
• Haskell - это один из мощных функциональных open-source языков программирования, появившийся в результате многолетних исследований.
• LazyList: страница, посвященная классу LazyList из библиотеки Jakarta Commons.
• State of the Lambda: Libraries Edition (EN): в этой статье Брайан Гетц (Brian Goetz) обсуждает преимущества отложенного выполнения для создания кода.
• Инфраструктура Totally Lazy предлагает множество функциональных расширений для Java, используя для этого интуитивно понятный DSL-подобный интерфейс.
• Библиотека Hamcrest предлагает богатый набор компонентов для сопоставления объектов (matcher objects, также известных как ограничения (constraints) или предикаты), которые позволяют декларативно определять правила для сопоставления объектов для последующего использования в других инфраструктурах. (В данный момент Hamcrest переносится на ported to GitHub.)
• Evolutionary architecture and emergent design: Fluent interfaces (Neal Ford, developerWorks, июль 2010) (EN): узнайте, как лаконичные интерфейсы устраняют лишний "шум" из синтаксиса кода, делая его более удобным для восприятия.
• Design Patterns: Elements of Reusable Object-Oriented Software (Erich Gamma et al., Addison-Wesley, 1994): подробную информацию о шаблоне Decorator можно найти в классической книге «банды четырех» по шаблонам проектирования.
• Scala: современный функциональный язык на основе JVM.
• Clojure: современная функциональная реализация Lisp, работающая поверх JVM.
• Execution in the Kingdom of Nouns (Steve Yegge, март 2006 г.) (EN): статья о различных аспектах дизайна языка Java.
• Раздел Java-технологий на портале developerWorks содержит сотни статей обо всех аспектах Java-программирования.