Java.next: Мемоизация и функциональный синергизм

Базовые функциональные возможности, а также их реализация и сочетание в языках Java.next

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

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

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



31.03.2014

Об этом цикле статей

Java-технология оставит в наследство не язык, а платформу. На платформе JVM работают более 200 языков программирования; какой-то из них со временем неминуемо вытеснит язык Java в качестве наилучшего способа программирования для JVM. Этот цикл статей посвящен исследованию трех языков нового поколения для платформы JVM — Groovy, Scala и Clojure — а также сравнению и противопоставлению новых возможностей и парадигм, чтобы дать Java-разработчикам возможность заглянуть в свое ближайшее будущее.

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

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

Мемоизация

Термин мемоизация (memoization) был предложен Дональдом Мичи (Donald Michie), исследователем искусственного интеллекта из Великобритании, для обозначения кэширования повторяющихся значений на уровне функций. Сегодня мемоизация широко применяется в языках функционального программирования как встроенная или относительно простая в реализации возможность.

Мемоизация полезна в следующем сценарии. Предположим, что у вас имеется функция с интенсивным потреблением вычислительных ресурсов, которую вы должны вызывать неоднократно. Обычное решение состоит в создании внутреннего кэша. Каждый раз, когда вы вычисляете значение для определенного набора параметров, вы помещаете это значение в кэш, используя в качестве ключей значения соответствующих параметров. Если в будущем эта функция будет вызвана с ранее встречавшимися значениями параметров, вы извлечете результирующее значение из кэша, а не будете вычислять его повторно. Кэширование на уровне функций — это классический компьютерный компромисс: мы увеличиваем потребление памяти (которая нередко имеется в изобилии) ради достижения более высокой производительности с течением времени.

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

Мемоизация в Groovy

Дополнительные сведения о мемоизации

Я описал механизм мемоизации в языке Groovy, включая сравнение производительности, в статье Функциональное мышление: Часть 3. Функциональные возможности Groovy моего цикла Функциональное мышление. Кроме того, в указанной статье демонстрируется более детализированный синтаксис мемоизации для всех трех языков Java.next.

Мемоизация в Groovy реализуется достаточно тривиально — посредством включения семейства функций memoize() в класс Closure. В качестве примера предположим, что у нас есть "дорогой" алгоритм хеширования, что вынуждает нас кэшировать его результаты с целью повышения эффективности. Это можно сделать посредством использования синтаксиса блока замыкания для определения метода и применения функции memoize() к возвращаемому результату(см. листинг 1). (Я вовсе не имел в виду, что используемый в листинге 1 алгоритм ROT13— (разновидность шифра Цезаря) имеет низкую производительность, поэтому притворитесь, что применение кэширования в этом примере является вполне оправданным).

Листинг 1. Мемоизация в Groovy
class NameHash {
  def static hash = {name ->
    name.collect{rot13(it)}.join()
  }.memoize()

  public static char rot13(s) {
    char c = s
    switch (c) {
      case 'A'..'M':
      case 'a'..'m': return c + 13

      case 'N'..'Z':
      case 'n'..'z': return c - 13
      default: return c
    }
  }
}

class NameHashTest extends GroovyTestCase {
  void testHash() {
    assertEquals("ubzre", NameHash.hash.call("homer"))  }
}

Обычно определения функций в Groovy похожи на определения функции rot13() в листинге 1, когда тело метода следует после списка параметров. В определении функции hash() используется несколько иной синтаксис, когда фрагмент кода присваивается переменной hash. Последняя часть определения — это вызов метода memoize(), который автоматически создает внутренний кэш для повторяющихся значений, связанных с параметром.

Метод memoize() фактически является семейством методов, что обеспечивает вам определенный контроль над характеристиками кэширования(таблица 1).

Таблица 1. Семейство методов memoize() в языке Groovy
МетодИспользование
memoize()Возвращает экземпляр замыкания с кэшированием
memoizeAtMost()Устанавливает верхнюю границу по количеству кэшируемых элементов
memoizeAtLeast(int protectedCacheSize)Устанавливает нижнюю границу по количеству кэшируемых элементов, что обеспечивает защиту определенного количества элементов от действия механизма сборки мусора
memoizeBetween(int protectedCacheSize, int maxCacheSizeУстанавливает нижнюю и верхнюю границы по количеству кэшируемых элементов

Представленные в таблице 1 методы обеспечивают "крупнозернистый" контроль над характеристиками кэширования — но не предоставляют "мелкозернистых" способов для непосредственной настройки характеристик кэша. Мемоизация предназначена для использования в качестве механизма общего назначения, который упрощает оптимизацию кэширования в распространенных случаях.

Мемоизация в Clojure

В Clojure мемоизация является встроенной. С помощью встроенной функции (memoize ) можно мемоизировать любую функцию. Например, если у вас есть существующая функция (hash "homer"), вы можете мемоизировать ее (memoize (hash "homer")) в кэшируемую версию. В листинге 2 реализуется пример хеширования в Clojure, соответствующий показанному в листинге 1 примеру для Groovy.

Листинг 2. Мемоизация в Clojure
(defn name-hash [name]
  (apply str (map #(rot13 %) (split name #"\d"))))

(def name-hash-m (memoize name-hash))

(testing "name hash"
  (is (= "ubzre" (name-hash "homer"))))

(testing "memoized name hash"
  (is (= "ubzre" (name-hash-m "homer")))))

Обратите внимание, что в листинге 1 для вызова мемоизированной функции требуется вызов метода call(). В Clojure-версии вызов мемоизированного метода внешне выглядит точно так же, как и обычный (пользователь метода не видит добавившейся "косвенности" и кэширования).

Мемоизация в Scala

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

Листинг 3. Мемоизация в Scala
def memoize[A, B](f: A => B) = new (A => B) {
    val cache = scala.collection.mutable.Map[A, B]()
    def apply(x: A): B = cache.getOrElseUpdate(x, f(x))
  }

def nameHash = memoize(hash)

Функция getOrElseUpdate() в листинге 3 отлично подходит для построения кэша. Она извлекает совпадающее значение или создает новую запись, если такое значение не существует.


Объединение функциональных возможностей

Объединение посредством составления

Термин составление (Composition) имеет множество значений применительно к разработке программного обеспечения. Функциональное составление относится к возможности объединения функций с целью получения комбинированных результатов. С математической точки зрения, если имеются функция f(x) и g(x), то должна существовать и функция f(g(x)). С точки зрения программного обеспечения, если у вас есть функция a() которая преобразует строки в верхний регистр, и функция b(), которая удаляет избыточные пробелы, то составная функция будут выполнять обе эти задачи.

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

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

Рассмотрим следующий пример. В листинге 4 показан метод indexOfAny() из проекта Apache Commons (который предоставляет множество вспомогательных средств для программирования на Java).

Листинг 4. Метод indexOfAny() из проекта Apache Commons
// From Apache Commons Lang, http://commons.apache.org/lang/
public static int indexOfAny(String str, char[] searchChars) {
    if (isEmpty(str) || ArrayUtils.isEmpty(searchChars)) { 
        return INDEX_NOT_FOUND;
    }
    int csLen = str.length();
    int csLast = csLen - 1;
    int searchLen = searchChars.length;
    int searchLast = searchLen - 1;
    for (int i = 0; i < csLen; i++) {
        char ch = str.charAt(i);
        for (int j = 0; j < searchLen; j++) { 
            if (searchChars[j] == ch) {
                if (i < csLast && j < searchLast && CharUtils.isHighSurrogate(ch)) {
                    if (searchChars[j + 1] == str.charAt(i + 1)) {
                        return i;
                    }
                 } else {
                     return i;
                 }

             }
         }
     }
     return INDEX_NOT_FOUND;
}

Первая треть кода в листинге 4 проверяет граничные случаи и инициализирует переменные, необходимые для последующего вложенного итерирования. Я буду постепенно переводить этот код на язык Clojure. На первом шаге я удаляю случаи выхода за граничные условия (см. листинг 5).

Листинг 5. Удаление случаев выхода за граничные условия
public static int indexOfAny(String str, char[] searchChars) {
    when(searchChars) {
        int csLen = str.length();
        int csLast = csLen - 1;
        int searchLen = searchChars.length;
        int searchLast = searchLen - 1;
        for (int i = 0; i < csLen; i++) {
            char ch = str.charAt(i);
            for (int j = 0; j < searchLen; j++) {
                if (searchChars[j] == ch) {
                    if (i < csLast && j < searchLast && CharUtils.isHighSurrogate(ch)) {
                        if (searchChars[j + 1] == str.charAt(i + 1)) {
                            return i;
                        }
		    } else {
		        return i;
		    }
		}
            }
        }
        return INDEX_NOT_FOUND;
    }
}

Язык Clojure интеллектуально обрабатывает ситуации null и empty, а также имеет такие интеллектуальные функции, как функция (when ...), которая возвращает значение true только в случае присутствия символов. Clojure — это язык с динамической (но строгой) типизацией, что избавляет от необходимости объявления типов переменных перед их использованием. Таким образом, я могу удалить объявления типов и получить код, показанный в листинге 6.

Листинг 6. Удаление объявлений типов
indexOfAny(str, searchChars) {
    when(searchChars) {
        csLen = str.length();
    csLast = csLen - 1;
    searchLen = searchChars.length;
    searchLast = searchLen - 1;
    for (i = 0; i < csLen; i++) {
          ch = str.charAt(i);
        for (j = 0; j < searchLen; j++) {
          if (searchChars[j] == ch) {      
          if (i < csLast && j < searchLast && CharUtils.isHighSurrogate(ch)) {
            if (searchChars[j + 1] == str.charAt(i + 1)) {
            return i;
          }
          } else {
            return i;
          }
        }
        }
    }
    return INDEX_NOT_FOUND;
    }
}

Цикл for— важнейший элемент императивных языков — поочередно предоставляет доступ к каждому элементу. Функциональные языки больше тяготеют к collection-методам, которые уже понимают граничные случаи (или избегают их), поэтому я могу безболезненно удалить такие методы, как метод isHighSurrogate() (который проверяет кодировки символов), и манипуляции с указателями индекса. Результат этого преобразования показан в листинге 7.

Листинг 7. Замена самого глубокого внутреннего цикла for на when-выражение
// when clause for innermost for
indexOfAny(str, searchChars) {
    when(searchChars) {
        csLen = str.length();                    
        for (i = 0; i < csLen; i++) {            
            ch = str.charAt(i);
            when (searchChars(ch)) i;
        }
    }
}

В листинге 7 я сворачиваю код в метод, который осуществляет проверку на наличие искомых символов и возвращает индекс, если эти символы найдены. Показанный в листинге 7 код — это не Java и не Clojure, а некий псевдокод, поэтому вышеупомянутый метод when на самом деле еще не существует. Однако Clojure-метод (when ), в который этот код постепенно превращается, является вполне реальным.

Теперь я заменяю самый внешний цикл for более лаконичным конструктом, используя for comprehension: это макрос, сочетающий функциональность доступа и фильтрации (помимо прочего) для коллекций. Полученный в результате код показан в листинге 8.

Листинг 8. Добавление for-comprehension
// add comprehension
indexOfAny(str, searchChars) {
    when(searchChars) {
        for ([i, ch] in indexed(str)) {    
            when (searchChars(ch)) i;
        }
    }
}

Для понимания for comprehension в листинге 8 необходимо сначала понять несколько других моментов. Функция (indexed ...) в Clojure принимает Sequence и возвращает последовательность, которая включает в себя пронумерованные элементы. Например, если я вызываю (indexed '(a b c)), то возвращенный результат будет выглядеть как ([0 a] [1 b] [2 c]). (одиночный апостроф указывает Clojure, что мне нужна литеральная последовательность символов, а вовсе не на то, что я хотел бы выполнить метод (a ) с двумя параметрами). Механизм for comprehension создает эту последовательность на основе моих искомых символов, а затем применяет внутреннее when-выражение с целью отыскания индекса соответствующих символов.

Последний шаг в описываемой трансформации состоит в преобразовании кода в соответствии с надлежащим синтаксисом Clojure и в восстановлении реальных функций и реального синтаксиса(см. листинг 9).

Листинг 9. Clojure-фикация кода
// Clojure-ify
(defn index-filter [pred coll]           
  (when pred                     
    (for [[index element] (indexed coll) :when (pred element)] index)))

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

Еще одной целью Clojure является достижение выразительности при минимальном количестве символов; в этом отношении Java по сравнению с Clojure – это просто ужас. В таблице 2 сравнивается количество "движущихся частей" в листинге 4 и в листинге 9.

Таблица 2. Сравнение количества "движущихся частей"
Императивный подходФункциональный подход
Функции11
Классы10
Внутренние точки выхода20
Переменные30
Ветвления40
Булевы операторы10
Вызовы функций63
Всего184

Различие по степени сложности действительно впечатляет. При этом, хотя код на Clojure проще, он одновременно более универсален. В следующем примере я индексирую последовательность подбрасываний монеты, смоделированных с помощью ключевых слов Clojure :h (лицевая сторона монеты, аверс) и :t (обратная сторона монеты, реверс).

(index-filter #{:h} [:t :t :h :t :h :t :t :t :h :h]) 
-> (2 4 8 9)

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

Моя функция (index-filter ) является универсальной, поэтому я могу использовать ее с числами. Например, я могу определить наименьший порядковый номер, для которого число Фибоначчи превышает 1000.

Отложенное выполнение

Отложенное выполнение— откладывание вычисления выражения на максимально поздний момент — еще один хороший пример расширения возможностей в функциональных языках ценой минимальных дополнительных усилий со стороны разработчика или вообще без таковых. В статьях Функциональное мышление: Отложенное выполнение. Часть 1. Исследование отложенного выполнения в Java и Функциональное мышление: Отложенное выполнение. Часть 2. Продолжаем изучение отложенного выполнения описывается отложенное выполнение в языках Java.next и приводятся соответствующие примеры.

(first 
  (index-filter #(> % 1000) (fibo)))
-> 17

Функция (fibo) возвращает бесконечную, но с отложенным выполнением, последовательность чисел Фибоначчи; функция (index-filter ) находит первый элемент, для которого число Фибоначчи превышает 1000 (оказывается, что для элемента под номером 18 число Фибоначчи составляет 1597.) Сочетание функциональных конструктов, динамической типизации, отложенного выполнения и компактного синтаксиса обеспечивает весьма мощные возможности.


Заключение

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

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

Ресурсы

Научиться

  • Оригинал статьи: Java.next: Memoization and functional synergy.
  • ROT13: ROT13 — это пример т. н. шифра Цезаря, изобретенного в античности алгоритма шифрования, которым пользовался Юлий Цезарь.
  • Apache Commons: популярный пакет вспомогательных ресурсов для экосистемы Java.
  • Groovy: динамическая разновидность Java с обновленным синтаксисом и расширенными возможностями.
  • Scala: современный функциональный язык, работающий на платформе JVM.
  • Clojure: современный функциональный вариант Lisp, работающий на платформе JVM.
  • Функциональное мышление: : колонка Нила Форда на developerWorks, посвященная функциональному программированию.
  • Execution in the Kingdom of Nouns Стив Йегг (Steve Yegge), март 2006 г. Статья в развлекательном стиле, описывающая некоторые аспекты проектирования на языке Java.
  • Записная книжка дизайнера языка: : в этом цикле статей developerWorks архитектор языка Java Брайан Гетц исследует некоторые проблемы дизайна языка, вызвавшие трудности при эволюции языка Java версий Java SE 7, Java SE 8 и далее.
  • Раздел developerWorks, посвященный Java-технологии: сотни статей по всем аспектам программирования на Java.

Обсудить

  • Присоединяйтесь к сообществу Get involved in the developerWorks community. Связывайтесь с другими пользователями developerWorks и знакомьтесь с ориентированными на разработчиков форумами, блогами, группами и вики-ресурсами.

Комментарии

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=967299
ArticleTitle=Java.next: Мемоизация и функциональный синергизм
publish-date=03312014