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

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

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

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

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

Функциональное программирование уходит корнями в академия, развивающиеся из лямбда-исчисление, формальная система вычислений, основанная только на функциях. Функциональное программирование исторически было менее популярным, чем императивное программирование, но многие функциональные языки сегодня находят применение в промышленности и образовании, включая Common Lisp, Схема,[3][4][5][6] Clojure, Язык Wolfram Language,[7][8] Ракетка,[9] Erlang,[10][11][12] OCaml,[13][14] Haskell,[15][16] и F #.[17][18] Функциональное программирование также является ключом к некоторым языкам, которые добились успеха в определенных областях, например р в статистике,[19][20] J, K и Q в финансовом анализе и XQuery /XSLT за XML.[21][22] Декларативные языки, зависящие от предметной области, например SQL и Лекс /Yacc использовать некоторые элементы функционального программирования, например, запретить изменяемые значения.[23] Кроме того, многие другие языки программирования поддерживают программирование в функциональном стиле или имеют реализованные функции функционального программирования, такие как C ++ 11, Котлин,[24] Perl,[25] PHP,[26] Python,[27] Раку,[28] и Scala.[29]

История

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

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

Первый функциональный язык программирования, LISP, был разработан в конце 1950-х годов для IBM 700/7000 серии научных компьютеров Джон Маккарти в то время как в Массачусетский Институт Технологий (Массачусетский технологический институт).[33] Функции LISP были определены с использованием лямбда-нотации Черча, расширенной конструкцией метки, позволяющей рекурсивный функции.[34] Lisp первым представил многие парадигматические особенности функционального программирования, хотя ранние Lisp были мультипарадигмальные языки, и включил поддержку множества стилей программирования по мере развития новых парадигм. Более поздние диалекты, такие как Схема и Clojure, и ответвления, такие как Дилан и Юля, стремился упростить и рационализировать Лисп вокруг чисто функционального ядра, в то время как Common Lisp был разработан, чтобы сохранить и обновить парадигматические особенности многочисленных старых диалектов, которые он заменил.[35]

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

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

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

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

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

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

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

Совсем недавно он нашел применение в таких нишах, как параметрическая CAD любезно предоставлено OpenSCAD язык, построенный на основе геометрии CSG, хотя его ограничение на переназначение значений (все значения рассматриваются как константы) привело к путанице среди пользователей, которые не знакомы с концепцией функционального программирования.[41]

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

Концепции

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

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

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

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

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

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

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

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

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

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

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

Рекурсия

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

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

В Схема языковой стандарт требует, чтобы реализации поддерживали правильную хвостовую рекурсию, то есть они должны разрешать неограниченное количество активных хвостовых вызовов.[47][48] Правильная хвостовая рекурсия - это не просто оптимизация; это языковая функция, которая гарантирует пользователям, что они могут использовать рекурсию для выражения цикла, и это будет безопасно для места.[49] Более того, вопреки своему названию, он учитывает все хвостовые вызовы, а не только хвостовую рекурсию. Хотя правильная хвостовая рекурсия обычно реализуется путем превращения кода в императивные циклы, реализации могут реализовывать это другими способами. Например, КУРИЦА намеренно поддерживает стек и позволяет переполнение стека. Однако, когда это происходит, его уборщик мусора потребует место обратно,[50] разрешает неограниченное количество активных хвостовых вызовов, даже если это не превращает хвостовую рекурсию в цикл.

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

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

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

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

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

длина печати ([2 + 1, 3 * 2, 1/0, 5-4])

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

Обычная стратегия реализации ленивого вычисления на функциональных языках: сокращение графика.[52] Ленивое вычисление используется по умолчанию в нескольких чисто функциональных языках, включая Миранда, Чистый, и Haskell.

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

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

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

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

Некоторые функциональные языки, ориентированные на исследования, такие как Coq, Агда, Cayenne, и Эпиграмма основаны на интуиционистская теория типов, что позволяет типам зависеть от условий. Такие типы называются зависимые типы. Эти системы типов не имеют разрешимого вывода типов, их трудно понять и использовать для программирования.[55][56][57][58] Но зависимые типы могут выражать произвольные предложения в логика предикатов. Сквозь Изоморфизм Карри – Ховарда, то хорошо типизированные программы на этих языках становятся средством написания формальных математические доказательства из которого компилятор может генерировать сертифицированный код. Хотя эти языки в основном представляют интерес для академических исследований (в том числе в формализованная математика ), их начали использовать и в технике. Compcert это компилятор для подмножества Язык программирования C который написан на Coq и официально проверен.[59]

Ограниченная форма зависимых типов, называемая обобщенные алгебраические типы данных (GADT) могут быть реализованы таким образом, чтобы обеспечить некоторые преимущества программирования с зависимой типизацией, избегая при этом большей части его неудобств.[60] GADT доступны в Компилятор Glasgow Haskell, в OCaml (начиная с версии 4.00) и в Scala (как «case-классы») и были предложены в качестве дополнения к другим языкам, включая Java и C #.[61]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

const numList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];позволять результат = 0;за (позволять я = 0; я < numList.длина; я++) {  если (numList[я] % 2 === 0) {    результат += numList[я] * 10;  }}

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

const результат = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]               .фильтр(п => п % 2 === 0)               .карта(а => а * 10)               .уменьшать((а, б) => а + б);

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

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

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

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

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

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

Вопросы эффективности

Функциональные языки программирования обычно менее эффективно используют ЦПУ и память, чем императивные языки, такие как C и Паскаль.[67] Это связано с тем, что некоторые изменяемые структуры данных, такие как массивы, имеют очень простую реализацию с использованием существующего оборудования. Доступ к плоским массивам может быть очень эффективным с помощью ЦП с глубоким конвейером, предварительно загруженных через кеши (без сложных погоня за указателем ) или обрабатывается с помощью инструкций SIMD. Также непросто создать их не менее эффективные неизменяемые аналоги общего назначения. Для чисто функциональных языков в наихудшем случае замедление является логарифмическим по количеству используемых ячеек памяти, поскольку изменяемая память может быть представлена ​​чисто функциональной структурой данных с логарифмическим временем доступа (например, сбалансированным деревом).[68] Однако такие замедления не универсальны. Для программ, выполняющих интенсивные численные вычисления, функциональные языки, такие как OCaml и Чистый лишь немного медленнее, чем C согласно Игра "Тесты компьютерного языка".[69] Для программ, обрабатывающих большие матрицы и многомерный базы данных, множество функциональные языки (такие как J и K ) были разработаны с оптимизацией скорости.

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

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

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

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

JavaScript, Lua[74] и Python имел функции первого класса с момента их создания.[75] Python поддерживает "лямбда ", "карта ", "уменьшать ", и "фильтр "в 1994 году, а также закрытия в Python 2.2,[76] хотя Python 3 отнес "сокращение" к functools стандартный библиотечный модуль.[77] Первоклассные функции были введены в другие основные языки, такие как PHP 5.3, Visual Basic 9, C # 3.0, C ++ 11, и Котлин.[24][нужна цитата ]

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

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

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

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

Точно так же идея неизменяемых данных из функционального программирования часто включается в императивные языки программирования,[81] например кортеж в Python, который является неизменяемым массивом.

Приложения

Академия

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

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

Функциональное программирование нашло применение в самых разных промышленных приложениях. Например, Erlang, который был разработан Шведский Компания Ericsson в конце 1980-х годов изначально использовался для реализации отказоустойчивой телекоммуникации системы,[11] но с тех пор стал популярным для создания ряда приложений в таких компаниях, как Nortel, Facebook, Électricité de France и WhatsApp.[10][12][82][83][84] Схема, диалект Лисп, был использован в качестве основы для нескольких приложений на ранних Apple Macintosh компьютеры,[3][4] и был применен к таким задачам, как обучение программное обеспечение для моделирования[5] и телескоп контроль.[6] OCaml, который был представлен в середине 1990-х годов, нашел коммерческое использование в таких областях, как финансовый анализ,[13] Водитель проверка, промышленная робот программирование и статический анализ встроенное программное обеспечение.[14] Haskell хотя изначально задумывался как исследовательский язык,[16] также применяется рядом компаний в таких областях, как аэрокосмические системы, проектирование оборудования и веб-программирование.[15][16]

Другие языки функционального программирования, которые нашли применение в промышленности, включают: Scala,[85] F #,[17][18] Язык Wolfram Language,[7] Лисп,[86] Стандартный ML,[87][88] и Clojure.[89]

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

Образование

Много университеты преподают или преподавали функциональное программирование в рамках своих студент Степени информатики.[90][91][92][93] Некоторые используют это как введение в программирование,[93] в то время как другие преподают его после обучения императивному программированию.[92][94]

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

Смотрите также

Рекомендации

  1. ^ Худак, Павел (Сентябрь 1989 г.). «Концепция, эволюция и применение языков функционального программирования» (PDF). Опросы ACM Computing. 21 (3): 359–411. Дои:10.1145/72551.72554. S2CID  207637854.
  2. ^ а б Хьюз, Джон (1984). «Почему так важно функциональное программирование».CS1 maint: ref = harv (связь)
  3. ^ а б Клингер, Уилл (1987). «Многозадачность и MacScheme». MacTech. 3 (12). Получено 2008-08-28.
  4. ^ а б Хартхаймер, Энн (1987). «Программирование текстового редактора в MacScheme + Toolsmith». MacTech. 3 (1). Архивировано из оригинал на 2011-06-29. Получено 2008-08-28.
  5. ^ а б Кидд, Эрик. Тренинг по борьбе с терроризмом по схеме. CUFP 2007. Получено 2009-08-26.
  6. ^ а б Клейс, Ричард. Схема в космосе. CUFP 2006. Получено 2009-08-26.
  7. ^ а б «Руководство по языку Wolfram: функциональное программирование». 2015. Получено 2015-08-24.
  8. ^ «Функциональный и процедурный язык программирования». Кафедра прикладной математики. Колорадский университет. Архивировано из оригинал 13 ноября 2007 г.
  9. ^ «Сценарии на основе состояний в Uncharted 2» (PDF). Архивировано из оригинал (PDF) на 2012-12-15. Получено 2011-08-08.
  10. ^ а б «Кто использует Erlang для разработки продуктов?». Часто задаваемые вопросы об Erlang. Получено 2018-04-27.
  11. ^ а б Армстронг, Джо (июнь 2007 г.). История Erlang. Третья конференция ACM SIGPLAN по истории языков программирования. Сан-Диего, Калифорния. Дои:10.1145/1238844.1238850.
  12. ^ а б Ларсон, Джим (март 2009 г.). «Эрланг для параллельного программирования». Коммуникации ACM. 52 (3): 48. Дои:10.1145/1467247.1467263. S2CID  524392.
  13. ^ а б Минский, Ярон; Недели, Стивен (июль 2008 г.). «Caml Trading - опыт функционального программирования на Уолл-стрит». Журнал функционального программирования. 18 (4): 553–564. Дои:10.1017 / S095679680800676X. Получено 2008-08-27.
  14. ^ а б Лерой, Ксавье. Некоторые виды использования Caml в промышленности (PDF). CUFP 2007. Получено 2009-08-26.
  15. ^ а б «Haskell в индустрии». Haskell Вики. Получено 2009-08-26. Haskell имеет широкий спектр коммерческого применения: от аэрокосмической и оборонной до финансовых, веб-стартапов, фирм по проектированию оборудования и производителей газонокосилок.
  16. ^ а б c Худак, Павел; Hughes, J .; Jones, S.P .; Уодлер, П. (июнь 2007 г.). История Haskell: лень с классом. Третья конференция ACM SIGPLAN по истории языков программирования. Сан-Диего, Калифорния. Дои:10.1145/1238844.1238856. Получено 2013-09-26.
  17. ^ а б Мэнселл, Ховард (2008). Количественные финансы на F #. CUFP 2008. Получено 2009-08-29.
  18. ^ а б Пик, Алекс (2009). Первое существенное бизнес-приложение на F #. CUFP 2009. Архивировано с оригинал на 2009-10-17. Получено 2009-08-29.
  19. ^ «Программа конференции useR! 2006 включает доклады о коммерческом использовании R». R-project.org. 2006-06-08. Получено 2011-06-20.
  20. ^ Чемберс, Джон М. (1998). Программирование с данными: руководство по языку S. Springer Verlag. С. 67–70. ISBN  978-0-387-98503-9.
  21. ^ Новачев, Дмитрий. «Функциональный язык программирования XSLT - Доказательство на примерах». Получено 27 мая, 2006.
  22. ^ Мерц, Дэвид. «Парадигмы программирования XML (часть четвертая): подход функционального программирования к обработке XML». IBM developerWorks. Получено 27 мая, 2006.
  23. ^ Чемберлин, Дональд Д.; Бойс, Раймонд Ф. (1974). «SEQUEL: структурированный английский язык запросов». Труды 1974 ACM SIGFIDET: 249–264.
  24. ^ а б «Функциональное программирование - язык программирования Kotlin». Котлин. Получено 2019-05-01.
  25. ^ Dominus, Марк Дж. (2005). Perl высшего порядка. Морган Кауфманн. ISBN  978-1-55860-701-9.
  26. ^ Холивелл, Саймон (2014). Функциональное программирование на PHP. php [архитектор]. ISBN  9781940111056.
  27. ^ The Cain Gang Ltd. "Метаклассы Python: Кто? Почему? Когда?" (PDF). Архивировано из оригинал (PDF) 30 мая 2009 г.. Получено 27 июн 2009.
  28. ^ Vanderbauwhede, Вим. «Более чистый код с функциональным программированием». Архивировано из оригинал 11 сен 2020. Получено 6 октября 2020.
  29. ^ «Эффективная Скала». Scala вики. Получено 2012-02-21. Эффективная Scala.
  30. ^ Тьюринг, А. М. (1937). «Вычислимость и λ-определимость». Журнал символической логики. Издательство Кембриджского университета. 2 (4): 153–163. Дои:10.2307/2268280. JSTOR  2268280.
  31. ^ Хаскелл Брукс Карри; Роберт Фейс (1958). Комбинаторная логика. Издательская компания Северной Голландии. Получено 10 февраля 2013.
  32. ^ Церковь, А. (1940). «Формулировка простой теории типов». Журнал символической логики. 5 (2): 56–68. Дои:10.2307/2266170. JSTOR  2266170.
  33. ^ Маккарти, Джон (Июнь 1978 г.). История Лиспа (PDF). История языков программирования. Лос Анджелес, Калифорния. С. 173–185. Дои:10.1145/800025.808387.
  34. ^ Джон Маккарти (1960). «Рекурсивные функции символьных выражений и их машинное вычисление, Часть I.» (PDF). Коммуникации ACM. ACM Нью-Йорк, Нью-Йорк, США. 3 (4): 184–195. Дои:10.1145/367177.367199. S2CID  1489409.
  35. ^ Гай Л. Стил; Ричард П. Габриэль (февраль 1996 г.). Эволюция Лиспа (PDF). В ACM / SIGPLAN Вторая история языков программирования. С. 233–330. Дои:10.1145/234286.1057818. ISBN  978-0-201-89502-5. S2CID  47047140.
  36. ^ Воспоминания о Герберт А. Саймон (1991), Модели моей жизни стр.189-190 ISBN  0-465-04640-1 утверждает, что он, Эл Ньюэлл и Клифф Шоу «... обычно считаются родителями [области] искусственного интеллекта», за то, что они написали Теоретик логики, программа, доказывающая теоремы из Principia Mathematica автоматически. Для этого им пришлось изобрести язык и парадигму, которые, если смотреть ретроспективно, включают функциональное программирование.
  37. ^ Бэкус, Дж. (1978). «Можно ли освободить программирование от стиля фон Неймана ?: Функциональный стиль и его алгебра программ». Коммуникации ACM. 21 (8): 613–641. Дои:10.1145/359576.359579.
  38. ^ Р.М. Берстолл. Соображения по дизайну для функционального языка программирования. Приглашенный доклад, Тр. Infotech State of the Art Conf. «Программная революция», Копенгаген, 45–57 (1977).
  39. ^ Р.М. Берстолл и Дж. Дарлингтон. Система трансформации для разработки рекурсивных программ. Журнал Ассоциации вычислительной техники 24 (1): 44–67 (1977)
  40. ^ Р.М. Берстолл, Д. Маккуин и Д.Т. Саннелла. НАДЕЖДА: экспериментальный прикладной язык. Proc. Конференция LISP 1980 г., Стэнфорд, 136–143 (1980).
  41. ^ "Сделайте обнаружение assign () проще!". OpenSCAD.
  42. ^ Питер Брайт (13 марта 2018 г.). «Разработчики любят модные новые языки, но зарабатывают больше с функциональным программированием». Ars Technica.
  43. ^ Джон Леонард (24 января 2017 г.). «Скрытый рост функционального программирования». Вычислительная техника.
  44. ^ Лео Чунг (9 мая 2017 г.). "Функциональное программирование лучше для вашего стартапа?". InfoWorld.
  45. ^ Понтан, Дик. «Функциональное программирование достигает зрелости». BYTE.com (август 1994 г.). Архивировано из оригинал на 2006-08-27. Получено 31 августа, 2006.
  46. ^ а б "ISO / IEC JTC 1 / SC 22 / WG5 / N2137". Международная организация по стандартизации. 6 июля 2017 г. Цитировать журнал требует | журнал = (помощь)
  47. ^ «Пересмотренный отчет ^ 6 по алгоритмической языковой схеме». R6rs.org. Получено 2013-03-21.
  48. ^ «Пересмотренный отчет ^ 6 об алгоритмической языковой схеме - обоснование». R6rs.org. Получено 2013-03-21.
  49. ^ Клингер, Уильям (1998). «Правильная хвостовая рекурсия и эффективность использования пространства». Материалы конференции ACM SIGPLAN 1998 по проектированию и реализации языков программирования - PLDI '98. С. 174–185. Дои:10.1145/277650.277719. ISBN  0897919874. S2CID  16812984.
  50. ^ Бейкер, Генри (1994). "Минусы не должны ПРОТИВ его аргументов, Часть II: Чейни о M.T.A."
  51. ^ Тернер, Д.А. (2004-07-28). «Полное функциональное программирование». Журнал универсальных компьютерных наук. 10 (7): 751–768. Дои:10.3217 / jucs-010-07-0751.
  52. ^ Реализация языков функционального программирования. Саймон Пейтон Джонс, опубликованный Prentice Hall, 1987
  53. ^ а б Джон Лаанчбери (1993). «Естественная семантика для ленивых оценок». CiteSeerX  10.1.1.35.2016. Цитировать журнал требует | журнал = (помощь)
  54. ^ Роберт В. Харпер (2009). Практические основы языков программирования (PDF). Архивировано из оригинал (PDF) на 2016-04-07.
  55. ^ Юэ, Жерар П. (1973). «Неразрешимость объединения в логике третьего порядка». Информация и контроль. 22 (3): 257–267. Дои:10.1016 / с0019-9958 (73) 90301-х.
  56. ^ Юэ, Жерар (сентябрь 1976 г.). Resolution d'Equations dans des Langages d'Ordre 1,2, ... ω (Доктор философии) (на французском языке). Парижский университет VII.
  57. ^ Юэ, Жерар (2002). «Объединение высшего порядка 30 лет спустя» (PDF). In Carreño, V .; Muñoz, C .; Тахар, С. (ред.). Материалы 15-й Международной конференции TPHOL. LNCS. 2410. Springer. С. 3–12.
  58. ^ Уэллс, Дж. Б. (1993). «Типизация и проверка типов в лямбда-исчислении второго порядка эквивалентны и неразрешимы». Tech. Реп. 93-011. CiteSeerX  10.1.1.31.3590.
  59. ^ Лерой, Ксавье (17 сентября 2018 г.). "Компилятор, проверенный Compcert".
  60. ^ Пейтон Джонс, Саймон; Витиниотис, Димитриос; Вейрих, Стефани; Джеффри Вашберн (апрель 2006 г.). «Простой вывод типа на основе унификации для GADT». Icfp 2006: 50–61.
  61. ^ Кеннеди, Эндрю; Руссо, Клаудио (октябрь 2005 г.). Обобщенные алгебраические типы данных и объектно-ориентированное программирование (PDF). OOPSLA. Сан-Диего, Калифорния. ISBN  9781595930316. Архивировано из оригинал (PDF) 29 декабря 2006 г. источник цитирования
  62. ^ Хьюз, Джон. «Почему так важно функциональное программирование» (PDF). Технологический университет Чалмерса.
  63. ^ Чисто функциональные структуры данных к Крис Окасаки, Издательство Кембриджского университета, 1998, ISBN  0-521-66350-4
  64. ^ L’orange, Жан Никлас. "polymatheia - понимание постоянного вектора Clojure, pt. 1". Полиматея. Получено 2018-11-13.
  65. ^ Ньюберн, Дж. «Все о монадах: подробное руководство по теории и практике монадического программирования на Haskell». Получено 2008-02-14.
  66. ^ «Тринадцать способов взглянуть на черепаху». fF # для развлечения и прибыли. Получено 2018-11-13.
  67. ^ Полсон, Ларри С. (28 июня 1996 г.). ML для работающего программиста. Издательство Кембриджского университета. ISBN  978-0-521-56543-1. Получено 10 февраля 2013.
  68. ^ Спивак, Даниэль (26 августа 2008 г.). «Реализация постоянных векторов в Scala». Фиксация кода.
  69. ^ «Какие программы самые быстрые? | Компьютерная языковая тестовая игра». benchmarksgame.alioth.debian.org. Архивировано из оригинал на 2013-05-20. Получено 2011-06-20.
  70. ^ Игорь Печанский; Вивек Саркар (2005). «Спецификация неизменяемости и ее приложения». Параллелизм и вычисления: практика и опыт. 17 (5–6): 639–662. Дои:10.1002 / cpe.853.
  71. ^ «Глава 25. Профилирование и оптимизация». Book.realworldhaskell.org. Получено 2011-06-20.
  72. ^ Хартель, Питер; Хенк Мюллер; Хью Глейзер (март 2004 г.). "Функциональный опыт C" (PDF). Журнал функционального программирования. 14 (2): 129–135. Дои:10.1017 / S0956796803004817.; Дэвид Мертц. «Функциональное программирование на Python, часть 3». IBM developerWorks. Архивировано из оригинал на 2007-10-16. Получено 2006-09-17.(Часть 1, Часть 2 )
  73. ^ "Функции - язык программирования D 2.0". Цифровой Марс. 30 декабря 2012 г.
  74. ^ "Неофициальный FAQ по Lua (uFAQ)".
  75. ^ Айх, Брендан (3 апреля 2008 г.). «Популярность».
  76. ^ ван Россум, Гвидо (2009-04-21). "Истоки" функциональных "возможностей Python". Получено 2012-09-27.
  77. ^ "functools - Функции высшего порядка и операции с вызываемыми объектами". Фонд программного обеспечения Python. 2011-07-31. Получено 2011-07-31.
  78. ^ Скарсауне, Мартин (2008). Проект порта Java SICS Автоматический перевод большой объектно-ориентированной системы с Smalltalk на Java.
  79. ^ Гослинг, Джеймс. «Закрытие». Джеймс Гослинг: на Явской дороге. Oracle. Архивировано из оригинал на 2013-04-14. Получено 11 мая 2013.
  80. ^ Уильямс, Майкл (8 апреля 2013 г.). «Краткое руководство по Java SE 8 Lambda».
  81. ^ Блох, Джошуа (2008). «Пункт 15: Минимизируйте изменчивость». Эффективная Java (Второе изд.). Эддисон-Уэсли. ISBN  978-0321356680.
  82. ^ Пиро, Кристофер (2009). Функциональное программирование в Facebook. CUFP 2009. Архивировано с оригинал на 2009-10-17. Получено 2009-08-29.
  83. ^ «Sim-Diasca: крупномасштабный механизм параллельного моделирования дискретных событий на Erlang». Ноябрь 2011 г.
  84. ^ 1 миллион это так 2011 год // Блог WhatsApp, 06.01.2012: «последняя важная часть нашей инфраструктуры - Erlang»
  85. ^ Момтахан, Ли (2009). Scala в EDF Trading: реализация предметно-ориентированного языка для определения производных цен с помощью Scala. CUFP 2009. Архивировано с оригинал на 2009-10-17. Получено 2009-08-29.
  86. ^ Грэм, Пол (2003). "Превосходя средний показатель". Получено 2009-08-29.
  87. ^ Симс, Стив (2006). Создание стартапа со стандартным машинным обучением (PDF). CUFP 2006. Получено 2009-08-29.
  88. ^ Лаурикари, Вилле (2007). Функциональное программирование в безопасности связи. CUFP 2007. Получено 2009-08-29.
  89. ^ Лоример, Р. Дж. (19 января 2009 г.). "Анонсировано приложение Clojure Live Production". InfoQ.
  90. ^ «Функциональное программирование: 2019-2020». Оксфордский университет, факультет компьютерных наук. Получено 28 апреля 2020.
  91. ^ "Программирование I (Haskell)". Имперский колледж Лондона, факультет вычислительной техники. Получено 28 апреля 2020.
  92. ^ а б "Бакалавриат по информатике - Модули". Получено 28 апреля 2020.
  93. ^ а б Абельсон, Хэл; Сассман, Джеральд Джей (1985). «Предисловие ко второму изданию». Структура и интерпретация компьютерных программ (2-е изд.). MIT Press.
  94. ^ Джон ДеНеро (осень 2019). "Компьютерные науки 61A, Беркли". Департамент электротехники и компьютерных наук, Беркли. Получено 2020-08-14.
  95. ^ Эммануэль Шанцер из Bootstrap взял интервью в телешоу Triangulation на TWiT.tv сеть

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

внешняя ссылка