Функциональное мышление
Часть 1. Шаблоны проектирования для функционального программирования
Использование шаблонов проектирования в функциональном программировании
Серия контента:
Этот контент является частью # из серии # статей: Функциональное мышление
Этот контент является частью серии:Функциональное мышление
Следите за выходом новых статей этой серии.
Некоторые сторонники функционального программирования заявляют, что идея шаблонов проектирования ошибочна, и функциональное программирование в них не нуждается. Такую точку зрения можно обосновать, исходя из узкого понимания слова "шаблон" но это спор скорее о терминах, чем о практическом применении. Концепция "шаблона проектирования" - именованного и каталогизированного решения для стандартной проблемы - по-прежнему актуальна. Однако шаблоны проектирования в различных парадигмах программирования могут принимать различный вид. Поскольку в функциональном программировании применяются другие строительные блоки и подходы, некоторые из традиционных шаблонов "банды четырех" (см. раздел "Ресурсы") утрачивают актуальность, в то время как другие по-прежнему решают проблемы, но совершенно иными способами. В этой и последующей статьях исследуются несколько традиционных шаблонов проектирования и выполняется их «переосмысление» в функциональном стиле.
В мире функционального программирования стандартные шаблоны проектирования проявляются одним из трех способов.
- шаблон проектирования поглощается языком;
- шаблон проектирования существует и в функциональной парадигме, но детали реализации меняются.
- решение реализуется с помощью возможностей, которые отсутствуют в других языках или парадигмах. Например, многие решения, основанные на метапрограммировании, выглядят лаконично и элегантно, но в языке 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, сравнив реализацию, основанную на классах, с версией, основанной на мемоизации. В-третьих, функциональные языки и среды исполнения могут обладать абсолютно иными возможностями, которые позволяют им решать проблемы своими уникальными способами.
В следующей статье я продолжу исследование точек пересечения между шаблонами проектирования и функциональным программированием и приведу примеры использования третьего подхода.
Ресурсы для скачивания
Похожие темы
- 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 для поддержки глобального состояния в объектно-ориентированных языках.