Зачем нужно функциональное программирование

В результате изучения материала главы 1 студент должен:

знать

• • особенности функционального стиля программирования;
• • недостатки и преимущества функционального стиля по отношению к императивному стилю программирования;

уметь

• • преобразовывать программы, написанные в императивном стиле, в программы, написанные в функциональном стиле;
• • оптимизировать функциональные программы для параллельных вычислений;

владеть

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

Особенности функционального стиля

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

Рис. 1.1. Схема простой функциональной программы.

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

Можно привести много примеров простых и сложных программ, имеющих смысл и работающих, но этой схеме. Например, в программе аналитических преобразований выражений входными и выходными данными будут выражения, представленные в разной форме. Другой пример — компилятор с некоторого языка программирования: входными данными программы будет текст, написанный на этом языке программирования, а выходными данными — объектный код программы. Третий пример — программа составления расписания учебных занятий: исходные данные для такой программы — набор «пожеланий» к расписанию, а выходные данные — таблица, представляющая расписание занятий.

В то же время многие программы выполняются не по схеме «черного ящика». Например, любая программа, организующая активное взаимодействие (диалог) с пользователем, не является преобразователем набора входных данных в выходные, если только не считать, что входными и выходными данными в этом случае является «среда», включающая в том числе и пользователя.

Всякая программа, написанная в функциональном стиле, — эго программа, представляющая собой функцию, аргументом которой служат входные данные из некоторого допустимого набора и выдающую определенный результат. Обычно при этом подразумевается, что функция, определяющая поведение программы, на одних и тех же входных данных всегда выдает один и тот же результат, т. е. это функция детерминированная. Можно заметить, что любая программа, содержащая запросы к пользователю (взаимодействующая с пользователем) — не детерминированная, поскольку ее поведение может зависеть от «поведения пользователя», т. е. конкретных данных, введенных пользователем.

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

• • каждая функция в программе выдает один и тот же результат на одном и том же наборе входных данных (аргументов функции), т. е. результат работы функции является «повторяемым»;
• • вычисление функции не может повлиять на результат работы других функций, т. е. функции являются «чистыми».

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

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

Можно ли писать программы в функциональном стиле на традиционном языке программирования? Конечно, да. Если программа представляет собой набор чистых детерминированных функций, то она будет «функциональной» независимо от того, написана ли она па специальном языке функционального программирования Haskell или на традиционном Java. Рассмотрим, например, задачу вычисления суммы вещественных элементов списка. Функция, решающая эту задачу, должна, получив в качестве исходных данных список из вещественных чисел, вычислить и выдать в качестве результата сумму элементов списка. На языке Java функция может выглядеть следующим образом (листинг 1.1).

Листинг 1.1. Функция вычисления суммы элементов числового списка.

double sumList (List list) { double sum = 0;

for (Double element: list) { sum += element;

}.

return sum;

}.

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

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

Впрочем, в нашем случае исправить программу, приведя ее в соответствие с принципами функционального стиля программирования, можно. Для этого определим нашу функцию следующим образом (листинг 1.2).

Листинг 1.2. Рекурсивная функция вычисления суммы элементов списка.

double sumList (List list) { final int size = list, size (); final int mid = size / 2; return

size == 0? 0 :

size == 1? list. get (O) :

sumList (list.subList (0, mid)) + sumList (list.subList (mid, size));

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

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

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

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

Рассмотрим следующую простую задачу. Пусть требуется определить функцию, с помощью которой можно создавать суперпозицию двух вещественных функций одного вещественного аргумента. Другими словами, нужно описать инструмент, с помощью которого из двух произвольных функций f (х) и g (х) можно было бы получить новую функцию fg (х), результат работы которой определялся бы уравнением fg (x) = f (g (х)). Конечно, решение этой задачи было бы очень полезным в ситуации, когда практически единственным инструментом программирования является определение и вызов различных функций. В последних версиях языка Java, начиная с версии Java 8, имеется довольно широкий набор средств функционального программирования, так что поставленную задачу можно решить довольно просто (функция образования суперпозиции двух других функций включена в стандартную библиотеку программ этой версии Java). В листинге 1.3 приведена искомая функция.

Листинг 1.3. Реализация суперпозиции на Java static FunctiorKT, V>

compose (FunctionctJ, V> f, FunctiorKT, U> g) { return x -> f. apply (g.apply (x));

}.

Даже если вы не очень хорошо разбираетесь во всех деталях записи, общий смысл написанного понять можно. Результатом работы этой функции является новая функция с аргументом х, результат работы которой — последовательное применение (apply) функций g и f к этому аргументу. Видно, впрочем, что на самом деле аргументы f ид — это не совсем функции: запись f (д (х)) синтаксически неверна. Объекты типа Function — это сложно устроенные объекты, внутри которых и спрятана исполняемая функция. Несмотря на внешнюю простоту записи, в приведенной реализации имеется много скрытых деталей, которые необходимы для того, чтобы весьма сложно организованный объект имел вид обычной функции. Например, если подумать, то становится непонятно, почему аргументы функции comp — переданные ей функции f и g — не пропадают после выхода из этой функции, а остаются «жить» внутри возвращаемого результата.

Немного странным выглядит и использование функции compose в довольно простой ситуации. Естественная на первый взгляд запись compose (Math. sin, Math. cos) (3.14) оказывается синтаксически неверной. Правильной будет запись compose (Math: :sin, Math: :cos). apply (3.14). Очень хорошо видно, что используемые нами «функции» — это не совсем функции в традиционном понимании, и в язык Java пришлось добавить много нового синтаксиса для того, чтобы выразить такие манипуляции с функциями, которые в функциональных языках выглядят очень просто и естественно, да и реализуются просто.

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

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