Функциональные указатели, замыкания и лямбда
Я только сейчас узнаю о функциональных указателях, и, когда я читал главу K&R по этому вопросу, первое, что меня поразило, было: "Эй, это как закрытие". Я знал, что это предположение в корне неверно, и после поиска в Интернете я не нашел никакого анализа этого сравнения.
Так почему же указатели на функции в стиле C в корне отличаются от замыканий или лямбд? Насколько я могу судить, это связано с тем, что указатель на функцию по-прежнему указывает на определенную (именованную) функцию, в отличие от практики анонимного определения функции.
Почему передача функции в функцию, которая считается более мощной во втором случае, где она не названа, чем в первом случае, когда передается обычная повседневная функция?
Пожалуйста, скажите мне, как и почему я ошибаюсь, сравнивая их так близко.
Благодарю.
13 ответов
Лямбда (или замыкание) инкапсулирует как указатель функции, так и переменные. Вот почему в C# вы можете сделать:
int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
return i < lessThan;
};
Я использовал там анонимный делегат в качестве замыкания (его синтаксис немного яснее и ближе к C, чем лямбда-эквивалент), который захватил lessThan (переменную стека) в замыкании. Когда вычисляется замыкание, будет продолжаться обращение к lessThan (чей кадр стека мог быть уничтожен). Если я изменю меньше, чем тогда, я изменю сравнение:
int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
return i < lessThan;
};
lessThanTest(99); // returns true
lessThan = 10;
lessThanTest(99); // returns false
В C это было бы незаконно:
BOOL (*lessThanTest)(int);
int lessThan = 100;
lessThanTest = &LessThan;
BOOL LessThan(int i) {
return i < lessThan; // compile error - lessThan is not in scope
}
хотя я мог бы определить указатель на функцию, которая принимает 2 аргумента:
int lessThan = 100;
BOOL (*lessThanTest)(int, int);
lessThanTest = &LessThan;
lessThanTest(99, lessThan); // returns true
lessThan = 10;
lessThanTest(100, lessThan); // returns false
BOOL LessThan(int i, int lessThan) {
return i < lessThan;
}
Но теперь я должен передать 2 аргумента при оценке. Если бы я хотел передать указатель на эту функцию в другую функцию, где lessThan не находился в области видимости, мне пришлось бы либо вручную поддерживать ее, передавая ее каждой функции в цепочке, либо передавая ее в глобальную.
Хотя большинство основных языков, которые поддерживают замыкания, используют анонимные функции, для этого нет никаких требований. Вы можете иметь замыкания без анонимных функций и анонимные функции без замыканий.
Резюме: замыкание представляет собой комбинацию указателя на функцию + захваченных переменных.
Как человек, который написал компиляторы для языков как с "настоящими" замыканиями, так и без них, я с уважением не согласен с некоторыми ответами выше. Закрытие Lisp, Scheme, ML или Haskell не создает новую функцию динамически. Вместо этого он повторно использует существующую функцию, но делает это с новыми свободными переменными. Набор свободных переменных часто называют средой, по крайней мере, теоретиками языка программирования.
Замыкание - это просто агрегат, содержащий функцию и среду. В компиляторе Standard ML из Нью-Джерси мы представили один в качестве записи; одно поле содержало указатель на код, а другие поля содержали значения свободных переменных. Компилятор создал новое замыкание (не функцию) динамически, выделяя новую запись, содержащую указатель на тот же код, но с другими значениями для свободных переменных.
Вы можете смоделировать все это в C, но это боль в заднице. Две техники популярны:
Передайте указатель на функцию (код) и отдельный указатель на свободные переменные, чтобы замыкание было разделено на две переменные C.
Передайте указатель на структуру, где структура содержит значения свободных переменных, а также указатель на код.
Техника #1 идеальна, когда вы пытаетесь симулировать какой-то полиморфизм в C, и вы не хотите раскрывать тип окружения - вы используете указатель void * для представления окружения. Для примеров, посмотрите на C Дейв Хэнсон Интерфейсы и Реализации. Техника № 2, которая больше напоминает то, что происходит в компиляторах нативного кода для функциональных языков, также напоминает другую знакомую технику... объекты C++ с виртуальными функциями-членами. Реализации практически идентичны.
Это наблюдение привело к мудрости от Генри Бейкера:
Люди в мире Алгол / Фортран годами жаловались на то, что не понимают, какое возможное использование замыканий функций будет иметь в эффективном программировании будущего. Затем произошла революция "объектно-ориентированного программирования", и теперь все программируют, используя замыкания функций, за исключением того, что они по-прежнему отказываются называть их так.
В C вы не можете определить встроенную функцию, поэтому вы не можете создать замыкание. Все, что вы делаете, это передаете ссылку на какой-то заранее определенный метод. В языках, которые поддерживают анонимные методы / замыкания, определение методов гораздо более гибкое.
Проще говоря, указатели на функции не имеют связанной с ними области видимости (если не считать глобальную область), тогда как замыкания включают область метода, который их определяет. С лямбдами, вы можете написать метод, который пишет метод. Замыкания позволяют вам связать "некоторые аргументы с функцией и получить в результате функцию с меньшим числом аргументов". (взято из комментария Томаса). Вы не можете сделать это в C.
РЕДАКТИРОВАТЬ: Добавление примера (я собираюсь использовать синтаксис Actionscript-ish, потому что это то, что у меня сейчас на уме):
Скажем, у вас есть какой-то метод, который принимает другой метод в качестве аргумента, но не предоставляет способ передать какие-либо параметры этому методу при его вызове? Как, скажем, некоторый метод, который вызывает задержку перед запуском метода, который вы передали (глупый пример, но я хочу, чтобы он был простым).
function runLater(f:Function):Void {
sleep(100);
f();
}
Теперь предположим, что вы хотите использовать runLater(), чтобы отложить некоторую обработку объекта:
function objectProcessor(o:Object):Void {
/* Do something cool with the object! */
}
function process(o:Object):Void {
runLater(function() { objectProcessor(o); });
}
Функция, которую вы передаете process(), больше не является статически определенной функцией. Он генерируется динамически и может включать ссылки на переменные, которые находились в области видимости при определении метода. Таким образом, он может обращаться к "o" и "objectProcessor", даже если они не входят в глобальную область видимости.
Я надеюсь, что это имело смысл.
Закрытие = логика + среда.
Например, рассмотрим этот метод C# 3:
public Person FindPerson(IEnumerable<Person> people, string name)
{
return people.Where(person => person.Name == name);
}
Лямбда-выражение не только инкапсулирует логику ("сравнить имя"), но также и среду, включая параметр (то есть локальную переменную) "имя".
Более подробно об этом смотрите в моей статье о замыканиях, в которой рассказывается о C# 1, 2 и 3, и показано, как замыкания облегчают работу.
В C указатели на функции могут передаваться в качестве аргументов функций и возвращаться как значения из функций, но функции существуют только на верхнем уровне: вы не можете вкладывать определения функций друг в друга. Подумайте о том, что потребуется C для поддержки вложенных функций, которые могут обращаться к переменным внешней функции, и в то же время иметь возможность отправлять указатели на функции вверх и вниз по стеку вызовов. (Чтобы следовать этому объяснению, вы должны знать основы того, как вызовы функций реализованы в C и на большинстве похожих языков: просмотрите статью стека вызовов в Википедии.)
Какой тип объекта является указателем на вложенную функцию? Это не может быть просто адрес кода, потому что, если вы вызываете его, как он получает доступ к переменным внешней функции? (Помните, что из-за рекурсии может быть несколько разных вызовов внешней функции, активной одновременно.) Это называется проблемой funarg, и есть две подзадачи: проблема downar funargs и задача up funargs.
Проблема нисходящих funargs, то есть отправка указателя функции "вниз по стеку" в качестве аргумента вызываемой функции, на самом деле не является несовместимой с C, и GCC поддерживает вложенные функции в качестве нисходящих funargs. В GCC, когда вы создаете указатель на вложенную функцию, вы действительно получаете указатель на батут, динамически создаваемый фрагмент кода, который устанавливает статический указатель ссылки и затем вызывает реальную функцию, которая использует статический указатель ссылки для доступа переменные внешней функции.
Задача вверх funargs является более сложной. GCC не запрещает вам позволить указателю батута существовать после того, как внешняя функция больше не активна (не имеет записи в стеке вызовов), а затем указатель статической ссылки может указывать на мусор. Записи активации больше не могут быть размещены в стеке. Обычное решение - разместить их в куче, и позволить функциональному объекту, представляющему вложенную функцию, просто указать на запись активации внешней функции. Такой объект называется закрытием. Тогда язык, как правило, должен поддерживать сборку мусора, чтобы можно было освобождать записи, если на них больше нет указателей.
Лямбды ( анонимные функции) - это действительно отдельная проблема, но обычно язык, который позволяет вам определять анонимные функции на лету, также позволяет вам возвращать их как значения функций, так что они в конечном итоге становятся замыканиями.
Лямбда - это анонимная динамически определяемая функция. Вы просто не можете сделать это в C... что касается замыканий (или объединения двух), типичный пример lisp будет выглядеть примерно так:
(defun get-counter (n-start +-number)
"Returns a function that returns a number incremented
by +-number every time it is called"
(lambda () (setf n-start (+ +-number n-start))))
В терминах C можно сказать, что лексическая среда (стек) get-counter захватывается анонимной функцией и изменяется внутри, как показано в следующем примере:
[1]> (defun get-counter (n-start +-number)
"Returns a function that returns a number incremented
by +-number every time it is called"
(lambda () (setf n-start (+ +-number n-start))))
GET-COUNTER
[2]> (defvar x (get-counter 2 3))
X
[3]> (funcall x)
5
[4]> (funcall x)
8
[5]> (funcall x)
11
[6]> (funcall x)
14
[7]> (funcall x)
17
[8]> (funcall x)
20
[9]>
Замыкания подразумевают, что некоторая переменная из точки определения функции связана с логикой функции, например, возможность объявления мини-объекта на лету.
Одна важная проблема с C и замыканиями - переменные, расположенные в стеке, будут уничтожены при выходе из текущей области, независимо от того, было ли на них указание замыкания. Это может привести к ошибкам, которые люди получают, когда небрежно возвращают указатели на локальные переменные. Замыкания в основном подразумевают, что все релевантные переменные являются либо пересчитанными, либо собранными мусором в куче.
Мне неудобно приравнивать лямбду к замыканию, потому что я не уверен, что лямбды во всех языках являются замыканиями, иногда я думаю, что лямбды были только что локально определенными анонимными функциями без привязки переменных (Python pre 2.1?).
В GCC можно моделировать лямбда-функции, используя следующий макрос:
#define lambda(l_ret_type, l_arguments, l_body) \
({ \
l_ret_type l_anonymous_functions_name l_arguments \
l_body \
&l_anonymous_functions_name; \
})
Пример из источника:
qsort (array, sizeof (array) / sizeof (array[0]), sizeof (array[0]),
lambda (int, (const void *a, const void *b),
{
dump ();
printf ("Comparison %d: %d and %d\n",
++ comparison, *(const int *) a, *(const int *) b);
return *(const int *) a - *(const int *) b;
}));
Использование этой техники, конечно, исключает возможность работы вашего приложения с другими компиляторами и, по-видимому, является "неопределенным" поведением, так что YMMV.
Закрытие захватывает свободные переменные в среде. Среда все еще будет существовать, даже если окружающий код больше не будет активным.
Пример в Common Lisp, где MAKE-ADDER возвращает новое закрытие.
CL-USER 53 > (defun make-adder (start delta) (lambda () (incf start delta)))
MAKE-ADDER
CL-USER 54 > (compile *)
MAKE-ADDER
NIL
NIL
Используя вышеупомянутую функцию:
CL-USER 55 > (let ((adder1 (make-adder 0 10))
(adder2 (make-adder 17 20)))
(print (funcall adder1))
(print (funcall adder1))
(print (funcall adder1))
(print (funcall adder1))
(print (funcall adder2))
(print (funcall adder2))
(print (funcall adder2))
(print (funcall adder1))
(print (funcall adder1))
(describe adder1)
(describe adder2)
(values))
10
20
30
40
37
57
77
50
60
#<Closure 1 subfunction of MAKE-ADDER 4060001ED4> is a CLOSURE
Function #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment #(60 10)
#<Closure 1 subfunction of MAKE-ADDER 4060001EFC> is a CLOSURE
Function #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment #(77 20)
Обратите внимание, что DESCRIBE Функция показывает, что объекты функции для обоих замыканий одинаковы, но среда различна.
Common Lisp делает и замыкания, и чисто функциональные объекты (без среды) как функции, и их можно вызывать одинаково, при этом используя FUNCALL,
Большинство ответов указывают, что замыкания требуют указателей на функции, возможно, на анонимные функции, но, как писал Марк, замыкания могут существовать с именованными функциями. Вот пример в Perl:
{
my $count;
sub increment { return $count++ }
}
Закрытие является средой, которая определяет $count переменная. Это доступно только для increment подпрограмма и сохраняется между вызовами.
Основное различие возникает из-за отсутствия лексического определения объема C.
Указатель на функцию - это просто указатель на блок кода. Любая переменная не из стека, на которую она ссылается, является глобальной, статической или аналогичной.
Закрытие, OTOH, имеет свое собственное состояние в форме "внешних переменных", или "повышенных значений". они могут быть настолько частными или общими, насколько вы хотите, используя лексическую область видимости. Вы можете создать множество замыканий с одним и тем же кодом функции, но с разными экземплярами переменных.
Несколько замыканий могут совместно использовать некоторые переменные и, следовательно, могут быть интерфейсом объекта (в смысле ООП). чтобы сделать это в C, вы должны связать структуру с таблицей указателей на функции (это то, что делает C++, с классом vtable).
короче говоря, замыкание - это указатель на функцию плюс некоторое состояние. это конструкция более высокого уровня
Большой вопрос: что такое замыкание и/или лямбда за кулисами? что это становится замыканием и/или лямбдой или даже больше, делегатом? вполне возможный ответ заключается в том, что они становятся своего рода указателем на функцию в виде ассемблерного кода, поэтому замыкания, делегаты, лямбда-выражения, анонимные функции, по сути, являются своего рода сахарным синтаксисом для объявления/определения указателей функций на высоком уровне, но эти объявления включает в себя некоторый механизм для определения некоторой области действия переменных среды.
В C указатель на функцию - это указатель, который будет вызывать функцию при разыменовании ее, замыкание - это значение, которое содержит логику функции и среду (переменные и значения, с которыми они связаны), а лямбда-выражение обычно ссылается на значение, которое на самом деле безымянная функция. В C функция не является значением первого класса, поэтому она не может быть передана, поэтому вы должны вместо этого передать указатель на нее, однако в функциональных языках (таких как Scheme) вы можете передавать функции так же, как передаете любое другое значение