Функциона́льное программи́рование — парадигма программирования, в которой процесс вычисления представляется как применение чистых функций к неизменяемым данным. Она не предполагает изменяемости и явного хранения состояния программы, что противопоставляет её императивной парадигме, где одной из базовых концепций является переменная, — участок памяти, хранящий некоторое значение и позволяющий менять его по мере выполнения алгоритма.
Функциональное программирование исключает грязные функции. Последние, в отличие от чистых, могут опираться не только на собственные аргументы, но и на внешние факторы, такие как результаты побочных эффектов или значения глобальных переменных. Функциональная чистота гарантирует, что при одних и тех же входных данных, результат будет одинаковым. Это положение открывает ряд возможностей таких как кеширование результатов исчисления, произвольное параллельное выполнение и любое другое изменение порядка редукции, ленивые вычисления, и прочее.
Основой для функционального программирования служит лямбда-исчисление, многие функциональные языки можно рассматривать как «надстройку» над нимА. Филд, П. Харрисон Функциональное программирование: Пер. с англ. — М.: Мир, 1993. — 637 с, ил. ISBN 5-03-001870-0. Стр. 120 [Глава 6: Математические основы: λ-исчисление]..
Языки функционального программирования Наиболее известными языками функционального программирования являются: Лисп (Джон Маккарти, 1958) и множество его диалектов, наиболее известные — Scheme, Clojure и Common Lisp; в 1970-е годы для поддержки языка создавались специализированные аппаратные комплексы — лисп-машины; Erlang (Джо Армстронг, 1986) — функциональный язык с поддержкой процессов, а также его прямой потомок Elixir; APL — предшественник современных научных вычислительных сред, таких как MATLAB; ML (Робин Милнер, 1979) и его основные диалекты Standard ML и OCaml; F# — функциональный язык семейства ML для платформы .NET; Scala — язык платформы JVM, сочетающий возможности функционального и объектно-ориентированного программирования; Miranda (Дэвид Тёрнер, 1985) и его прямой потомок чистый функциональный язык Haskell; Nemerle — гибридный функционально-императивный язык.
Ещё не полностью функциональные изначальные версии и Лиспа, и APL внесли особый вклад в создание и развитие функционального программирования. Более поздние версии Lisp, такие как Scheme, а также различные варианты APL поддерживали все свойства и концепции функционального языка.
Как правило, интерес к функциональным языкам программирования, особенно чисто функциональным, был скорее научный, нежели коммерческий. Однако, такие примечательные языки как Erlang, OCaml, Haskell, Scheme (после 1986) а также специфические R (статистика), Wolfram (символьная математика), J и K (финансовый анализ), и XSLT (XML) находили применение в индустрии коммерческого программирования. Такие широко распространённые декларативные языки как SQL и Lex/Yacc содержат некоторые элементы функционального программирования, например, не используют переменных. Языки работы с электронными таблицами также можно рассматривать как функциональные, потому что в ячейках электронных таблиц задаётся массив функций, как правило зависящих лишь от других ячеек, а при желании смоделировать переменные приходится прибегать к возможностям императивного языка макросов.
История Лямбда-исчисление стало теоретической базой для описания и вычисления функций. Являясь математической абстракцией, а не языком программирования, оно составило базис почти всех языков функционального программирования на сегодняшний день. Сходное теоретическое понятие, комбинаторная логика, является более абстрактным, нежели λ-исчисления и было создано раньше. Эта логика используется в некоторых эзотерических языках, например в Unlambda. И λ-исчисление, и комбинаторная логика были разработаны для более ясного и точного описания принципов и основ математики + переиздание ISBN 978-5-382-01266-7; 2011 г..
Первым функциональным языком был Лисп, созданный Джоном Маккарти в период его работы в Массачусетском технологическом институте в конце пятидесятых и реализованный, первоначально, для IBM 700/7000. В Лиспе впервые введено множество понятий функционального языка, хотя при этом в языке применяется не только парадигма функционального программирования. Дальнейшим развитием Лиспа стали такие языки как Scheme и Dylan.
Язык обработки информации (, IPL) иногда определяется как самый первый машинный функциональный языкВ своих мемуарах Герберт Саймон (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 утверждает, что его, Al. Ньюэлл, и Клифф Шоу которых «часто называют родителями искусственного интеллекта» за написание программы автоматически доказывающей теоремы из Principia Mathematica. Для того, чтобы достичь этого, они должны были придумать язык и парадигму, которую, ретроспективно, можно рассматривать как функциональное программирование.. Это язык ассемблерного типа для работы со списком символов. В нём было понятие «генератора», который использовал функцию в качестве аргумента, а также, поскольку это язык ассемблерного уровня, он может позиционироваться как язык, имеющий функции высшего порядка. Однако, в целом IPL акцентирован на использование императивных понятий.
Кеннет Айверсон разработал язык APL в начале шестидесятых, документировав его в своей книге A Programming Language (ISBN 978-0-471-43014-8). APL оказал значительное влияние на язык , созданный Джоном Бэкусом. В начале девяностых Айверсон и создали преемника APL — язык программирования J. В середине девяностых , ранее работавший с Айверсоном, создал язык K, который впоследствии использовался в финансовой индустрии на коммерческой основе.
В 1970-х годах в университете Эдинбурга Робин Милнер создал язык ML, а Дэвид Тернер начинал разработку языка SASL в университете Сент-Эндрюса и, впоследствии, язык Miranda в университете города Кент. В конечном итоге на основе ML были созданы несколько языков, среди которых наиболее известные Objective Caml и Standard ML. Также в семидесятых осуществлялась разработка языка программирования, построенного по принципу Scheme (реализация не только функциональной парадигмы), получившего описание в известной работе «Lambda Papers», а также в книге восемьдесят пятого года «Structure and Interpretation of Computer Programs».
В 1972 году Пер Мартин-Лёф создал интуиционистскую теорию типов (также называемую конструктивной). В этой теории функциональное программирование получило конструктивное доказательство того, что ранее было известно как зависимый тип. Это дало мощный толчок к развитию диалогового доказательства теорем и к последующему созданию множества функциональных языков.
Haskell был создан в конце 1980-х годов в попытке соединить множество идей, полученных в ходе исследования функционального программирования.
Концепции Некоторые концепции и парадигмы специфичны для функционального программирования и в основном чужды императивному программированию (включая объектно-ориентированное программирование). Тем не менее, языки программирования обычно представляют собой гибрид нескольких парадигм программирования, поэтому «большей частью императивные» языки программирования могут использовать какие-либо из этих концепций.
Функции высших порядков
Функции высших порядков — это такие функции, которые могут принимать в качестве аргументов и возвращать другие функции.. Математики такую функцию чаще называют оператором, например, оператор взятия производной или оператор интегрирования.
Функции высших порядков позволяют использовать карринг — преобразование функции от пары аргументов в функцию, берущую свои аргументы по одному. Это преобразование получило своё название в честь Хаскелла Карри.
Чистые функции Чистыми называют функции, которые не имеют побочных эффектов ввода-вывода и памяти (они зависят только от своих параметров и возвращают только свой результат). Чистые функции обладают несколькими полезными свойствами, многие из которых можно использовать для оптимизации кода: если результат чистой функции не используется, её вызов может быть удалён без вреда для других выражений; результат вызова чистой функции может быть мемоизирован, то есть сохранён в таблице значений вместе с аргументами вызова; если нет никакой зависимости по данным между двумя чистыми функциями, то порядок их вычисления можно поменять или распараллелить (говоря иначе, вычисление чистых функций удовлетворяет принципам потокобезопасности); если весь язык не допускает побочных эффектов, то можно использовать любую политику вычисления. Это предоставляет свободу компилятору комбинировать и реорганизовывать вычисление выражений в программе (например, исключить древовидные структуры).
Благодаря мемоизации, если в дальнейшем функция вызывается с этими же аргументами, её результат может быть взят прямо из таблицы значений не вычисляясь (иногда это называется принципом прозрачности ссылок). Мемоизация, ценой небольшого расхода памяти, позволяет существенно увеличить производительность и уменьшить порядок роста некоторых рекурсивных алгоритмов.
Хотя большинство компиляторов императивных языков программирования распознают чистые функции и удаляют общие подвыражения для вызовов чистых функций, они не могут делать это всегда для предварительно скомпилированных библиотек, которые, как правило, не предоставляют эту информацию. Некоторые компиляторы, такие как gcc, в целях оптимизации предоставляют программисту ключевые слова для обозначения чистых функций. Fortran 95 позволяет обозначать функции как «pure» (чистые)XL Fortran for AIX, V13.1 > Language Reference, Pure procedures (Fortran 95).
Рекурсия
В функциональных языках цикл обычно реализуется в виде рекурсии. Строго говоря, в функциональной парадигме программирования нет такого понятия, как цикл. Рекурсивные функции вызывают сами себя, позволяя операции выполняться снова и снова. Для использования рекурсии может потребоваться большой стек, но этого можно избежать в случае хвостовой рекурсии. Хвостовая рекурсия может быть распознана и оптимизирована компилятором в код, получаемый после компиляции аналогичной итерации в императивном языке программирования. Стандарты языка Scheme требуют распознавать и оптимизировать хвостовую рекурсию. Оптимизировать хвостовую рекурсию можно путём преобразования программы в стиле использования продолжений при её компиляции, как один из способов.
Рекурсивные функции можно обобщить с помощью функций высших порядков, используя, например, катаморфизм и анаморфизм (или «свёртка» и «развёртка»). Функции такого рода играют роль такого понятия как цикл в императивных языках программирования.
Подход к вычислению аргументов Функциональные языки можно классифицировать по тому, как обрабатываются аргументы функции в процессе её вычисления. Технически различие заключается в денотационной семантике выражения. К примеру, при строгом подходе к вычислению выражения: print(len([2+1, 3*2, 1/0, 5-4])) на выходе будет ошибка, так как в третьем элементе списка присутствует деление на ноль. При нестрогом подходе значением выражения будет 4, поскольку для вычисления длины списка значения его элементов, строго говоря, не важны и могут вообще не вычисляться. При строгом (аппликативном) порядке вычисления заранее подсчитываются значения всех аргументов перед вычислением самой функции. При нестрогом подходе (нормальный порядок вычисления) значения аргументов не вычисляются до тех пор, пока их значение не понадобится при вычислении функцииН. А. Роганова Функциональное программирование: Учебное пособие для студентов высших учебных заведений — М.: ГИНФО, 2002. — 260 с. Стр. 14 п. 3.1. Ленивые и энергичные вычисления.
Как правило, нестрогий подход реализуется в виде редукции графа. Нестрогое вычисление используется по умолчанию в нескольких чисто функциональных языках, в том числе Miranda и Haskell.
В нефункциональных языках