Указатели на функции, замыкания и лямбда

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

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

Обновлено: добавление примера (я собираюсь использовать синтаксис ActionScript, потому что это то, что у меня на уме прямо сейчас):

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

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

Функция, которую вы передаете процессу (), больше не является какой-то статически определенной функцией. Он генерируется динамически и может включать ссылки на переменные, которые были в области видимости при определении метода. Таким образом, он может получить доступ к 'o' и 'objectProcessor', даже если они не входят в глобальную область видимости.

Надеюсь, это имело смысл.

Замыкание = логика + окружение.

Например, рассмотрим этот метод C# 3:

public Person FindPerson(IEnumerable<Person> people, string name)
{
    return people.Where(person => person.Name == name);
}

Лямбда-выражение инкапсулирует не только логику («сравнить имя»), но и среду, включая параметр (т.е. локальную переменную) «имя».

Чтобы узнать больше об этом, посмотрите мой статья о закрытии, который проведет вас через C# 1, 2 и 3, показывая, как закрытие упрощает задачу.

Основное отличие возникает из-за отсутствия лексической области видимости в C.

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

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

Несколько замыканий могут совместно использовать некоторые переменные, а значит, могут быть интерфейсом объекта (в смысле ООП). чтобы сделать это в C, вы должны связать структуру с таблицей указателей функций (то, что делает C++, с классом vtable).

короче говоря, замыкание - это указатель на функцию ПЛЮС некоторое состояние. это конструкция более высокого уровня

Лямбда - это анонимная функция динамически определяемый. Вы просто не можете сделать это в 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# вы можете:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

Я использовал там анонимный делегат в качестве закрытия (его синтаксис немного яснее и ближе к C, чем лямбда-эквивалент), который захватил lessThan (переменную стека) в закрытие. Когда закрытие оценивается, будет по-прежнему ссылаться на 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 не входил в область видимости, мне пришлось бы либо вручную поддерживать его в рабочем состоянии, передавая его каждой функции в цепочке, либо повышая его до глобального.

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

Резюме: замыкание - это комбинация указателя на функцию + захваченных переменных.

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

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

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

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

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

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

Большинство ответов указывают на то, что замыкания требуют указателей функций, возможно, на анонимные функции, но поскольку замыкания Марк написал могут существовать с именованными функциями. Вот пример на Perl:

{
    my $count;
    sub increment { return $count++ }
}

Замыкание - это среда, которая определяет переменную $count. Он доступен только для подпрограммы increment и сохраняется между вызовами.

Как человек, писавший компиляторы для языков как с «настоящими» замыканиями, так и без них, я с уважением не согласен с некоторыми из приведенных выше ответов. Замыкание на Lisp, Scheme, ML или Haskell не создает новую функцию динамически. Вместо этого это повторно использует существующую функцию, но делает это с новые бесплатные переменные. Набор свободных переменных часто называют среда, по крайней мере, теоретиками языка программирования.

Замыкание - это просто агрегат, содержащий функцию и среду. В компиляторе Standard ML of New Jersey мы представляли его как запись; одно поле содержало указатель на код, а другие поля содержали значения свободных переменных. Компилятор динамически создал новое закрытие (не функцию) выделяет новую запись, содержащую указатель на код такой же, но со значениями разные для свободных переменных.

Вы можете смоделировать все это на C, но это заноза в заднице. Популярны две техники:

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

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

Метод №1 идеален, когда вы пытаетесь смоделировать какой-то тип полиморфизм на C и не хотите раскрывать тип среды - вы используете указатель void * для представления среды. Для примера посмотрите Интерфейсы C и реализации Дэйва Хэнсона. Техника №2, которая больше напоминает то, что происходит в компиляторах машинного кода для функциональных языков, также напоминает другую знакомую технику ... объекты C++ с виртуальными функциями-членами. Реализации практически идентичны.

Это наблюдение привело к острой шутке Генри Бейкера:

People in the Algol/Fortran world complained for years that they didn't understand what possible use function closures would have in efficient programming of the future. Then the `object oriented programming' revolution happened, and now everyone programs using function closures, except that they still refuse to to call them that.

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

Одна из важных проблем с 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.