Функциональное программирование

До сих пор рассматриваемые нами парадигмы программирования воспринимались нами как некоторые "полезные надстройки над императивным программированием". Уже отмечалось, например, что параллельное программирование - это программирование в терминах взаимодействия некоторых одновременно работающих абстрактных вычислителей, и почти ничего не говорили о вычислительной модели, на которой основаны отдельные элементы этой системы. Мы ничего не сказали о том, на каком языке описаны обработчики сообщений у объектов (кроме того, что в этих языках основной операцией является посылка сообщения). Функциональное программирование представляет из себя одну из альтернатив императивному подходу.

В императивном программировании алгоритмы - это описания последовательно исполняемых операций. Здесь существует понятие "текущего шага исполнения" (то есть, времени), и "текущего состояния", которое меняется с течением этого времени.

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

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

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

Выражение::= Простое выражение | Составное выражение
Простое выражение::= Константа | Имя
Составное выражение::= Лямбда-абстракция | Применение | Квалифицирванное выражение | Ветвление
Лямбда-абстракция::= lambda Имя -> Выражение end
Применение::= ( Выражение Выражение )
Квалифицированное выражение::= let (Имя = Выражение;)* in Выражение end
Ветвление::= if Выражение then Выражение (elseif Выражение then Выражение)* else Выражение end

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

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

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

1.) Считать, что аргумент является кортежем. Например, apply = lambda (f, x) -> (f x) end можно понимать как apply = lambda y -> ((first y) (second y)) end.

2.) Понять, что множество вычислимых функций X * Y -> Z очевидным образом взаимнооднозначно отображается в множество вычислимых функций X -> (Y -> Z). Так, apply = lambda f -> lambda x -> (f x) endend.

Когда нам надоест ставить скобки вокруг применения функций к аргументам, мы можем объявить операцию применения функции (которую мы при записи опускаем, так же, как в математике принято не писать явно символ умножения) левоассоциативной, то есть, понимать запись вида f x y как ((f x) y). Это - традиционное соглашение, поэтому никаких "стандартов" мы при этом не нарушаем.

Чистое лямбда-исчисление Черча позволяет обходится исключительно именами, лямбда-абстракциями от одного аргумента и применениями выражений к выражениям. Оказывается, в этих терминах можно описать и "предопределенные" константы (числа и т.п.), структуры данных (списки, кортежи...), логические значения и ветвление. Более того, в чистом лямбда-исчислении можно обойтись без квалифицированных выражений, и, следовательно, выразить рекурсию, не используя для этого употребления имени функции в теле функции. Некоторые экспериментальные модели функционального программирования позволяют обходится без каких-либо имен вообще. Подробнее об этом можно почитать в специальной литературе, например, в книге Филда и Харрисона "Функциональное программирование".

Функциональное программирование обладает следующими двумя примечательными свойствами:

1.) Аппликативность: программа есть выражение, составленное из применения функций к аргументам.

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

Настраиваемость активно используется в таком направлении программирования, как generic programming. Основная задача, решаемая в рамках это направления - создание максимально универсальных библиотек, ориентированных на решение часто встречающихся подзадач (обработка агрегатных данных; потоковый ввод-вывод; взаимодействие между программами, написанными на разных языках и различающихся в деталях семантики; универсальные оконные библиотеки). Эти направления наиболее ярко представлены в STL - стандартной библиотеке шаблонов (контейнеров) языка Си++, а так же - в реализации платформы.NET фирмы MicroSoft. Нередко в разговорах о пользе функционального программирования можно услышать следующее утверждение: "самые крупные специалисты по функциональному языку Haskell в настоящее время находятся в MicroSoft Research".

Для обеспечения видовой корректности программ в функциональные языки вводят специальные системы типов, ориентированные на поддержку настраиваемости. Как правило, трансляторы функциональных языков могут самостоятельно определять типы выражений, без каких-либо описаний типов вообще. Так, функция add = lambda x -> lambda y -> x+y endend будет иметь тип number -> number -> number, а уже рассматриваемая нами функция apply - тип any (X). any (Y).(X->Y)->X->Y, где any обозначает "квантор всеобщности" для типов, а X и Y являются переменными.

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

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