До сих пор рассматриваемые нами парадигмы программирования
воспринимались нами как некоторые "полезные надстройки над императивным
программированием". Уже отмечалось, например, что параллельное
программирование - это программирование в терминах взаимодействия
некоторых одновременно работающих абстрактных вычислителей, и почти
ничего не говорили о вычислительной модели, на которой основаны
отдельные элементы этой системы. Мы ничего не сказали о том, на каком
языке описаны обработчики сообщений у объектов (кроме того, что в этих
языках основной операцией является посылка сообщения). Функциональное
программирование представляет из себя одну из альтернатив императивному
подходу.
В императивном программировании алгоритмы - это описания
последовательно исполняемых операций. Здесь существует понятие
"текущего шага исполнения" (то есть, времени), и "текущего состояния",
которое меняется с течением этого времени.
В функциональном
программировании понятие времени отсутствует. Программы являются
выражениями, исполнение программ заключается в вычислении этих
выражений. Практически все математики, сами того не замечая, занимаются
функциональным программированием, описывая, например, чему равно
абсолютное значение произвольного вещественного числа.
Императивное
программирование основано на машине Тьюринга-Поста - абстрактном
вычислительном устройстве, предложенном на заре алгоритмической эры для
описания алгоритмов. Функциональное программирование основано на более
естественном с математической точки зрения формализме -
лямбда-исчислении Черча.
Как правило, рассматривают так
называемое "расширенное лямбда-исчисление". Его грамматику можно описать
следующим образом (жаль, что не в любой локализации есть символ
"лямбда"):
Выражение ::= Простое выражение | Составное выражение
Простое выражение ::= Константа | Имя
Составное выражение ::= Лямбда-абстракция | Применение | Квалифицирванное выражение | Ветвление
Лямбда-абстракция ::= 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 являются переменными.
Можно
заметить, что так как порядок вычисления подвыражений не имеет значения
(благо "состояния" у функциональной программы нет), функциональное
программирвание может быть естественным образом реализовано на
платформах, поддерживающих параллелизм. "Потоковая модель"
функционального программирования, о которой так же можно почитать у
Филда и Харрисона, является естественным представлением функиональных
программ в терминах систем взаимодействующих процессов.
Функциональное
программирование, как и другие модели "неимперативного"
программирования, обычно применяется для решения задач, которые трудно
сформулировать в терминах последовательных операций. Практически все
задачи, связанные с искусственным интеллектом, попадают в эту категорию.
Среди них следует отметить задачи распознавания образов, общение с
пользователем на естественном языке, реализацию экспертных систем,
автоматизированное доказательство теорем, символьные вычисления. Эти
задачи далеки от традиционного прикладного программирования, поэтому им
уделяется не так много внимания в учебных программах по информатике.
