Функциональное мышление: Функциональные шаблоны проектирования, часть 1

в 6:39, , рубрики: functional programming, groovy, jvm, Программирование, метки: , ,

Нил Форд, Архитектор ПО, ThoughWorks Inc.
06 Марта 2012
перевод статьи Functional thinking: Functional design patterns, Part 1

Некоторые представители функционального мира утверждают, что концепция шаблонов проектирования содержит недостатки и ей нет места в мире функционального программирования(далее ФП). Это мнение может быть подтвержено используя довольно узкое определение слова шаблон(pattern), но это больше касается семантики, чем реально использования.
Концепция шаблона проектирования — именованное, представленное в виде каталога решение для распространенной проблемы- живо и здравствует.Тем ни менее, шаблоны могут принимать различные обличья, в рамках разных парадигм. Учитывая, что подходы к построению программ и решению проблем в функциональном программировании другие, некоторые шаблоны «Банды четырех»(Gang of Four, GoF) исчезают, другие сохраняют проблему, но решают ее радикально по-другому.Эта часть и несколько других будет содержать в себе исследования некоторых традиционных шаблонов проектирования и переосмыслять их в рамках функционального подхода.

В мире ФП традиционные шаблоны проектирования, обычно проявляются одним из 3х способов:

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

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

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

Карринг это возможность присущая многим языкам программирования. Названа в честь математика Хаскелла Карри(в его честь также назван функциональный язык программирования Haskell), карринг позволяет преобразовывать многоаргументую функцию таким образом, что она может быть вызвана как цепочка функций с одним аргументом. Близкая по смыслу техника частичного применения (partial application), техника позволяющая назначить фиксированное значение одному или больше аргументам функции, тем самым производя функцию с меньшей арностью (arity)(Арность — это количество аргументов функции, прим.перев: например бинарную функцию в унарную). Обе техники обсуждались в предыдущей части «Thinking functionally, Part 3.»(на хабре: Functional thinking: Thinking functionally, Part 3)

В контексте шаблонов проектирования, карринг ведет себя как фабрика для функций. Функции первого класса или высшего порядка (first-class or higher-order) распространенная возможность для функциональных языков, позволяющая функции вести себя будто она структура данных.Благодаря этому я могу создавать и возращать функции базирующиеся на определенном критерии, чем по сути и занимается фабрика. Например, если у вас есть общая функция, которая занимается сложением двух чисел, вы можете использовать карринг как фабрику для того, чтобы создать функцию, которая всегда добавляет один из своих параметров — инкремент, реализация на Groovy. показана в Листинге 1:

Листинг 1. Карринг как фабрика функций

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

println "increment 7: ${incrementer(7)}" // prints "increment 7: 8"

В Листинге 1, я каррирую первый параметр как 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() рекурсивно фильтрует список целочисленных значений (integers) c помощью параметра p. p — это функция-предикат (predicate function) — распространенный термин в мире ФП для функции типа Boolean.Метод filter() проверяет или список не пуст и если да, то просто возвращается; в противном случае, он проверяет, первый элемент в списке (xs.head) с помощью предиката для того, чтобы увидеть
должен ли он быть включен в список отфильтрованных. Если он проходит предикат, то возвращаемое значение будет состоять из «головы» вначале и «хвоста» в виде отфильтрованного списка оставшихся значений. Если первый элемент не проходит проверку предиката, возвращаемое значение состоит исключительно из отфильтрованной оставшейся части списка.

Что интересно, в Листинге 2, с точки зрения шаблонов проектирования, так это «типичное» использование каррирования в методе dividesBy().Заметьте, что dividesBy() принимает 2 параметра, а возвращает true или false, исходя из того делится ли второй параметр на первый нацело. Тем ни менее, когда этот метод вызывается как часть вызова метода filter(), он вызывается только с одним параметром — результатом которого является каррированная функция, которая затем используется в качестве предиката в методе filter().

Этот пример иллюстрирует первое из трех возможных проявлений шаблонов в ФП, исходя из спика приведенного вначале.Во-первых карринг встроен либо в язык, либо в среду исполнения (runtime). Таким образом концепция фабрики функций является органичной и не требует дополнительных структур. Во-вторых, он иллюстрирует мое мнение по поводу разных реализаций. Использование карринга, как в Листинге 2, наверное никогда не приходило в голову типичному Java программисту; мы никогда не имели переносимого кода и никогда не думали о построении конкретных функций из более общих.На самом деле, вероятно что императивные разработчики даже не будут задумываться о применении тут шаблона, т.к создание специфичного dividesBy() метода из обощенного кажется ничтожной проблемой, в то время как шаблоны проектирования — полагаясь в основном на структуры для решения проблем, и, следовательно, требует много ресурсов для реализации- кажутся решением для больших проблем. Использование карринга, как было задумано не оправдывает формальность специального названия, тем более что оно уже есть


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

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

Шаблон проектирования «Шаблонный метод» (Template Method)

Функции высшего порядка значительно упрощают реализацию шаблона «Шаблонный метод», поскольку они устраняют излишние структуры. «Шаблонный метод» определяет скелет алгоритма в методе, передавая некоторые шаги подклассам и заставляя их определять эти шаги не изменяя структуры алгоритма. Типичная реализация данного шаблона в Листинге 3, на Groovy, с помощью блоков кода (code blocks).

Листинг 3: «Стандартная» реализация шаблонного метода

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: Реализация «Шаблонного метода» с помощью функций высшего порядка

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, шаги алгоритма являются просто свойствами класса, назначаемые как любое другое свойство.Это пример, в котором возможности языка полностью поглощают детали реализации. Все так же полезно говорить о шаблоне как о решении (делегируя шаги последующим обработчикам) решении проблемы. но реализация намного проще.

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

Отличная поддержка блоков кода делает язык дружелюбным для разработчика.Например, я мог бы создать другую версию класса Customer, который принимает любое количество параметров для обработки. Рассмотрим случай, когда вы хотите дать возможность подклассам пропустить некоторые шаги.В Groovy есть специальный оператор защищенного доступа (?.), который удостоверяется, что объект не равен null, до того как выполнить какой-то его метод. Рассмотрим определение метода process() в Листинге 5:

Листинг 5: Добавление защиты вызова блока кода

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

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

Шаблон проектирования «Стратегия» (Strategy)

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

Традиционная реализация шаблона «Стратегия», для вычисления произведения чисел, представлена в Листинге 6:

Листинг 6: Использование шаблона «Стратегия» для произведения чисел.

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, я определяю интерфейс для произведения двух чисел.Я реализую интерфейс с двумя конкретными классами (стратегиями): первая непосредственное произведение, вторая через сложение. Для тестирования этих стратегий, я создал тест кейс, представленный в Листинге 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. Так же как и в примере «Шаблонного метода», я обмениваю формальность на удобство. Традиционный подход вынуждает описывать имя и структуру в рамках каждой стратегии, что иногда желаемо. Тем ни менее, отмечу что у меня была возможность добавить строгие защитные меры в код в Листинге 8, где я не могу легко обходить ограничения наложенные более традиционным подходом — который больше аргумент вида «динамический-против-статического» чем «ФП-против-шаблонов».

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


Шаблон проектирования «Приспособленец» (Flyweight) и мемоизация

Шаблон проектирования Flyweight это техника оптимизации, которая использует совместное использование(sharing) для поддержки большого количества мелкозернистых ссылок на объекты. Вы поддерживаете пул доступных объектов, создаете ссылки втнури пула для определенных представлений (view). 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 связывает пользователя с компьютером.

Распространенный способ улучшения данного кода представляет собой комбинацию шаблонов Фабрика и Приспособленец. Рассмотрим фабрику-синглетон для генерации канонических типов компьютера, представим в Листинге 10:

Листинг 10: Фабрика-синглетон для flyweight экземпляров компьютера

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() метода. Это традиционная фабрика-синглетон если б вы писали ее на Java.

Тем ни менее, синглетон это тоже шаблон проектирования, и он служит в качестве другого примера шаблона поглощенного во время выполнения (runtime).Рассмотрим упрощенную ComputerFactory, используя @Singleton аннотацию из Groovy, в листинге 11:

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

@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]
  }
}

Для того, чтоб протестировать действительно ли фабрика возвращает канонические экземпляры класса, я написал юнит-тест, показанный в листинге 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)
}

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

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

Листинг 13. Мемоизация «приспособленцев» (Memoization of flyweigths)

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

def computerOfType = computerOf.memoize()

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

В Листинге 14 показан юнит тест сравнивающий вызов двумя различными подходами

Листинг 14: Сравнение подходов

@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
} 

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


Заключение

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


В слудующей части, я продолжу рассмотрение шаблонов проектирования и разберу третий вариант работы шаблонов в ФП.

Автор: Sigrlami

Поделиться

* - обязательные к заполнению поля