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

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

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

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

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

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

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

Это замечание привело к остроте от Генри Бейкера:

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

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

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

EDIT: добавление примера (я собираюсь использовать синтаксис 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 проблема и есть две подзадачи: в нисходящая проблема фунаргов и восходящая проблема фунаргов.

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

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

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

лямбда-это анонимная, динамически определяемыми

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

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

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

The закрытие отражает свободные переменные на окружающая среда. Среда все еще будет существовать, даже если окружающий код больше не будет активен.

пример в 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)

отметим, что

основное отличие возникает из-за отсутствия лексического охвата в C.

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

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

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

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

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

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

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

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