Первоклассная функция

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

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

Существуют определенные трудности реализации при передаче функций в качестве аргументов или их возвращении в качестве результатов, особенно при наличии нелокальных переменных, представленных в вложенных и анонимные функции. Исторически они назывались задачами funarg, название происходит от «аргумент функции». В ранних императивных языках этих проблем можно было избежать, либо не поддерживая функции в качестве типов результатов (например, ALGOL 60, Pascal ), либо исключая вложенные функции и, следовательно, нелокальные переменные (например, С ). Ранний функциональный язык Lisp использовал подход динамического определения области действия, где нелокальные переменные относятся к ближайшему определению этой переменной в точке, где выполняется функция, а не в том месте, где она был определен. Надлежащая поддержка функций первого класса с лексической областью видимости была представлена ​​в схеме и требует обработки ссылок на функции как замыканий вместо простых указателей на функции, что, в свою очередь, делает сборку мусора необходимостью.

• 1 Основные понятия
  • 1.1 Функции высшего порядка: передача функций в качестве аргументов
  • 1.2 Анонимные и вложенные функции
  • 1.3 Нелокальные переменные и замыкания
  • 1.4 Функции высшего порядка: возврат функции как результаты
  • 1.5 Присвоение функций переменным
  • 1.6 Равенство функций
• 2 Теория типов
• 3 Поддержка языка
• 4 См. также
• 5 Примечания
• 6 Ссылки
• 7 Внешние ссылки

В этом разделе мы сравниваем, как определенные идиомы программирования обрабатываются на функциональном языке с функциями первого класса (Haskell ) по сравнению с императивным языком, где функции граждане второго сорта (C ).

Функции высшего порядка: передача функций в качестве аргументов

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

map :: (a ->b) ->[a] ->[b] map f = map f (x: xs) = fx: 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 обновляет массив in-place, не возвращая никакого значения, тогда как в 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}; карта (f, список, 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}; карта (закрытие, 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.

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

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

Функциональные языки программирования, такие как Схема, 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

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

Лисп

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

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

Python

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

Ruby

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

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

Явное каррирование с [1] .

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

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

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