Первоклассная функция
В информатике говорят , что язык программирования имеет первоклассные функции , если он рассматривает функции как первоклассных граждан . Это означает, что язык поддерживает передачу функций в качестве аргументов другим функциям, возврат их как значений из других функций, присвоение их переменным или сохранение в структурах данных. [1] требуется поддержка анонимных функций (функциональных литералов). Некоторым теоретикам языков программирования также [2] В языках с функциями первого класса имена функций не имеют какого-либо особого статуса; они обрабатываются как обычные переменные с типом функции . [3] Этот термин был придуман Кристофером Стрейчи в контексте «функций первоклассных граждан» в середине 1960-х годов. [4]
Первоклассные функции необходимы для стиля функционального программирования , в котором использование функций высшего порядка является стандартной практикой. Простым примером функции высшего порядка является функция карты , которая принимает в качестве аргументов функцию и список и возвращает список, сформированный путем применения функции к каждому члену списка. Чтобы язык поддерживал карту , он должен поддерживать передачу функции в качестве аргумента.
Существуют определенные трудности реализации при передаче функций в качестве аргументов или возврате их в качестве результатов, особенно при наличии нелокальных переменных, введенных во вложенные и анонимные функции . Исторически это называлось проблемами funarg , название происходит от «аргумента функции». [5] В ранних императивных языках этих проблем можно было избежать, либо не поддерживая функции как типы результатов (например, АЛГОЛ 60 , Паскаль ), либо опуская вложенные функции и, следовательно, нелокальные переменные (например, C ). Ранний функциональный язык Lisp использовал подход динамической области видимости , где нелокальные переменные относятся к ближайшему определению этой переменной в точке выполнения функции, а не там, где она была определена. Правильная поддержка с лексической областью функций первого класса была введена в Scheme и требует обработки ссылок на функции как замыканий , а не простых указателей на функции . [4] что, в свою очередь, делает сбор мусора необходимостью.
Концепции [ править ]
В этом разделе мы сравниваем, как отдельные идиомы программирования обрабатываются в функциональном языке с функциями первого класса ( Haskell ) по сравнению с императивным языком, где функции являются гражданами второго класса ( C ).
Функции высшего порядка: передача функций в качестве аргументов [ править ]
В языках, где функции являются первоклассными гражданами, функции могут передаваться в качестве аргументов другим функциям так же, как и другие значения (функция, принимающая другую функцию в качестве аргумента, называется функцией высшего порядка). На языке Хаскель :
карта :: ( a -> b ) -> [ a ] -> [ b ]
карта f [] = []
карта f ( x : xs ) = f x : карта 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.
Анонимные и вложенные функции [ править ]
В языках, поддерживающих анонимные функции, мы можем передать такую функцию в качестве аргумента функции более высокого порядка:
основной = карта ( \ 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 = пусть a = 3
b = 1
в карте ( \ x -> a * x + b ) [ 1 , 2 , 3 , 4 , 5 ]
Если функции представлены простыми указателями на функции, мы больше не можем знать, как следует передать ей значение, находящееся за пределами тела функции, и из-за этого замыкание необходимо создавать вручную. Поэтому о «первоклассных» функциях здесь говорить не приходится.
typedef struct {
int ( * f )( int , int , int );
инт а ;
интервал б ;
} замыкание_т ;
void карта ( closure_t * closure , int x [], size_t n ) {
for ( int i = 0 ; i < n ; ++ i )
x [ i ] = ( closure -> f )( closure -> a , closure - > б , х [ я ]);
}
Int F ( int a , int b , int x ) {
return a * x + b ;
}
void main () {
int l [] = { 1 , 2 , 3 , 4 , 5 };
интервал а = 3 ;
интервал б = 1 ;
closure_t закрытие = { f , a , b };
карта ( & замыкание , л , 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 | Имеет указатели на функции, объекты функций . (Также см. ниже.)
Явное частичное применение возможно с | |
| С# | Да | Да | 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].
См. также [ править ]
- Дефункционализация
- оценивать
- Первоклассное сообщение
- Каппа-исчисление - формализм, исключающий функции первого класса.
- Тест мужчина или мальчик
- Частичное применение
Примечания [ править ]
- ^ Абельсон, Гарольд ; Сассман, Джеральд Джей (1984). Структура и интерпретация компьютерных программ . МТИ Пресс. Формулирование абстракций с помощью процедур высшего порядка . ISBN 0-262-01077-1 . Архивировано из оригинала 21 сентября 2021 г. Проверено 27 сентября 2021 г.
- ^ Прагматика языка программирования , Майкл Ли Скотт, раздел 11.2 «Функциональное программирование».
- ^ Роберто Иерусалимский ; Луис Энрике де Фигейредо; Вальдемар Селес (2005). «Реализация Lua 5.0» . Журнал универсальной информатики . 11 (7): 1159–1176. дои : 10.3217/jucs-011-07-1159 .
- ^ Перейти обратно: а б Берстолл, Род; Стрейчи, Кристофер (2000). «Понимание языков программирования» (PDF) . Вычисления высшего порядка и символьные вычисления . 13 (52): 11–49. дои : 10.1023/А:1010052305354 . S2CID 1989590 . Архивировано из оригинала 16 февраля 2010 года.
{{cite journal}}: CS1 maint: bot: статус исходного URL неизвестен ( ссылка ) (также 16 февраля 2010 г. ) - ^ Джоэл Мозес . «Функция FUNCTION в LISP, или Почему проблему FUNARG следует называть проблемой среды» . Памятка MIT AI 199, 1970 г.
- ^ «Если вы попытаетесь вызвать вложенную функцию по ее адресу после завершения работы содержащей функции, начнется ад». ( Коллекция компиляторов GNU: вложенные функции )
- ^ Эндрю В. Аппель (1995). «Интенсиональное равенство ;=) для продолжений» .
- ^ Таненбаум, А.С. (1977). «Сравнение ПАСКАЛЬ и Алгола 68» . Компьютерный журнал . 21 (4): 319. doi : 10.1093/comjnl/21.4.316 .
- ^ «История Python: истоки «функциональных» особенностей Python» . 21 апреля 2009 г.
- ^ Вложенные функции с использованием лямбда-выражений/замыканий
- ^ Перейти обратно: а б Док № 1968 : В. Самко; Дж. Уиллкок, Дж. Ярви, Д. Грегор, А. Лумсдайн (26 февраля 2006 г.) Лямбда-выражения и замыкания для C++
- ^ «Центр разработки Mac: Темы по программированию блоков: Введение» . Архивировано из оригинала 31 августа 2009 г.
- ^ «2 примера на Go, которые можно частично применить» .
- ^ "частичное_приложение" . Документы.рс . Проверено 3 ноября 2020 г.
- ^ «SRFI 26: Обозначение для специализации параметров без каррирования» .
- ^ «Джон Ресиг — Частичное применение в JavaScript» .
- ^ Кац, Ян (23 июля 2010 г.). «Код Lua для карри (функции каррирования)» . Архивировано из оригинала 06.11.2018.
- ^ «Блог | Perlgeek.de :: Каррирование» .
- ^ «Что нового в Python 2.5 — документация Python 3.10.0» .
- ^ «Анонимные функции — MATLAB и Simulink — MathWorks Великобритания» .
- ^ Оценка частичной функции в MATLAB
- ↑ Замыкания в ZetaLisp. Архивировано 19 марта 2012 г. на Wayback Machine.
Ссылки [ править ]
- Леонидас Фегарас . «Функциональные языки и функции высшего порядка» . CSE5317/CSE4305: Проектирование и создание компиляторов. Техасский университет в Арлингтоне.
Внешние ссылки [ править ]
- Первоклассные функции Rosetta Code .
- Функции высшего порядка. Архивировано 12 ноября 2019 г. в Wayback Machine на IBM DeveloperWorks.