Указатели функций, замыкания и лямбда - PullRequest
83 голосов
/ 16 октября 2008

Я только сейчас узнаю о функциональных указателях и, когда я читал главу K & R по этому вопросу, первое, что поразило меня, было: «Эй, это как закрытие». Я знал, что это предположение в корне неверно, и после поиска в Интернете я не нашел никакого анализа этого сравнения.

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

Почему передача функции в функцию, которая считается более мощной, во втором случае, где она безымянна, чем в первом, где передается обычная повседневная функция?

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

Спасибо.

Ответы [ 12 ]

107 голосов
/ 16 октября 2008

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

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

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

40 голосов
/ 06 декабря 2008

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

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

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

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

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

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

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

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

9 голосов
/ 16 октября 2008

В 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», даже если они не входят в глобальную область.

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

6 голосов
/ 16 октября 2008

Закрытие = логика + среда.

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

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

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

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

4 голосов
/ 16 октября 2008

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

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

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

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

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

3 голосов
/ 16 октября 2008

Лямбда - это анонимная, динамически определяемая функция. Вы просто не можете сделать это в 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]> 
2 голосов
/ 26 ноября 2015

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

Пример в 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.

2 голосов
/ 24 ноября 2015

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

Пример из source :

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.

2 голосов
/ 13 января 2009

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

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

Мне неудобно отождествлять лямбду с замыканием, потому что я не уверен, что лямбды во всех языках являются замыканиями, иногда я думаю, что лямбды были только что локально определенными анонимными функциями без привязки переменных (Python pre 2.1?).

1 голос
/ 17 октября 2008

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

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

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

...