Функциональное мышление: Часть 1. Функциональные возможности Groovy

Исследование возможностей Groovy

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

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

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



30.07.2012

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

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

Признаюсь, мне никогда не хотелось вернуться к языкам программирования, в которых отсутствует автоматическая "уборка мусора". Я долгие годы проработал с языком C++ и ему подобными, и не собираюсь отказываться от удобств, предлагаемых современными языками. В этом и заключается история прогресса в области разработки ПО. Мы создаем уровни абстракции, чтобы обрабатывать (и скрывать) низкоуровневые подробности реализации. По мере роста вычислительной мощности компьютеров мы перекладываем все больше задач на языки программирования и среды исполнения. Всего десять лет назад разработчики избегали интерпретируемых языков, так как они считались слишком «медленными» для промышленных приложений, а сейчас использование подобных языков стало стандартной практикой. Многие возможности функциональных языков десять лет назад работали крайне медленно, но сегодня их использование имеет смысл, так как они оптимизируют время и усилия, затрачиваемые разработчиками.

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

Функциональные списки в Groovy

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

Альтернативный взгляд на списки

Если ваша основная работа связана с языком программирования С или ему подобными (включая Java), то, вы, скорее всего, представляете списки в виде индексированных коллекций. Подобная точка зрения упрощает итерирование по коллекции, даже если для этого индекс явно и не используется, как показано в Groovy-коде в листинге 1.

Листинг 1. Просмотр списка со скрытым использованием индексов
def perfectNumbers = [6, 28, 496, 8128]

def iterateList(listOfNums) {
  listOfNums.each { n ->
    println "${n}"
  }
}

iterateList(perfectNumbers)

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

Рисунок 1. Список как набор упорядоченных ячеек
Рисунок 1. Список как набор упорядоченных ячеек

В большинстве функциональных языков списки рассматриваются иначе, и, к счастью, Groovy также разделяет эту точку зрения. Вместо того чтобы рассматривать список как набор упорядоченных ячеек, представим его как комбинацию первого элемента списка ("начало" – head) и остальной части списка ("остаток" – tail), как показано на рисунке 2.

Рисунок 2. Список, состоящий из "начала" и "остальной части"
Рисунок 2. Список, состоящий из начала и остальной части

Если посмотреть на список с такого угла, то можно организовать итерирование по нему с помощью рекурсии, как показано в листинге 2.

Листинг 2. Просмотр списка с помощью рекурсии
def recurseList(listOfNums) {
  if (listOfNums.size == 0) return;
    println "${listOfNums.head()}"
    recurseList(listOfNums.tail())
}

recurseList(perfectNumbers)

В методе recurseList() в листинге 2 я сначала проверяю, что список, переданный в качестве параметра, не является пустым. Если список пустой (в нем нет элементов), то работа закончена и можно выполнить возврат. Если же в списке содержатся значения, то сначала я вывожу первый элемент списка (с помощью Groovy-метода head()), а затем рекурсивно вызываю метод recurseList() для оставшейся части списка.

У рекурсии существуют определенные технические ограничения, встроенные в платформу (см. раздел "Ресурсы"), так что подобное решение помогает не во всех ситуациях. Но оно вполне подходит для списков с небольшим числом элементов. Меня больше интересует влияние такого подхода, на структуру кода, в ожидании того момента, когда эти ограничения ослабеют или исчезнут вообще. С учетом этих недостатков преимущества рекурсивного подхода в первом приближении могут показаться неочевидными. Чтобы опровергнуть это представление, рассмотрим проблему фильтрации списка. В листинге 3 приведен пример фильтрующего метода, который принимает на вход список и предикат (булевское условие), определяющей принадлежность элемента к списку.

Листинг 3. Императивная фильтрация в Groovy
def filter(list, p) {
  def new_list = []
  list.each { i -> 
    if (p(i))
      new_list << i
  }
  new_list
}

modBy2 = { n -> n % 2 == 0}

l = filter(1..20, modBy2)

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

В листинге 4 приведена рекурсивная реализация метода filter() из листинга 3.

Листинг 4. Рекурсивная фильтрация в Groovy
def filter(list, p) {
  if (list.size() == 0) return list
  if (p(list.head()))
    [] + list.head() + filter(list.tail(), p)
  else 
    filter(list.tail(), p)
}

l = filter(1..20, {n-> n % 2 == 0})

В методе filter() в листинге 4 сначала проверяется размер переданного списка, и если он пустой, то выполняется выход из метода. Затем я проверяю первый элемент списка на соответствие фильтрующему предикату, и если он соответствует условию, я добавляю его в список с результатами (этот список изначально пуст, чтобы гарантировать, что будут возвращаться только подходящие значения). После этого я рекурсивно вызываю метод filter(), передавая в качестве параметра остальную часть списка.

Разница между кодом из листингов 3 и 4 заключается в ответе на вопрос: «кто отвечает за сохранение состояния?» В императивной версии это обязанность ложится на меня. Я должен создать новую переменную new_list и добавлять в неё элементы, а затем вернуть после завершения метода. В рекурсивной версии язык программирования берет на себя обработку возвращаемого значения, строя его на основе стека по мере возвращения значений из рекурсивно вызванных методов. Отметим, что при выходе из метода filter() в листинге 4 вызывается команда return, которая используется для создания промежуточного значения на основе стека.

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

Изменив свою точку зрения относительно списков, мы сможем по-новому взглянуть и на такие аспекты, как размер списка и его область видимости.

Списки с отложенной загрузкой элементов в Groovy

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

В листинге 5 приведен пример использования «ленивого» списка в Groovy, а затем мы посмотрим, как он реализуется.

Листинг 5. Использование "ленивого" списка в Groovy
def prepend(val, closure) { new LazyList(val, closure) }

def integers(n) { prepend(n, { integers(n + 1) }) }

@Test
public void lazy_list_acts_like_a_list() {
  def naturalNumbers = integers(1)
  assertEquals('1 2 3 4 5 6 7 8 9 10', 
      naturalNumbers.getHead(10).join(' '))
  def evenNumbers = naturalNumbers.filter { it % 2 == 0 }
  assertEquals('2 4 6 8 10 12 14 16 18 20', 
      evenNumbers.getHead(10).join(' '))
}

Первый метод prepend() в листинге 5 создает новый объект типа LazyList, позволяя добавлять в него значения. Следующий метод integers() возвращает список с целыми числами, созданный с помощью метода prepend(). В метод prepend() передаются два параметра: исходное состояние списка и блок кода, использующийся для генерации следующего значения. Метод integers() действует как "фабрика", создающая "ленивый" список, содержащий целые числа, используя первое значение в списке для вычисления последующих значений.

Для извлечения значений из списка я вызываю метод getHead(), который возвращает указанное число значений с начала списка. В листинге 5 переменная naturalNumbers – это "бесконечная" последовательность всех целых чисел. Чтобы получить некоторые из них, я вызываю метод getHead() и указываю, сколько элементов необходимо вернуть. Как видно из проверки, мне возвращается список из первых десяти натуральных чисел (от 1 до 10). С помощью метода filter() я получаю "бесконечный" список, содержащий только четные числа, и использую метод getHead(), чтобы получить первые десять четных чисел.

В листинге 6 приведен исходный код класса LazyList.

Листинг 6. Реализация класса LazyList
class LazyList {
  private head, tail

  LazyList(head, tail) {
    this.head = head;
    this.tail = tail
  }

  def LazyList getTail() { tail ? tail() : null }

  def List getHead(n) {
    def valuesFromHead = [];
    def current = this
    n.times {
      valuesFromHead << current.head
      current = current.tail
    }
    valuesFromHead
  }

  def LazyList filter(Closure p) {
    if (p(head))
      p.owner.prepend(head, { getTail().filter(p) })
    else
      getTail().filter(p)
  }
}

Данный список содержит атрибуты head ("начало") и tail ("остаток"), устанавливаемые в конструкторе. Метод getTail() проверяет, что значение атрибута tail() не равно null, и, если это так, выполняет код, содержащийся в данном атрибуте. Метод getHead() по одному собирает элементы, которые необходимо вернуть, извлекая существующий элемент из "начала" списка (атрибут head) и заставляя "остаток" (атрибут tail) сгенерировать следующее значение. Вызов n.times {} повторяет эту операцию столько раз, сколько было запрошено элементов, и в конце метод getHead() возвращает собранные значения.

В методе filter() в листинге 5 используется такой же рекурсивный подход, как и в листинге 4, но в данном случае он реализован в виде составной части списка, а не самостоятельной функции.

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

Список с отложенным созданием элементов, содержащий совершенные числа

Если вы читали предыдущие статьи из этой серии, то наверняка помните мой любимый пример — программу для поиска совершенных чисел (см. статью "Функциональное мышление. Часть 1"). Одним из недостатков всех представленных ранее версий этой программы была необходимость явного указания числа, тип которого нужно было определить. Теперь я хочу создать список, который будет создавать и возвращать совершенные числа по мере необходимости. Для этого я написал компактную программу в функциональном стиле для поиска совершенных чисел с поддержкой списков с отложенным созданием элементов, исходный код которой приведен в листинге 7.

Листинг 7. Упрощенная версия классификатора чисел, содержащая метод nextPerfectNumberFrom
class NumberClassifier {
  static def factorsOf(number) {
      (1..number).findAll { i -> number % i == 0 }
  }

  static def isPerfect(number) {
      factorsOf(number).inject(0, {i, j -> i + j}) == 2 * number
  }

  static def nextPerfectNumberFrom(n) {
    while (! isPerfect(++n)) ;
    n
  }
}

Если код в методах factorsOf() и isPerfect() кажется вам непонятным, вы можете найти пояснения по этим методам в предыдущей статье. Новый метод nextPerfectNumber() использует метод isPerfect() для поиска следующего совершенного числа, которое должно быть больше значения, переданного в качестве параметра. На выполнение этого метода уйдет много времени даже для маленьких значений (особенно если учесть, что код не оптимизирован), так как совершенных чисел существует не так уж и много.

Используя эту новую версию классификатора чисел, я могу создать "ленивый" список совершенных чисел, как показано в листинге 8.

Листинг 8. Список совершенных чисел с отложенным созданием элементов
def perfectNumbers(n) { 
  prepend(n, 
    { perfectNumbers(nextPerfectNumberFrom(n)) }) };

@Test
public void infinite_perfect_number_sequence() {
  def perfectNumbers = perfectNumbers(nextPerfectNumberFrom(1))
  assertEquals([6, 28, 496], perfectNumbers.getHead(3))
}

С помощью метода prepend(), объявленного в листинге 5, я создаю список совершенных чисел, используя исходное значение в качестве "начала" и блок кода с функциональностью для вычисления следующего совершенного числа в качестве "остатка". Я инициализирую список первым совершенным числом после единицы (метод NumberClassifier.nextPerfectNumberFrom() можно легко вызвать напрямую благодаря конструкции static import). В конце я вызываю метод getHead(), чтобы получить три первых совершенных числа.

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

Если ваше представление о списке основано на "пронумерованных ячейках", думать о бесконечных последовательностях сложно. Если же рассматривать список как "первый элемент" и "остальные элементы списка", вы сможете уделять больше внимания элементам списка, а не его структуре, что в свою очередь поможет освоить концепцию "ленивого" списка.


Заключение

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

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

Ресурсы

Научиться

  • Functional thinking: Functional features in Groovy, Part 1: оригинал статьи (EN).
  • The Productive Programmer (Neal Ford, O'Reilly Media, 2008): новая книга Нила Форда, в которой более подробно рассматриваются некоторые вопросы из данной серии статей.
  • An Excursion in Java Recursion: статья об ограничениях рекурсии, существующих в языке программирования Java.
  • Find limit of recursion (EN): статья о том, как определить максимально возможную глубину рекурсии для вашей платформы с помощью тестов с Web-сайта RosettaCode.
  • Apache Commons LazyList: в библиотеке Apache Commons уже имеется реализация списка с отложенным созданием элементов.
  • Посетите магазин книг, посвященных ИТ-технологиям и различным аспектам программирования.

Получить продукты и технологии

Комментарии

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=828180
ArticleTitle=Функциональное мышление: Часть 1. Функциональные возможности Groovy
publish-date=07302012