Interested Article - Функции первого класса

В информатике язык программирования имеет функции первого класса , если он рассматривает функции как объекты первого класса . В частности, это означает, что язык поддерживает передачу функций в качестве аргументов другим функциям, возврат их как результат других функций, присваивание их переменным или сохранение в структурах данных . Некоторые теоретики языков программирования считают необходимым условием также поддержку анонимных функций . В языках с функциями первого класса имена функций не имеют никакого специального статуса, они рассматриваются как обычные значения, тип которых является функциональным . Термин был впервые использован в контексте «функции как объекты первого класса» в середине 1960-х .

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

Существуют некоторые сложности в реализации передачи функций как аргументов и возвращении их как результата, особенно в присутствии , введённых во и анонимных функциях . Исторически они были названы проблемами фунарга , от английского «function argument» . В ранних императивных языках программирования эти проблемы обходились путём отказа от поддержки возвращения функций как результата или отказа от вложенных функций и следовательно нелокальных переменных (в частности, C ). Lisp , один из первых функциональных языков программирования, применяет подход динамической области видимости , где нелокальные переменные возвращают ближайшее определение этих переменных к точке, в которой функция была вызвана, вместо точки, в которой она была объявлена. Полноценная поддержка для функций первого порядка была введена в Scheme и предполагает обработку ссылок на функции как замыканий вместо чистых , что, в свою очередь, делает необходимым применение сборки мусора .

Концепции

В этой секции рассматривается, как конкретные идиомы программирования реализуются в функциональных языках с функциями первого порядка ( 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 ; . Structure and Interpretation of Computer Programs (англ.) . — MIT Press , 1984. — P. Section 1.3 . — ISBN 0-262-01077-1 .
, by Michael Lee Scott, section 11.2 «Functional Programming».
Roberto Ierusalimschy; Luiz Henrique de Figueiredo; Waldemar Celes. (неопр.) . 23 июня 2017 года.
↑ Rod Burstall, «Christopher Strachey—Understanding Programming Languages», 13 :52 (2000)
. от 3 апреля 2015 на Wayback Machine . MIT AI Memo 199, 1970.