В компьютерных наукахязык программирование имеет функции первого класса, если он рассматривиет функции как объекты первого класса. В частности, это означает, что язык поддерживает передачу функций в качестве аргументов другим функциям, возврат их как результат других функций, присваивание их переменным или сохранение в страктурах данных [1] Некоторые теоретики языков программирование считают необходимым условием также поддержку анонимных функций. [2] В языках с функциями первого класса именя функций не имеют никакого специального статуса, они рассматриваются как обычные переменные типа функцииfunction type.[3] Термин был впервые использован Кристофером Стрейчи в контексте «функции как объекты первого класса» в середине 1960-х. [4]
Функции первого класса являются неотъемлимой частью [функционального программирования], в котором использование функций высшего порядка является стандартной практикой. Простым примером функции высшего порядка будет функция map, которая принимает в качестве своих аргументов фунцию и список и возвращается список, после примененения функции к каждому элементу списке. Чтобы язык программирования поддерживал map, он должен поддерживать передачу функций как аргумента.
Существуют некоторые сложности в реализации передачи функций как аргументов и возвращении их как разультата, особенно в присутствии non-local variable, введенных в вложенных и анонимных функциях. Исторически они были названы funarg problems, the name coming from "function argument".[5] В ранних императивных языках программирования эти проблемы обходились путем отказа от поддержки возвращения функций как результата или отказа от вложенных функций и следовательно нелокальных переменных(в частности C). Lisp, один из первых функциональных языков программирования примених подход dynamic scoping, где нелокальные переменные возвращают ближайшее определение этих переменных к точке, в которой функция была вызвана, вместо точки, в которой она была объявлена. Полноценная поддержка для lexically scoped функций первого порядка была введена в Scheme и предполагает обработку ссылок на функции как замыканий вместо чистых function pointers[4], что, в свою очередь, делает необходимым применение garbage collection.
Концепции edit
В этой секции рассматривается, как конкретные идиомы программирования реализуются в функциональных языках с функциями первого порядка (Haskell) сравнительно с императивными языками, где функции - объекты второго порядка (C).
Функции высшего порядка: передача функции как аргумента edit
В языках, где функции - это объекты первого порядка, функции могут быть переданы как аргументы другим функциями так же как и любые другие значения. Так, например, в Haskell:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
Языки, где функции не являются объектами первого порядка позволяют реализовывать функции высшего порядка с помощью использования таких приемов как function pointers or delegates. Так, в языке 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 требует дополительный параметр(размер массива) и вносит изменения в структуру на месте, не возвращая никаких данных, в то время как фрагмент на Haskell возвращает новый список, оставляя старый в неизменном виде, что связано с особенностями реализации списков.
Анонимные и вложенные функции edit
В языках, поддерживающих анонимные функции, можно передать такую функцию как аргумент функции высшего порядка:
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);
}
Нелокальные переменные и замыкания edit
Если язык программирования поддерживает анонимные или вложенные функции достаточно логично предполагать, что они будут ссылаться на переменные за пределами тела функции (called non-local variables):
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);
}
Функции высшего порядка: возврат функций как результата edit
При возврате функции на самом деле происходит возврат её замыкания. В примере на С все локальные переменные, заключенные в замыкание выйдут из scope как только программы выйдет из функции, которая составляет замыкание. Форсирование замыкания в дальнейшем может привести к неопределенному поведению.
См. также edit
- Defunctionalization
- eval
- First-class message
- Kappa calculus – a formalism which excludes first-class functions
- Man or boy test
- Partial application
Примечания edit
- ^ Abelson, Harold; Sussman, Gerald Jay (1984). Structure and Interpretation of Computer Programs. MIT Press. 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" (PDF).
{{cite journal}}: Cite journal requires|journal=(help) - ^ a b 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". MIT AI Memo 199, 1970.
Литература edit
- Leonidas Fegaras. "Functional Languages and Higher-Order Functions". CSE5317/CSE4305: Design and Construction of Compilers. University of Texas at Arlington.
Ссылки edit
Категория:Функциональное программирование Категория:Лямбда-исчисление