Функциональное программирование: абстракции по-другому

Инкапсуляция, полиморфизм и наследование уже настолько сильно въелись в наше сознание, что часто мы не задумываемся, а существуют ли другие способы управления сложностью программных систем. В самом деле, можно ли без ООП разрабатывать крупные проекты? Давайте разберемся, что предлагают инструменты функционального программирования (ФП) для решения тех задач, ради которых изобретали ООП.

Начнем с простого утверждения: все, что может ООП, может и ФП, и наоборот. Обратимся к истории [1]. В 1936 году Алан Тьюринг в своей научной статье "On Computable Numbers" описывает абстрактный императивный компьютер, ставший прототипом сегодняшних компьютеров. Позже, после изобретения первых ЭВМ, стали появляться языки программирования, довольно сильно приближенные к устройству компьютера и, таким образом, реализующие императивную модель вычислений. Однако ранее в том же году Алонцо Черч публикует свою работу "An Unsolvable Problem of Elementary Number Theory", где представляет формальную систему лямбда-исчисления - базу всех функциональных языков программирования. Вскоре оказалось, что эти два подхода математически тождественны, и теперь они известны под названием тезиса Черча-Тьюринга.

Конечно, с развитием технологий оба эти подхода стали сложнее и богаче, и теперь общее между ними найти еще труднее. Но мы попробуем.

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

Во-первых, в Clojure, как и во всех диалектах Lisp-а, используется префиксная нотация. В ней 2 + 2 записывается так: (+ 2 2). Скобки означают создание списка; первый элемент списка - функция, остальные элементы - аргументы этой функции. Т.е. общий вид такой: (function arg1 arg2 argN). Это так называемое символьное выражение (S-выражение) или "форма".

Во-вторых, в Clojure хоть и нет переменных, зато можно объявить символ, который навсегда будет привязан к какому-то значению. Делается это так: (def a 5) - эта форма создаст символ а и привяжет его к значению 5. Ни символ, ни его значение впоследствии изменить уже будет нельзя.

В-третьих, в Clojure можно объявлять функции. Например, так: (defn my-func [arg1 arg2] (body)). Здесь my-func - имя функции, в квадратных скобках перечислены ее аргументы, а вместо body необходимо подставить любую форму Clojure.

И в-последних, анонимные функции объявляются так: (fn [arg1 arg2] (body)). Здесь fn создает анонимную функцию, аргументы которой перечислены в квадратных скобках. Body - тело функции. Сокращенная запись создания анонимной функции: #(body). Если у функции есть несколько аргументов, то они доступны через символы %1, %2 и т.д. Если аргумент только один, то он доступен через символ %.

Вот и все, приступим.

Моделирование сущностей реального мира

Сущности бывают статические (предметы) и динамические (процессы). Для моделирования статических объектов ООП подходит как нельзя лучше. У каждого объекта есть состояние (данные) и методы изменения его состояния. Поскольку все правила изменения состояния инкапсулированы внутри объекта, то никакая другая сущность не может привести этот объект в ошибочное состояние.

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

В [2] приводится цитата Алана Перлиса, американского ученого, известного своими пионерскими разработками в языках программирования: "Лучше иметь 100 функций, оперирующих одной структурой данных, чем 10 функций, оперирующих десятью структурами". А еще лучше инкапсулировать все необходимые данные прямо в функции таким образом, чтобы ее результат зависел только от некоторого небольшого числа параметров, и не зависел ни от каких других данных.

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

Предположим, что язык, на котором мы программируем, настолько прост, что не имеет практически никаких привычных инструментов. Все данные, которыми он оперирует, имеют ссылочный тип. Множество его операций составляет объявление символов, объявление и вызов процедур, как именованных, так и анонимных (в виде замыканий), оператор условного перехода и... все. А нам бы хотелось иметь хотя бы функцию list для создания списка из двух элементов, функции first для получения первого элемента списка и rest - для получения оставшихся элементов. Этих операций (list, first, rest) нам хватило бы для того, чтобы создавать полноценные списки из любого количества элементов, индексированного доступа к ним и т. д.

Функция list должна иметь следующий синтаксис: (list arg1 arg2), возвращать она должна список из этих двух элементов. Т. е., чтобы построить список из трех элементов, можно будет выполнить операцию (list arg1 (list arg2 arg3)). Таким образом, первым элементом списка станет arg1, а вторым - новый список из двух элементов arg2 и arg3. Чтобы получить, например, второй элемент этого списка, нужно будет выполнить операции: (first (rest my-list)), где my-list - символ, указывающий на созданный ранее список из элементов arg1, arg2 и arg3. Функция (rest my-list) вернет все элементы списка, кроме первого (т. е. то, что сконструировано операцией (list arg2 arg3)), а функция (first (list arg2 arg3)) вернет arg2.

Как все это реализовать?

Реализуем list как функцию, возвращающую замыкание (замыкание - функция вместе с контекстом, в котором она была определена). Каждый раз, когда будет вызвана list, автоматически будет создаваться новое замыкание. Его можно будет сохранить, привязав к какому-нибудь символу.

(defn list [x y]  (fn [m]   (if (= m 0)     x     y)  ) )

Первая строка определяет функцию list, которая принимает два параметра - x и y. Вторая строка создает замыкание, функцию, принимающую параметр m. Эта функция замкнута в своем контексте, т.е. параметры x и y будут сохранять переданные им значения до конца жизни самого замыкания. Оператор if на следующей строке проверит параметр m и вернет x, если m равен нулю, и y в остальных случаях. Создадим два списка.

(def a (list 5 7)) (def b (list 10 11))

Символ a здесь будет содержать замыкание, в котором x и y равны 5 и 7, а символ b - замыкание, где x и y равны 10 и 11. Поскольку замыкание - это функция, то ее можно вызвать. Таким образом, (a 0) вернет 5, (а 1) - 7, (b 0) - 10, (b 1) - 11 независимо от порядка их вызова. Легко заметить, что функции first и rest определяются так:

(def first [my-list] (my-list 0)) (def rest [my-list] (my-list 1))

Этот пример показывает, что сложные структуры данных можно реализовать при помощи одних лишь функций и замыканий, что и составляет основу функционального подхода. Вообще, разобранная задача слишком примитивна, чтобы показать всю мощь идеи использования функций в замкнутом контексте. Используя эту технологию, можно построить объекты, по свойствам не отличимые от тех же, что есть в ООП. Хороший пример на эту тему можно увидеть в [4], где, используя лишь средства функционального языка Scheme, в главе 22 строится оконный интерфейс пользователя.

Уровни абстракции

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

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

Рассмотрим, например, функцию математического ожидания. В [5] формула матожидания для выборки с одинаковыми вероятностями определена так:

где x - элемент выборки, p - его вероятность, а N - размер выборки. Реализация на Clojure выглядит так:

(defn mx [my-list] (/ (reduce + my-list) (count my-list)))

Здесь определена функция mx, которая принимает список my-list в качестве аргумента. Форма (reduce + my-list) применяет функцию "+" к каждому элементу списка и накапливает результат - т.е. суммирует все элементы списка. Форма (count my-list) подсчитывает количество элементов списка. Результатом функции mx будет сумма всех элементов my-list, деленная на их количество.

Рассмотрим теперь формулу дисперсии [5]:

где m_x - среднее значение выборки.

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

(defn meta-mx [my-list my-fn]  (/ (reduce + (map my-fn my-list)) (count my-list)))

Обратите внимание, отличие meta-mx от mx состоит лишь в том, что суммируются не элементы списка my-list, а элементы списка, который получается после применения функции my-fn к каждому элементу my-list.

Тогда функция mx определяется через meta-mx, например, так:

(defn mx [my-list] (meta-mx my-list #(+ % 0)))

Здесь в функцию meta-mx, кроме списка my-list, передается анонимная функция #(+ % 0), которая для каждого элемента списка в meta-mx вернет этот самый элемент.

Функция variance (дисперсия) определяется так:

(defn variance [my-list my-mx] (meta-mx my-list #(* (- % my-mx) (- % my-mx) ) ))

В нее необходимо передать список my-list и значение его матожидания my-mx. Анонимная функция #(* (- % my-mx) (- % my-mx)) соответствует упоминавшейся выше формуле (x_i-m_x)².

Таким образом, у нас получилась простая иерархия функций. Функция meta-mx соответствует абстрактному классу, необходимому только для извлечения общей функциональности. Функции mx и variance являются чем-то вроде дочерних классов, более конкретизированными версиями meta-mx.

Выводы

Функциональное программирование, так же, как и ООП, содержит различные инструменты управления сложностью программ. Они включают в себя функции высшего порядка, замыкания, ленивые вычисления, неизменяемые данные и др. Некоторые из них мы рассмотрели в этой статье и увидели, что они, в общем, тоже достаточно эффективны. Отличия ФП от ООП, в основном, в том, что функциональная парадигма больше сфокусирована на моделировании динамических сущностей, процессов, а объектно-ориентированная проще моделирует статические объекты. Тем не менее, как первая, так и вторая парадигма позволяют решать почти любые программные задачи. Одно из возможных применений ФП в промышленном программировании - это реализация доменных правил и логики, как, например, предложено в [6]. Решив задачу наиболее подходящим для нее инструментом, удастся сэкономить массу сил и времени.

Литература

1. L. VanderHart, S. Sierra, "Practical Clojure", Apress, 2010.
2. www.clojure.org.
3. Х. Абельсон, Д.Сассман, "Структура и интерпретация компьютерных программ", Добросвет, 2006.
4. M. Felleisen, R. Findler, M. Flatt, S. Krishnamurthi, "How to Design Programs", The MIT Press, pp. 273-278.
5. Е.С. Вентцель, Л.А. Овчаров, "Теория вероятностей и ее инженерные приложения", второе изд., "Высшая школа", Москва, 2000.
6. K. Henney, "97 Things Every Programmer Should Know", O'Reilly, 2010, pp. 4-5.

Дмитрий БУШЕНКО,
d.bushenko@gmail.com