Punteros de función, cierres y Lambda

Recién ahora estoy aprendiendo acerca de los indicadores de función y, mientras leía el capítulo de K&R sobre el tema, lo primero que me llamó la atención fue: "Oye, esto es como un cierre". Sabía que esta suposición es fundamentalmente incorrecta de alguna manera y después de una búsqueda en línea no encontré realmente ningún análisis de esta comparación.

Entonces, ¿por qué los punteros de función de estilo C son fundamentalmente diferentes de los cierres o lambdas? Por lo que puedo decir, tiene que ver con el hecho de que el puntero de función todavía apunta a una función definida (nombrada) en oposición a la práctica de definir la función de forma anónima.

¿Por qué pasar una función a una función se considera más poderosa en el segundo caso, donde no tiene nombre, que en el primero, en el que solo se pasa una función normal y diaria?

Por favor, dígame cómo y por qué me equivoco al comparar los dos tan de cerca.

Gracias.

Una lambda (o cierre ) encapsula tanto el puntero de función como las variables. Por eso, en C #, puede hacer:

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

Usé un delegado anónimo allí como cierre (su sintaxis es un poco más clara y más cercana a C que el equivalente lambda), que capturó lessThan (una variable de pila) en el cierre. Cuando se evalúa el cierre, se seguirá haciendo referencia a lessThan (cuyo marco de pila puede haber sido destruido). Si cambio menos de, entonces cambio la comparación:

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

lessThanTest(99); // returns true
lessThan = 10;
lessThanTest(99); // returns false

En C, esto sería ilegal:

BOOL (*lessThanTest)(int);
int lessThan = 100;

lessThanTest = &LessThan;

BOOL LessThan(int i) {
   return i < lessThan; // compile error - lessThan is not in scope
}

aunque podría definir un puntero de función que toma 2 argumentos:

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

Pero ahora tengo que pasar los 2 argumentos cuando lo evalúo. Si quisiera pasar este puntero de función a otra función en la que lessThan no estuviera dentro del alcance, tendría que mantenerlo activo manualmente pasándolo a cada función en la cadena, o promocionándolo a un global.

Aunque la mayoría de los lenguajes convencionales que admiten cierres utilizan funciones anónimas, no existe ningún requisito para ello. Puede tener cierres sin funciones anónimas y funciones anónimas sin cierres.

Resumen: un cierre es una combinación de puntero de función + variables capturadas.

Como alguien que ha escrito compiladores para lenguajes con y sin cierres 'reales', no estoy de acuerdo respetuosamente con algunas de las respuestas anteriores. Un cierre Lisp, Scheme, ML o Haskell no crea una nueva función de forma dinámica . En su lugar, reutiliza una función existente pero lo hace con nuevas variables libres . La colección de variables libres a menudo se denomina entorno , al menos por los teóricos del lenguaje de programación.

Un cierre es solo un agregado que contiene una función y un entorno. En el compilador Standard ML of New Jersey, representamos uno como un registro; un campo contenía un puntero al código y los otros campos contenían los valores de las variables libres. El compilador creó un nuevo cierre (no una función) dinámicamente al asignar un nuevo registro que contiene un puntero al mismo código, pero con diferentes valores para las variables libres.

Puedes simular todo esto en C, pero es un fastidio. Dos técnicas son populares:

1. Pase un puntero a la función (el código) y un puntero separado a las variables libres, de modo que el cierre se divida entre dos variables C.

2. Pase un puntero a una estructura, donde la estructura contiene los valores de las variables libres y también un puntero al código.

La técnica n. ° 1 es ideal cuando intentas simular algún tipo de polimorfismo en C y no quieres revelar el tipo de entorno; utilizas un puntero vacío * para representar el entorno. Para ver ejemplos, mire las interfaces e implementaciones C de Dave Hanson . La técnica # 2, que se asemeja más a lo que sucede en los compiladores de código nativo para lenguajes funcionales, también se parece a otra técnica familiar ... Objetos C ++ con funciones miembro virtuales. Las implementaciones son casi idénticas.

Esta observación llevó a una broma de Henry Baker:

La gente en el mundo Algol / Fortran se quejó durante años de que no entendían qué posible uso tendrían los cierres de funciones en la programación eficiente del futuro. Luego ocurrió la revolución de la "programación orientada a objetos", y ahora todos programan usando cierres de funciones, excepto que todavía se niegan a llamarlos así.

En C no puede definir la función en línea, por lo que realmente no puede crear un cierre. Todo lo que estás haciendo es pasar una referencia a algún método predefinido. En lenguajes que admiten métodos / cierres anónimos, la definición de los métodos es mucho más flexible.

En los términos más simples, los punteros de función no tienen un alcance asociado con ellos (a menos que cuente el alcance global), mientras que los cierres incluyen el alcance del método que los define. Con lambdas, puede escribir un método que escribe un método. Los cierres le permiten vincular "algunos argumentos a una función y obtener como resultado una función de menor aridad". (tomado del comentario de Thomas). No puedes hacer eso en C.

EDITAR: agregando un ejemplo (voy a usar una sintaxis similar a Actionscript porque eso es lo que tengo en mente en este momento):

Supongamos que tiene algún método que toma otro método como argumento, pero no proporciona una forma de pasar ningún parámetro a ese método cuando se llama. Como, digamos, algún método que causa un retraso antes de ejecutar el método que le pasó (ejemplo estúpido, pero quiero que sea simple).

function runLater(f:Function):Void {
  sleep(100);
  f();
}

Ahora digamos que desea utilizar runLater () para retrasar el procesamiento de un objeto:

function objectProcessor(o:Object):Void {
  /* Do something cool with the object! */
}

function process(o:Object):Void {
  runLater(function() { objectProcessor(o); });
}

La función que está pasando a process () ya no es una función definida estáticamente. Se genera dinámicamente y puede incluir referencias a variables que estaban dentro del alcance cuando se definió el método. Entonces, puede acceder a 'o' y 'objectProcessor', aunque no estén en el alcance global.

Espero que tenga sentido.

Cierre = lógica + entorno.

Por ejemplo, considere este método de C # 3:

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

La expresión lambda no solo encapsula la lógica ("comparar el nombre") sino también el entorno, incluido el parámetro (es decir, la variable local) "nombre".

Para obtener más información sobre esto, eche un vistazo a mi artículo sobre cierres que lo lleva a través de C # 1, 2 y 3, y muestra cómo los cierres facilitan las cosas.

En C, los punteros de función pueden pasarse como argumentos a funciones y devolverse como valores de funciones, pero las funciones existen solo en el nivel superior: no se pueden anidar definiciones de funciones entre sí. Piense en lo que haría falta para que C admita funciones anidadas que puedan acceder a las variables de la función externa, y al mismo tiempo poder enviar punteros de función hacia arriba y hacia abajo en la pila de llamadas. (Para seguir esta explicación, debe conocer los conceptos básicos de cómo se implementan las llamadas a funciones en C y la mayoría de los lenguajes similares: navegue por la entrada de la pila de llamadas en Wikipedia).

¿Qué tipo de objeto es un puntero a una función anidada? No puede ser solo la dirección del código, porque si lo llama, ¿cómo accede a las variables de la función externa? (Recuerde que debido a la recursividad, puede haber varias llamadas diferentes de la función externa activa al mismo tiempo.) Esto se llama el problema de funarg , y hay dos subproblemas: el problema de funargs hacia abajo y el problema de funargs hacia arriba.

El problema de funargs descendentes, es decir, enviar un puntero de función "hacia abajo de la pila" como argumento a una función que llamas, en realidad no es incompatible con C, y GCC admite funciones anidadas como funargs descendentes. En GCC, cuando crea un puntero a una función anidada, realmente obtiene un puntero a un trampolín , una pieza de código construida dinámicamente que configura el puntero de enlace estático y luego llama a la función real, que usa el puntero de enlace estático para acceder las variables de la función externa.

El problema de los funargs hacia arriba es más difícil. GCC no le impide dejar que exista un puntero de trampolín después de que la función externa ya no esté activa (no tiene registro en la pila de llamadas), y luego el puntero de enlace estático podría apuntar a basura. Los registros de activación ya no se pueden asignar en una pila. La solución habitual es asignarlos en el montón y dejar que un objeto de función que represente una función anidada apunte al registro de activación de la función externa. Tal objeto se llama cierre . Entonces, el lenguaje normalmente tendrá que admitir la recolección de basura para que los registros se puedan liberar una vez que no haya más punteros apuntándolos.

Las lambdas ( funciones anónimas ) son en realidad un tema aparte, pero generalmente un lenguaje que le permite definir funciones anónimas sobre la marcha también le permitirá devolverlas como valores de función, por lo que terminan siendo cierres.

Una lambda es una función anónima definida dinámicamente . Simplemente no puede hacer eso en C ... en cuanto a los cierres (o la convicción de los dos), el ejemplo típico de lisp se vería algo como:

(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))))

En términos de C, podría decir que el entorno léxico (la pila) de get-counterestá siendo capturado por la función anónima y modificado internamente como muestra el siguiente ejemplo:

[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]> 

Los cierres implican que alguna variable desde el punto de la definición de la función está vinculada con la lógica de la función, como poder declarar un mini-objeto sobre la marcha.

Un problema importante con C y los cierres es que las variables asignadas en la pila se destruirán al salir del alcance actual, independientemente de si un cierre las apuntó. Esto conduciría al tipo de errores que las personas obtienen cuando devuelven descuidadamente punteros a variables locales. Básicamente, los cierres implican que todas las variables relevantes son elementos contabilizados por referencia o elementos recolectados como basura en un montón.

No me siento cómodo al equiparar lambda con cierre porque no estoy seguro de que lambdas en todos los lenguajes sean cierres, a veces creo que lambdas acaba de ser funciones anónimas definidas localmente sin el enlace de variables (¿Python pre 2.1?).

En GCC es posible simular funciones lambda usando la siguiente macro:

#define lambda(l_ret_type, l_arguments, l_body)       \
({                                                    \
    l_ret_type l_anonymous_functions_name l_arguments \
    l_body                                            \
    &l_anonymous_functions_name;                      \
})

Ejemplo de fuente :

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

El uso de esta técnica, por supuesto, elimina la posibilidad de que su aplicación funcione con otros compiladores y aparentemente tiene un comportamiento "indefinido", por lo que YMMV.

El cierre captura las variables libres en un entorno . El entorno seguirá existiendo, aunque es posible que el código circundante ya no esté activo.

Un ejemplo en Common Lisp, donde MAKE-ADDERdevuelve un nuevo cierre.

CL-USER 53 > (defun make-adder (start delta) (lambda () (incf start delta)))
MAKE-ADDER

CL-USER 54 > (compile *)
MAKE-ADDER
NIL
NIL

Usando la función anterior:

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)

Tenga en cuenta que la DESCRIBEfunción muestra que los objetos de función para ambos cierres son los mismos, pero el entorno es diferente.

Common Lisp hace que tanto los cierres como los objetos de función pura (aquellos sin un entorno) sean funciones y uno puede llamar a ambos de la misma manera, aquí usando FUNCALL.

La principal diferencia surge de la falta de alcance léxico en C.

Un puntero de función es solo eso, un puntero a un bloque de código. Cualquier variable que no sea de pila a la que haga referencia es global, estática o similar.

Un cierre, OTOH, tiene su propio estado en forma de 'variables externas' o 'upvalues'. pueden ser tan privados o compartidos como desee, utilizando el ámbito léxico. Puede crear muchos cierres con el mismo código de función, pero diferentes instancias de variables.

Algunos cierres pueden compartir algunas variables, y también puede ser la interfaz de un objeto (en el sentido de OOP). para hacer eso en C tienes que asociar una estructura con una tabla de punteros de función (eso es lo que hace C ++, con una clase vtable).

en resumen, un cierre es un puntero de función MÁS algún estado. es una construcción de nivel superior

La mayoría de las respuestas indican que los cierres requieren punteros de función, posiblemente a funciones anónimas, pero como Mark escribió, los cierres pueden existir con funciones con nombre. Aquí hay un ejemplo en Perl:

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

El cierre es el entorno que define la $countvariable. Solo está disponible para la incrementsubrutina y persiste entre llamadas.

En C, un puntero de función es un puntero que invocará una función cuando la desreferencia, un cierre es un valor que contiene la lógica de una función y el entorno (variables y los valores a los que están vinculados) y una lambda generalmente se refiere a un valor que es en realidad una función sin nombre. En C, una función no es un valor de primera clase, por lo que no se puede pasar, por lo que debe pasarle un puntero, sin embargo, en lenguajes funcionales (como Scheme) puede pasar funciones de la misma manera que pasa cualquier otro valor