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

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

Функциональное программирование основано на теориях λ-исчисления (Алонзо Чёрч, 1936) и комбинаторной логики (Моисей Исаевич Шёнфинкель и Хаскелл Карри).

Наиболее известными языками функционального программирования являются:

LISP (Джон МакКарти, 1958, множество его потомков, наиболее современные из которых — Scheme и Common Lisp)
ML (Робин Милнер, 1979, из ныне используемых диалектов известны Standard ML и Objective CAML)
Miranda (Дэвид Тёрнер, 1985, который впоследствии дал развитие языку Haskell).
Nemerle — гибридный функционально/императивный язык.

КонцепцииПравить

Некоторые концепции и идиомы специфичны для функционального программирования и в основном чужды императивному программированию (включая объектно-ориентированное программирование). Тем не менее, языки программирования обычно представляют собой гибрид нескольких парадигм программирования, поэтому «большей частью императивные» языки программирования могут использовать какие-либо из этих концепций.

Функции высших порядковПравить

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

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

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

РекурсияПравить

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

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

Другие парадигмы программированияПравить

Схожие парадигмыПравить

Одной из близких парадигм программирования является логическое программирование, в котором программа представляет собой множество пар (логическое условие, новые факты). В логическом программировании, также как и в функциональном программировании, программист остаётся в неведении о методах, применяемых при вычислении, и последовательности исполнения элементарных действий. Бо́льшая часть ответственности за эффективность вычислений в логическом и функциональном программировании перекладывается на «плечи» транслятора используемого языка программирования.

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

См. такжеПравить

ЛитератураПравить

Городняя Л. В. Основы функционального программирования. Курс лекций — М.: Интернет-университет информационных технологий, 2004. — 280 стр. ISBN 5-9556-0008-6
Душкин Р. В. Функциональное программирование на языке Haskell. — М.: ДМК Пресс, 2006. — 608 стр. ISBN 5-94074-335-8
Филд А., Харрисон П. Функциональное программирование. — М.: Мир, 1993. — 637 стр. ISBN 5-03-001870-0