stringtranslate.com

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

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

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

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

Функциональное программирование имеет свои корни в академической среде , развиваясь из лямбда-исчисления , формальной системы вычислений, основанной только на функциях. Функциональное программирование исторически было менее популярно, чем императивное программирование, но многие функциональные языки сегодня находят применение в промышленности и образовании, включая Common Lisp , Scheme , [3] [4] [5] [6] Clojure , Wolfram Language , [7] [8] Racket , [9] Erlang , [10] [11] [12] Elixir , [13] OCaml , [14] [15] Haskell , [16] [17] и F# . [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] Kotlin , [28] Perl , [29] PHP , [30] Python , [31] Go , [32] Rust , [33] Raku , [34] Scala , [35] и Java (начиная с Java 8) . [36]

Благодаря своей компоновке парадигмы функционального программирования могут быть пригодны для архитектур, основанных на микросервисах . [37]

История

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

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

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

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

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

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

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

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

В 1970-х годах Гай Л. Стил и Джеральд Джей Сассман разработали Scheme , как описано в Lambda Papers и учебнике 1985 года Structure and Interpretation of Computer Programs . Scheme был первым диалектом LISP, который использовал лексическую область видимости и требовал оптимизации хвостовых вызовов , функций, которые поощряют функциональное программирование.

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

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

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

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

Концепции

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

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

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

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

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

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

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

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

Рекурсия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

const numList = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] ; пусть результат = 0 ; для ( пусть 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 реализует их с помощью монад , полученных из теории категорий . [81] Монады предлагают способ абстрагирования определенных типов вычислительных шаблонов, включая (но не ограничиваясь) моделирование вычислений с изменчивым состоянием (и другими побочными эффектами, такими как ввод-вывод) императивным образом без потери чистоты. Хотя существующие монады могут быть легко применены в программе, при наличии соответствующих шаблонов и примеров, многие студенты считают их сложными для концептуального понимания, например, когда их просят определить новые монады (что иногда необходимо для определенных типов библиотек). [82]

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

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

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

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

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

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

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

Ленивая оценка также может ускорить программу, даже асимптотически, тогда как она может замедлить ее максимум на постоянный множитель (однако, она может привести к утечкам памяти, если используется неправильно). Launchbury 1993 [67] обсуждает теоретические вопросы, связанные с утечками памяти из-за ленивой оценки, а O'Sullivan et al. 2008 [94] дает некоторые практические советы по их анализу и исправлению. Однако наиболее общие реализации ленивой оценки, широко использующие разыменованный код и данные, плохо работают на современных процессорах с глубокими конвейерами и многоуровневыми кэшами (где промах кэша может стоить сотни циклов) [ требуется ссылка ] .

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

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

( четно? 5 ) ( .равно ( mod 5 2 ) 0 )

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

( defn even? "Возвращает true, если n четное, выдает исключение, если n не является целым числом" { :added "1.0" :static true } [ n ] ( if ( integer? n ) ( zero? ( bit-and ( clojure.lang.RT/uncheckedLongCast n ) 1 )) ( throw ( IllegalArgumentException. ( str "Аргумент должен быть целым числом: " n )))))

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

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

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

Можно использовать функциональный стиль программирования в языках, которые традиционно не считаются функциональными языками. [98] Например, и D [99] , и Fortran 95 [60] явно поддерживают чистые функции.

JavaScript , Lua , [100] Python и Go [101] имели функции первого класса с самого начала. [102] Python поддерживал « lambda », « map », « reduce » и « filter » в 1994 году, а также замыкания в Python 2.2, [103] хотя Python 3 перенес «reduce» в functoolsстандартный библиотечный модуль. [104] Функции первого класса были введены в другие основные языки, такие как PHP 5.3, Visual Basic 9 , C# 3.0, C++11 и Kotlin . [28] [ требуется ссылка ]

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

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

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

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

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

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

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

Мать ( Чарльз ,  Элизабет ). Мать ( Гарри ,  Диана ).

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

?-  мать ( harry ,  X ). X  =  diana . ?-  мать ( charles ,  X ). X  =  elizabeth .

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

?-  мать ( X ,  Элизабет ). X  =  Чарльз . ?-  мать ( X ,  Диана ). X  =  Гарри .

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

?-  мать ( X ,  Y ). X  =  Чарльз , Y  =  Элизабет . X  =  Гарри , Y  =  Диана .

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

материнская_бабушка ( X )  =  мать ( мать ( X )).

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

maternal_grandmother ( X ,  Y )  :-  мать ( X ,  Z ),  мать ( Z ,  Y ).

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

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

дедушка ( X )  :=  родитель ( родитель ( X )). родитель ( X )  :=  мать ( X ). родитель ( X )  :=  отец ( X ).мать ( Чарльз )  :=  Элизабет . отец ( Чарльз )  :=  Филлип . мать ( Гарри )  :=  Диана . отец ( Гарри )  :=  Чарльз .?-  дедушка ( X , Y ). X  =  Гарри , Y  =  Элизабет . X  =  Гарри , Y  =  Филлип .

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

Приложения

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

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

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

Электронные таблицы

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

Академия

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

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

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

Другие функциональные языки программирования, которые использовались в промышленности, включают Scala , [119] F# , [18] [19] Wolfram Language , [7] Lisp , [120] Standard ML [121] [122] и Clojure. [123] Scala широко используется в науке о данных , [124] в то время как ClojureScript , [125] Elm [126] или PureScript [127] являются некоторыми из функциональных языков программирования фронтенда, используемых в производстве. Фреймворк Phoenix от Elixir также используется некоторыми относительно популярными коммерческими проектами, такими как Font Awesome или Allegro (одна из крупнейших платформ электронной коммерции в Польше) [128] , рекламная платформа Allegro Lokalnie. [129]

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

Образование

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

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

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

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

Примечания и ссылки

  1. ^ Хадак, Пол (сентябрь 1989 г.). «Концепция, эволюция и применение функциональных языков программирования» (PDF) . ACM Computing Surveys . 21 (3): 359–411. doi :10.1145/72551.72554. S2CID  207637854. Архивировано из оригинала (PDF) 2016-01-31 . Получено 2013-08-10 .
  2. ^ Хьюз, Джон (1984). «Почему функциональное программирование имеет значение».
  3. ^ ab Clinger, Will (1987). "MultiTasking и MacScheme". MacTech . 3 (12) . Получено 28.08.2008 .
  4. ^ ab Hartheimer, Anne (1987). "Программирование текстового редактора в MacScheme+Toolsmith". MacTech . 3 (1). Архивировано из оригинала 2011-06-29 . Получено 2008-08-28 .
  5. ^ ab Kidd, Eric. Обучение реагированию на терроризм в схеме. CUFP 2007. Архивировано из оригинала 21.12.2010 . Получено 26.08.2009 .
  6. ^ ab Cleis, Richard. Scheme in Space. CUFP 2006. Архивировано из оригинала 2010-05-27 . Получено 2009-08-26 .
  7. ^ ab "Wolfram Language Guide: Функциональное программирование". 2015. Получено 24.08.2015 .
  8. ^ "Функциональный против процедурного языка программирования". Кафедра прикладной математики . Университет Колорадо. Архивировано из оригинала 2007-11-13 . Получено 2006-08-28 .
  9. ^ "State-Based Scripting in Uncharted 2" (PDF) . Архивировано из оригинала (PDF) 2012-12-15 . Получено 2011-08-08 .
  10. ^ ab "Кто использует Erlang для разработки продукта?". Часто задаваемые вопросы об Erlang . Получено 27.04.2018 .
  11. ^ ab Armstrong, Joe (июнь 2007). "История Erlang". Труды третьей конференции ACM SIGPLAN по истории языков программирования . Третья конференция ACM SIGPLAN по истории языков программирования. Сан-Диего, Калифорния. doi :10.1145/1238844.1238850. ISBN 9781595937667.
  12. ^ ab Larson, Jim (март 2009). "Erlang для параллельного программирования". Сообщения ACM . 52 (3): 48. doi : 10.1145/1467247.1467263 . S2CID  524392.
  13. ^ "Язык программирования Elixir" . Получено 2021-02-14 .
  14. ^ ab Minsky, Yaron; Weeks, Stephen (июль 2008 г.). «Caml Trading — experiences with functional programming on Wall Street». Journal of Functional Programming . 18 (4): 553–564. doi : 10.1017/S095679680800676X (неактивен 1 ноября 2024 г.). S2CID  30955392.{{cite journal}}: CS1 maint: DOI неактивен по состоянию на ноябрь 2024 г. ( ссылка )
  15. ^ ab Leroy, Xavier. Некоторые применения Caml в промышленности (PDF) . CUFP 2007. Архивировано из оригинала (PDF) 2011-10-08 . Получено 2009-08-26 .
  16. ^ ab "Haskell в промышленности". Haskell Wiki . Получено 26.08.2009 . Haskell имеет широкий спектр коммерческого использования: от аэрокосмической и оборонной промышленности до финансов, веб-стартапов, фирм по проектированию оборудования и производителей газонокосилок.
  17. ^ abc Hudak, Paul ; Hughes, J.; Jones, SP; Wadler, P. (июнь 2007 г.). История Haskell: ленивый с классом. Третья конференция ACM SIGPLAN по истории языков программирования. Сан-Диего, Калифорния. doi :10.1145/1238844.1238856 . Получено 26.09.2013 .
  18. ^ ab Mansell, Howard (2008). Количественные финансы на языке F#. CUFP 2008. Архивировано из оригинала 2015-07-08 . Получено 2009-08-29 .
  19. ^ ab Peake, Alex (2009). Первое существенное приложение для бизнеса на языке F#. CUFP 2009. Архивировано из оригинала 17 октября 2009 г. Получено 29 августа 2009 г.
  20. ^ де Моура, Леонардо; Ульрих, Себастьян (июль 2021 г.). «The Lean 4 Theorem Prover and Programming Language». Конспект лекций по искусственному интеллекту . Конференция по автоматизированной дедукции. Том 12699. С. 625–635. doi : 10.1007/978-3-030-79876-5_37 . ISSN  1611-3349.
  21. ^ Банц, Мэтт (27.06.2017). «Введение в функциональное программирование на JavaScript». Opensource.com . Получено 09.01.2021 .
  22. ^ "Расписание конференции useR! 2006 включает доклады по коммерческому использованию R". R-project.org. 2006-06-08 . Получено 2011-06-20 .
  23. ^ Чемберс, Джон М. (1998). Программирование с данными: руководство по языку S. Springer Verlag. стр. 67–70. ISBN 978-0-387-98503-9.
  24. ^ Новачев, Димитр. "Язык функционального программирования XSLT — доказательство через примеры" . Получено 27 мая 2006 г.
  25. ^ Мерц, Дэвид. "XML Programming Paradigms (часть четвертая): Функциональное программирование в подходе к обработке XML". IBM developerWorks . Получено 27 мая 2006 г.
  26. ^ Чемберлин, Дональд Д .; Бойс, Рэймонд Ф. (1974). «SEQUEL: структурированный английский язык запросов». Труды ACM SIGFIDET 1974 года : 249–264.
  27. ^ Функциональное программирование на C# - Саймон Пейнтер - NDC Oslo 2020, 8 августа 2021 г., заархивировано из оригинала 2021-10-30 , извлечено 2021-10-23
  28. ^ ab "Функциональное программирование - язык программирования Kotlin". Kotlin . Получено 01.05.2019 .
  29. ^ Доминус, Марк Дж. (2005). Perl высшего порядка . Морган Кауфманн . ISBN 978-1-55860-701-9.
  30. ^ Холиуэлл, Саймон (2014). Функциональное программирование на PHP . php[архитектор]. ISBN 9781940111056.
  31. ^ The Cain Gang Ltd. "Python Metaclasses: Who? Why? When?" (PDF) . Архивировано из оригинала (PDF) 30 мая 2009 г. . Получено 27 июня 2009 г. .
  32. ^ "GopherCon 2020: Дилан Миус - Функциональное программирование на Go". YouTube . 22 декабря 2020 г.
  33. ^ "Функциональные возможности языка: итераторы и замыкания — язык программирования Rust". doc.rust-lang.org . Получено 09.01.2021 .
  34. ^ Vanderbauwhede, Wim (18 июля 2020 г.). «Более чистый код с функциональным программированием». Архивировано из оригинала 28 июля 2020 г. Получено 6 октября 2020 г.
  35. ^ "Effective Scala". Scala Wiki . Архивировано из оригинала 2012-06-19 . Получено 2012-02-21 . Effective Scala.
  36. ^ "Документация для пакета java.util.function начиная с Java 8 (также известного как Java 1.8)" . Получено 2021-06-16 .
  37. ^ Роджер, Ричард (11 декабря 2017 г.). Дао микросервисов . Мэннинг. ISBN 9781638351733.
  38. ^ Тьюринг, AM (1937). «Вычислимость и λ-определимость». Журнал символической логики . 2 (4). Cambridge University Press: 153–163. doi : 10.2307/2268280. JSTOR  2268280. S2CID  2317046.
  39. ^ Хаскелл Брукс Карри; Роберт Фейс (1958). Комбинаторная логика . North-Holland Publishing Company . Получено 10 февраля 2013 г.
  40. ^ Чёрч, А. (1940). «Формулировка простой теории типов». Журнал символической логики . 5 (2): 56–68. doi :10.2307/2266170. JSTOR  2266170. S2CID  15889861.
  41. ^ Маккарти, Джон (июнь 1978 г.). История Lisp (PDF) . История языков программирования . Лос-Анджелес, Калифорния. С. 173–185. doi :10.1145/800025.808387.
  42. ^ Джон Маккарти (1960). «Рекурсивные функции символических выражений и их вычисление машиной, часть I». (PDF) . Сообщения ACM . 3 (4). ACM Нью-Йорк, Нью-Йорк, США: 184–195. doi :10.1145/367177.367199. S2CID  1489409.
  43. ^ Гай Л. Стил; Ричард П. Габриэль (февраль 1996). "Эволюция Lisp". История языков программирования---II (PDF) . стр. 233–330. doi :10.1145/234286.1057818. ISBN 978-0-201-89502-5. S2CID  47047140.
  44. ^ В мемуарах Герберта А. Саймона (1991), Models of My Life стр. 189-190 ISBN 0-465-04640-1 утверждается, что он, Эл Ньюэлл и Клифф Шоу "...обычно считаются родителями [области] искусственного интеллекта" за написание Logic Theorist , программы, которая автоматически доказывала теоремы из Principia Mathematica . Чтобы добиться этого, им пришлось изобрести язык и парадигму, которые, если смотреть ретроспективно, встраивают функциональное программирование. 
  45. ^ Ландин, Питер Дж. (1964). «Механическая оценка выражений». The Computer Journal . 6 (4). British Computer Society : 308–320. doi : 10.1093/comjnl/6.4.308 .
  46. ^ Диль, Стефан; Хартель, Питер; Сестофт, Питер (2000). «Абстрактные машины для реализации языка программирования». Future Generation Computer Systems . Том 16. С. 739–751.
  47. ^ Ландин, Питер Дж. (февраль 1965a). «Соответствие между АЛГОЛом 60 и лямбда-нотацией Чёрча: часть I». Сообщения ACM . 8 (2). Ассоциация вычислительной техники : 89–101. doi : 10.1145/363744.363749 . S2CID  6505810.
  48. ^ Ландин, Питер Дж. (март 1965b). «Соответствие между АЛГОЛом 60 и лямбда-нотацией Чёрча: часть II». Сообщения ACM . 8 (3). Ассоциация вычислительной техники : 158–165. doi : 10.1145/363791.363804 . S2CID  15781851.
  49. ^ Ландин, Питер Дж. (март 1966b). «Следующие 700 языков программирования». Сообщения ACM . 9 (3). Ассоциация вычислительной техники : 157–166. doi : 10.1145/365230.365257 . S2CID  13409665.
  50. ^ Бэкус, Дж. (1978). «Можно ли освободить программирование от стиля фон Неймана?: функциональный стиль и его алгебра программ». Сообщения ACM . 21 (8): 613–641. doi : 10.1145/359576.359579 .
  51. ^ RM Burstall. Design Considerations for a functional programming language. Приглашенный доклад, Proc. Infotech State of the Art Conf. "The Software Revolution", Копенгаген, 45–57 (1977)
  52. ^ RM Burstall и J. Darlington. Система преобразования для разработки рекурсивных программ. Журнал Ассоциации вычислительной техники 24(1):44–67 (1977)
  53. ^ RM Burstall, DB MacQueen и DT Sannella. HOPE: экспериментальный аппликативный язык. Труды конференции LISP 1980 года, Стэнфорд, 136–143 (1980).
  54. ^ "Сделайте обнаружение assign() проще!". OpenSCAD . Архивировано из оригинала 2023-04-19.
  55. ^ Питер Брайт (13 марта 2018 г.). «Разработчики любят модные новые языки, но зарабатывают больше с помощью функционального программирования». Ars Technica .
  56. ^ Джон Леонард (24 января 2017 г.). «Незаметный рост функционального программирования». Вычислительная техника.
  57. ^ Лео Чунг (9 мая 2017 г.). «Подходит ли функциональное программирование для вашего стартапа?». InfoWorld .
  58. ^ Шон Тулл - Моноидальные категории для анализа формальных понятий.
  59. ^ Pountain, Dick. "Функциональное программирование достигает зрелости". Byte (август 1994) . Архивировано из оригинала 2006-08-27 . Получено 31 августа 2006 .
  60. ^ ab "ISO/IEC JTC 1/SC 22/WG5/N2137 – Fortran 2015 Committee Draft (J3/17-007r2)" (PDF) . Международная организация по стандартизации. 6 июля 2017 г. С. 336–338.
  61. ^ "Пересмотренный^6 отчет о схеме алгоритмического языка". R6rs.org . Получено 2013-03-21 .
  62. ^ "Пересмотренный^6 отчет по схеме алгоритмического языка - Обоснование". R6rs.org . Получено 21.03.2013 .
  63. ^ Клингер, Уильям (1998). "Правильная хвостовая рекурсия и эффективность использования пространства". Труды конференции ACM SIGPLAN 1998 года по проектированию и реализации языков программирования - PLDI '98 . стр. 174–185. doi :10.1145/277650.277719. ISBN 0897919874. S2CID  16812984.
  64. ↑ Бейкер, Генри (1994). «CONS Should Not CONS Its Arguments, Part II: Cheney on MTA» Архивировано из оригинала 2006-03-03 . Получено 2020-04-29 .
  65. ^ Тернер, ДА (28 июля 2004 г.). «Полное функциональное программирование». Журнал универсальной компьютерной науки . 10 (7): 751–768. doi :10.3217/jucs-010-07-0751.
  66. ^ Реализация функциональных языков программирования. Саймон Пейтон Джонс, опубликовано Prentice Hall, 1987
  67. ^ ab Launchbury, John (март 1993 г.). Естественная семантика для ленивых вычислений . Симпозиум по принципам языков программирования. Чарльстон, Южная Каролина: ACM . стр. 144–154. doi : 10.1145/158511.158618 .
  68. ^ Роберт В. Харпер (2009). Практические основы языков программирования (PDF) . Архивировано из оригинала (PDF) 2016-04-07.
  69. ^ Huet, Gérard P. (1973). «Неразрешимость объединения в логике третьего порядка». Информация и управление . 22 (3): 257–267. doi :10.1016/s0019-9958(73)90301-x.
  70. ^ Юэ, Жерар (сентябрь 1976 г.). Резолюция d'Equations dans des Langages d'Ordre 1,2,...ω (доктор философии) (на французском языке). Парижский университет VII.
  71. ^ Huet, Gérard (2002). «Высшее объединение порядка 30 лет спустя» (PDF) . В Carreño, V.; Muñoz, C.; Tahar, S. (ред.). Труды 15-й международной конференции TPHOL . LNCS. Том 2410. Springer. стр. 3–12.
  72. ^ Уэллс, Дж. Б. (1993). «Типичность и проверка типов в лямбда-исчислении второго порядка эквивалентны и неразрешимы». Tech. Rep. 93-011 : 176–185. CiteSeerX 10.1.1.31.3590 . 
  73. ^ Лерой, Ксавье (17 сентября 2018 г.). «Проверенный компилятор Compcert».
  74. ^ Пейтон Джонс, Саймон; Витиниотис, Димитриос; Вайрих, Стефани ; Джеффри Уошберн (апрель 2006 г.). «Простой вывод типов на основе унификации для GADT». Icfp 2006 : 50–61.
  75. ^ "OCaml Manual". caml.inria.fr . Получено 2021-03-08 .
  76. ^ "Алгебраические типы данных". Документация Scala . Получено 2021-03-08 .
  77. ^ Кеннеди, Эндрю; Руссо, Клаудио В. (октябрь 2005 г.). Обобщенные алгебраические типы данных и объектно-ориентированное программирование (PDF) . OOPSLA. Сан-Диего, Калифорния: ACM . doi :10.1145/1094811.1094814. ISBN 9781595930316. Архивировано из оригинала 29.12.2006.
  78. ^ Хьюз, Джон. «Почему функциональное программирование имеет значение» (PDF) . Технологический университет Чалмерса .
  79. ^ Чисто функциональные структуры данных Криса Окасаки , Cambridge University Press , 1998, ISBN 0-521-66350-4 
  80. ^ L'orange, Жан Никлас. "polymatheia - Понимание постоянного вектора Clojure, ч. 1". Polymatheia . Получено 13.11.2018 .
  81. ^ Майкл Барр, Чарльз Уэллс — Теория категорий для компьютерных наук.
  82. ^ Ньюберн, Дж. "Все о монадах: полное руководство по теории и практике монадического программирования в Haskell" . Получено 14 февраля 2008 г.
  83. ^ "Тринадцать способов смотреть на черепаху". fF# для развлечения и выгоды . Получено 2018-11-13 .
  84. ^ Полсон, Ларри К. (28 июня 1996 г.). ML для работающего программиста. Cambridge University Press. ISBN 978-0-521-56543-1. Получено 10 февраля 2013 г.
  85. ^ Спивак, Дэниел (26 августа 2008 г.). «Реализация постоянных векторов в Scala». Code Commit . Архивировано из оригинала 23 сентября 2015 г. Получено 17 апреля 2012 г.
  86. ^ "Какие программы самые быстрые? | Computer Language Benchmarks Game". benchmarksgame.alioth.debian.org. Архивировано из оригинала 2013-05-20 . Получено 2011-06-20 .
  87. ^ Игорь Печчанский; Вивек Саркар (2005). «Спецификация неизменяемости и ее применение». Параллелизм и вычисления: практика и опыт . 17 (5–6): 639–662. doi :10.1002/cpe.853. S2CID  34527406.
  88. ^ "Подробный взгляд на коллекции Clojure". InfoQ . Получено 29.04.2024 .
  89. ^ "Ссылки и заимствования - Язык программирования Rust". doc.rust-lang.org . Получено 29.04.2024 .
  90. ^ "Проверка ссылок с помощью времени жизни - язык программирования Rust". doc.rust-lang.org . Получено 29.04.2024 .
  91. ^ "Параллельные коллекции (Учебники Java™ > Основные классы Java > Параллелизм)". docs.oracle.com . Получено 29.04.2024 .
  92. ^ «Понимание модели акторов для создания неблокируемых, высокопроизводительных распределенных систем — Scaleyourapp». scaleyourapp.com . 2023-01-28 . Получено 2024-04-29 .
  93. ^ Чезарини, Франческо; Томпсон, Саймон (2009). Программирование на Erlang: параллельный подход к разработке программного обеспечения (1-е изд.). O'Reilly Media, Inc. (опубликовано 2009-06-11). стр. 6. ISBN 978-0-596-55585-6.
  94. ^ "Глава 25. Профилирование и оптимизация". Book.realworldhaskell.org . Получено 20.06.2011 .
  95. ↑ Берта, Сэмюэл (29 апреля 2024 г.), samber/lo , получено 29 апреля 2024 г.
  96. ^ "Go Wiki: Compiler And Runtime Optimizations - The Go Programming Language". go.dev . Получено 29.04.2024 .
  97. ^ "Сравнение производительности: циклы против итераторов - язык программирования Rust". doc.rust-lang.org . Получено 29.04.2024 .
  98. ^ Hartel, Pieter; Henk Muller; Hugh Glaser (март 2004 г.). "The Functional C experience" (PDF) . Journal of Functional Programming . 14 (2): 129–135. doi :10.1017/S0956796803004817. S2CID  32346900. Архивировано из оригинала (PDF) 2011-07-19 . Получено 2006-05-28 .; Дэвид Мерц. "Функциональное программирование на Python, часть 3". IBM developerWorks . Архивировано из оригинала 2007-10-16 . Получено 2006-09-17 .(Часть 1, Часть 2)
  99. ^ "Функции — язык программирования D 2.0". Digital Mars. 30 декабря 2012 г.
  100. ^ "Неофициальный FAQ по Lua (uFAQ)".
  101. ^ "Функции первого класса в Go - Язык программирования Go". golang.org . Получено 04.01.2021 .
  102. ↑ Эйх, Брендан (3 апреля 2008 г.). «Популярность».
  103. ^ Ван Россум, Гвидо (21.04.2009). "Истоки "функциональных" возможностей Python" . Получено 27.09.2012 .
  104. ^ "functools — Функции высшего порядка и операции над вызываемыми объектами". Python Software Foundation. 2011-07-31 . Получено 2011-07-31 .
  105. ^ Скарсауне, Мартин (2008). Проект порта SICS Java. Автоматический перевод большой объектно-ориентированной системы с языка Smalltalk на язык Java .
  106. ^ Гослинг, Джеймс. «Закрытия». Джеймс Гослинг: на Java Road . Oracle. Архивировано из оригинала 2013-04-14 . Получено 11 мая 2013 г.
  107. ↑ Уильямс, Майкл (8 апреля 2013 г.). «Java SE 8 Lambda Quick Start».
  108. ^ Блох, Джошуа (2008). "Пункт 15: Минимизируйте изменчивость". Effective Java (Второе изд.). Addison-Wesley. ISBN 978-0321356680.
  109. ^ "Object.freeze() - JavaScript | MDN". developer.mozilla.org . Получено 2021-01-04 . Метод Object.freeze() замораживает объект. Замороженный объект больше не может быть изменен; замораживание объекта предотвращает добавление к нему новых свойств, удаление существующих свойств, предотвращает изменение перечисляемости, настраиваемости или возможности записи существующих свойств и предотвращает изменение значений существующих свойств. Кроме того, замораживание объекта также предотвращает изменение его прототипа. freeze() возвращает тот же объект, который был передан.
  110. ^ Дэниел Фридман; Уильям Берд; Олег Киселёв; Джейсон Хеманн (2018). The Reasoned Schemer, Второе издание . Издательство MIT.
  111. ^ А. Касас, Д. Кабеса, М. В. Эрменегильдо. Синтаксический подход к объединению функциональной нотации, ленивых вычислений и высшего порядка в системах LP. 8-й Международный симпозиум по функциональному и логическому программированию (FLOPS'06), страницы 142-162, апрель 2006 г.
  112. ^ "Как я делаю свои вычисления". stallman.org . Получено 29.04.2024 .
  113. ^ "Helix". helix-editor.com . Получено 29.04.2024 .
  114. ^ Уэйкелинг, Дэвид (2007). "Функциональное программирование электронных таблиц" (PDF) . Журнал функционального программирования . 17 (1): 131–143. doi :10.1017/S0956796806006186. ISSN  0956-7968. S2CID  29429059.
  115. ^ Пейтон Джонс, Саймон ; Бернетт, Маргарет ; Блэквелл, Алан (март 2003 г.). «Улучшение самого популярного в мире функционального языка: определяемые пользователем функции в Excel». Архивировано из оригинала 16 октября 2005 г.
  116. ^ Пиро, Кристофер (2009). Функциональное программирование в Facebook. CUFP 2009. Архивировано из оригинала 2009-10-17 . Получено 2009-08-29 .
  117. ^ "Sim-Diasca: крупномасштабная система параллельного дискретного моделирования на языке Erlang". Ноябрь 2011 г.
  118. ^ 1 миллион — это так 2011 Архивировано 19 февраля 2014 г. на Wayback Machine // Блог WhatsApp, 06 января 2012 г.: «последняя важная часть нашей инфраструктуры — это Erlang»
  119. ^ Момтахан, Ли (2009). Scala в EDF Trading: реализация предметно-ориентированного языка для ценообразования производных инструментов с помощью Scala. CUFP 2009. Архивировано из оригинала 2009-10-17 . Получено 2009-08-29 .
  120. ^ Грэм, Пол (2003). "Beating the Averages" . Получено 29-08-2009 .
  121. ^ Симс, Стив (2006). Создание стартапа с помощью стандартного машинного обучения (PDF) . CUFP 2006. Получено 29 августа 2009 г.
  122. ^ Лаурикари, Вилле (2007). Функциональное программирование в безопасности коммуникаций. CUFP 2007. Архивировано из оригинала 21.12.2010 . Получено 29.08.2009 .
  123. ^ Лоример, Р. Дж. (19 января 2009 г.). «Анонсировано приложение Clojure для живого производства». InfoQ .
  124. ^ Bugnion, Pascal (2016). Scala для науки о данных (1-е изд.). Packt . ISBN 9781785281372.
  125. ^ "Почему разработчикам нравится ClojureScript". StackShare . Получено 29.04.2024 .
  126. ^ Херрик, Джастин (29.04.2024), jah2488/elm-companies , получено 29.04.2024
  127. ^ "Почему разработчикам нравится PureScript". StackShare . Получено 29.04.2024 .
  128. ^ Команда, редакционная статья (08.01.2019). "ALLEGRO - все, что вам нужно знать о лучшей польской торговой площадке". Новости электронной коммерции в Германии . Получено 29.04.2024 .
  129. ^ "Веб-сайты, использующие Phoenix Framework - Wappalyzer". www.wappalyzer.com . Получено 29.04.2024 .
  130. ^ "Функциональное программирование: 2019-2020". Оксфордский университет, кафедра компьютерных наук . Получено 28 апреля 2020 г.
  131. ^ "Программирование I (Haskell)". Имперский колледж Лондона, факультет вычислительной техники . Получено 28 апреля 2020 г.
  132. ^ ab "Computer Science BSc - Modules" . Получено 28 апреля 2020 г. .
  133. ^ ab Абельсон, Хэл ; Сассман, Джеральд Джей (1985). «Предисловие ко второму изданию». Структура и интерпретация компьютерных программ (2-е изд.). MIT Press.
  134. ^ Джон ДеНеро (осень 2019 г.). "Computer Science 61A, Berkeley". Department of Electrical Engineering and Computer Sciences, Berkeley . Получено 14 августа 2020 г.
  135. ↑ Эммануэль Шанцер из Bootstrap дал интервью в телешоу Triangulation на канале TWiT.tv.
  136. ^ "Почему Scheme для вводного программирования?". home.adelphi.edu . Получено 29.04.2024 .
  137. ^ Сотрудники, IMACS (2011-06-03). «Что такое схема и почему она полезна для студентов?». IMACS – Making Better Thinkers for Life . Получено 29.04.2024 .

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

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

Послушайте эту статью ( 28 минут )
Разговорный значок Википедии
Этот аудиофайл был создан на основе редакции этой статьи от 25 августа 2011 года и не отражает последующие правки. ( 2011-08-25 )
( Аудиопомощь  · Больше устных статей )