Функциональное мышление: Отложенное выполнение. Часть 2

Продолжаем изучение отложенного выполнения

Реализация отложенного выполнения упрощается в языках, поддерживающих замыкания. Эта статья из цикла "Функциональное мышление" показывает, как получить список с отложенным выполнением, используя Groovy-замыкания в качестве строительных блоков. Затем мы исследуем некоторые концептуальные преимущества отложенного выполнения, связанные с производительностью, включая возможность отложенной инициализации полей, присутствующую в некоторых языках.

19 декабря 2012 г. – автор дополнил информацию в первых двух абзацах, следующих за листингом 4.

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

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



02.09.2013

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

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

В предыдущей статье "Отложенное выполнение. Часть 1" я исследовал библиотеки для отложенного выполнения, присутствующие в Java™. В этой статье я покажу, как построить простой список с отложенным выполнением с помощью замыканий, а затем исследую некоторые преимущества отложенного выполнения с точки зрения производительности и отдельные особенности реализации подобного поведения в Groovy, Scala и Clojure.

Создание списка с отложенным выполнением

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

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

Пустой строгий список в Groovy представляется массивом с помощью пустых квадратных скобок: []. Если я помещу его в замыкание, то он превратится в пустой список с отложенным выполнением.

{-> [] }

Если мне потребуется добавить элемент a в список, я могу добавить его в начало списка, а затем снова превратить получившийся список в список с отложенным выполнением:

{-> [ a, {-> [] } ] }

Метод для добавления элемента в начало списка обычно называется prepend (присоединять спереди) или cons (соединять). Если требуется добавить несколько элементов, я повторю эту операцию для каждого нового элемента, таким образом, добавление трех элементов (a, b, c) будет выглядеть следующим образом.

{-> [a, {-> [b, {-> [ c, {-> [] } ] } ] } ] }

Хотя представленный синтаксис выглядит не очень изящно, но после понимания фундаментального принципа я смогу создать Groovy-класс, реализующий стандартный набор методов для коллекции с отложенным выполнением, как показано в листинге 1.

Листинг 1. Использование замыканий для создания Groovy-списка с отложенным выполнением
class PLazyList {
  private Closure list

  private PLazyList(list) {
    this.list = list
  }

  static PLazyList nil() {
    new PLazyList({-> []})
  }

  PLazyList cons(head) {
    new PLazyList({-> [head, list]})
  }

  def head() {
    def lst = list.call()
    lst ? lst[0] : null
  }

  def tail() {
    def lst = list.call()
    lst ? new PLazyList(lst.tail()[0]) : nil()
  }

  boolean isEmpty() {
    list.call() == []
  }

  def fold(n, acc, f) {
    n == 0 || isEmpty() ? acc : tail().fold(n - 1, f.call(acc, head()), f)
  }

  def foldAll(acc, f) {
    isEmpty() ? acc : tail().foldAll(f.call(acc, head()), f)
  }

  def take(n) {
    fold(n, []) {acc, item -> acc << item}
  }

  def takeAll() {
    foldAll([]) {acc, item -> acc << item}
  }

  def toList() {
    takeAll()
  }
}

Конструктор в листинге 1 объявлен частным (private) и автоматически вызывается для создания пустого списка, которое происходит при вызове статического метода nil() (подобное поведение описывается шаблоном проектирования Singleton). Метод cons() позволяет добавлять новые элементы, присоединяя переданный параметр в начало списка, а затем помещая получившийся список в блок замыкания.

Следующие три метода отвечают за обход списка. Метод head() возвращает первый элемент списка, а метод tail() возвращает подсписок, содержащий все элементы кроме первого. В обоих случаях я вызываю метод call() для блока замыкания, чтобы "форсировать" его исполнение в терминах отложенного выполнения. Так как моей целью является получение значений, то выполнение откладывается до фактического момента запроса значения. Метод isEmpty() проверяет, не осталось ли в списке невычисленных выражений.

Остальные методы представляют собой функции высшего порядка для выполнения манипуляций со списком. Методы fold() и foldAll() представляют абстракцию fold (свертывание), также известную как reduce (сведение) или как injectAll() в Groovy. Я демонстрировал использование подобных методов во многих предшествующих статьях (например, "Функциональное мышление. Часть 3"), но это первый раз, когда используется рекурсивное определение, написанное исключительно с помощью блоков замыканий. Метод foldAll() проверяет, пуст список или нет, и если он пуст, возвращает значение acc (аккумулятор — стартовое значение для операции свертывания). Если же в списке есть элементы, то рекурсивно вызывается метод foldAll() для оставшейся части списка (которая извлекается через вызов tail()), с передачей ему аккумулятора (параметр acc) и первого элемента списка (параметр head). Функция (параметр f) принимает на вход два значения и возвращает единственный результат — это и есть операция "свертывания", когда вы объединяете элемент с его ближайшим соседом.

В листинге 2 демонстрируется создание списка и выполнение операций над ним.

Листинг 2. Использование списков с отложенным выполнением
def lazylist = PLazyList.nil().cons(4).cons(3).cons(2).cons(1)
println(lazylist.takeAll()) //[1, 2, 3, 4]
println(lazylist.foldAll(0, {i, j -> i + j})) // 10
lazylist = PLazyList.nil().cons(1).cons(2).cons(4).cons(8)
println(lazylist.take(2))  //[8, 4]

В листинге 2 я создаю список, присоединяя значения к пустому списку с помощью метода cons(). Заметьте, что когда я вызываю метод takeAll(), он возвращает элементы в порядке, противоположном порядку их добавления в список. Напомню, что метод cons() является сокращением для метода prepend и поэтому добавляет элементы в начало списка. Метод foldAll() позволяет мне просуммировать все элементы списка, указав блок кода для необходимого преобразования {i, j -> i + j}, в котором в качестве "свертывающей" операции используется сложение. В конце я использую метод take(), чтобы форсировать вычисление только первых двух элементов.

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


Преимущества отложенного выполнения

Списки с отложенным выполнением обладают несколькими преимуществами. Во-первых, их можно использовать для создания бесконечных последовательностей. Поскольку значения не вычисляются до того момента, когда они действительно понадобятся, вы можете создавать бесконечные списки с помощью коллекций с отложенным выполнением. Я уже представлял пример подобной реализации для Groovy в статье "Функциональные возможности в Groovy. Часть 1". Вторым преимуществом является сокращение объема, необходимого для хранения данных. Если вместо хранения всей коллекции можно вычислять последующие значения, то я могу пожертвовать скоростью выполнения в пользу объема. Выбор коллекции с отложенным выполнением для использования в той или иной ситуации фактически является выбором между расходами на хранение значений и расходами, необходимыми для их вычисления.

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

Листинг 3. Поиск палиндромов в Groovy
def isPalindrome(s) {
  def sl = s.toLowerCase()
  sl == sl.reverse()
}

def findFirstPalindrome(s) {
  s.tokenize(' ').find {isPalindrome(it)}
}

s1 = "The quick brown fox jumped over anna the dog";
println(findFirstPalindrome(s1)) // anna

s2 = "Bob went to Harrah and gambled with Otto and Steve"
println(findFirstPalindrome(s2)) // Bob

Метод isPalindrome() в листинге 3 нормализует регистр переданного слова, а затем определяет, является оно палиндромом или нет (палиндром — слово или предложение, читаемое одинаково в обоих направлениях). Метод findFirstPalindrome() пытается найти первый палиндром, содержащийся в переданной строке, с помощью Groovy-метода find(), который принимает на вход блок кода, содержащий алгоритм для фильтрации значений.

Предположим, что у меня имеется большая последовательность символов, в которой мне необходимо найти первый палиндром. При исполнении метода findFirstPalindrome() код в листинге 3 сначала разделяет целую последовательность на фрагменты, создавая промежуточную структуру данных, а затем выполняет метод find(). Groovy-метод tokenize() не поддерживает отложенное выполнение, поэтому он может создать большую временную структуру данных, а впоследствии отбросить большую часть ее содержимого.

Рассмотрим тот же код в листинге 4, написанный на языке Clojure.

Листинг 4. Поиск палиндромов в Clojure
(defn palindrome? [s]
  (let [sl (.toLowerCase s)]
  (= sl (apply str (reverse sl)))))

(defn find-palindromes [s]
    (filter palindrome? (clojure.string/split s #" ")))

(println (find-palindromes "The brown fox jumped over anna."))
; (anna)
(println (find-palindromes "Bob went to Harrah and gambled with Otto"))
; (Bob Harrah Otto)
(println (take 1 (find-palindromes "Bob went to Harrah and gambled with Otto")))
; (Bob)

Хотя реализации, представленные в листингах 3 и 4, и совпадают, но в них используются различные языковые конструкции. В Clojure-функции palindrome я перевожу переданную строку в нижний регистр, а затем сравниваю ее с реверсированной строкой. Дополнительный вызов метода apply преобразует последовательность символов, возвращенную функцией reverse, обратно в объект типа String для последующего сравнения. Функция find-palindromes использует Clojure-функцию filter, принимающую на вход функцию, которая будет использоваться для фильтрации, и коллекцию объектов, которую нужно отфильтровать. Для вызова функции palindrome в Clojure доступны несколько альтернативных вариантов. Так, я могу создать анонимную функцию, чтобы вызывать ее как #(palindrome? %), что является сокращенной записью анонимной функции с единственным параметром; полная форма подобной записи приведена ниже:

    (fn [x]
      (palindrome? x))

При использовании единственного параметра Clojure позволяет мне не объявлять анонимную функцию и называть параметр, заменив его имя в вызове функции подстановочным символом %: #(palindrome? %). В листинге 4 я могу использовать еще более короткую форму для непосредственного наименования функции, так метод filter() получает на вход метод, принимающий единственный параметр и возвращающий boolean-значение, что можно записать как palindrome?.

При переходе от Groovy к Clojure изменяется не только синтаксис. В Clojure все операции со структурами данных, выполнение которых может быть отложено, действительно откладываются, включая такие действия как filter() (фильтрация) и split() (разбиение). Таким образом, в Clojure-версии все операции автоматически откладываются на более поздний период, что видно по второму примеру в листинге 4, где я вызываю метод find-palindromes для коллекции из нескольких элементов. Метод filter() для подобной коллекции вызывается только в тот момент, когда я хочу распечатать результат выполнения. Если мне требуется только результат обработки только первого элемента коллекции, то я должен указать необходимое количество обращений к списку.

В языке Scala отложенное выполнение реализовано немного по другому. Вместо того чтобы по умолчанию откладывать все операции, Scala предлагает для коллекций специальные представления с отложенным выполнением (lazy view). В листинге 5 приведено Scala-решение для задачи c палиндромом.

Листинг 5. Реализация палиндрома в Scala
def isPalindrome(x: String) = x == x.reverse
def findPalidrome(s: Seq[String]) = s find isPalindrome

findPalindrome(words take 1000000)

В листинге 5 извлечение одного миллиона значений из коллекции words с помощью метода take вышло бы крайне затратным, особенно если нам необходимо найти только первый палиндром. Чтобы преобразовать эту коллекцию в коллекцию с отложенным выполнением, я воспользуюсь методом view:

findPalindrome(words.view take 1000000)

Метод view допускает отложенный обход коллекции, что позволяет писать более эффективный код.


Отложенная инициализация полей

Прежде чем закончить с темой отложенного выполнения, я бы хотел упомянуть два языка, обладающих отличной возможностью, которая позволяет отложить сложные операции по инициализации полей. В Scala, применив ключевое слово lazy к декларации val, вы можете поменять тип инициализации поля с "немедленного" (eager) на "по необходимости" (as-needed).

lazy val x = timeConsumingAndOrSizableComputation()

Фактически это сокращенный вариант записи для полного кода, приведенного в листинге 6.

Листинг 6. Сокращенный синтаксис для записи полей с отложенным выполнением в Scala
var _x = None
def x = if (_x.isDefined) _x.get else {
  _x = Some(timeConsumingAndOrSizableComputation())
  _x.get
}

В Groovy подобная возможность доступна благодаря дополнительной возможности языка, известной как трансформации абстрактного синтаксического дерева (Abstract Syntax Tree (AST) Transformations). Подобная возможность позволяет вам взаимодействовать с компилятором в процессе генерации нижележащего абстрактного синтаксического дерева, допуская внесение изменений пользователем на самых нижних уровнях языка. Одной из подобных предопределенных трансформаций является атрибут @Lazy, использование которого демонстрируется в листинге 7.

Листинг 7. Отложенная инициализация полей в Groovy
class Person {
    @Lazy pets = ['Cat', 'Dog', 'Bird']
}

def p = new Person()
assert !(p.dump().contains('Cat'))

assert p.pets.size() == 3
assert p.dump().contains('Cat')

В листинге 7 объект p типа Person не имеет значения Cat в коллекции pets до того момента, как будет выполнено первое обращение к этой структуре данных. Groovy также позволяет использовать блок кода с замыканием для инициализации структуры данных.

class Person {
    @Lazy List pets = { /* complex computation here */ }()
}

Также можно сказать Groovy, чтобы он использовал для размещения полей с отложенной инициализацией "слабые" ссылки (soft references - Java-версия указателя, который может быть автоматически освобожден "сборщиком мусора" при необходимости очистки памяти).

class Person {
    @Lazy(soft = true) List pets = ['Cat', 'Dog', 'Bird']
}

Заключение

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

Ресурсы

  • Functional thinking: Laziness, Part 2: оригинал статьи (EN).
  • Lazy lists in Groovy (EN): статья в блоге Андрея Парамонова, посвященная созданию списков с отложенным выполнением с помощью замыканий.
  • Scala: современный функциональный язык на основе JVM.
  • Clojure: современная функциональная реализация Lisp, работающая поверх JVM.
  • Инфраструктура Totally Lazy предлагает множество функциональных расширений для Java, используя для этого интуитивно понятный DSL-подобный интерфейс.
  • Functional Java: инфраструктура, добавляющая в язык Java многие конструкции из арсенала функциональных языков.
  • The busy developer's guide to Scala (EN): в этой серии статей, опубликованной на портале developerWorks, можно узнать больше о языке Scala.
  • Посетите магазин книг, посвященных ИТ-технологиям и различным аспектам программирования.
  • Раздел Java-технологий на портале developerWorks содержит сотни статей обо всех аспектах Java-программирования.

Комментарии

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=943238
ArticleTitle=Функциональное мышление: Отложенное выполнение. Часть 2
publish-date=09022013