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

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

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

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

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

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

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

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

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

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

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

Люди в мире Algol / Fortran годами жаловались, что не понимают, какое возможное закрытие функций будет иметь в эффективном программировании будущего. Затем произошла революция "объектно-ориентированного программирования", и теперь все программируют, используя закрытие функций, за исключением того, что они все еще отказываются называть их так.

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

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

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

Задача восходящих фанарг сложнее. 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.

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

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

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

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

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

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

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

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

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