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

Уместно упомянуть выдающуюся книгу П. Хендерсона “Функциональное программирование” [10].

Существует некоторая внешняя аналогия между процедурным и функциональным программированием.

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

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

x

Р₁ f₁

Р₂ f₂

P₃ f₃

y

y = f₃(f₂(f₁(x)))

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

Процедурное программирование - это "сплошные побочные эффекты".

Самой простой и фундаментальной иллюстрацией служит оператор присваивания:

Х:= Х + 1, где правый Х - это (относительный) адрес в памяти, где находится предыдущее значение Х … Или типичная процедура работы с массивом (матрицей) - в "вольном переводе" на математический язык, здесь "функция" меняет свой аргумент, который становится значением "функции".

Вместо циклов процедурного программирования (как раз отслеживающих значения изменяемых констант) в функциональном программировании используется рекурсия.

Процедурные языки можно считать машинно-зависимыми, поскольку они ориентированы на архитектуру машины Фон Неймана: память - процессор.

С точки зрения реализации, функциональному программированию присущи: представление программы в виде списковой структуры и вычисление в режиме интерпретации. (Поэтому тот же Э. Дейкстра назвал функциональное программирование самым извращенным использованием машины Фон-Неймана).

Пример: Пусть имеется оператор присваивания

y:= (a+b) * c

и пусть ему соответствует функциональная запись

(приравнять у (умножить (сложить a b) с))

Списковая структура, представляющая эту функцию, будет:

приравнять у

умножить с

сложить а b

сумма

Вычисление - это трансформация списка в режиме интерпретации. Вначале вычисляется функция сложения и ссылка на эту функцию заменяется ссылкой на полученную сумму. Затем вычисляется произведение и т.д.

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

Минусы функционального программирования: Режим интерпретации в десятки раз снижает скорость вычисления; из-за необходимости хранить списковую структуры нерационально используется память.

Первым языком функционального программирования был язык LISP и многие базовые понятия этого языка стали классикой функционального программирования.

Базовые функции функционального программирования:

car(x) - дает первый элемент списка х;

cdr(х) - хвост списка (список без первого элемента);

cons(x,y) - добавляет элемент х к списку у;

append(x,y) - добавляет список y к списку x;