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

Сущность функционального (аппликативного) программирования определена А.П. Ершовым как "… способ составления программ, в которых единственным действием является вызов функции, единственным способом расчленения программы на части является введение имени для функции, а единственным правилом композиции – оператор суперпозиции функции. Никаких ячеек памяти, операторов присваивания, ни, тем боле, блок-схем, ни передачи управления".

Роль основной конструкции в функциональных языках играет выражение. К выражениям относятся скалярные константы, структурированные объекты, функции, тела функций и вызовы функций. Функция трактуется как однозначное отображение из Х в Х, где Х – множество выражений.

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

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

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

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

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

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

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

Первым таким языком был LISP (ЛИСП) (LISt Processing – обработка списков). Созданный в 1959 году. Цель его создания состояла в организации удобства обработки символьной информации. Существенная черта этого языка – унификация программных структур и структур данных: все выражения записываются в виде списков.