Функциональное мышление
Отложенное выполнение. Часть 1
Исследование отложенного выполнения в Java
Серия контента:
Этот контент является частью # из серии # статей: Функциональное мышление
Этот контент является частью серии:Функциональное мышление
Следите за выходом новых статей этой серии.
Отложенное выполнение присутствует во многих функциональных языках программирования. Его смысл - отложить вычисление выражений настолько, насколько это возможно. "Отложенные" коллекции предоставляют свои элементы по мере необходимости, а не вычисляют их заранее, что обеспечивает некоторые преимущества. Во-первых, так можно отложить сложные вычисления до того момента, когда они действительно понадобятся. Во-вторых, можно создавать "бесконечные" коллекции, которые будут постоянно возвращать новые элементы при обращении к ним. В-третьих, "отложенное" использование таких функциональных возможностей, как отображение (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.
Ресурсы для скачивания
Похожие темы
- 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-программирования.