7. Функциональное программирование
До сих пор рассматриваемые нами парадигмы программирования воспринимались нами как некоторые "полезные надстройки над императивным программированием". Уже отмечалось, например, что параллельное программирование - это программирование в терминах взаимодействия некоторых одновременно работающих абстрактных вычислителей, и почти ничего не говорили о вычислительной модели, на которой основаны отдельные элементы этой системы. Мы ничего не сказали о том, на каком языке описаны обработчики сообщений у объектов (кроме того, что в этих языках основной операцией является посылка сообщения).
Функциональное программирование представляет из себя одну из альтернатив императивному подходу. В императивном программировании алгоритмы - это описания последовательно исполняемых операций. Здесь существует понятие "текущего шага исполнения" (то есть, времени), и "текущего состояния", которое меняется с течением этого времени. В функциональном программировании понятие времени отсутствует.
В функциональном программировании программы являются выражениями, исполнение программ заключается в вычислении этих выражений.
Практически все математики, сами того не замечая, занимаются функциональным программированием, описывая, например, чему равно абсолютное значение произвольного вещественного числа. Императивное программирование основано на машине Тьюринга-Поста - абстрактном вычислительном устройстве, предложенном на заре алгоритмической эры для описания алгоритмов.
Функциональное программирование основано на более естественном с математической точки зрения формализме - лямбда-исчислении Черча. Как правило, рассматривают так называемое "расширенное лямбда-исчисление". Его грамматику можно описать следующим образом: Выражение ::= Простое выражение | Составное выражение Простое выражение ::= Константа | Имя Составное выражение ::= Лямбда-абстракция | Применение | Квалифицированное выражение | Ветвление Лямбда-абстракция ::= 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) end end.
Когда нам надоест ставить скобки вокруг применения функций к аргументам, мы можем объявить операцию применения функции (которую мы при записи опускаем, так же, как в математике принято не писать явно символ умножения) левоассоциативной, то есть, понимать запись вида f x y как ((f x) y). Это - традиционное соглашение, поэтому никакие "стандарты" не нарушаются. Чистое лямбда-исчисление Черча позволяет обходиться исключительно именами, лямбда-абстракциями от одного аргумента и применениями выражений к выражениям.
Оказывается, в этих терминах можно описать и "предопределенные" константы (числа и т.п.), структуры данных (списки, кортежи...), логические значения и ветвление. Более того, в чистом лямбда-исчислении можно обойтись без квалифицированных выражений, и, следовательно, выразить рекурсию, не используя для этого употребления имени функции в теле функции. Некоторые экспериментальные модели функционального программирования позволяют обходиться без каких-либо имен вообще.
Подробнее об этом можно почитать в специальной литературе, например, в книге Филда и Харрисона "Функциональное программирование". Функциональное программирование обладает следующими двумя примечательными свойствами: 1.) Аппликативность: программа есть выражение, составленное из применения функций к аргументам. 2.) Настраиваемость: так как не только программа, но и любой программный объект (в идеале) является выражением, можно легко порождать новые программные объекты по образцу, как значения соответствующих выражений (применение порождающей функции к параметрам образца). Настраиваемость активно используется в таком направлении программирования, как generic programming. Основная задача, решаемая в рамках это направления - создание максимально универсальных библиотек, ориентированных на решение часто встречающихся подзадач (обработка агрегатных данных; потоковый ввод-вывод; взаимодействие между программами, написанными на разных языках и различающихся в деталях семантики; универсальные оконные библиотеки). Эти направления наиболее ярко представлены в STL - стандартной библиотеке шаблонов (контейнеров) языка Си++, а так же - в реализации платформы .NET фирмы MicroSoft. Нередко в разговорах о пользе функционального программирования можно услышать следующее утверждение: "самые крупные специалисты по функциональному языку Haskell в настоящее время находятся в MicroSoft Research". Для обеспечения видовой корректности программ в функциональные языки вводят специальные системы типов, ориентированные на поддержку настраиваемости. Как правило, трансляторы функциональных языков могут самостоятельно определять типы выражений, без каких-либо описаний типов вообще. Так, функция add = lambda x -> lambda y -> x+y end end будет иметь тип number -> number -> number, а уже рассматриваемая нами функция apply - тип any(X).any(Y).(X->Y)->X->Y, где any обозначает "квантор всеобщности" для типов, а X и Y являются переменными. Можно заметить, что, так как порядок вычисления подвыражений не имеет значения, так как "состояния" у функциональной программы нет, поэтому функциональное программирование может быть естественным образом реализовано на платформах, поддерживающих параллелизм. "Потоковая модель" функционального программирования, о которой так же можно почитать у Филда и Харрисона, является естественным представлением функциональных программ в терминах систем взаимодействующих процессов. Функциональное программирование, как и другие модели "неимперативного" программирования, обычно применяется для решения задач, которые трудно сформулировать в терминах последовательных операций. Практически все задачи, связанные с искусственным интеллектом, попадают в эту категорию. Среди них следует отметить задачи распознавания образов, общение с пользователем на естественном языке, реализацию экспертных систем, автоматизированное доказательство теорем, символьные вычисления. Эти задачи далеки от традиционного прикладного программирования, поэтому им уделяется не так много внимания в учебных программах по информатике.