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

Для программирования, ориентированного на подпрограммы, см. Процедурное программирование .

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

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

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

Функциональное программирование уходит корнями в академические круги , развившись из лямбда-исчисления , формальной системы вычислений, основанной только на функциях. Функциональное программирование исторически было менее популярным, чем императивное программирование, но многие функциональные языки сегодня находят применение в промышленности и образовании, включая Common Lisp , Scheme , Clojure , Язык Вольфрам , Ракетка , Эрланг , Эликсир , ОКамл , Хаскелл , и Фа# . Lean — это функциональный язык программирования, обычно используемый для проверки математических теорем. Функциональное программирование также является ключом к некоторым языкам, которые добились успеха в определенных областях, таких как JavaScript в Интернете, R в статистике, J , K и Q в финансовом анализе и XQuery / XSLT для XML . Декларативные языки, специфичные для предметной области, такие как SQL и Lex / Yacc, используют некоторые элементы функционального программирования, например, не позволяют изменять изменяемые значения . Кроме того, многие другие языки программирования поддерживают программирование в функциональном стиле или реализуют функции функционального программирования, такие как C++11 , C# , Котлин , Перл , PHP , Питон , Идти , Ржавчина , Раку , Скала , и Java (начиная с Java 8) .

История

Лямбда -исчисление , разработанное в 1930-х годах Алонзо Чёрчем , представляет собой формальную систему , вычислений построенную на основе применения функций . В 1937 году Алан Тьюринг доказал, что лямбда-исчисление и машины Тьюринга являются эквивалентными моделями вычислений. показывая, что лямбда-исчисление является полным по Тьюрингу . Лямбда-исчисление лежит в основе всех функциональных языков программирования. Эквивалентная теоретическая формулировка, комбинаторная логика , была разработана Мозесом Шенфинкелем и Хаскеллом Карри в 1920-х и 1930-х годах.

Позже Чёрч разработал более слабую систему — просто типизированное лямбда-исчисление , которое расширило лямбда-исчисление, назначив тип данных всем терминам. Это формирует основу статически типизированного функционального программирования.

Первый высокого уровня язык функционального программирования , Lisp , был разработан в конце 1950-х годов для IBM 700/7000 серии научных компьютеров Джоном Маккарти, работавшим в Массачусетском технологическом институте (MIT). Функции Лиспа были определены с использованием лямбда-нотации Чёрча, дополненной конструкцией метки, позволяющей использовать рекурсивные функции. Лисп первым представил множество парадигматических особенностей функционального программирования, хотя ранние Лиспы были мультипарадигмальными языками и включали поддержку многочисленных стилей программирования по мере развития новых парадигм. Более поздние диалекты, такие как Scheme и Clojure , а также ответвления, такие как Dylan и Julia , стремились упростить и рационализировать Lisp вокруг чисто функционального ядра, в то время как Common Lisp был разработан для сохранения и обновления парадигматических особенностей многочисленных старых диалектов, которые он заменил.

Язык обработки информации (IPL), 1956 год, иногда называют первым компьютерным языком функционального программирования. Это язык ассемблера для управления списками символов. У него есть понятие генератора , который представляет собой функцию, которая принимает функцию в качестве аргумента, и, поскольку это язык уровня ассемблера, код может быть данными, поэтому IPL можно рассматривать как имеющий функции более высокого порядка. Однако он в значительной степени опирается на структуру изменяющегося списка и аналогичные императивные функции.

Кеннет Э. Айверсон разработал APL в начале 1960-х годов, описанный в его книге 1962 года «Язык программирования» (англ. ISBN   9780471430148 ). APL оказала основное влияние на Джона Бэкуса FP . В начале 1990-х Айверсон и Хуэй создали J. Роджер В середине 1990-х годов Артур Уитни , ранее работавший с Айверсоном, создал K , который используется в коммерческих целях в финансовых отраслях вместе со своим Q. потомком

В середине 1960-х годов Питер Ландин изобрел машину SECD . первая абстрактная машина для функционального языка программирования, описал соответствие между АЛГОЛом 60 и лямбда-исчислением , и предложил язык программирования ISWIM .

Джон Бэкус представил FP в своей лекции на Премии Тьюринга 1977 года «Можно ли программирование освободиться от стиля фон Неймана ? Функциональный стиль и его алгебра программ». Он определяет функциональные программы как построенные иерархически посредством «комбинирования форм», позволяющих создать «алгебру программ»; на современном языке это означает, что функциональные программы следуют принципу композиционности . Статья Бэкуса популяризировала исследования в области функционального программирования, хотя в ней особое внимание уделялось программированию на уровне функций, а не стилю лямбда-исчисления, который сейчас ассоциируется с функциональным программированием.

Язык ML был создан в 1973 году Робином Милнером в Эдинбургском университете , а Дэвид Тёрнер разработал язык SASL в Университете Сент-Эндрюса . Также в Эдинбурге в 1970-х Берстолл и Дарлингтон разработали функциональный язык NPL . NPL был основан на уравнениях рекурсии Клини и впервые был использован в их работе по преобразованию программ. Затем Берстолл, МакКуин и Саннелла внедрили проверку полиморфных типов из ML, чтобы создать язык Hope . ML со временем развился в несколько диалектов, наиболее распространенными из которых сейчас являются OCaml и Standard ML .

В 1970-х годах Гай Л. Стил и Джеральд Джей Сассман разработали Scheme , как описано в Lambda Papers и учебнике 1985 года «Структура и интерпретация компьютерных программ» . Scheme был первым диалектом Lisp, который использовал лексическую область видимости и требовал оптимизации хвостовых вызовов — функций, которые поощряют функциональное программирование.

В 1980-х годах Пер Мартин-Лёф разработал интуиционистскую теорию типов (также называемую конструктивной теорией типов), которая связывала функциональные программы с конструктивными доказательствами , выраженными как зависимые типы . Это привело к появлению новых подходов к интерактивному доказательству теорем и повлияло на развитие последующих языков функционального программирования.

Ленивый функциональный язык Miranda , разработанный Дэвидом Тёрнером, первоначально появился в 1985 году и оказал сильное влияние на Haskell . Поскольку Miranda была собственностью компании, в 1987 году Haskell начал с консенсуса по формированию открытого стандарта для исследований в области функционального программирования; выпуски реализации продолжались с 1990 года.

Совсем недавно он нашел применение в таких нишах, как параметрическое САПР на языке OpenSCAD , построенном на платформе CGAL , хотя его ограничение на переназначение значений (все значения рассматриваются как константы) привело к путанице среди пользователей, незнакомых с функциональным программированием как с концепция.

Функциональное программирование продолжает использоваться в коммерческих целях.

Концепции

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

Функции первого класса и высшего порядка

Основные статьи: Функция первого класса и функция высшего порядка.

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

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

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

Чистые функции

Основная статья: Чистая функция

Чистые функции (или выражения) не имеют побочных эффектов (память или ввод-вывод). Это означает, что чистые функции обладают несколькими полезными свойствами, многие из которых можно использовать для оптимизации кода:

• Если результат чистого выражения не используется, его можно удалить, не затрагивая другие выражения.
• Если чистая функция вызывается с аргументами, которые не вызывают побочных эффектов, результат является постоянным по отношению к этому списку аргументов (иногда это называется ссылочной прозрачностью или идемпотентностью ), т. е. повторный вызов чистой функции с теми же аргументами возвращает тот же результат. (Это может позволить оптимизировать кэширование, например, мемоизацию .)
• Если между двумя чистыми выражениями нет зависимости данных, их порядок можно изменить на обратный или они могут выполняться параллельно и не могут мешать друг другу (другими словами, вычисление любого чистого выражения является потокобезопасным ).
• Если весь язык не допускает побочных эффектов, то можно использовать любую стратегию оценки; это дает компилятору свободу переупорядочивать или комбинировать вычисления выражений в программе (например, с помощью deforestation ).

Хотя большинство компиляторов императивных языков программирования обнаруживают чистые функции и выполняют исключение общих подвыражений для вызовов чистых функций, они не всегда могут сделать это для предварительно скомпилированных библиотек, которые обычно не раскрывают эту информацию, что предотвращает оптимизацию, включающую эти внешние функции. Некоторые компиляторы, такие как gcc , добавляют дополнительные ключевые слова, позволяющие программисту явно пометить внешние функции как чистые и включить такую ​​оптимизацию. Фортран 95 также позволяет обозначать функции как чистые . Добавлен С++11 constexpr ключевое слово со схожей семантикой.

Рекурсия

Основная статья: Рекурсия (информатика)

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

Стандарт языка Scheme требует , чтобы реализации поддерживали правильную хвостовую рекурсию, то есть они должны допускать неограниченное количество активных хвостовых вызовов. Правильная хвостовая рекурсия — это не просто оптимизация; это языковая функция, которая гарантирует пользователям, что они могут использовать рекурсию для выражения цикла, и это будет безопасно для пространства. Более того, вопреки названию, он учитывает все хвостовые вызовы, а не только хвостовую рекурсию. Хотя правильная хвостовая рекурсия обычно реализуется путем превращения кода в императивные циклы, реализации могут реализовывать ее другими способами. Например, Chicken намеренно поддерживает стек и позволяет ему переполниться . Однако, когда это произойдет, его сборщик мусора потребует место обратно. позволяя неограниченное количество активных хвостовых вызовов, даже если это не превращает хвостовую рекурсию в цикл.

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

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

Строгая и нестрогая оценка

Основная статья: Стратегия оценки

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

print length([2+1, 3*2, 1/0, 5-4])

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

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

Хьюз 1984 утверждает, что отложенное вычисление является механизмом улучшения модульности программы за счет разделения задач и облегчения независимой реализации производителей и потребителей потоков данных. Launchbury 1993 описывает некоторые трудности, которые создает ленивая оценка, особенно при анализе требований программы к памяти, и предлагает операционную семантику , помогающую в таком анализе. Харпер 2009 предлагает включать в один и тот же язык как строгую, так и ленивую оценку, используя систему типов языка, чтобы различать их.

Типовые системы

Основная статья: Система типов

Особенно после разработки вывода типа Хиндли-Милнера в 1970-х годах, языки функционального программирования имеют тенденцию использовать типизированное лямбда-исчисление , отклоняя все недопустимые программы во время компиляции и рискуя получить ложноположительные ошибки , в отличие от нетипизированного лямбда-исчисления , которое принимает все допустимые значения. программ во время компиляции и рискует ложноотрицательными ошибками , используемыми в Lisp и его вариантах (таких как Scheme ), поскольку они отклоняют все недопустимые программы во время выполнения, когда информации достаточно, чтобы не отклонять действительные программы. Использование алгебраических типов данных делает удобным манипулирование сложными структурами данных; наличие строгой проверки типов во время компиляции делает программы более надежными при отсутствии других методов обеспечения надежности, таких как разработка через тестирование , в то время как вывод типов освобождает программиста от необходимости вручную объявлять типы компилятору в большинстве случаев.

Некоторые ориентированные на исследования функциональные языки, такие как Coq , Agda , Cayenne и Epigram, основаны на интуиционистской теории типов , которая позволяет типам зависеть от термов. Такие типы называются зависимыми типами . Эти системы типов не имеют разрешимого вывода типов, их трудно понять и программировать. Но зависимые типы могут выражать произвольные предложения в логике высшего порядка . Таким образом, благодаря изоморфизму Карри-Говарда хорошо типизированные программы на этих языках становятся средством написания формальных математических доказательств , на основе которых компилятор может генерировать сертифицированный код . Хотя эти языки представляют в основном интерес для академических исследований (в том числе в формализованной математике ), они начали использоваться и в технике. Compcert — это компилятор подмножества языка программирования C , написанного на Coq и формально проверенного.

Ограниченная форма зависимых типов, называемая обобщенными алгебраическими типами данных (GADT), может быть реализована таким образом, чтобы обеспечить некоторые преимущества зависимо типизированного программирования, избегая при этом большинства его неудобств. GADT доступны в компиляторе Glasgow Haskell , в OCaml. и в Скале , и были предложены в качестве дополнения к другим языкам, включая Java и C#.

Ссылочная прозрачность

Основная статья: Ссылочная прозрачность

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

Рассмотрим C оператор присваивания x=x * 10, это изменяет значение, присвоенное переменной x. Допустим, начальное значение x был 1, затем два последовательных вычисления переменной x урожайность 10 и 100 соответственно. Понятно, что замена x=x * 10 с любым 10 или 100 придает программе другое значение, поэтому выражение не является ссылочно прозрачным. Фактически, операторы присваивания никогда не бывают ссылочно прозрачными.

Теперь рассмотрим другую функцию, например int plusone(int x) {return x+1;} является прозрачным, так как не меняет неявно входной сигнал x и, следовательно, не имеет таких побочных эффектов . Функциональные программы используют исключительно функции этого типа и поэтому являются ссылочно прозрачными.

Структуры данных

Основная статья: Чисто функциональная структура данных

Чисто функциональные структуры данных часто представляются иначе, чем их императивные аналоги. Например, массив с постоянным временем доступа и обновления является базовым компонентом большинства императивных языков, а многие императивные структуры данных, такие как хеш-таблица и двоичная куча , основаны на массивах. Массивы можно заменить картами или списками произвольного доступа, которые допускают чисто функциональную реализацию, но имеют логарифмическое время доступа и обновления. Чисто функциональные структуры данных обладают постоянством — свойством сохранять предыдущие версии структуры данных неизменными. В Clojure постоянные структуры данных используются как функциональная альтернатива своим императивным аналогам. Например, постоянные векторы используют деревья для частичного обновления. Вызов метода вставки приведет к созданию некоторых, но не всех узлов.

Сравнение с императивным программированием

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

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

Императивное и функциональное программирование

Следующие два примера (написанные на JavaScript ) достигают одного и того же эффекта: они умножают все четные числа в массиве на 10 и складывают их все, сохраняя окончательную сумму в переменной «result».

Традиционный императивный цикл:

const numList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let result = 0;
for (let i = 0; i < numList.length; i++) {
  if (numList[i] % 2 === 0) {
    result += numList[i] * 10;
  }
}

Функциональное программирование с функциями высшего порядка:

const result = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
               .filter(n => n % 2 === 0)
               .map(a => a * 10)
               .reduce((a, b) => a + b, 0);

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

Моделирование состояния

Есть задачи (например, поддержание баланса банковского счета), которые часто кажутся наиболее естественными для реализации с помощью государства. Чисто функциональное программирование выполняет эти задачи, а также задачи ввода-вывода, такие как прием пользовательского ввода и вывод на экран, другим способом.

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

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

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

Альтернативные методы, такие как логика Хоара и уникальность, были разработаны для отслеживания побочных эффектов в программах. Некоторые современные исследовательские языки используют системы эффектов , чтобы сделать присутствие побочных эффектов явным.

Проблемы эффективности

Функциональные языки программирования обычно менее эффективно используют процессор и память, чем императивные языки, такие как C и Pascal . Это связано с тем, что некоторые изменяемые структуры данных, такие как массивы, имеют очень простую реализацию с использованием существующего оборудования. К плоским массивам можно очень эффективно обращаться с помощью процессоров с глубокой конвейеризацией, эффективно выполнять предварительную выборку через кэши (без сложной погони за указателями ) или обрабатывать их с помощью SIMD-инструкций. Также непросто создать их столь же эффективные неизменяемые аналоги общего назначения. Для чисто функциональных языков наихудшее замедление является логарифмическим по количеству используемых ячеек памяти, поскольку изменяемая память может быть представлена ​​чисто функциональной структурой данных с логарифмическим временем доступа (например, сбалансированным деревом). Однако такое замедление не является универсальным. для программ, выполняющих интенсивные числовые вычисления, функциональные языки, такие как OCaml и Clean , лишь немного медленнее, чем C. По данным The Computer Language Benchmarks Game , Для программ, обрабатывающих большие матрицы и многомерные базы данных , были разработаны функциональные языки работы с массивами (такие как J и K ) с оптимизацией скорости.

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

Неизменяемые данные с разделением идентификаторов и состояний и схемы без общего доступа также потенциально могут быть более подходящими для одновременного и параллельного программирования благодаря уменьшению или устранению риска определенных рисков параллелизма, поскольку параллельные операции обычно являются атомарными , и это позволяет устранить необходимость в замках. Вот как например java.util.concurrent реализованы классы, где некоторые из них являются неизменяемыми вариантами соответствующих классов, не пригодными для одновременного использования. Языки функционального программирования часто имеют модель параллелизма, которая вместо общего состояния и синхронизации использует механизмы передачи сообщений (например, модель актера , где каждый актер является контейнером для состояния, поведения, дочерних актеров и очереди сообщений). в Erlang / Elixir или Akka. Этот подход распространен

Ленивые вычисления также могут ускорить работу программы, даже асимптотически, тогда как они могут замедлить ее максимум на постоянный коэффициент (однако они могут привести к утечкам памяти при неправильном использовании ). Лаунбери, 1993 г. обсуждает теоретические проблемы, связанные с утечками памяти из-за ленивых вычислений, а О'Салливан и др. 2008 год дайте несколько практических советов по их анализу и исправлению. Однако наиболее общие реализации ленивых вычислений, широко использующие разыменованный код и данные, плохо работают на современных процессорах с глубокими конвейерами и многоуровневыми кэшами (где промах в кэше может стоить сотен циклов). .

Стоимость абстракции

Некоторые языки функционального программирования могут не оптимизировать абстракции, такие как функции более высокого порядка, такие как « карта » или « фильтр », так же эффективно, как базовые императивные операции. Рассмотрим в качестве примера следующие два способа проверить, является ли 5 ​​четным числом в Clojure :

(even? 5)
(.equals (mod 5 2) 0)

При тестировании с использованием инструмента Criterium на ПК Ryzen 7900X GNU/Linux в Leiningen REPL 2.11.2, работающем на Java VM версии 22 и Clojure версии 1.11.1, первая реализация, которая реализована как:

(defn even?
  "Returns true if n is even, throws an exception if n is not an integer"
  {:added "1.0"
   :static true}
   [n] (if (integer? n)
        (zero? (bit-and (clojure.lang.RT/uncheckedLongCast n) 1))
        (throw (IllegalArgumentException. (str "Argument must be an integer: " n)))))

имеет среднее время выполнения 4,76 мс, а второй, в котором .equals представляет собой прямой вызов базового метода Java , имеет среднее время выполнения 2,8 мкс — примерно в 1700 раз быстрее. Частично это можно отнести к проверке типов и обработке исключений, задействованных в реализации even?, поэтому давайте возьмем, к примеру, библиотеку lo для Go , которая реализует различные функции высшего порядка, распространенные в функциональных языках программирования, с использованием дженериков . В тесте, предоставленном автором библиотеки, вызов map на 4% медленнее, чем аналог for цикл и имеет тот же профиль распределения , что можно объяснить различными оптимизациями компилятора, такими как встраивание .

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

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

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

JavaScript , Луа , Питон и Го с самого начала имели первоклассные функции . В 1994 году в Python была поддержка « лямбда », « карты », « сокращения » и « фильтра », а также замыканий в Python 2.2. хотя Python 3 отнес «сокращение» к functools стандартный библиотечный модуль. Первоклассные функции были представлены в других основных языках, таких как PHP 5.3, Visual Basic 9 , C# 3.0, C++11 и Kotlin .

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

В Java анонимные классы иногда могут использоваться для имитации замыканий; однако анонимные классы не всегда являются подходящей заменой замыканиям, поскольку их возможности более ограничены. Java 8 поддерживает лямбда-выражения в качестве замены некоторых анонимных классов.

В C# анонимные классы не нужны, поскольку замыкания и лямбда-выражения полностью поддерживаются. Библиотеки и расширения языка для неизменяемых структур данных разрабатываются для облегчения программирования в функциональном стиле на C#.

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

Точно так же идея неизменяемых данных из функционального программирования часто включается в императивные языки программирования. например, кортеж в Python, который представляет собой неизменяемый массив, и Object.freeze() в JavaScript.

Сравнение с логическим программированием

Логическое программирование можно рассматривать как обобщение функционального программирования, в котором функции являются частным случаем отношений. Например, функция мать(X) = Y (каждый X имеет только одну мать Y) может быть представлена ​​отношением мать(X, Y). В то время как функции имеют строгий шаблон ввода-вывода аргументов, отношения могут быть запрошены с любым шаблоном входов и выходов. Рассмотрим следующую логическую программу:

mother(charles, elizabeth).
mother(harry, diana).

Программу можно запросить, как функциональную программу, для создания матерей из детей:

?- mother(harry, X).
X = diana.
?- mother(charles, X).
X = elizabeth.

Но его также можно запросить в обратном направлении , чтобы сгенерировать дочерние элементы:

?- mother(X, elizabeth).
X = charles.
?- mother(X, diana).
X = harry.

Его даже можно использовать для генерации всех экземпляров материнского отношения:

?- mother(X, Y).
X = charles,
Y = elizabeth.
X = harry,
Y = diana.

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

maternal_grandmother(X) = mother(mother(X)).

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

maternal_grandmother(X, Y) :- mother(X, Z), mother(Z, Y).

Здесь :- означает , если и , значит и .

Однако разница между этими двумя представлениями просто синтаксическая. В Ciao Prolog отношения могут быть вложенными, как функции в функциональном программировании:

grandparent(X) := parent(parent(X)).
parent(X) := mother(X).
parent(X) := father(X).

mother(charles) := elizabeth.
father(charles) := phillip.
mother(harry) := diana.
father(harry) := charles.

?- grandparent(X,Y).
X = harry,
Y = elizabeth.
X = harry,
Y = phillip.

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

Приложения

Текстовые редакторы

Emacs , семейство текстовых редакторов с широкими возможностями расширения, использует собственный диалект Lisp для написания плагинов. первоначальный автор самой популярной реализации Emacs, GNU Emacs и Emacs Lisp, Ричард Столлман, считает Lisp одним из своих любимых языков программирования.

Helix , начиная с версии 24.03, поддерживает предварительный просмотр AST как S-выражений , которые также являются основной функцией семейства языков программирования Lisp.

Таблицы

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

Академия

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

Промышленность

Функциональное программирование используется в широком спектре промышленных приложений. Например, Erlang , который был разработан шведской компанией Ericsson в конце 1980-х годов, изначально использовался для реализации отказоустойчивых телекоммуникационных систем. но с тех пор стал популярен благодаря созданию ряда приложений в таких компаниях, как Nortel , Facebook , Électricité de France и WhatsApp . Scheme , диалект Lisp , использовался в качестве основы для нескольких приложений на ранних Apple Macintosh . компьютерах и применялся к таким проблемам, как программное обеспечение для обучения и моделирования. и управление телескопом . OCaml , появившийся в середине 1990-х годов, нашел коммерческое использование в таких областях, как финансовый анализ, проверка драйверов , программирование промышленных роботов и статический анализ встроенного программного обеспечения . Haskell , хотя изначально задумывался как исследовательский язык, также применяется в таких областях, как аэрокосмические системы, проектирование аппаратного обеспечения и веб-программирование.

Другие языки функционального программирования, которые нашли применение в промышленности, включают Scala , Ф# , Язык Вольфрам , Лисп , Стандартный ML и Кложур. Scala широко используется в области науки о данных , в то время как ClojureScript , Вяз или чистый скрипт — это некоторые из функциональных языков программирования внешнего интерфейса, используемых в производстве. Фреймворк Phoenix от Elixir также используется некоторыми относительно популярными коммерческими проектами, такими как Font Awesome или Allegro (одна из крупнейших платформ электронной коммерции в Польше). Платформа объявлений Allegro Lokalnie.

Функциональные «платформы» популярны в финансовой сфере для анализа рисков (особенно среди крупных инвестиционных банков). Факторы риска кодируются как функции, которые формируют взаимозависимые графики (категории) для измерения корреляций в рыночных сдвигах, аналогично оптимизации на основе Грёбнера , но также и для нормативных рамок, таких как комплексный анализ и обзор капитала . Учитывая использование вариаций OCaml и Caml в финансах, эти системы иногда считают связанными с категориальной абстрактной машиной . Функциональное программирование находится под сильным влиянием теории категорий .

Образование

Во многих университетах преподают функциональное программирование. Некоторые рассматривают это как вводную концепцию программирования. в то время как другие сначала обучают императивным методам программирования.

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

В частности, Scheme уже много лет является относительно популярным выбором для обучения программированию.

См. также

• Стремительная оценка
• Функциональное реактивное программирование
• Индуктивное функциональное программирование
• Список функциональных языков программирования
• Список тем функционального программирования
• Вложенная функция
• Чисто функциональное программирование

Дальнейшее чтение

• Абельсон, Хэл ; Сассман, Джеральд Джей (1985). Структура и интерпретация компьютерных программ . МТИ Пресс.
• Кузино, Ги и Мишель Мони. Функциональный подход к программированию . Кембридж, Великобритания: Издательство Кембриджского университета , 1998.
• Карри, Хаскелл Брукс и Фейс, Роберт и Крейг, Уильям. Комбинаторная логика . Том I. Издательство Северной Голландии, Амстердам, 1958.
• Карри, Хаскелл Б .; Хиндли, Дж. Роджер ; Селдин, Джонатан П. (1972). Комбинаторная логика . Том. II. Амстердам: Северная Голландия. ISBN  978-0-7204-2208-5 .
• Доминус, Марк Джейсон. Perl высшего порядка . Морган Кауфманн . 2005.
• Феллейзен, Матиас; Финдлер, Роберт; Флэтт, Мэтью; Кришнамурти, Шрирам (2018). Как разрабатывать программы . МТИ Пресс.
• Грэм, Пол. Общий ANSI LISP . Энглвуд Клиффс, Нью-Джерси: Прентис Холл , 1996.
• МакЛеннан, Брюс Дж. Функциональное программирование: практика и теория . Аддисон-Уэсли, 1990.
• Майклсон, Грег (10 апреля 2013 г.). Введение в функциональное программирование с помощью лямбда-исчисления . Курьерская компания. ISBN  978-0-486-28029-5 .
• О'Салливан, Брайан; Стюарт, Дон; Герцен, Джон (2008). Реальный мир Haskell . О'Рейли.
• Пратт, Терренс В. и Марвин Виктор Зелковиц . Языки программирования: проектирование и реализация . 3-е изд. Энглвуд Клиффс, Нью-Джерси: Прентис Холл , 1996.
• Салус, Питер Х. Функциональные и логические языки программирования . Том. 4 Справочника по языкам программирования. Индианаполис, Индиана: Техническое издательство Macmillan , 1998.
• Томпсон, Саймон. Haskell: Мастерство функционального программирования . Харлоу, Англия: Addison-Wesley Longman Limited , 1996.

Внешние ссылки

• Форд, Нил. «Функциональное мышление» . Проверено 10 ноября 2021 г.
• Ахмечет, Слава (19 июня 2006 г.). «defmacro — функциональное программирование для всех нас» . Проверено 24 февраля 2013 г. Введение
• Функциональное программирование на Python (Дэвид Мерц): часть 1 , часть 2 , часть 3