В предыдущей статье "ООП, ФП, параллелизм и смена парадигмы" ("КВ" №30) я рассказал о функциональной парадигме программирования. ФП вновь в фаворе в связи с растущим интересом к параллельной реализации алгоритмов. Учитывая, что существующие инструменты мейнстрима предоставляют слишком сложные и низкоуровневые инструменты разработки параллельного ПО, сегодня многие ищут другие инструменты с лучшей поддержкой параллелизма. Одним из таких инструментов является функциональный язык Clojure - современный диалект Lisp'а, реализованный на JVM и предоставляющий удобную и высокоуровневую поддержку многопоточного программирования.
Функциональное программирование - старая, давно известная парадигма. Сегодня она пока не слишком популярна, ведь основное место в умах программистов занимает ООП. Кроме того, она настолько не похожа на парадигмы мейнстрима, что не все способны воспринять ее в принципе. Если вы знакомы только с языками вроде Pascal, C#, Python и им подобным, но не имели дела с диалектами Lisp, языками Haskell, Erlang, F# или Ocaml, то вскоре вы почувствуете легкий шок. Функциональная парадигма вообще ортогональна ООП и практически не имеет с ней ничего общего.
Прежде, чем мы рассмотрим несколько примеров на Clojure, я бы хотел напомнить основные свойства всех функциональных языков [1]. Во-первых, прозрачность по ссылкам. Этот термин означает неизменяемость данных и, таким образом, отсутствие переменных. Да, вначале может показаться странным, что в языке программирования все данные могут быть только неизменяемыми. Но давайте вспомним хотя бы класс String в Java. Все строки в Java тоже неизменяемые, и, тем не менее, никто не жалуется.
Во-вторых, декларативность. Программы, написанные в декларативном стиле, говорят о том, что нужно сделать, а компилятор решает - как. Программист может даже и не знать, как именно будет выполняться то, что он предлагает сделать, не вникать в низкоуровневые детали реализации. Это также может вначале показаться странным. Но когда вы описываете HTML-страницу, вы ведь тоже не знаете, как именно браузер ее отображает, какие элементы и в какой последовательности выполняет?
Не могу не процитировать классический учебник программирования [2]: "... компьютерный язык - это не просто способ заставить компьютер производить вычисления, а новое формальное средство выражения методологических идей. Таким образом, программы должны писаться для того, чтобы их читали люди, и лишь во вторую очередь - для выполнения машиной". То есть то, что программу можно выполнить на компьютере - вообще не обязательное свойство языка программирования, а лишь приятное дополнение к мощному средству выражения определенного рода идей.
Третье свойство - это имеющаяся возможность формального преобразования функциональных программ с целью их оптимизации. Точно так же, как JIT-компилятор .NET выполняет различные оптимизации алгоритмов под конкретное железо, компилятор функциональных языков способен оптимизировать функциональную программу для достижения максимальной производительности. Отличие от того же .NET в том, что функциональную программу можно оптимизировать значительно существеннее. Например, автоматически распараллелить выполнение некоторых функций или вообще не выполнять некоторые из вызванных функций, если их значения не требуются для работы программы.
Для того, чтобы лучше пояснить, чем классическая императивная программа отличается от функциональной, приведу два рисунка [3]. На рис. 1 показана программа, как ее привыкли писать на С или Java.
 |
| Рис. 1 |
На рис. 2 показана функциональная программа, как ее написали бы на Clojure.
 |
| Рис. 2 |
В императивных языках функцией можно назвать именованную последовательность инструкций, сгруппированных для удобства использования. В функциональных языках понятие функции ближе к математике. Это некоторая операция, принимающая аргументы и возвращающая результат. Императивные языки выполняют задачи за счет большого числа инструкций, которые последовательно изменяют состояние (данные) программы. В функциональных языках та же цель достигается за счет композиции функций, результат выполнения которых передается в другие функции и т.д.
Синтаксис Clojure во многом унаследован от своего более древнего предка - языка Lisp. И если Lisp, впервые представленный публике Джоном МакКарти в 1958 году [3], содержит некоторые исторические пережитки, то Clojure, разработанный Ричем Хики в 2007-м [4], отражает наиболее современные концепции и более усовершенствованный синтаксис. И, тем не менее, Clojure, пусть осовременненый, но все же Lisp, а потому содержит все его достоинства и недостатки. Самое, пожалуй, необычное свойство синтаксиса Lisp-подобных языков - это представление всех данных в виде списков, да еще и в префиксном виде. Так, например, привычная нам запись f(x,y), означающая вызов функции f с аргументами x и y, в Clojure будет выглядеть так: (f x y). Обычная арифметическая операция 2+2 в Clojure будет записана так: (+ 2 2). Такая запись означает, как и в предыдущем случае, что нужно вызвать функцию "+" и передать ей два аргумента: 2 и 2. Повсеместной практикой является композиция функций, т.е. передача результата одной функции как аргумент другой. Например, 3 * (2+2) на Clojure будет записано так: (* 3 (+ 2 2)).
Показанная форма записи вызова функций называется S-выражением. Джон МакКарти вообще-то собирался изменить такой способ вызова функций на привычный нам по языкам C и Pascal, но отложил это на неопределенный срок [5]. Со временем оказалось, что появилось поколение программистов, которые инфиксной записи предпочитают S-выражения, так что это свойство Lisp-а решили оставить как есть. Позже, когда в Lisp добавили макросы, оказалось, что S-выражения очень удобны для построения собственных языков на основе Lisp.
Еще одно важное свойство Lisp-а, перекочевавшее в Clojure, - развитые средства метапрограммирования. Макрос в Clojure - это код, который пишет код. Подсистема макросов в Clojure, как и в Lisp, делает его программируемым языком программирования. Вот эти-то две составляющие, S-выражения и развитая поддержка макросов делают все Lisp-подобные языки настолько непохожими на остальные, что с большим трудом воспринимаются основной массой программистов.
Символом Lisp-а стал инопланетянин, изображенный возле заголовка статьи. Он показывает, что программы на Lisp чужды мозгу простых земных программистов. А поскольку Clojure - тоже Lisp, то и мы сейчас прикоснемся к инопланетному разуму.
Давайте рассмотрим какой-нибудь простой алгоритм, известный всем с детства. Например, в школе на уроках информатики проходят сортировку массива пузырьком. Сформулируем задачу сортировки.
Дано неупорядоченное множество элементов А. Необходимо получить упорядоченное множество В, состоящее из всех элементов множества А, расположенных в порядке убывания.
Реализация на Java выглядит так:
package javatest;
public class Main {
public static void main(String[] args) {
int arr[] = {5, 2, 4, 3, 1};
for (int j = 0; j < arr.length-1; j++)
for (int i = j + 1; i < arr.length; i++) {
if (arr[j] < arr[i]) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
}
}
}
Наверное, не имеет смысла пояснять этот пример, он слишком хорошо всем знаком. Но давайте попробуем переформулировать этот алгоритм в декларативном стиле.
Во-первых, что такое множество. В, состоящее из элементов множества А, расположенных в порядке убывания? Очевидно, первый элемент множества В - это максимальный элемент множества А. Второй элемент множества В - максимальный элемент множества А без того первого максимального элемента.
B[0] = max(A); A' = A - max(A); B[1] = max(A'); A'' = A' - max(A').
Т.е. имеют место рекуррентные соотношения:
B[n] = max(A(n))
A(n+1) = A(n) - max(A(n)).
Функция нахождения максимального элемента на множестве, реализованная на Clojure, представлена ниже:
(defn my-set-max [my-set] (if (= (count my-set) 1) (first my-set) (max (first my-set) (my-set-max (next my-set))) ) )
Она тривиальна, поэтому перейдем к более интересной функции, описывающей рассмотренные соотношения для множеств А и В:
(defn my-sort [A B]
(if (empty? A)
B
(let [max-in-A (my-set-max A)
next-A (remove #(= % max-in-A) A)
next-B (cons max-in-A B)]
(recur next-A next-B)
)
)
)
Здесь let объявляет привязки символов к их значениям. Конструкция max-in-A (my-set-max A) вычисляет максимальное значение множества А и привязывает его к символу max-in-A. Символ max-in-A - не переменная в привычном нам понимании, т.к. после привязки его к определенному значению изменить эту привязку, как и само значение, невозможно.
Конструкция (remove #(= % max-in-A) A) порождает новое множество, содержащее все элементы множества А, кроме его максимального элемента. Полученное множество будет привязано к символу next-A. К символу next-B будет привязано упорядоченное множество, которое состоит из предыдущего варианта множества В и максимального элемента множества А.
Конструкция (recur next-A next-B) объявляет, что необходимо выполнить рекурсивно функцию my-sort с новыми значениями: next-A и next-B. А запуск сортировки можно сделать таким образом: (my-sort '(5, 2, 4, 3, 1) []).
То есть код на Clojure не описывает, как необходимо выполнять вычисления; он не изменяет никаких данных; в этом коде нет циклов, временных переменных и изменяемых массивов. Код на Clojure просто объявляет, что такое упорядоченное множество В. Точь-в-точь как это делают приведенные выше рекуррентные соотношения, записанные языком математики.
Значит, во-первых, код на Clojure более понятен. Во-вторых, поскольку в нем нет изменяемых данных, его можно безопасно использовать в параллельных потоках. И, в-третьих, по этой же причине, его очень легко тестировать.
Впрочем, я не утверждаю, что код на Clojure всегда лучше кода на Java. Я просто говорю, что иногда, когда к исходнику предъявляются определенного рода требования вроде потокобезопасности, такой исходник проще написать и поддерживать на Clojure, чем на Java.
Подведем итоги. Clojure - это современный Lisp-подобный язык, разработанный специально для функционального программирования с уклоном в параллелизм. Он позволяет проще разрабатывать потокобезопасный код, поощряет декларативное программирование и параллельные вычисления. В этой статье я не коснулся таких важных вещей, как интеграция с Java (которая в Clojure просто на высоте!), различных механизмов распараллеливания, встроенных прямо в язык (например, Software Transactional Memory), и много чего еще. Но надеюсь, что заинтересовал вас настолько, что вы займетесь Clojure самостоятельно. А в следующей статье расскажу еще о нескольких интересных особенностях функционального программирования.
Дмитрий БУШЕНКО,
d.bushenko@gmail.com
Литература
- А. Филд, П.Харрисон, "Функциональное программирование", Москва, Мир, 1993.
- Х. Абельсон, Д.Сассман, "Структура и интерпретация компьютерных программ", Добросвет, 2006.
- D.Cooper, "Basic Lisp Techniques", 2003.
- L. VanderHart, S. Sierra, "Practical Clojure", Apress, 2010.
- P.Seibel, "Practical Common Lisp", Apress, 2005.
Версия для печати
Комментарии