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

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

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

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

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

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

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

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

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

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

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