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

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

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

Функції вищого порядку: повернення функцій як результату

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

Див. також

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

Примітки

1. 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. 
2. Programming language pragmatics, by Michael Lee Scott, section 11.2 «Functional Programming».
3. Roberto Ierusalimschy; Luiz Henrique de Figueiredo; Waldemar Celes. The Implementation of Lua 5.0. 
4. Rod Burstall, «Christopher Strachey—Understanding Programming Languages», Higher-Order and Symbolic Computation 13:52 (2000)
5. Joel Moses. «The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem». MIT AI Memo 199, 1970.

Посилання

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

Література

• Leonidas Fegaras. . CSE5317/CSE4305: Design and Construction of Compilers. University of Texas at Arlington.