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

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

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

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

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

Например, список

(А (B C) D (E (F G)))

состоит из четырех элементов. Первый – это атом A, второй это список (B C), третий - атом D, а четвертый список (E (F G)), содержащий в качестве второго элемента список (F G).

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

Все записи на функциональном языке представляют собой список. Например (A B C D) читает так: «Функция A применяется к аргументам B,C,D.»

Примеры функций на языке Scheme (диалекте LISP).

1. Функция вычисления факториала

(DEFINE (factorial n)

(IF (= n 0)

(*n (factorial(-n 1)))

)

)

DEFINE – специальная форма для определения функций

factorial – имя функции

n – параметр

IF – оператор ветвления (в языке Scheme всего две управляющие структуры для ветвления и мультиветвления)

1. Функция сравнения двух списков

(DEFINE (equallist lis1 lis2)

(COND

((NULL? lis1) (NULL? lis2))

((NULL? lis2) ‘())

((EQ? (CAR lis1)(CAR lis2))

(equallist (CDR lis1) (CDR lis2)))

(ELSE’ ())

))

)

DEFINE – специальная форма для определения функций

equallist – имя функции

lis1, lis2 – параметры

COND – оператор мультиветвления, ищет первый предикат имеющий значение истина, вычисляет выражение и возвращает его.

NULL? – стандартная функция, возвращающая «истина» если ее параметр - пустой список

EQ? - стандартная функция – возвращающая «истина», если оба ее параметра атомы и эквиваленты между собой, в противном случае – пустой список.

CDR – элементарная функция возвращающая остаток заданного списка после удаления его первого элемента

CAR – элементарная функция, возвращающая первый элемент списка

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