В информатике говорят , что язык программирования имеет первоклассные функции, если он рассматривает функции как первоклассных граждан . Это означает, что язык поддерживает передачу функций в качестве аргументов другим функциям, возврат их как значений из других функций и присвоение их переменным или сохранение их в структурах данных. [1] Некоторым теоретикам языков программирования также требуется поддержка анонимных функций (функциональных литералов). [2] В языках с первоклассными функциями имена функций не имеют какого-либо особого статуса; они обрабатываются как обычные переменные с типом функции . [3] Этот термин был придуман Кристофером Стрейчи в контексте «функций первоклассных граждан» в середине 1960-х годов. [4]
Первоклассные функции необходимы для стиля функционального программирования , в котором использование функций высшего порядка является стандартной практикой. Простым примером функции высшего порядка является функция карты , которая принимает в качестве аргументов функцию и список и возвращает список, сформированный путем применения функции к каждому члену списка. Чтобы язык поддерживал карту , он должен поддерживать передачу функции в качестве аргумента.
Существуют определенные трудности реализации при передаче функций в качестве аргументов или возврате их в качестве результатов, особенно при наличии нелокальных переменных, введенных во вложенные и анонимные функции . Исторически это называлось проблемами funarg , название происходит от «аргумента функции». [5] В ранних императивных языках этих проблем можно было избежать, либо не поддерживая функции как типы результатов (например, ALGOL 60 , Pascal ), либо опуская вложенные функции и, следовательно, нелокальные переменные (например, C ). Ранний функциональный язык Lisp использовал подход динамической области видимости , где нелокальные переменные относятся к ближайшему определению этой переменной в точке выполнения функции, а не там, где она была определена. Правильная поддержка функций первого класса с лексической областью видимости была введена в Scheme и требует обработки ссылок на функции как замыканий , а не простых указателей на функции , [4] что, в свою очередь, делает сбор мусора необходимостью.
В этом разделе мы сравниваем, как отдельные идиомы программирования обрабатываются в функциональном языке с функциями первого класса ( Haskell ) по сравнению с императивным языком, где функции являются гражданами второго класса ( C ).
В языках, где функции являются первоклассными гражданами, функции могут передаваться в качестве аргументов другим функциям так же, как и другие значения (функция, принимающая другую функцию в качестве аргумента, называется функцией высшего порядка). На языке Хаскель :
карта :: ( a -> b ) -> [ a ] -> [ b ] карта f [] = [] карта f ( x : xs ) = f x : карта f xs Языки, в которых функции не являются первоклассными, часто по-прежнему позволяют писать функции более высокого порядка с помощью таких функций, как указатели на функции или делегаты . На языке С :
void map ( int ( * f )( int ), int x [], size_t n ) { for ( int i = 0 ; i < n ; i ++ ) x [ i ] = f ( x [ i ]); } Между двумя подходами существует ряд отличий, не связанных напрямую с поддержкой первоклассных функций. Образец Haskell работает со списками , а образец C — с массивами . Обе являются наиболее естественными составными структурами данных на соответствующих языках, и если бы пример C работал со связанными списками, это сделало бы его излишне сложным. Это также объясняет тот факт, что функции C нужен дополнительный параметр (задающий размер массива). Функция C обновляет массив на месте , не возвращая никакого значения, тогда как в Haskell структуры данных являются постоянными (возвращается новый список). в то время как старый остается нетронутым.) Образец Haskell использует рекурсию для обхода списка, а образец C использует итерацию . Опять же, это наиболее естественный способ выразить эту функцию на обоих языках, но образец Haskell можно было бы легко выразить в терминах складки, а образец C — в терминах рекурсии. Наконец, функция Haskell имеет полиморфный тип, поскольку он не поддерживается C, мы присвоили всем переменным типа константу типа int.
В языках, поддерживающих анонимные функции, мы можем передать такую функцию в качестве аргумента функции более высокого порядка:
основной = карта ( \ x -> 3 * x + 1 ) [ 1 , 2 , 3 , 4 , 5 ] В языке, который не поддерживает анонимные функции, нам приходится вместо этого привязывать их к имени:
int f ( int x ) { return 3 * x + 1 ; } int main () { int list [] = { 1 , 2 , 3 , 4 , 5 }; карта ( f , список , 5 ); } Когда у нас есть анонимные или вложенные функции, для них становится естественным ссылаться на переменные вне своего тела (называемые нелокальными переменными ):
main = пусть a = 3 b = 1 в карте ( \ x -> a * x + b ) [ 1 , 2 , 3 , 4 , 5 ] Если функции представлены голыми указателями на функции, мы больше не можем знать, как следует передать ей значение, находящееся за пределами тела функции, и из-за этого замыкание необходимо создавать вручную. Поэтому о «первоклассных» функциях здесь говорить не приходится.
typedef struct { int ( * f )( int , int , int ); инт а ; интервал б ; } замыкание_т ; void карта ( closure_t * closure , int x [], size_t n ) { for ( int i = 0 ; i < n ; ++ i ) x [ i ] = ( closure -> f )( closure -> a , closure - > б , х [ я ]); } int f ( int a , int b , int x ) { return a * x + b ; } void main () { int l [] = { 1 , 2 , 3 , 4 , 5 }; интервал а = 3 ; интервал б = 1 ; closure_t закрытие = { f , a , b }; карта ( & замыкание , л , 5 ); } Также обратите внимание, что mapтеперь специализируется на функциях, ссылающихся на два intобъекта вне их среды. Это можно настроить в более общем плане, но для этого потребуется больше шаблонного кода . Если fбы это была вложенная функция, мы бы все равно столкнулись с той же проблемой, и именно по этой причине они не поддерживаются в C. [6]
Возвращая функцию, мы фактически возвращаем ее закрытие. В примере C любые локальные переменные, захваченные замыканием, выйдут из области видимости, как только мы вернемся из функции, создающей замыкание. Принудительное закрытие на более позднем этапе приведет к неопределенному поведению, что может привести к повреждению стека. Это известно как проблема восходящего фунарга .
Присвоение функций переменным и сохранение их внутри (глобальных) структур данных потенциально сталкивается с теми же трудностями, что и возврат функций.
f :: [[ Integer ] -> [ Integer ]] f = let a = 3 b = 1 in [ map ( \ x -> a * x + b ), map ( \ x -> b * x + a )] Поскольку большинство литералов и значений можно проверить на равенство, естественно задаться вопросом, может ли язык программирования поддерживать функции проверки равенства. При дальнейшем рассмотрении этот вопрос оказывается более сложным, и следует различать несколько типов равенства функций: [7]
В теории типов тип функций, принимающих значения типа A и возвращающих значения типа B , может быть записан как A → B или B A. В соответствии Карри-Ховарда типы функций связаны с логическим следствием ; лямбда-абстракция соответствует исключению гипотетических предположений, а применение функции соответствует правилу вывода modus ponens . Помимо обычного случая программных функций, теория типов также использует первоклассные функции для моделирования ассоциативных массивов и подобных структур данных .
В теоретико-категорном подходе к программированию наличие функций первого класса соответствует предположению о закрытой категории . Например, просто типизированное лямбда-исчисление соответствует внутреннему языку декартовых замкнутых категорий .
Языки функционального программирования, такие как Erlang , Scheme , ML , Haskell , F# и Scala , имеют первоклассные функции. Когда был разработан Lisp , один из первых функциональных языков, не все аспекты первоклассных функций были правильно поняты, в результате чего функции имели динамическую область видимости. Более поздние диалекты Scheme и Common Lisp действительно имеют первоклассные функции с лексической областью действия.
Многие языки сценариев, включая Perl , Python , PHP , Lua , Tcl /Tk, JavaScript и Io , имеют первоклассные функции.
Для императивных языков необходимо проводить различие между Алголом и его потомками, такими как Паскаль, традиционным семейством C и современными вариантами со сборкой мусора. Семейство Algol допускает вложенные функции и функции высшего порядка, принимающие функции в качестве аргументов, но не функции высшего порядка, которые возвращают функции в качестве результатов (кроме Algol 68, который позволяет это). Причиной этого было то, что было неизвестно, как обращаться с нелокальными переменными, если в результате возвращалась вложенная функция (а Алгол 68 в таких случаях выдает ошибки времени выполнения).
Семейство C позволяло как передавать функции в качестве аргументов, так и возвращать их как результаты, но избегало любых проблем, не поддерживая вложенные функции. (Компилятор gcc допускает их в качестве расширения.) Поскольку полезность возврата функций в первую очередь заключается в возможности возвращать вложенные функции, которые захватывают нелокальные переменные, вместо функций верхнего уровня, эти языки обычно не считаются первыми. -классовые функции.
Современные императивные языки часто поддерживают сборку мусора, что делает возможной реализацию первоклассных функций. Первоклассные функции часто поддерживались только в более поздних версиях языка, включая C# 2.0 и расширение Apple Blocks для C, C++ и Objective-C. В C++11 добавлена поддержка анонимных функций и замыканий в язык, но из-за отсутствия в языке сборки мусора необходимо уделять особое внимание нелокальным переменным в функциях, возвращаемых в качестве результатов (см. ниже). ).
functionдолжен использоваться для получения функции как значения: (function foo)оценивается как объект функции. #'fooсуществует в виде сокращенной записи. Чтобы применить такой объект функции, необходимо использовать функцию funcall: (funcall #'foo bar baz).functools.partialначиная с версии 2.5 и operator.methodcallerначиная с версии 2.6.Methodили Procдля использования в качестве первоклассных данных. Синтаксис вызова такого функционального объекта отличается от вызова обычных методов.[1].{{cite journal}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )(также 16 февраля 2010 г.