Функции первого класса
Из Википедии, бесплатной энциклопедии
В информатике язык программирования имеет функции первого класса, если он рассматривает функции как объекты первого класса. В частности, это означает, что язык поддерживает передачу функций в качестве аргументов другим функциям, возврат их как результат других функций, присваивание их переменным или сохранение в структурах данных[1]. Некоторые теоретики языков программирования считают необходимым условием также поддержку анонимных функций[2]. В языках с функциями первого класса имена функций не имеют никакого специального статуса, они рассматриваются как обычные значения, тип которых является функциональным[3]. Термин был впервые использован Кристофером Стрэчи в контексте «функции как объекты первого класса» в середине 1960-х[4].
Функции первого класса являются неотъемлемой частью функционального программирования, в котором использование функций высшего порядка является стандартной практикой. Простым примером функции высшего порядка будет функция map
, принимающая в качестве своих аргументов функцию и список и возвращающая список после применения функции к каждому его элементу. Чтобы язык программирования поддерживал map
, он должен поддерживать передачу функций как аргумента.
Существуют некоторые сложности в реализации передачи функций как аргументов и возвращении их как результата, особенно в присутствии нелокальных переменных, введённых во вложенных и анонимных функциях. Исторически они были названы проблемами фунарга, от английского «function argument»[5]. В ранних императивных языках программирования эти проблемы обходились путём отказа от поддержки возвращения функций как результата или отказа от вложенных функций и следовательно нелокальных переменных (в частности, C). Lisp, один из первых функциональных языков программирования, применяет подход динамической области видимости, где нелокальные переменные возвращают ближайшее определение этих переменных к точке, в которой функция была вызвана, вместо точки, в которой она была объявлена. Полноценная поддержка для лексического контекста функций первого порядка была введена в Scheme и предполагает обработку ссылок на функции как замыканий вместо чистых[4], что, в свою очередь, делает необходимым применение сборки мусора.
Концепции[править | править код]
В этой секции рассматривается, как конкретные идиомы программирования реализуются в функциональных языках с функциями первого порядка (Haskell) сравнительно с императивными языками, где функции — объекты второго порядка (C).
Функции высшего порядка: передача функции как аргумента[править | править код]
В языках, где функции — это объекты первого порядка, функции могут быть переданы как аргументы другим функциями так же, как и любые другие значения. Так, например, в Haskell:
map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : map f xs
Языки, где функции не являются объектами первого порядка, позволяют реализовывать функции высшего порядка с помощью использования делегатов.
Указатели в языке Си с некоторыми ограничениями позволяют строить функции высшего порядка (можно передавать и возвращать адрес именованной функции, но нельзя порождать новые функции):
void map(int (*f)(int), int x[], size_t n) { for (int i = 0; i < n; i++) x[i] = f(x[i]); }
Анонимные и вложенные функции[править | править код]
В языках, поддерживающих анонимные функции, можно передать такую функцию как аргумент функции высшего порядка:
main = map (\x -> 3 * x + 1) [1, 2, 3, 4, 5]
В языках, не поддерживающих анонимных функций, необходимо сперва связать функцию с именем:
int f(int x) { return 3 * x + 1; } int main() { int l[] = {1, 2, 3, 4, 5}; map(f, l, 5); }
Нелокальные переменные и замыкания[править | править код]
Если язык программирования поддерживает анонимные или вложенные функции, достаточно логично предполагать, что они будут ссылаться на переменные за пределами тела функции:
main = let a = 3 b = 1 in map (\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); }
Функции высшего порядка: возврат функций как результата[править | править код]
При возврате функции на самом деле происходит возврат её замыкания. В примере на С все локальные переменные, заключённые в замыкание, выйдут из области видимости как только функция, которая составляет замыкание, вернёт управление. Форсирование замыкания в дальнейшем может привести к неопределённому поведению.
См. также[править | править код]
Примечания[править | править код]
- ↑ Abelson, Harold; Sussman, Gerald Jay Structure and Interpretation of Computer Programs (англ.). — MIT Press, 1984. — P. Section 1.3 Formulating Abstractions with Higher—Order Procedures. — ISBN 0-262-01077-1.
- ↑ Programming language pragmatics, by Michael Lee Scott, section 11.2 «Functional Programming».
- ↑ Roberto Ierusalimschy; Luiz Henrique de Figueiredo; Waldemar Celes. The Implementation of Lua 5.0 (неопр.). Архивировано 23 июня 2017 года.
- ↑ 1 2 Rod Burstall, «Christopher Strachey—Understanding Programming Languages», Higher-Order and Symbolic Computation 13:52 (2000)
- ↑ Joel Moses. «The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem» Архивная копия от 3 апреля 2015 на Wayback Machine. MIT AI Memo 199, 1970.
Литература[править | править код]
- Leonidas Fegaras. «Functional Languages and Higher-Order Functions». CSE5317/CSE4305: Design and Construction of Compilers. University of Texas at Arlington.