Функція першого класу

В інформатиці мова програмування має функції першого класу, якщо вона розглядає функції як об'єкти першого класу.Зокрема, це означає, що мова підтримує передачу функцій як аргументів інших функцій, повернення їх як результат інших функцій, присвоювання їх змінним або збереження в структурах даних.^[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

Мови, де функції не є об'єктами першого порядку, дозволяють реалізовувати функції вищого порядку за допомогою використання таких прийомів як делегування. Вказівники у мові C з деякими обмеженнями дозволяють будувати функції вищого порядку (можна передавати і повертати адресу іменованої функції, але не можна породжувати нові функції):

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);
}

При поверненні функції насправді відбувається повернення її замикання. У прикладі на С всі локальні змінні, укладені в замикання вийдуть з області видимості як тільки програми вийде з функції, яка становить замикання. Форсування замикання в подальшому може призвести до невизначеного поведінки.

• Лямбда-вирази
• Функціональний тип

• First-class functions on Rosetta Code.
• Higher order functions at IBM developerWorks

• Leonidas Fegaras. «Functional Languages and Higher-Order Functions». CSE5317/CSE4305: Design and Construction of Compilers. University of Texas at Arlington.