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

Часть 1. Шаблоны проектирования для функционального программирования

Использование шаблонов проектирования в функциональном программировании

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

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

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

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

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

Фабрики и карринг

Карринг (currying) присутствует в списке возможностей многих функциональных языков. Этот прием, названный в честь математика Хаскелла Карри (Haskell Curry) (в честь которого также был назван язык программирования Haskell) преобразует функцию, принимающую на вход несколько аргументов, так, что она может вызываться как последовательность функций с единственным аргументом. Частичное применение (partial application) – это прием, родственный каррингу, при котором одному или нескольким аргументам функции присваиваются фиксированные значения, так что получается новая функция меньшей арности (арность функции определяется количеством передаваемых ей параметров). Я рассматривал оба подхода в статье "Функциональное мышление. Часть 3".

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

Листинг 1. Использование карринга в качестве «фабрики» функций

def adder = { x, y -> return x + y }
def incrementer = adder.curry(1)

println "инкрементировать 7: ${incrementer(7)}" 
// в результате запуска будет напечатано "инкрементировать 7: 8"

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

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

Листинг 2. Стандартный сценарий использования карринга в Scala

object CurryTest extends Application {

  def filter(xs: List[Int], p: Int => Boolean): List[Int] =
    if (xs.isEmpty) xs
    else if (p(xs.head)) xs.head :: filter(xs.tail, p)
    else filter(xs.tail, p)

  def dividesBy(n: Int)(x: Int) = ((x % n) == 0)

  val nums = List(1, 2, 3, 4, 5, 6, 7, 8)
  println(filter(nums, dividesBy(2)))
  println(filter(nums, dividesBy(3)))
}

Код в листинге 2 демонстрирует пример из документации Scala, в котором одновременно используются рекурсия и карринг (см. раздел "Ресурсы"). В методе filter() рекурсивно фильтруется список целых чисел с помощью параметра p. p – это функция-предикат, стандартный термин из области функционального программирования для определения булевской функции. Метод filter() проверяет, есть ли в списке элементы, и если он пуст, просто происходит возврат. В противном случае с помощью предиката проверяется первый элемент списка (xs.head) и определяется, нужно ли включать его в "отфильтрованный" список или нет. Если элемент соответствует предикату, возвращается новый список с проверенным головным элементом в начале и отфильтрованной частью в качестве остатка. Если же первый элемент не соответствует условию предиката, то возвращается только отфильтрованная часть списка.

С точки зрения шаблонов проектирования особый интерес в листинге 2 представляет "встроенное" использование карринга в методе dividesBy(). Этот метод принимает на вход два параметра и возвращает true или false в зависимости от того, является ли второй параметр делителем первого или нет. Однако, когда метод dividesBy() вызывается в ходе вызова метода filter(), ему передается только один параметр, в результате чего получается карринг-функция, которая затем используется в качестве предиката в методе filter().

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

Функции первого класса и шаблоны проектирования

Наличие функций первого класса значительно упрощает многие употребительные шаблоны проектирования. Шаблон Command (команда) вообще становится ненужным, так как для хранения переносимой функциональности больше не требуется объект-оболочка.

Шаблон Template Method

Функции первого класса упрощают реализацию шаблона Template Method (шаблонный метод — см. раздел "Ресурсы"), так как позволяют отказаться от потенциально ненужной структуры. Шаблон Template Method определяет "скелет" алгоритма в методе, перенося отдельные этапы алгоритма в подклассы и заставляя их определять эти этапы, при этом не изменяя структуру алгоритма. Реализация Template Method на языке Groovy приведена в листинге 3.

Листинг 3. "Стандартная" реализация шаблона Template Method

abstract class Customer {
  def plan
    
  def Customer() {
    plan = []
  }
    
  def abstract checkCredit()
  def abstract checkInventory()
  def abstract ship()
    
  def process() {
    checkCredit()
    checkInventory()
    ship()
  }
}

В листинге 3 метод process() основывается на методах checkCredit(), checkInventory() и ship(), определения которых должны быть представлены подклассами, так как они являются абстрактными.

Поскольку функции первого класса могут действовать так же, как и любые другие структуры данных, я могу переопределить пример из листинга 3, используя блоки кода, как показано в листинге 4.

Листинг 4. Реализация шаблона Template Method на основе функций первого класса

class CustomerBlocks {
  def plan, checkCredit, checkInventory, ship
    
  def CustomerBlocks() {
    plan = []
  }
    
  def process() {
    checkCredit()
    checkInventory()
    ship()
  }
}

class UsCustomerBlocks extends CustomerBlocks{
  def UsCustomerBlocks() {
    checkCredit = { plan.add "checking US customer credit" }
    checkInventory = { plan.add "checking US warehouses" }
    ship = { plan.add "Shipping to US address" }
  }
}

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

Эти два решения не эквивалентны. В традиционной реализации Template Method в листинге 3 абстрактный класс требует от подклассов реализовывать зависимые методы. Конечно, подкласс может просто создать метод с пустым телом, но определение абстрактного метода формирует документацию определенного рода, которая напоминает программистам, что именно нужно учитывать при наследовании классов. С другой стороны, «строгое» объявление методов может не подойти для ситуаций, когда требуется большая гибкость. Например, я бы мог создать версию класса Customer, которая принимает на вход список с любым количеством методов для последующей обработки.

Полноценная поддержка таких возможностей, как блоки кода, делает язык более дружественным к программисту. Рассмотрим случай, когда мы хотим позволить классам-наследникам пропустить некоторые из этапов. В Groovy для этого имеется специальный оператор для безопасного доступа (?.), который проверяет, что объект не равен null, перед тем как вызвать его метод. Рассмотрим определение метода process() в листинге 5.

Листинг 5. Обеспечение безопасности при вызове блока кода

def process() {
  checkCredit?.call()
  checkInventory?.call()        
  ship?.call()
}

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

Strategy

Другим популярным шаблоном проектирования, который также можно упростить с помощью функций первого класса, является Strategy (стратегия). Этот шаблон определяет семейство алгоритмов, инкапсулируя каждый из них и делая их взаимозаменяемыми. Это позволяет изменять алгоритмы независимо от использующих их клиентов. Функции первого класса позволяют легко создавать стратегии и манипулировать ими.

Традиционная реализация шаблона Strategy для подсчета произведения чисел приведена в листинге 6.

Листинг 6. Использование шаблона Strategy для вычисления произведения двух чисел

interface Calc {
  def product(n, m)
}

class CalcMult implements Calc {
  def product(n, m) { n * m }
}

class CalcAdds implements Calc {

  def product(n, m) {
    def result = 0
    n.times {
      result += m
    }
    result
  }
}

В листинге 6 я определяю интерфейс с методом product() для вычисления произведения двух чисел. Я реализую этот интерфейс в двух конкретных классах (стратегиях): в первом используется умножение, а во втором сложение. Для проверки этих стратегий я создаю тестовый сценарий, приведенный в листинге 7.

Листинг 7. Тестирование стратегий для вычисления произведений

class StrategyTest {
  def listOfStrategies = [new CalcMult(), new CalcAdds()]

  @Test
  public void product_verifier() {
    listOfStrategies.each { s ->
      assertEquals(10, s.product(5, 2))
    }
  }
}

Как и ожидалось в листинге 7, обе стратегии возвращают одно и тоже значение. Используя блоки кода как функции первого класса, я могу очистить предыдущий пример от большинства формальностей. Рассмотрим пример со стратегиями для возведения в степень, представленный в листинге 8.

Листинг 8. Менее формальное тестирование стратегий для возведения в степень

@Test
public void exp_verifier() {
  def listOfExp = [
      {i, j -> Math.pow(i, j)},
      {i, j ->
        def result = i
        (j-1).times { result *= i }
        result
      }]

  listOfExp.each { e ->
    assertEquals(32, e(2, 5))
    assertEquals(100, e(10, 2))
    assertEquals(1000, e(10, 3))
  }
}

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

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

Flyweight и мемоизация

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

Рассмотрим приведенные в листинге 9 классы, моделирующие различные типы компьютеров.

Листинг 9. Простые классы, моделирующие типы компьютеров.

class Computer {
  def type
  def cpu
  def memory
  def hardDrive
  def cd
}

class Desktop extends Computer {
  def driveBays
  def fanWattage
  def videoCard
}

class Laptop extends Computer {
  def usbPorts
  def dockingBay
}

class AssignedComputer {
  def computerType
  def userId

  public AssignedComputer(computerType, userId) {
    this.computerType = computerType
    this.userId = userId
  }
}

Судя по этим классам, было бы неэффективно создавать новый объект типа Computer для каждого пользователя, так как все компьютеры имеют одинаковую спецификацию. Класс AssignedComputer связывает компьютер с пользователем.

Стандартный способ повысить эффективность этого кода — это объединить в нем шаблоны Factory и Flyweight. Рассмотрит singleton-фабрику для создания канонических объектов типа Computer, приведенную в листинге 10.

Листинг 10. Singleton-фабрика для создания flyweight-объектов типа Computer

class ComputerFactory {
  def types = [:]
  static def instance;
  
  private ComputerFactory() {
    def laptop = new Laptop()
    def tower = new Desktop()
    types.put("MacBookPro6_2", laptop)
    types.put("SunTower",  tower)
  }

  static def getInstance() {
    if (instance == null)
      instance = new ComputerFactory()
    instance
  }

  def ofType(computer) {
    types[computer]
  }  
}

Класс ComputerFactory создает кэш с компьютерами различных типов, а затем возвращает необходимый объект при помощи своего метода ofType(). Это стандартная singleton-фабрика, какие обычно создаются в Java.

Однако Singleton – это тоже шаблон проектирования (см. раздел "Ресурсы"), и он служит другим хорошим примером шаблона, "поглощенного" средой исполнения. Рассмотрим версию класса ComputerFactory, упрощенную с помощью аннотации @Singleton, предоставляемой Groovy.

Листинг 11. Упрощенная singleton-фабрика

@Singleton class ComputerFactory {
  def types = [:]
  
  private ComputerFactory() {
    def laptop = new Laptop()
    def tower = new Desktop()
    types.put("MacBookPro6_2", laptop)
    types.put("SunTower",  tower)
  }

  def ofType(computer) {
    types[computer]
  }
}

Чтобы проверить, что фабрика возвращает канонические объекты, я написал unit-тест, приведенный в листинге 12.

Листинг 12. Тестирование канонических типов

@Test
public void flyweight_computers() {
  def bob = new AssignedComputer(ComputerFactory.instance.ofType("MacBookPro6_2"), "Bob")
  def steve = new AssignedComputer(ComputerFactory.instance.ofType("MacBookPro6_2"), 
  "Steve") assertTrue(bob.computerType == steve.computerType)
}

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

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

Листинг 13. Мемоизация flyweight-значений

def computerOf = {type ->
  def of = [MacBookPro6_2: new Laptop(), SunTower: new Desktop()]
  return of[type]
}

def computerOfType = computerOf.memoize()

В листинге 13 канонические типы компьютеров объявляются в методе computerOf(). Для создания мемоизированной версии этой функции я просто вызываю метод memoize(), определенный в среде исполнения Groovy.

В листинге 14 приведен unit-тест, сравнивающий работу обоих подходов.

Листинг 14. Сравнение подходов к реализации flyweight-объектов

@Test
public void flyweight_computers() {
  def bob = new AssignedComputer(ComputerFactory.instance.ofType("MacBookPro6_2"), "Bob")
  def steve = new AssignedComputer(ComputerFactory.instance.ofType("MacBookPro6_2"), 
  "Steve") assertTrue bob.computerType == steve.computerType

  def sally = new AssignedComputer(computerOfType("MacBookPro6_2"), "Sally")
  def betty = new AssignedComputer(computerOfType("MacBookPro6_2"), "Betty")
  assertTrue sally.computerType == betty.computerType
}

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

Заключение

В этой статье я представил три варианта того, как семантика шаблонов проектирования может проявляться в функциональном программировании. Во-первых, они могут быть "поглощены" языком или средой исполнения. Я показал подобные решения для шаблонов Factory, Strategy, Singleton и Template Method. Во-вторых, шаблоны могут сохранить свою семантику, но получить совершенно другую реализацию; я продемонстрировал этот подход на примере шаблона Flyweight, сравнив реализацию, основанную на классах, с версией, основанной на мемоизации. В-третьих, функциональные языки и среды исполнения могут обладать абсолютно иными возможностями, которые позволяют им решать проблемы своими уникальными способами.

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

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

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

Похожие темы

• Functional thinking: Functional design patterns, Part 1: оригинал статьи (EN).
• The Productive Programmer (Neal Ford, O'Reilly Media, 2008): новая книга Нила Форда, в которой более подробно рассматриваются некоторые вопросы из данной серии статей.
• Design Patterns: Elements of Reusable Object-Oriented Software (Erich Gamma et al., Addison-Wesley, 1994): классическая книга четырех авторов ("банды четырех") по шаблонам проектирования.
• Design Patterns in Dynamic Languages: презентация Питера Норвига (Peter Norvig) объясняет, почему языки программирования с богатыми возможностями (например, функциональные) не так сильно нуждаются в шаблонах проектирования.
• Scala: современный функциональный язык программирования, работающий поверх JVM.
• The busy Java developer's guide to Scala: серия статей Теда Ньюарда (Ted Neward) на портале developerWorks, знакомящая с языком программирования Scala.
• Template method pattern: известный шаблон проектирования из каталога книги Design Patterns.
• Singleton pattern: известный шаблон проектирования из каталога книги Design Patterns для поддержки глобального состояния в объектно-ориентированных языках.