✖


Jump to content

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

(Перенаправлено из функций первого класса )

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

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

Существуют определенные трудности реализации при передаче функций в качестве аргументов или возврате их в качестве результатов, особенно при наличии нелокальных переменных, введенных во вложенные и анонимные функции . Исторически это называлось проблемами funarg , название происходит от «аргумента функции». [5] В ранних императивных языках этих проблем можно было избежать, либо не поддерживая функции как типы результатов (например, АЛГОЛ 60 , Паскаль ), либо опуская вложенные функции и, следовательно, нелокальные переменные (например, C ). Ранний функциональный язык Lisp использовал подход динамической области видимости , где нелокальные переменные относятся к ближайшему определению этой переменной в точке выполнения функции, а не там, где она была определена. Правильная поддержка с лексической областью видимости функций первого класса была введена в Scheme и требует обработки ссылок на функции как замыканий, а не простых указателей на функции . [4] что, в свою очередь, делает сбор мусора необходимостью.

Концепции

[ редактировать ]

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

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

[ редактировать ]
Дополнительная информация: функция высшего порядка.

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

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

Между двумя подходами существует ряд отличий, не связанных напрямую с поддержкой первоклассных функций. Образец 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. [6]

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

[ редактировать ]

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

Присвоение функций переменным

[ редактировать ]

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

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

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

[ редактировать ]
Дополнительная информация: Функциональное равенство.

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

Расширенное равенство
Две функции f и g считаются экстенсионально равными, если они согласуются на своих выходах для всех входов (∀ x . f ( x ) = g ( x )). Например, согласно этому определению равенства любые две реализации стабильного алгоритма сортировки , такие как сортировка вставкой и сортировка слиянием , будут считаться равными. Решение о расширенном равенстве в целом неразрешимо и даже для функций с конечными областями определения часто неразрешимо. По этой причине ни один язык программирования не реализует равенство функций как экстенсиональное равенство.
Интенсиональное равенство
При интенсиональном равенстве две функции f и g считаются равными, если они имеют одинаковую «внутреннюю структуру». Такого рода равенство можно реализовать в интерпретируемых языках путем сравнения исходного кода тел функций (например, в Interpreted Lisp 1.5) или объектного кода в компилируемых языках . Интенсиональное равенство подразумевает экстенсиональное равенство (при условии, что функции детерминированы и не имеют скрытых входных данных, таких как программный счетчик или изменяемая глобальная переменная ).
Эталонное равенство
Учитывая непрактичность реализации экстенсионального и интенсионального равенства, большинство языков, поддерживающих функции проверки на равенство, используют ссылочное равенство. Всем функциям или замыканиям присваивается уникальный идентификатор (обычно адрес тела функции или замыкания), а равенство определяется на основе равенства идентификатора. Два отдельно определенных, но в остальном идентичных определения функции будут считаться неравными. Референциальное равенство подразумевает интенсиональное и экстенсиональное равенство. Ссылочное равенство нарушает ссылочную прозрачность и поэтому не поддерживается в чистых языках, таких как Haskell.

Теория типов

[ редактировать ]
Основная статья: Тип функции

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

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

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

[ редактировать ]

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

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

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

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

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

Язык Функции высшего порядка Вложенные функции Нелокальные переменные Примечания
Аргументы Результаты Именованный Анонимный Замыкания Частичное применение
Семья Алголь АЛГОЛ 60 Да Нет Да Нет Вниз Нет Иметь типы функций .
АЛГОЛ 68 Да Да [8] Да Да Вниз [9] Нет
Паскаль Да Нет Да Нет Вниз Нет
Есть Да Нет Да Нет Вниз Нет
Оберон Да Только невложенные Да Нет Вниз Нет
Дельфи Да Да Да 2009 2009 Нет
Семья С С Да Да Да, в GNU C Да в Clang ( блоки ) Да в Clang ( блоки ) Нет Имеет указатели на функции .
С++ Да Да С++11 [10] С++11 [11] С++11 [11] С++11 Имеет указатели на функции, объекты функций . (Также см. ниже.)

Явное частичное применение возможно с std::bind.

С# Да Да 7 2.0 / 3.0 2.0 3.0 Имеет делегаты (2.0) и лямбда-выражения (3.0).
Цель-C Да Да Использование анонимного 2.0 + Блоки [12] 2.0 + Блоки Нет Имеет указатели на функции.
Ява Да Да Использование анонимного Ява 8 Ява 8 Да Имеет анонимные внутренние классы .
Идти Да Да Использование анонимного Да Да Да [13]
Лимбо Да Да Да Да Да Нет
газеты Да Да Да Да Да Нет
Ржавчина Да Да Да Да Да Да [14]
Функциональные языки Лисп Синтаксис Синтаксис Да Да Общий Лисп Нет (см. ниже)
Схема Да Да Да Да Да СРФИ 26 [15]
Юлия Да Да Да Да Да Да
Кложур Да Да Да Да Да Да
МЛ Да Да Да Да Да Да
Хаскелл Да Да Да Да Да Да
jq Да Нет Да Только выражения Вниз Нет
Скала Да Да Да Да Да Да
Эрланг Да Да Да Да Да Да
Эликсир Да Да Да Да Да Да
Ф# Да Да Да Да Да Да
OCaml Да Да Да Да Да Да
Языки сценариев Этот Да Да Да Да Да Нет
JavaScript Да Да Да Да Да ECMAScript 5 Частичное применение возможно с кодом пользователя на ES3. [16]
Два Да Да Да Да Да Да [17]
PHP Да Да Использование анонимного 5.3 5.3 Нет Частичное применение возможно с использованием кода земли пользователя.
Перл Да Да 6 Да Да 6 [18]
Питон Да Да Да Только выражения Да 2.5 [19] (см. ниже)
Руби Синтаксис Синтаксис Без области действия Да Да 1.9 (см. ниже)
Другие языки Фортран Да Да Да Нет Нет Нет
Клен Да Да Да Да Да Нет
Математика Да Да Да Да Да Нет
МАТЛАБ Да Да Да Да [20] Да Да Возможно частичное применение за счет автоматического создания новых функций. [21]
Смолток Да Да Да Да Да Частичный Частичное применение возможно через библиотеку.
Быстрый Да Да Да Да Да Да
С++
Замыкания C++11 могут захватывать нелокальные переменные посредством конструкции копирования, по ссылке (без продления их времени жизни) или конструкции перемещения (переменная живет до тех пор, пока работает замыкание). Первый вариант безопасен, если замыкание возвращается, но требует копии и не может использоваться для изменения исходной переменной (которая может больше не существовать на момент вызова замыкания). Второй вариант потенциально позволяет избежать дорогостоящего копирования и позволяет изменять исходную переменную, но небезопасен в случае возврата замыкания (см. висячие ссылки ). Третий вариант безопасен, если замыкание возвращается и не требует копирования, но также не может использоваться для изменения исходной переменной.
Ява
Замыкания Java 8 могут захватывать только конечные или «фактически конечные» нелокальные переменные. Java Типы функций представлены как классы. Анонимные функции принимают тип, выведенный из контекста. Ссылки на методы ограничены. Дополнительные сведения см. в разделе Анонимная функция § Ограничения Java .
Лисп
с лексической областью Варианты Lisp поддерживают замыкания. Варианты с динамической областью действия не поддерживают замыкания и не требуют специальной конструкции для создания замыканий. [22]
В Common Lisp идентификатор функции в пространстве имен функции не может использоваться как ссылка на значение первого класса. Специальный оператор function должен использоваться для получения функции как значения: (function foo) оценивается как объект функции. #'foo существует в виде сокращенной записи. Чтобы применить такой объект функции, необходимо использовать funcall функция: (funcall #'foo bar baz).
Питон
Явное частичное применение с functools.partial начиная с версии 2.5, и operator.methodcaller начиная с версии 2.6.
Руби
Идентификатор обычной «функции» в Ruby (которая на самом деле является методом) не может использоваться как значение или передаваться. Сначала его необходимо извлечь в Method или Proc объект, который будет использоваться в качестве первоклассных данных. Синтаксис вызова такого функционального объекта отличается от вызова обычных методов.
Определения вложенных методов фактически не вкладывают область действия.
Явное каррирование с [1].

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Абельсон, Гарольд ; Сассман, Джеральд Джей (1984). Структура и интерпретация компьютерных программ . МТИ Пресс. Формулирование абстракций с помощью процедур высшего порядка . ISBN  0-262-01077-1 . Архивировано из оригинала 21 сентября 2021 г. Проверено 27 сентября 2021 г.
  2. ^ Прагматика языка программирования , Майкл Ли Скотт, раздел 11.2 «Функциональное программирование».
  3. ^ Роберто Иерусалимский ; Луис Энрике де Фигейредо; Вальдемар Селес (2005). «Реализация Lua 5.0» . Журнал универсальной информатики . 11 (7): 1159–1176. дои : 10.3217/jucs-011-07-1159 .
  4. ^ Jump up to: а б Берстолл, Род; Стрейчи, Кристофер (2000). «Понимание языков программирования» (PDF) . Вычисления высшего порядка и символьные вычисления . 13 (52): 11–49. дои : 10.1023/А:1010052305354 . S2CID   1989590 . Архивировано из оригинала 16 февраля 2010 года. {{cite journal}}: CS1 maint: bot: статус исходного URL неизвестен ( ссылка ) (также 16 февраля 2010 г.)
  5. ^ Джоэл Мозес . «Функция FUNCTION в LISP, или Почему проблему FUNARG следует называть проблемой среды» . Памятка MIT AI 199, 1970 г.
  6. ^ «Если вы попытаетесь вызвать вложенную функцию по ее адресу после завершения работы содержащей функции, начнется ад». ( Коллекция компиляторов GNU: вложенные функции )
  7. ^ Эндрю В. Аппель (1995). «Интенсиональное равенство ;=) для продолжений» .
  8. ^ Таненбаум, А.С. (1977). «Сравнение ПАСКАЛЬ и Алгола 68» . Компьютерный журнал . 21 (4): 319. doi : 10.1093/comjnl/21.4.316 .
  9. ^ «История Python: истоки «функциональных» особенностей Python» . 21 апреля 2009 г.
  10. ^ Вложенные функции с использованием лямбда-выражений/замыканий
  11. ^ Jump up to: а б Док № 1968 : В. Самко; Дж. Уиллкок, Дж. Ярви, Д. Грегор, А. Лумсдайн (26 февраля 2006 г.) Лямбда-выражения и замыкания для C++
  12. ^ «Центр разработки Mac: Темы по программированию блоков: Введение» . Архивировано из оригинала 31 августа 2009 г.
  13. ^ «2 примера на Go, которые можно частично применить» .
  14. ^ "частичное_приложение" . Документы.рс . Проверено 3 ноября 2020 г.
  15. ^ «SRFI 26: Обозначение для специализации параметров без каррирования» .
  16. ^ «Джон Ресиг — Частичное применение в JavaScript» .
  17. ^ Кац, Ян (23 июля 2010 г.). «Код Lua для карри (функции каррирования)» . Архивировано из оригинала 06.11.2018.
  18. ^ «Блог | Perlgeek.de :: Каррирование» .
  19. ^ «Что нового в Python 2.5 — документация Python 3.10.0» .
  20. ^ «Анонимные функции — MATLAB и Simulink — MathWorks Великобритания» .
  21. ^ Оценка частичной функции в MATLAB
  22. ↑ Замыкания в ZetaLisp. Архивировано 19 марта 2012 г. на Wayback Machine.

Ссылки

[ редактировать ]
[ редактировать ]
Retrieved from "https://en.wikipedia.org/w/index.php?title=First-class_function&oldid=1218716647"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: c37edb4f10a4c8f849fbba62c9447712__1712996400
URL1:https://arc.ask3.ru/arc/aa/c3/12/c37edb4f10a4c8f849fbba62c9447712.html
Заголовок, (Title) документа по адресу, URL1:
First-class function - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)