✖


Jump to content

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

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

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

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

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

Функциональное программирование уходит корнями в академические круги , развившись из лямбда-исчисления , формальной системы вычислений, основанной только на функциях. Функциональное программирование исторически было менее популярным, чем императивное программирование, но многие функциональные языки сегодня находят применение в промышленности и образовании, включая Common Lisp , Scheme , [3] [4] [5] [6] Clojure , Язык Вольфрам , [7] [8] Ракетка , [9] Эрланг , [10] [11] [12] Эликсир , [13] ОКамл , [14] [15] Хаскелл , [16] [17] и Фа# . [18] [19] Lean — это функциональный язык программирования, обычно используемый для проверки математических теорем. [20] Функциональное программирование также является ключом к некоторым языкам, которые добились успеха в определенных областях, таких как JavaScript в Интернете, [21] R в статистике, [22] [23] J , K и Q в финансовом анализе и XQuery / XSLT для XML . [24] [25] Декларативные языки, специфичные для предметной области, такие как SQL и Lex / Yacc, используют некоторые элементы функционального программирования, например, не позволяют изменять изменяемые значения . [26] Кроме того, многие другие языки программирования поддерживают программирование в функциональном стиле или реализуют функции функционального программирования, такие как C++11 , C# , [27] Котлин , [28] Перл , [29] PHP , [30] Питон , [31] Идти , [32] Ржавчина , [33] Раку , [34] Скала , [35] и Java (начиная с Java 8) . [36]

История [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чистые функции [ править ]

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

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

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

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

Рекурсия [ править ]

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

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

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

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

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

Строгая и нестрогая оценка [ править ]

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

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

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

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

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

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

Типовые системы [ править ]

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

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

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

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

Ссылочная прозрачность [ править ]

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

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

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

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

Структуры данных [ править ]

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

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

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

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

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

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

Следующие два примера (написанные на 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 реализует их с использованием монад , полученных из теории категорий . [80] Монады предлагают способ абстрагировать определенные типы вычислительных шаблонов, включая (но не ограничиваясь) моделирование вычислений с изменяемым состоянием (и другими побочными эффектами, такими как ввод-вывод) императивным образом без потери чистоты. Хотя существующие монады можно легко применить в программе при наличии соответствующих шаблонов и примеров, многим студентам трудно понять их концептуально, например, когда их просят определить новые монады (что иногда необходимо для определенных типов библиотек). [81]

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

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

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

Проблемы с эффективностью [ править ]

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

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

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

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

Стоимость абстракции [ править ]

Некоторые языки функционального программирования могут не оптимизировать абстракции, такие как функции более высокого порядка, такие как « карта » или « фильтр », так же эффективно, как базовые императивные операции. Рассмотрим в качестве примера следующие два способа проверить, является ли 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 цикл и имеет тот же профиль распределения , [94] что можно объяснить различными оптимизациями компилятора, такими как встраивание . [95]

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

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

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

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

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

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

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

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

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

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

Логическое программирование можно рассматривать как обобщение функционального программирования, в котором функции являются частным случаем отношений. [109] Например, функция мать(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 отношения могут быть вложенными, как функции в функциональном программировании: [110] 

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 одним из своих любимых языков программирования. [111]

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

Таблицы [ править ]

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

Академия [ править ]

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

Промышленность [ править ]

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

Другие языки функционального программирования, которые нашли применение в промышленности, включают Scala , [118] Ф# , [18] [19] Язык Вольфрам , [7] Лисп , [119] Стандартный ML [120] [121] и Кложур. [122] Scala широко используется в области науки о данных , [123] в то время как ClojureScript , [124] Вяз [125] или чистый скрипт [126] — это некоторые из функциональных языков программирования внешнего интерфейса, используемых в производстве. Фреймворк Phoenix от Elixir также используется некоторыми относительно популярными коммерческими проектами, такими как Font Awesome или Allegro (одна из крупнейших платформ электронной коммерции в Польше). [127] Платформа объявлений Allegro Lokalnie. [128]

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

Образование [ править ]

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

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

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

См. также [ править ]

Примечания и ссылки [ править ]

  1. ^ Худак, Пол (сентябрь 1989 г.). «Концепция, эволюция и применение языков функционального программирования» (PDF) . Обзоры вычислительной техники ACM . 21 (3): 359–411. дои : 10.1145/72551.72554 . S2CID   207637854 . Архивировано из оригинала (PDF) 31 января 2016 г. Проверено 10 августа 2013 г.
  2. ↑ Перейти обратно: Перейти обратно: а б Хьюз, Джон (1984). «Почему функциональное программирование имеет значение» .
  3. ↑ Перейти обратно: Перейти обратно: а б Клингер, Уилл (1987). «Многозадачность и MacScheme» . МакТех . 3 (12) . Проверено 28 августа 2008 г.
  4. ↑ Перейти обратно: Перейти обратно: а б Хартхаймер, Энн (1987). «Программирование текстового редактора в MacScheme+Toolsmith» . МакТех . 3 (1). Архивировано из оригинала 29 июня 2011 г. Проверено 28 августа 2008 г.
  5. ↑ Перейти обратно: Перейти обратно: а б Кидд, Эрик. Схема обучения реагированию на терроризм . CUFP 2007. Архивировано из оригинала 21 декабря 2010 г. Проверено 26 августа 2009 г.
  6. ↑ Перейти обратно: Перейти обратно: а б Клейс, Ричард. Схема в космосе . CUFP 2006. Архивировано из оригинала 27 мая 2010 г. Проверено 26 августа 2009 г.
  7. ↑ Перейти обратно: Перейти обратно: а б «Руководство по языку Wolfram: функциональное программирование» . 2015 . Проверено 24 августа 2015 г.
  8. ^ «Функциональный и процедурный язык программирования» . Кафедра прикладной математики . Университет Колорадо. Архивировано из оригинала 13 ноября 2007 г. Проверено 28 августа 2006 г.
  9. ^ «Сценарии на основе состояния в Uncharted 2» (PDF) . Архивировано из оригинала (PDF) 15 декабря 2012 г. Проверено 8 августа 2011 г.
  10. ↑ Перейти обратно: Перейти обратно: а б «Кто использует Erlang для разработки продуктов?» . Часто задаваемые вопросы об Эрланге . Проверено 27 апреля 2018 г.
  11. ↑ Перейти обратно: Перейти обратно: а б Армстронг, Джо (июнь 2007 г.). «История Эрланга». Материалы третьей конференции ACM SIGPLAN по истории языков программирования . Третья конференция ACM SIGPLAN по истории языков программирования. Сан-Диего, Калифорния. дои : 10.1145/1238844.1238850 . ISBN  9781595937667 .
  12. ↑ Перейти обратно: Перейти обратно: а б Ларсон, Джим (март 2009 г.). «Эрланг для параллельного программирования» . Коммуникации АКМ . 52 (3): 48. дои : 10.1145/1467247.1467263 . S2CID   524392 .
  13. ^ «Язык программирования Эликсир» . Проверено 14 февраля 2021 г.
  14. ↑ Перейти обратно: Перейти обратно: а б Мински, Ярон; Уикс, Стивен (июль 2008 г.). «Caml Trading — опыт функционального программирования на Уолл-стрит» . Журнал функционального программирования . 18 (4): 553–564. дои : 10.1017/S095679680800676X . S2CID   30955392 .
  15. ↑ Перейти обратно: Перейти обратно: а б Лерой, Ксавье. Некоторые варианты использования Caml в промышленности (PDF) . CUFP 2007. Архивировано из оригинала (PDF) 8 октября 2011 г. Проверено 26 августа 2009 г.
  16. ↑ Перейти обратно: Перейти обратно: а б «Хаскелл в промышленности» . Хаскелл Вики . Проверено 26 августа 2009 г. Haskell имеет широкий спектр коммерческого использования: от аэрокосмической и оборонной промышленности до финансов, веб-стартапов, фирм по разработке оборудования и производителей газонокосилок.
  17. ↑ Перейти обратно: Перейти обратно: а б с Худак, Павел ; Хьюз, Дж.; Джонс, СП; Уодлер, П. (июнь 2007 г.). История Haskell: лень с классами . Третья конференция ACM SIGPLAN по истории языков программирования. Сан-Диего, Калифорния. дои : 10.1145/1238844.1238856 . Проверено 26 сентября 2013 г.
  18. ↑ Перейти обратно: Перейти обратно: а б Мэнселл, Ховард (2008). Количественные финансы в F# . CUFP 2008. Архивировано из оригинала 8 июля 2015 г. Проверено 29 августа 2009 г.
  19. ↑ Перейти обратно: Перейти обратно: а б Пик, Алекс (2009). Первая существенная сфера бизнес-приложений на F# . CUFP 2009. Архивировано из оригинала 17 октября 2009 г. Проверено 29 августа 2009 г.
  20. ^ https://pp.ipd.kit.edu/uploads/publikationen/demoura21lean4.pdf
  21. ^ комментарии, 27 июня 2017 г. Matt Banz Feed 603up 2. «Введение в функциональное программирование на JavaScript» . Opensource.com . Проверено 9 января 2021 г. {{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка )
  22. ^ «В расписание конференции useR! 2006 включены доклады о коммерческом использовании R» . R-project.org. 8 июня 2006 г. Проверено 20 июня 2011 г.
  23. ^ Чемберс, Джон М. (1998). Программирование с данными: Руководство по языку S. Спрингер Верлаг. стр. 67–70. ISBN  978-0-387-98503-9 .
  24. ^ Новатчев, Дмитрий. «Язык функционального программирования XSLT — доказательство на примерах» . Проверено 27 мая 2006 г.
  25. ^ Мерц, Дэвид. «Парадигмы программирования XML (часть четвертая): подход функционального программирования к обработке XML» . IBM DeveloperWorks . Проверено 27 мая 2006 г.
  26. ^ Чемберлин, Дональд Д .; Бойс, Раймонд Ф. (1974). «ПРОДОЛЖЕНИЕ: структурированный английский язык запросов». Материалы ACM SIGFIDET 1974 г .: 249–264.
  27. ^ Функциональное программирование на C# — Simon Painter — NDC Oslo 2020 , заархивировано из оригинала 30 октября 2021 г. , получено 23 октября 2021 г.
  28. ↑ Перейти обратно: Перейти обратно: а б «Функциональное программирование — язык программирования Kotlin» . Котлин . Проверено 1 мая 2019 г.
  29. ^ Доминус, Марк Дж. (2005). Perl высшего порядка . Морган Кауфманн . ISBN  978-1-55860-701-9 .
  30. ^ Холиуэлл, Саймон (2014). Функциональное программирование на PHP . php[архитектор]. ISBN  9781940111056 .
  31. ^ Компания Cain Gang Ltd. «Метаклассы Python: кто? Почему? Когда?» (PDF) . Архивировано из оригинала (PDF) 30 мая 2009 года . Проверено 27 июня 2009 г.
  32. ^ «GopherCon 2020: Дилан Миус — функциональное программирование на Go» . Ютуб .
  33. ^ «Функциональные возможности языка: итераторы и замыкания — язык программирования Rust» . doc.rust-lang.org . Проверено 9 января 2021 г.
  34. ^ Вандербаухеде, Вим (18 июля 2020 г.). «Чистый код с функциональным программированием» . Архивировано из оригинала 28 июля 2020 года . Проверено 6 октября 2020 г.
  35. ^ «Эффективная Скала» . Скала Вики . Архивировано из оригинала 19 июня 2012 г. Проверено 21 февраля 2012 г. Эффективная Скала.
  36. ^ «Документация для пакета java.util.function начиная с Java 8 (также известной как Java 1.8)» . Проверено 16 июня 2021 г.
  37. ^ Тьюринг, AM (1937). «Вычислимость и λ-определимость». Журнал символической логики . 2 (4). Издательство Кембриджского университета: 153–163. дои : 10.2307/2268280 . JSTOR   2268280 . S2CID   2317046 .
  38. ^ Хаскелл Брукс Карри; Роберт Фейс (1958). Комбинаторная логика . Издательская компания Северной Голландии . Проверено 10 февраля 2013 г.
  39. ^ Черч, А. (1940). «Формулировка простой теории типов». Журнал символической логики . 5 (2): 56–68. дои : 10.2307/2266170 . JSTOR   2266170 . S2CID   15889861 .
  40. ^ Маккарти, Джон (июнь 1978 г.). История Лиспа (PDF) . История языков программирования . Лос-Анджелес, Калифорния. стр. 173–185. дои : 10.1145/800025.808387 .
  41. ^ Джон Маккарти (1960). «Рекурсивные функции символьных выражений и их машинное вычисление, Часть I». (PDF) . Коммуникации АКМ . 3 (4). ACM Нью-Йорк, Нью-Йорк, США: 184–195. дои : 10.1145/367177.367199 . S2CID   1489409 .
  42. ^ Гай Л. Стил; Ричард П. Габриэль (февраль 1996 г.). «Эволюция Лиспа». История языков программирования---II (PDF) . стр. 233–330. дои : 10.1145/234286.1057818 . ISBN  978-0-201-89502-5 . S2CID   47047140 .
  43. ^ Мемуары Герберта А. Саймона (1991), Модели моей жизни, стр. 189-190. ISBN   0-465-04640-1 утверждает, что он, Эл Ньюэлл и Клифф Шоу «... обычно считаются родителями [области] искусственного интеллекта» за написание Logic Theorist , программы, доказывающей теоремы. из Principia Mathematica автоматически. Чтобы добиться этого, им пришлось изобрести язык и парадигму, которые, если смотреть ретроспективно, включают в себя функциональное программирование.
  44. ^ Ландин, Питер Дж. (1964). «Механическая оценка выражений» . Компьютерный журнал . 6 (4). Британское компьютерное общество : 308–320. дои : 10.1093/comjnl/6.4.308 .
  45. ^ Диль, Стефан; Хартель, Питер; Сестофт, Питер (2000). «Абстрактные машины для реализации языков программирования». Компьютерные системы будущего поколения . Том. 16. С. 739–751.
  46. ^ Ландин, Питер Дж. (февраль 1965a). «Соответствие между АЛГОЛом 60 и лямбда-нотацией Чёрча: часть I» . Коммуникации АКМ . 8 (2). Ассоциация вычислительной техники : 89–101. дои : 10.1145/363744.363749 . S2CID   6505810 .
  47. ^ Ландин, Питер Дж. (март 1965b). «Соответствие между АЛГОЛом 60 и лямбда-нотацией Чёрча: часть II» . Коммуникации АКМ . 8 (3). Ассоциация вычислительной техники : 158–165. дои : 10.1145/363791.363804 . S2CID   15781851 .
  48. ^ Ландин, Питер Дж. (март 1966b). «Следующие 700 языков программирования» . Коммуникации АКМ . 9 (3). Ассоциация вычислительной техники : 157–166. дои : 10.1145/365230.365257 . S2CID   13409665 .
  49. ^ Бэкус, Дж. (1978). «Можно ли программирование освободить от стиля фон Неймана?: Функциональный стиль и его алгебра программ» . Коммуникации АКМ . 21 (8): 613–641. дои : 10.1145/359576.359579 .
  50. ^ РМ Берстолл. Соображения по проектированию функционального языка программирования. Приглашенный доклад, Учеб. Конференция по новейшим технологиям Infotech. «Революция программного обеспечения», Копенгаген, 45–57 (1977).
  51. ^ RM Берстолл и Дж. Дарлингтон. Система преобразований для разработки рекурсивных программ. Журнал Ассоциации вычислительной техники 24 (1): 44–67 (1977).
  52. ^ RM Burstall, DB MacQueen и DT Sannella. НАДЕЖДА: экспериментальный аппликативный язык. Учеб. Конференция LISP 1980 г., Стэнфорд, 136–143 (1980).
  53. ^ «Облегчите обнаружение метода Assign()!» . OpenSCAD . Архивировано из оригинала 19 апреля 2023 г.
  54. ^ Питер Брайт (13 марта 2018 г.). «Разработчики любят новые модные языки, но зарабатывают больше с помощью функционального программирования» . Арс Техника .
  55. ^ Джон Леонард (24 января 2017 г.). «Скрытый рост функционального программирования» . Вычисления.
  56. ^ Лео Чунг (9 мая 2017 г.). «Подойдет ли функциональное программирование для вашего стартапа?» . Инфомир .
  57. ^ Шон Талл - Моноидальные категории для анализа формальных концепций.
  58. ^ Паунтейн, Дик. «Функциональное программирование достигает зрелости» . Байт (август 1994 г.) . Архивировано из оригинала 27 августа 2006 г. Проверено 31 августа 2006 г.
  59. ↑ Перейти обратно: Перейти обратно: а б «ISO/IEC JTC 1/SC 22/WG5/N2137» . Международная организация по стандартизации. 6 июля 2017 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
  60. ^ «Пересмотренный отчет^6 об алгоритмической языковой схеме» . R6rs.org . Проверено 21 марта 2013 г.
  61. ^ «Пересмотренный отчет^6 об алгоритмической языковой схеме — обоснование» . R6rs.org . Проверено 21 марта 2013 г.
  62. ^ Клингер, Уильям (1998). «Правильная хвостовая рекурсия и эффективность использования пространства». Материалы конференции ACM SIGPLAN 1998 года по проектированию и реализации языков программирования — PLDI '98 . стр. 174–185. дои : 10.1145/277650.277719 . ISBN  0897919874 . S2CID   16812984 .
  63. ^ Бейкер, Генри (1994). «CONS не должен аргументировать CONS, Часть II: Чейни о MTA» Архивировано из оригинала 3 марта 2006 г. . Проверено 29 апреля 2020 г.
  64. ^ Тернер, окружной прокурор (28 июля 2004 г.). «Тотальное функциональное программирование» . Журнал универсальной информатики . 10 (7): 751–768. дои : 10.3217/jucs-010-07-0751 .
  65. ^ Реализация языков функционального программирования . Саймон Пейтон Джонс, опубликовано Prentice Hall, 1987 г.
  66. ↑ Перейти обратно: Перейти обратно: а б Джон Лаунбери (1993). «Естественная семантика для ленивой оценки»: 144–154. CiteSeerX   10.1.1.35.2016 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
  67. ^ Роберт В. Харпер (2009). Практические основы языков программирования (PDF) . Архивировано из оригинала (PDF) 7 апреля 2016 г.
  68. ^ Юэ, Жерар П. (1973). «Неразрешимость объединения в логике третьего порядка». Информация и контроль . 22 (3): 257–267. дои : 10.1016/s0019-9958(73)90301-x .
  69. ^ Юэ, Жерар (сентябрь 1976 г.). Решение уравнений на языках порядка 1,2,...ω (доктор философии) (на французском языке). Парижский университет VII.
  70. ^ Юэ, Жерар (2002). «Объединение высшего порядка 30 лет спустя» (PDF) . Ин Карреньо, В.; Муньос, К.; Тахар, С. (ред.). Материалы 15-й Международной конференции ТФОЛ . ЛНКС. Том. 2410. Спрингер. стр. 3–12.
  71. ^ Уэллс, Дж. Б. (1993). «Типизация и проверка типов в лямбда-исчислении второго порядка эквивалентны и неразрешимы». Тех. Реп. 93-011 : 176–185. CiteSeerX   10.1.1.31.3590 .
  72. ^ Лерой, Ксавье (17 сентября 2018 г.). «Компилятор, проверенный Compcert» .
  73. ^ Пейтон Джонс, Саймон; Витиниотис, Димитриос; Вейрих, Стефани ; Джеффри Уошберн (апрель 2006 г.). «Простой вывод типов на основе унификации для GADT» . МЦФП 2006 : 50–61.
  74. ^ «Руководство по OCaml» . caml.inria.fr . Проверено 8 марта 2021 г.
  75. ^ «Алгебраические типы данных» . Документация Скала . Проверено 8 марта 2021 г.
  76. ^ Кеннеди, Эндрю; Руссо, Клаудио (октябрь 2005 г.). Обобщенные алгебраические типы данных и объектно-ориентированное программирование (PDF) . Сан-Диего, Калифорния. ISBN  9781595930316 . Архивировано из оригинала (PDF) 29 декабря 2006 г. {{cite book}}: |work= игнорируется ( помощь ) CS1 maint: отсутствует местоположение издатель ( ссылка ) источник цитирования
  77. ^ Хьюз, Джон. «Почему функциональное программирование имеет значение» (PDF) . Технологический университет Чалмерса .
  78. ^ Чисто функциональные структуры данных Криса Окасаки , Cambridge University Press , 1998, ISBN   0-521-66350-4
  79. ^ Л'Оранж, Жан Никлас. «polymatheia — понимание постоянного вектора Clojure, часть 1» . Полиматея . Проверено 13 ноября 2018 г.
  80. ^ Майкл Барр, Чарльз Уэлл - Теория категорий в информатике.
  81. ^ Ньюберн, Дж. «Все о монадах: исчерпывающее руководство по теории и практике монадического программирования на Haskell» . Проверено 14 февраля 2008 г.
  82. ^ «Тринадцать способов взглянуть на черепаху» . fF# для развлечения и прибыли . Проверено 13 ноября 2018 г.
  83. ^ Полсон, Ларри К. (28 июня 1996 г.). ML для работающего программиста . Издательство Кембриджского университета. ISBN  978-0-521-56543-1 . Проверено 10 февраля 2013 г.
  84. ^ Спивак, Дэниел (26 августа 2008 г.). «Реализация постоянных векторов в Scala» . Фиксация кода . Архивировано из оригинала 23 сентября 2015 года . Проверено 17 апреля 2012 г.
  85. ^ «Какие программы самые быстрые? | Игра «Компьютерные языковые тесты»» . тестыgame.alioth.debian.org. Архивировано из оригинала 20 мая 2013 г. Проверено 20 июня 2011 г.
  86. ^ Игорь Пещанский; Вивек Саркар (2005). «Спецификация неизменности и ее приложения». Параллелизм и вычисления: практика и опыт . 17 (5–6): 639–662. дои : 10.1002/cpe.853 . S2CID   34527406 .
  87. ^ «Углубленный взгляд на коллекции Clojure» . ИнфоQ . Проверено 29 апреля 2024 г.
  88. ^ «Ссылки и заимствования — язык программирования Rust» . doc.rust-lang.org . Проверено 29 апреля 2024 г.
  89. ^ «Проверка ссылок с помощью времени жизни — язык программирования Rust» . doc.rust-lang.org . Проверено 29 апреля 2024 г.
  90. ^ «Параллельные коллекции (Руководства по Java™ > Основные классы Java > Параллелизм)» . docs.oracle.com . Проверено 29 апреля 2024 г.
  91. ^ «Понимание модели актеров для создания неблокирующих распределенных систем с высокой пропускной способностью — Scaleyourapp» . Scaleyourapp.com . 28 января 2023 г. Проверено 29 апреля 2024 г.
  92. ^ Чезарини, Франческо; Томпсон, Саймон (2009). Программирование на Erlang: параллельный подход к разработке программного обеспечения (1-е изд.). O'Reilly Media, Inc. (опубликовано 11 июня 2009 г.). п. 6. ISBN  0596555857, 9780596555856 . {{cite book}}: Проверять |isbn= значение: недопустимый символ ( помощь )
  93. ^ «Глава 25. Профилирование и оптимизация» . Book.realworldhaskell.org . Проверено 20 июня 2011 г.
  94. ^ Берта, Сэмюэл (29 апреля 2024 г.), samber/lo , извлечено
  95. ^ «Go Wiki: оптимизация компилятора и среды выполнения — язык программирования Go» . go.dev . Проверено 29 апреля 2024 г.
  96. ^ «Сравнение производительности: циклы и итераторы — язык программирования Rust» . doc.rust-lang.org . Проверено 29 апреля 2024 г.
  97. ^ Хартель, Питер; Хенк Мюллер; Хью Глейзер (март 2004 г.). «Опыт функционального C» (PDF) . Журнал функционального программирования . 14 (2): 129–135. дои : 10.1017/S0956796803004817 . S2CID   32346900 . Архивировано из оригинала (PDF) 19 июля 2011 г. Проверено 28 мая 2006 г. ; Дэвид Мерц. «Функциональное программирование на Python, часть 3» . IBM DeveloperWorks . Архивировано из оригинала 16 октября 2007 г. Проверено 17 сентября 2006 г. ( Часть 1 , Часть 2 )
  98. ^ «Функции — Язык программирования D 2.0» . Цифровой Марс. 30 декабря 2012 г.
  99. ^ «Неофициальный FAQ по Lua (uFAQ)» .
  100. ^ «Первоклассные функции в Go — языке программирования Go» . golang.org . Проверено 4 января 2021 г.
  101. ^ Эйх, Брендан (3 апреля 2008 г.). «Популярность» .
  102. ^ ван Россум, Гвидо (21 апреля 2009 г.). «Происхождение «функциональных» возможностей Python» . Проверено 27 сентября 2012 г.
  103. ^ "functools — Функции высшего порядка и операции над вызываемыми объектами" . Фонд программного обеспечения Python. 31 июля 2011 г. Проверено 31 июля 2011 г.
  104. ^ Скарсауне, Мартин (2008). Проект SICS Java Port Автоматический перевод большой объектно-ориентированной системы со Smalltalk на Java .
  105. ^ Гослинг, Джеймс. «Замыкания» . Джеймс Гослинг: на Яванской дороге . Оракул. Архивировано из оригинала 14 апреля 2013 г. Проверено 11 мая 2013 г.
  106. ^ Уильямс, Майкл (8 апреля 2013 г.). «Краткий старт Java SE 8 Lambda» .
  107. ^ Блох, Джошуа (2008). «Пункт 15: Минимизация изменчивости». Эффективная Java (Второе изд.). Аддисон-Уэсли. ISBN  978-0321356680 .
  108. ^ «Object.freeze() — JavaScript | MDN» . http://developer.mozilla.org . Проверено 4 января 2021 г. Метод Object.freeze() замораживает объект. Замороженный объект больше нельзя изменить; Замораживание объекта предотвращает добавление к нему новых свойств, удаление существующих свойств, предотвращает изменение перечисляемости, настраиваемости или возможности записи существующих свойств, а также предотвращает изменение значений существующих свойств. Кроме того, замораживание объекта также предотвращает изменение его прототипа. Freeze() возвращает тот же объект, который был передан.
  109. ^ Дэниел Фридман; Уильям Берд; Олег Киселев; Джейсон Хеманн (2018). Разумный интриган, второе издание . Массачусетский технологический институт Пресс.
  110. ^ А. Касас, Д. Кабеса, М. В. Эрменегильдо. Синтаксический подход к Сочетание функциональной записи, ленивого вычисления и высшего порядка в Системы ЛП. 8-й Международный симпозиум по функционалу и логике Программирование (FLOPS'06), страницы 142–162, апрель 2006 г.
  111. ^ «Как я занимаюсь вычислениями» . сайт stallman.org . Проверено 29 апреля 2024 г.
  112. ^ «Хеликс» . helix-editor.com . Проверено 29 апреля 2024 г.
  113. ^ Уэйклинг, Дэвид (2007). «Функциональное программирование электронных таблиц» (PDF) . Журнал функционального программирования . 17 (1): 131–143. дои : 10.1017/S0956796806006186 . ISSN   0956-7968 . S2CID   29429059 .
  114. ^ Пейтон Джонс, Саймон ; Бернетт, Маргарет ; Блэквелл, Алан (март 2003 г.). «Улучшение самого популярного в мире функционального языка: пользовательские функции в Excel» . Архивировано из оригинала 16 октября 2005 г.
  115. ^ Пиро, Кристофер (2009). Функциональное программирование в Facebook . CUFP 2009. Архивировано из оригинала 17 октября 2009 г. Проверено 29 августа 2009 г.
  116. ^ «Sim-Diasca: крупномасштабный механизм параллельного моделирования дискретных событий в Erlang» . Ноябрь 2011 г.
  117. ^ 1 миллион - это так, 2011 г. Архивировано 19 февраля 2014 г. в Wayback Machine // Блог WhatsApp, 6 января 2012 г.: «Последняя важная часть нашей инфраструктуры - Erlang»
  118. ^ Момтахан, Ли (2009). Scala в EDF Trading: реализация предметно-ориентированного языка для ценообразования производных финансовых инструментов с помощью Scala . CUFP 2009. Архивировано из оригинала 17 октября 2009 г. Проверено 29 августа 2009 г.
  119. ^ Грэм, Пол (2003). «Победа над средними показателями» . Проверено 29 августа 2009 г.
  120. ^ Симс, Стив (2006). Создание стартапа с помощью стандартного машинного обучения (PDF) . КУФП 2006 . Проверено 29 августа 2009 г.
  121. ^ Лаурикари, Вилле (2007). Функциональное программирование в области безопасности коммуникаций . CUFP 2007. Архивировано из оригинала 21 декабря 2010 г. Проверено 29 августа 2009 г.
  122. ^ Лоример, Р.Дж. (19 января 2009 г.). «Анонсировано приложение Clojure для живого производства» . ИнфоQ .
  123. ^ Бюньон, Паскаль (2016). Scala для науки о данных (1-е изд.). Пакет . ISBN  9781785281372 .
  124. ^ «Почему разработчикам нравится ClojureScript» . СтекПоделиться . Проверено 29 апреля 2024 г.
  125. ^ Херрик, Джастин (29 апреля 2024 г.), jah2488/elm-company , получено 29 апреля 2024 г.
  126. ^ «Почему разработчикам нравится PureScript» . СтекПоделиться . Проверено 29 апреля 2024 г.
  127. ^ Команда, редакция (08.01.2019). «АЛЛЕГРО – все, что вам нужно знать о лучшей польской онлайн-площадке» . Новости электронной коммерции Германии . Проверено 29 апреля 2024 г.
  128. ^ «Веб-сайты, использующие Phoenix Framework — Wappalyzer» . www.wappalyzer.com . Проверено 29 апреля 2024 г.
  129. ^ «Функциональное программирование: 2019-2020» . Факультет компьютерных наук Оксфордского университета . Проверено 28 апреля 2020 г.
  130. ^ «Программирование I (Haskell)» . Имперский колледж Лондона, факультет вычислительной техники . Проверено 28 апреля 2020 г.
  131. ↑ Перейти обратно: Перейти обратно: а б «Информатика, бакалавриат – Модули» . Проверено 28 апреля 2020 г.
  132. ↑ Перейти обратно: Перейти обратно: а б Абельсон, Хэл ; Сассман, Джеральд Джей (1985). «Предисловие ко второму изданию» . Структура и интерпретация компьютерных программ (2-е изд.). МТИ Пресс.
  133. ^ Джон ДеНеро (осень 2019 г.). «Информатика 61А, Беркли» . Департамент электротехники и компьютерных наук, Беркли . Проверено 14 августа 2020 г.
  134. ↑ Эммануэль Шанцер из Bootstrap дал интервью телешоу «Триангуляция» в TWiT.tv. сети
  135. ^ «Почему схема для вводного программирования?» . home.adelphi.edu . Проверено 29 апреля 2024 г.
  136. ^ Сотрудники IMACS (3 июня 2011 г.). «Что такое схема и почему она выгодна студентам?» . IMACS – Создание лучших мыслителей на всю жизнь . Проверено 29 апреля 2024 г.

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

Послушайте эту статью ( 28 минут )
Продолжительность: 27 минут 59 секунд.
Разговорная иконка Википедии
Этот аудиофайл был создан на основе редакции этой статьи от 25 августа 2011 г. ( 25 августа 2011 г. ) и не отражает последующие изменения.
( Аудио помощь · Больше устных статей )
  1. ^ «Домашняя страница Грега Майклсона» . Математические и компьютерные науки . Риккартон, Эдинбург: Университет Хериот-Ватт . Проверено 6 ноября 2022 г.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Functional_programming&oldid=1227193343"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e132746f13e96124d263d6c9e742d376__1717480800
URL1:https://arc.ask3.ru/arc/aa/e1/76/e132746f13e96124d263d6c9e742d376.html
Заголовок, (Title) документа по адресу, URL1:
Functional programming - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)