В информатике говорят , что язык программирования имеет функции первого класса , если он рассматривает функции как граждан первого класса . Это означает, что язык поддерживает передачу функций в качестве аргументов другим функциям, возвращая их как значения из других функций и присваивая их переменным или сохраняя их в структурах данных. [1] Некоторые теоретики языков программирования также требуют поддержки анонимных функций (литералов функций). [2] В языках с функциями первого класса имена функций не имеют особого статуса; они рассматриваются как обычные переменные с типом функции . [3] Этот термин был придуман Кристофером Стрейчи в контексте «функций как граждан первого класса» в середине 1960-х годов. [4]
Функции первого класса необходимы для функционального стиля программирования , в котором использование функций высшего порядка является стандартной практикой. Простым примером функции высшего порядка является функция map , которая принимает в качестве аргументов функцию и список и возвращает список, сформированный путем применения функции к каждому члену списка. Чтобы язык поддерживал map , он должен поддерживать передачу функции в качестве аргумента.
Существуют определенные трудности реализации при передаче функций в качестве аргументов или возврате их в качестве результатов, особенно при наличии нелокальных переменных, введенных во вложенные и анонимные функции . Исторически они назывались проблемами фунаргов , название происходит от «аргумент функции». [5] В ранних императивных языках этих проблем удалось избежать, либо не поддерживая функции как типы результатов (например, ALGOL 60 , Pascal ), либо пропуская вложенные функции и, таким образом, нелокальные переменные (например, C ). Ранний функциональный язык Lisp принял подход динамической области видимости , где нелокальные переменные ссылаются на ближайшее определение этой переменной в точке, где функция выполняется, а не там, где она была определена. Надлежащая поддержка лексически ограниченных функций первого класса была введена в Scheme и требует обработки ссылок на функции как замыканий вместо простых указателей на функции , [4] что, в свою очередь, делает сборку мусора необходимостью.
В этом разделе мы сравниваем, как конкретные идиомы программирования обрабатываются в функциональном языке с функциями первого класса ( Haskell ) по сравнению с императивным языком, где функции являются гражданами второго класса ( C ).
В языках, где функции являются гражданами первого класса, функции могут передаваться в качестве аргументов другим функциям таким же образом, как и другие значения (функция, принимающая другую функцию в качестве аргумента, называется функцией высшего порядка). В языке Haskell :
карта :: ( a -> b ) -> [ a ] -> [ b ] карта f [] = [] карта f ( x : xs ) = f x : карта f xs Языки, в которых функции не являются первоклассными, часто все еще позволяют писать функции более высокого порядка с помощью таких возможностей, как указатели функций или делегаты . В языке C :
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 }; map ( f , list , 5 ); } Как только у нас появляются анонимные или вложенные функции, для них становится естественным ссылаться на переменные за пределами их тела (называемые нелокальными переменными ):
main = пусть a = 3 b = 1 в карте ( \ x -> a * x + b ) [ 1 , 2 , 3 , 4 , 5 ] Если функции представлены голыми указателями функций, мы больше не можем знать, как значение, находящееся вне тела функции, должно быть передано ей, и из-за этого замыкание должно быть построено вручную. Поэтому мы не можем здесь говорить о функциях "первого класса".
typedef struct { int ( * f )( int , int , int ); int a ; int b ; } closure_t ; void map ( closure_t * closure , int x [], size_t n ) { for ( int i = 0 ; i < n ; ++ i ) x [ i ] = ( closure -> f )( closure -> a , closure -> b , x [ i ]); } int f ( int a , int b , int x ) { return a * x + b ; } void main () { int l [] = { 1 , 2 , 3 , 4 , 5 }; int a = 3 ; int b = 1 ; closure_t closure = { f , a , b }; map ( & closure , l , 5 ); } Также обратите внимание, что mapтеперь специализировано для функций, ссылающихся на два ints вне их окружения. Это можно настроить более обобщенно, но это требует больше шаблонного кода . Если fбы это была вложенная функция, мы бы все равно столкнулись с той же проблемой, и это причина, по которой они не поддерживаются в C. [6]
При возврате функции мы фактически возвращаем ее замыкание. В примере C любые локальные переменные, захваченные замыканием, выйдут из области видимости, как только мы вернемся из функции, которая создает замыкание. Принудительное замыкание в более поздней точке приведет к неопределенному поведению, возможно, испортив стек. Это известно как проблема ups-funarg .
Назначение функций переменным и сохранение их внутри (глобальных) структур данных потенциально сопряжено с теми же трудностями, что и возврат функций.
f :: [[ Целое число ] -> [ Целое число ]] f = пусть a = 3 b = 1 в [ карта ( \ x -> a * x + b ), карта ( \ 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 , имеют функции первого класса.
Для императивных языков необходимо провести различие между Algol и его потомками, такими как Pascal, традиционным семейством C и современными вариантами со сборкой мусора. Семейство Algol допускало вложенные функции и функции более высокого порядка, принимающие функции в качестве аргументов, но не функции более высокого порядка, возвращающие функции в качестве результатов (за исключением Algol 68, который допускает это). Причина этого в том, что было неизвестно, как обращаться с нелокальными переменными, если вложенная функция возвращалась как результат (и Algol 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: бот: исходный статус URL неизвестен ( ссылка )(также 2010-02-16