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

Сущность функционального (аппликативного) программирования определена А.П.Ершовым как "...способ составления программ, в которых единственным действием является вызов функции, единственным способом расчленения программы на части является введение имени для функции. Никаких ячеек памяти, ни операторов присваивания, ни циклов, ни, тем более, блок-схем, ни передачи управления". Роль основной конструкции в функциональных языках играет выражение. К выражениям относятся скалярные константы, структурированные объекты, функции, тела функций и вызовы функций. Функции трактуются как однозначное отображение из Xn в X,где X - множество выражений, что полностью соответствует понятию функции в математике.

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

1) классы констант, которыми могут манипулировать функции;

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

3) правила построения новых функций из базовых;

4) правила формирования выражений на основе вызовов функций.

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

1) вызовы базовых функций заменяются соответствующими значениями;

2) вызовы не базовых функций заменяются их телами, в которых параметры замещены аргументами.

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

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

Перечисленные свойства характеризуют аппликативные языки как языки программирования сверхвысокого уровня.

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

Самым первым функциональным языком явился LISP (List processing - обработка списков), разработанный и реализованный под руководством Дж.Маккарти в Массачусетском технологическом институте в 1959 г. для обработки символьной информации. Существенная черта LISP'а - предельная унификация программных структур и структур данных (выражения записываются в виде списков). Этот язык считается одним из основных языков при программировании систем искусственного интеллекта.

Существует множество версий языка LISP (INTERLISP, Common LISP и.т.д.). LISP послужил стартовой площадкой для разработки языков PLANNER и CONNIVER, которые используются для реализации процедурных моделей знаний. Сейчас известно множество функциональных языков, значительно более мощных, чем LISP. Среди них ML (Milner Languge) Милнера и Miranda Д.Тернера. С аппликативными языками тесно связаны языки машин потока данных (VALID, VAL, ID, LUCID).

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