Первоклассная функция - First-class function

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

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

Существуют определенные трудности реализации при передаче функций в качестве аргументов или их возврате в качестве результатов, особенно при наличии нелокальных переменных, представленных во вложенных и анонимных функциях . Исторически они назывались проблемами funarg , название происходит от «аргумент функции». В ранних императивных языках этих проблем можно было избежать либо без поддержки функций в качестве типов результатов (например, ALGOL 60 , Pascal ), либо путем исключения вложенных функций и, следовательно, нелокальных переменных (например, 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]);
}

Между этими двумя подходами есть ряд различий, которые напрямую не связаны с поддержкой первоклассных функций. Образец Haskell работает со списками , а образец C работает с массивами . Обе являются наиболее естественными составными структурами данных на соответствующих языках, и использование примера C для работы со связанными списками сделало бы его излишне сложным. Это также учитывает тот факт, что функции C требуется дополнительный параметр (задающий размер массива). Функция C обновляет массив на месте , не возвращая значения, тогда как в Haskell структуры данных являются постоянными (возвращается новый список. в то время как старый остается нетронутым.) В примере Haskell используется рекурсия для обхода списка, а в примере C используется итерация . Опять же, это наиболее естественный способ выразить эту функцию на обоих языках, но образец Haskell можно легко выразить в терминах свертки, а образец C - в терминах рекурсии. Наконец, функция Haskell имеет полиморфный тип, поскольку он не поддерживается в C, мы зафиксировали все переменные типа в константе типа int.

Анонимные и вложенные функции

В языках, поддерживающих анонимные функции, мы можем передать такую ​​функцию в качестве аргумента функции высшего порядка:

main = map (\x -> 3 * x + 1) [1, 2, 3, 4, 5]

На языке, который не поддерживает анонимные функции, мы должны вместо этого привязать его к имени:

int f(int x) {
    return 3 * x + 1;
}

int main() {
    int list[] = {1, 2, 3, 4, 5};
    map(f, list, 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);
}

Также обратите внимание, что mapтеперь он специализируется на функциях, относящихся к двум intвне их среды. Это можно настроить в более общем плане, но для этого потребуется больше шаблонного кода . Если fбы это была вложенная функция, мы все равно столкнулись бы с той же проблемой, и по этой причине они не поддерживаются в C.

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

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

Назначение функций переменным

Назначение функций переменным и их хранение в (глобальных) структурах данных потенциально сталкивается с теми же трудностями, что и возврат функций.

f :: [[Integer] -> [Integer]]
f = let a = 3
        b = 1
     in [map (\x -> a * x + b), map (\x -> b * x + a)]

Равенство функций

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

Экстенсивное равенство

Две функции f и g считаются экстенсивно равными, если они согласовывают свои выходы для всех входов (∀ x . F ( x ) = g ( x )). В соответствии с этим определением равенства, например, любые две реализации в алгоритме сортировки стабильной , такие как вставки рода и сортировка слиянием , будет считаться равными. Решение об экстенсиональном равенстве в общем случае неразрешимо и даже для функций с конечной областью определения часто неразрешимо. По этой причине ни один язык программирования не реализует равенство функций как экстенсиональное равенство.

Внутреннее равенство

При содержательном равенстве две функции f и g считаются равными, если они имеют одинаковую «внутреннюю структуру». Этот вид равенства может быть реализован в интерпретируемых языках путем сравнения исходного кода тел функций (например, в Interpreted Lisp 1.5) или объектного кода на скомпилированных языках . Интенсивное равенство подразумевает экстенсиональное равенство (при условии, что функции детерминированы и не имеют скрытых входных данных, таких как программный счетчик или изменяемая глобальная переменная ).

Ссылочное равенство

Учитывая непрактичность реализации экстенсионального и интенсионального равенства, большинство языков, поддерживающих функции тестирования на равенство, используют ссылочное равенство. Всем функциям или замыканиям присваивается уникальный идентификатор (обычно это адрес тела функции или замыкания), и равенство определяется на основе равенства идентификаторов. Два отдельно определенных, но в остальном идентичных определения функций будут считаться неравными. Ссылочное равенство подразумевает интенсиональное и экстенсиональное равенство. Ссылочное равенство нарушает ссылочную прозрачность и поэтому не поддерживается в чистых языках, таких как Haskell.

Теория типов

В теории типа , тип функций , принимающее значение типа А и возвращающееся значение типа B может быть записан в виде A → B или B ^A . В переписке Карри-Говарда , типы функций связаны с логической импликации ; лямбда-абстракция соответствует выполнению гипотетических предположений, а применение функции соответствует правилу вывода modus ponens . Помимо обычного случая программирования функций, теория типов также использует первоклассные функции для моделирования ассоциативных массивов и подобных структур данных .

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

Языковая поддержка

Функциональные языки программирования, такие как Scheme , ML , Haskell , F # и Scala , имеют первоклассные функции. Когда был разработан Lisp , один из самых ранних функциональных языков, не все аспекты функций первого класса были правильно поняты, в результате чего функции были динамически ограничены. Более поздние диалекты Scheme и Common Lisp действительно имеют функции первого класса с лексической областью видимости.

Многие языки сценариев, включая Perl , Python , PHP , Lua , Tcl / Tk, JavaScript и Io , имеют первоклассные функции.

Для императивных языков необходимо проводить различие между Algol и его потомками, такими как Pascal, традиционным семейством C и современными вариантами со сборкой мусора. Семейство Algol допускает вложенные функции и функции, принимающие функции более высокого порядка в качестве аргументов, но не функции более высокого порядка, которые возвращают функции в качестве результатов (за исключением Algol 68, который позволяет это). Причина этого заключалась в том, что не было известно, как работать с нелокальными переменными, если в результате была возвращена вложенная функция (и в таких случаях Algol 68 выдает ошибки времени выполнения).

Семейство C позволяло передавать функции как аргументы и возвращать их как результаты, но избегало каких-либо проблем, не поддерживая вложенные функции. (Компилятор gcc допускает их как расширение.) Поскольку полезность возвращаемых функций в первую очередь заключается в возможности возвращать вложенные функции, которые захватили нелокальные переменные, вместо функций верхнего уровня, эти языки обычно не считаются имеющими первыми -классовые функции.

Современные императивные языки часто поддерживают сборку мусора, что делает возможной реализацию первоклассных функций. Первоклассные функции часто поддерживались только в более поздних версиях языка, включая C # 2.0 и расширение Apple Blocks для C, C ++ и Objective-C. В C ++ 11 добавлена ​​поддержка анонимных функций и замыканий в языке, но из-за того, что язык не является сборщиком мусора, необходимо соблюдать особую осторожность, чтобы нелокальные переменные в функциях возвращались в качестве результатов (см. Ниже ).

C ++

Замыкания C ++ 11 могут захватывать нелокальные переменные путем создания копии, по ссылке (без продления срока их существования) или путем перемещения (переменная живет до тех пор, пока действует замыкание). Первый вариант безопасен, если замыкание возвращается, но требует копии и не может использоваться для изменения исходной переменной (которая может больше не существовать во время вызова замыкания). Второй вариант потенциально позволяет избежать дорогостоящей копии и позволяет изменять исходную переменную, но небезопасен в случае возврата закрытия (см. Висящие ссылки ). Третий вариант безопасен, если замыкание возвращается и не требует копии, но также не может использоваться для изменения исходной переменной.

Джава

Замыкания Java 8 могут захватывать только final или «фактически final» нелокальные переменные. Типы функций Java представлены как классы. Анонимные функции принимают тип, выведенный из контекста. Ссылки на методы ограничены. Дополнительные сведения см. В разделе Анонимная функция § Ограничения Java .

Лисп

Варианты Lisp с лексической областью видимости поддерживают замыкания. Варианты с динамической областью видимости не поддерживают замыкания и не нуждаются в специальной конструкции для создания замыканий.

В Common Lisp идентификатор функции в пространстве имен функции не может использоваться в качестве ссылки на значение первого класса. Для functionполучения функции как значения необходимо использовать специальный оператор : (function foo)вычисляет объект функции. #'fooсуществует как сокращенное обозначение. Для того, чтобы применить такую функцию объекта, необходимо использовать funcallфункцию: (funcall #'foo bar baz).

Python

Явное частичное применение с functools.partialверсии 2.5, а operator.methodcallerс версии 2.6.

Рубин

Идентификатор обычной «функции» в Ruby (которая на самом деле является методом) нельзя использовать в качестве значения или передавать. Сначала он должен быть извлечен в объект Methodили, Procчтобы использовать его в качестве первоклассных данных. Синтаксис вызова такого функционального объекта отличается от вызова обычных методов.

Определения вложенных методов на самом деле не вкладывают в область видимости.

Явное каррирование с помощью [1].

Смотрите также

• Дефункционализация
• оценка
• Первоклассное сообщение
• Исчисление Каппа - формализм, исключающий первоклассные функции
• Тест на мужчину или мальчика
• Частичное применение

Примечания

использованная литература

• Леонидас Фегарас . «Функциональные языки и функции высшего порядка» . CSE5317 / CSE4305: Проектирование и создание компиляторов. Техасский университет в Арлингтоне.

внешние ссылки

• Первоклассные функции на Rosetta Code .
• Функции высшего порядка на IBM developerWorks