Punteros de función, cierres y Lambda

Question

Ahora mismo estoy aprendiendo sobre los punteros de función y, mientras leía el capítulo K & amp; 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 errónea de alguna manera y después de una búsqueda en línea no encontré 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 las lambdas? Hasta donde 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 lugar de 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 cuando la primera es una función normal y cotidiana que se pasa?

Por favor, dime cómo y por qué me equivoco para comparar los dos tan de cerca.

Gracias.

Answer 1

Un lambda (o closing ) encapsula tanto el puntero de función como las variables. Es por esto que, en C #, puedes hacer:

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

Utilicé 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 lessThan, 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 el puntero de esta función a otra función en la que menos de lo que no estaba dentro del alcance, tendría que mantenerla activa manualmente pasándola a cada función de la cadena o promoviéndola a un nivel global.

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

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

Answer 2

Como alguien que ha escrito compiladores para lenguajes con y sin cierres "reales", respetuosamente no estoy de acuerdo con algunas de las respuestas anteriores. Un cierre de 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 llama el 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 función) dinámicamente asignando un nuevo registro que contiene un puntero al código mismo , pero con valores diferentes para Las variables libres.

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

1. Pase un puntero a la función (el código) y un puntero a las variables libres, para 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 # 1 es ideal cuando intentas simular algún tipo de polimorfismo en C y no quieres revelar el tipo de entorno: usas un puntero void * para representar el medio ambiente. Para ver ejemplos, consulte C Interfaces e Implementaciones 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 conocida ... objetos C ++ con funciones miembro virtuales. Las implementaciones son casi idénticas.

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

  

Las personas en el mundo de Algol / Fortran se quejaron durante años de que no entendían qué posibilidades podrían tener 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 los programas utilizan cierres de funciones, excepto que todavía se niegan a llamarlos así.

Answer 3

En C, no puede definir la función en línea, por lo que no puede crear un cierre. Todo lo que está haciendo es pasar una referencia a un método predefinido. En los idiomas 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 (a menos que cuentes el alcance global), mientras que los cierres incluyen el alcance del método que los define. Con las lambdas, puede escribir un método que escribe un método. Los cierres le permiten vincular " algunos argumentos a una función y, como resultado, obtener una función de menor aridad. & Quot; (tomado del comentario de Thomas). No puedes hacer eso en C.

EDITAR: Agregar un ejemplo (usaré la sintaxis de Actionscript-ish porque eso es lo que tengo en mente ahora):

¿Dices que tienes algún método que toma otro método como argumento, pero no proporciona una manera de pasarle parámetros a ese método cuando se llama? Como, digamos, algún método que causa un retraso antes de ejecutar el método que lo pasaste (ejemplo estúpido, pero quiero que sea sencillo).

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

Ahora diga que quiere usar el usuario 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 al proceso () ya no es una función definida estáticamente. Se genera dinámicamente y puede incluir referencias a variables que estaban en el alcance cuando se definió el método. Por lo tanto, puede acceder a 'o' y 'objectProcessor', aunque no estén en el ámbito global.

Espero que tenga sentido.

Answer 4

Closure = logic + environment.

Por ejemplo, considera este método 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 (" compara 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 le lleva a través de C # 1, 2 y 3, que muestra cómo los cierres facilitan las cosas.

Answer 5

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

¿Qué tipo de objeto es un puntero a una función anidada? No puede ser simplemente 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 recursión, puede haber varias llamadas diferentes de la función externa activa al mismo tiempo). Esto se denomina funarg problem , y hay dos subproblemas: el problema de funargs hacia abajo y el problema de funargs hacia arriba.

El problema de funargs hacia abajo, es decir, el envío de un puntero de función " abajo de la pila " como argumento de una función a la que llama, en realidad no es incompatible con C, y GCC soporta funciones anidadas como funargs hacia abajo. En GCC, cuando creas un puntero a una función anidada, realmente obtienes un puntero a un trampolín , un código de construcción dinámica 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 a las variables de la función exterior.

El problema de funargs hacia arriba es más difícil. GCC no le impide permitir que exista un puntero del 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 del enlace estático podría apuntar a la 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 representa una función anidada simplemente apunte al registro de activación de la función externa. Dicho objeto se denomina closing . Luego, el idioma normalmente tendrá que admitir recolección de basura para que los registros puedan estar liberado una vez que no hay más punteros apuntando a ellos.

Lambdas ( funciones anónimas ) es realmente un tema aparte, pero generalmente es un lenguaje que permite Definir funciones anónimas sobre la marcha también le permitirá devolverlas como valores de función, por lo que terminarán siendo cierres.

Answer 6

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 combinación de los dos), el típico ejemplo lisp se vería 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-counter está 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]> 

Answer 7

Los cierres implican que alguna variable desde el punto de definición de la función está vinculada a 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 dejar el alcance actual, independientemente de si el cierre las estaba apuntando. Esto llevaría a la clase de errores que las personas contraen cuando devuelven descuidadamente los punteros a las variables locales. Los cierres básicamente implican que todas las variables relevantes son elementos recontados o recolectados en un montón.

No me siento cómodo comparando lambda con el cierre porque no estoy seguro de que las lambdas en todos los idiomas sean cierres, a veces creo que las lambdas solo han sido funciones anónimas definidas localmente sin la unión de variables (Python pre 2.1?).

Answer 8

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 tu aplicación trabaje con otros compiladores y aparentemente está " undefined " comportamiento tan YMMV.

Answer 9

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

Un ejemplo en Common Lisp, donde MAKE-ADDER devuelve 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 función DESCRIBE muestra que los objetos de función para ambos cierres son iguales, pero el entorno es diferente.

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

Answer 10

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 no apilada a la que haga referencia es global, estática o similar.

Un cierre, OTOH, tiene su propio estado en forma de 'variables externas', o 'valores superiores'. Pueden ser tan privados o compartidos como desee, utilizando el alcance 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, por lo tanto, pueden ser la interfaz de un objeto (en el sentido de POO). 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 a la función MÁS algún estado. es un constructo de nivel superior

Answer 11

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 nombradas. Aquí hay un ejemplo en Perl:

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

El cierre es el entorno que define la variable $ count . Solo está disponible para la subrutina increment y persiste entre llamadas.

Answer 12

En C, el puntero de una función es un puntero que invocará una función cuando se elimine la referencia, un cierre es un valor que contiene la lógica de una función y el entorno (las 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 los lenguajes funcionales (como Esquema), puede pasar funciones de la misma manera que pasa cualquier otro valor