¿Es necesaria la recolección de basura para implementar cierres seguros?

14

Hace poco asistí a un curso en línea sobre lenguajes de programación en el que, entre otros conceptos, se presentaron cierres. Escribo dos ejemplos inspirados en este curso para dar un contexto antes de hacer mi pregunta.

El primer ejemplo es una función SML que produce una lista de los números del 1 al x, donde x es el parámetro de la función:

fun countup_from1 (x: int) =
    let
        fun count (from: int) =
            if from = x
            then from :: []
            else from :: count (from + 1)
    in
        count 1
    end

En el SML REPL:

val countup_from1 = fn : int -> int list
- countup_from1 5;
val it = [1,2,3,4,5] : int list

La countup_from1función usa el cierre auxiliar countque captura y usa la variable xde su contexto.

En el segundo ejemplo, cuando invoco una función create_multiplier t, recupero una función (en realidad, un cierre) que multiplica su argumento por t:

fun create_multiplier t = fn x => x * t

En el SML REPL:

- fun create_multiplier t = fn x => x * t;
val create_multiplier = fn : int -> int -> int
- val m = create_multiplier 10;
val m = fn : int -> int
- m 4;
val it = 40 : int
- m 2;
val it = 20 : int

Por lo tanto, la variable mestá vinculada al cierre devuelto por la llamada a la función y ahora puedo usarla a voluntad.

Ahora, para que el cierre funcione correctamente durante toda su vida útil, necesitamos extender la vida útil de la variable capturada t(en el ejemplo, es un entero pero podría ser un valor de cualquier tipo). Hasta donde sé, en SML esto es posible gracias a la recolección de basura: el cierre mantiene una referencia al valor capturado que luego es eliminado por el recolector de basura cuando se destruye el cierre.

Mi pregunta: en general, ¿es la recolección de basura el único mecanismo posible para garantizar que los cierres sean seguros (se pueden llamar durante toda su vida útil)?

¿O cuáles son otros mecanismos que podrían garantizar la validez de los cierres sin recolección de basura: copiar los valores capturados y almacenarlos dentro del cierre? ¿Restringir la vida útil del cierre para que no se pueda invocar después de que las variables capturadas hayan expirado?

¿Cuáles son los enfoques más populares?

EDITAR

No creo que el ejemplo anterior se pueda explicar / implementar copiando las variables capturadas en el cierre. En general, las variables capturadas pueden ser de cualquier tipo, por ejemplo, pueden estar vinculadas a una lista muy grande (inmutable). Entonces, en la implementación sería muy ineficiente copiar estos valores.

En aras de la exhaustividad, aquí hay otro ejemplo que utiliza referencias (y efectos secundarios):

(* Returns a closure containing a counter that is initialized
   to 0 and is incremented by 1 each time the closure is invoked. *)
fun create_counter () =
    let
        (* Create a reference to an integer: allocate the integer
           and let the variable c point to it. *)
        val c = ref 0
    in
        fn () => (c := !c + 1; !c)
    end

(* Create a closure that contains c and increments the value
   referenced by it it each time it is called. *)
val m = create_counter ();

En el SML REPL:

val create_counter = fn : unit -> unit -> int
val m = fn : unit -> int
- m ();
val it = 1 : int
- m ();
val it = 2 : int
- m ();
val it = 3 : int

Por lo tanto, las variables también se pueden capturar por referencia y siguen vivas después de que se create_counter ()haya completado la llamada a la función que las creó ( ).

Giorgio
fuente
2
Cualquier variable que esté cerrada debe protegerse de la recolección de basura, y cualquier variable que no esté cerrada debe ser elegible para la recolección de basura. De ello se deduce que cualquier mecanismo que pueda rastrear de manera confiable si una variable está cerrada o no también puede reclamar de manera confiable la memoria que ocupa la variable.
Robert Harvey
3
@btilly: el recuento es solo una de las muchas estrategias de implementación diferentes para un recolector de basura. Realmente no importa cómo se implemente el GC para el propósito de esta pregunta.
Jörg W Mittag
3
@btilly: ¿Qué significa la recolección de basura "verdadera"? El recuento es solo otra forma de implementar GC. El rastreo es más popular, probablemente debido a las dificultades de recopilar ciclos con el recuento. (Por lo general, terminas con un GC de rastreo separado de todos modos, entonces, ¿por qué molestarse en implementar dos GC si puedes salir con uno?) Pero hay otras formas de lidiar con los ciclos. 1) Solo prohibirlos. 2) Solo ignóralos. (Si está realizando una implementación para scripts rápidos y únicos, ¿por qué no?) 3) Intente detectarlos explícitamente. (Resulta que tener el recuento disponible puede acelerar eso).
Jörg W Mittag
1
Depende de por qué quieres cierres en primer lugar. Si desea implementar, digamos, una semántica de cálculo lambda completa, definitivamente necesita GC, punto. No hay otra forma de evitarlo. Si desea algo que se parezca distantemente a los cierres, pero no siga la semántica exacta de los mismos (como en C ++, Delphi, lo que sea): haga lo que quiera, use análisis de región, use la administración de memoria totalmente manual.
SK-logic
2
@Mason Wheeler: los cierres son solo valores, en general no es posible predecir cómo se moverán en tiempo de ejecución. En este sentido, no son nada especial, lo mismo sería válido para una cadena, una lista, etc.
Giorgio

Respuestas:

14

El lenguaje de programación Rust es interesante en este aspecto.

Rust es un lenguaje de sistema, con un GC opcional, y fue diseñado con cierres desde el principio.

Como las otras variables, los cierres de óxido vienen en varios sabores. Los cierres de pila , los más comunes, son para uso de una sola vez. Viven en la pila y pueden hacer referencia a cualquier cosa. Los cierres propios toman posesión de las variables capturadas. Creo que viven del llamado "montón de intercambio", que es un montón global. Su vida útil depende de quién los posea. Los cierres gestionados viven en el montón local de tareas, y el GC de la tarea los rastrea. Sin embargo, no estoy seguro de sus limitaciones de captura.

revs barjak
fuente
1
Enlace muy interesante y referencia al lenguaje Rust. Gracias. +1.
Giorgio
1
Pensé mucho antes de aceptar una respuesta porque encuentro que la respuesta de Mason también es muy informativa. Elegí este porque es informativo y cita un lenguaje menos conocido con un enfoque original para los cierres.
Giorgio
Gracias por eso. Estoy muy entusiasmado con este idioma joven y estoy feliz de compartir mi interés. No sabía si era posible realizar cierres seguros sin GC, antes de enterarme de Rust.
barjak
9

Desafortunadamente, comenzar con un GC lo convierte en una víctima del síndrome XY:

  • los cierres requieren que las variables que cerraron vivan siempre que el cierre lo requiera (por razones de seguridad)
  • usando el GC podemos extender la vida útil de esas variables el tiempo suficiente
  • Síndrome XY: ¿existen otros mecanismos para extender la vida útil?

Sin embargo, tenga en cuenta que la idea de extender la vida útil de una variable no es necesaria para un cierre; acaba de ser traído por el GC; la declaración de seguridad original es solo que las variables cerradas deben vivir tanto tiempo como el cierre (e incluso eso es inestable, podríamos decir que deberían vivir hasta después de la última invocación del cierre).

Esencialmente, hay dos enfoques que puedo ver (y podrían combinarse):

  1. Extienda la vida útil de las variables cerradas (como lo hace un GC, por ejemplo)
  2. Restringir la vida útil del cierre.

Este último es solo un enfoque simétrico. No se usa con frecuencia, pero si, como Rust, tiene un sistema de tipos compatible con la región, entonces es ciertamente posible.

Matthieu M.
fuente
7

La recolección de basura no es necesaria para cierres seguros, al capturar variables por valor. Un ejemplo destacado es C ++. C ++ no tiene recolección de basura estándar. Las lambdas en C ++ 11 son cierres (capturan variables locales del ámbito circundante). Cada variable capturada por un lambda puede especificarse para ser capturada por valor o por referencia. Si se captura por referencia, puede decir que no es seguro. Sin embargo, si una variable se captura por valor, entonces es segura, porque la copia capturada y la variable original están separadas y tienen vidas independientes.

En el ejemplo de SML que dio, es simple de explicar: las variables se capturan por valor. No hay necesidad de "extender la vida útil" de ninguna variable porque solo puede copiar su valor en el cierre. Esto es posible porque, en ML, no se pueden asignar variables. Por lo tanto, no hay diferencia entre una copia y muchas copias independientes. Aunque SML tiene recolección de basura, no está relacionada con la captura de variables por cierres.

La recolección de basura tampoco es necesaria para cierres seguros al capturar variables por referencia (tipo de). Un ejemplo es la extensión de Apple Blocks para los lenguajes C, C ++, Objective-C y Objective-C ++. No hay recolección de basura estándar en C y C ++. Los bloques capturan variables por valor por defecto. Sin embargo, si se declara una variable local con __block, entonces los bloques las capturan aparentemente "por referencia", y son seguras; pueden usarse incluso después del alcance en el que se definió el bloque. Lo que sucede aquí es que las __blockvariables son en realidad un estructura especial debajo, y cuando se copian bloques (los bloques deben copiarse para usarlos fuera del alcance en primer lugar), ellos "mueven" la estructura para__block variable en el montón, y el bloque gestiona su memoria, creo que a través del recuento de referencias.

usuario102008
fuente
44
"La recolección de basura no es necesaria para los cierres". La pregunta es si es necesaria para que el lenguaje pueda imponer cierres seguros. Sé que puedo escribir cierres seguros en C ++ pero el lenguaje no los impone. Para los cierres que extienden la vida útil de las variables capturadas, consulte la edición de mi pregunta.
Giorgio
1
Supongo que la pregunta podría reformularse: para cierres seguros .
Matthieu M.
1
El título contiene el término "cierres seguros", ¿crees que podría formularlo de una mejor manera?
Giorgio
1
¿Pueden corregir el segundo párrafo? En SML, los cierres extienden la vida útil de los datos a los que hacen referencia las variables capturadas. Además, es cierto que no puede asignar variables (cambiar su enlace) pero sí tiene datos mutables (a través de ref's). Entonces, OK, uno puede debatir si la implementación de cierres está relacionada con la recolección de basura o no, pero las declaraciones anteriores deben corregirse.
Giorgio
1
@ Jorge: ¿Qué tal ahora? Además, ¿en qué sentido encuentra incorrecta mi afirmación de que los cierres no necesitan extender la vida útil de una variable capturada? Cuando habla de datos mutables, habla de tipos de referencia ( refs, matrices, etc.) que apuntan a una estructura. Pero el valor es la referencia en sí, no lo que señala. Si tiene var a = ref 1y hace una copia var b = ay usa b, ¿eso significa que todavía está usando a? No. ¿Tiene acceso a la misma estructura señalada por a? Sí. Así es como funcionan estos tipos en SML y no tienen nada que ver con los cierres
user102008
6

La recolección de basura no es necesaria para implementar cierres. En 2008, el lenguaje Delphi, que no es basura recolectada, agregó una implementación de cierres. Funciona así:

El compilador crea un objeto functor debajo del capó que implementa una interfaz que representa un cierre. Todas las variables locales cerradas se cambian de locales para el procedimiento de cierre a campos en el objeto functor. Esto asegura que el estado se mantenga mientras el functor lo esté.

La limitación de este sistema es que cualquier parámetro pasado por referencia a la función de cierre, así como el valor del resultado de la función, no puede ser capturado por el functor porque no son locales cuyo alcance está limitado al de la función de cierre.

La referencia de cierre hace referencia al functor, utilizando azúcar sintáctico para que el desarrollador lo vea como un puntero de función en lugar de una interfaz. Utiliza el sistema de recuento de referencias de Delphi para las interfaces para garantizar que el objeto functor (y todo el estado que posee) permanezca "vivo" todo el tiempo que sea necesario, y luego se libera cuando el recuento cae a 0.

Mason Wheeler
fuente
1
¡Ah, entonces solo es posible capturar la variable local, no los argumentos! ¡Esto parece una compensación razonable e inteligente! +1
Giorgio
1
@Giorgio: puede capturar argumentos, solo que no son parámetros var .
Mason Wheeler
2
También pierde la capacidad de tener 2 cierres que se comunican a través del estado privado compartido. No lo encontrará en los casos de uso básico, pero limita su capacidad de hacer cosas complejas. ¡Sigue siendo un gran ejemplo de lo que es posible!
btilly
3
@btilly: En realidad, si coloca 2 cierres dentro de la misma función de cierre, eso es perfectamente legal. Terminan compartiendo el mismo objeto functor, y si modifican el mismo estado entre sí, los cambios en uno se reflejarán en el otro.
Mason Wheeler
2
@MasonWheeler: "No. La recolección de basura no es de naturaleza determinista; no hay garantía de que algún objeto sea recogido, y mucho menos cuándo sucederá. Pero el conteo de referencias es determinista: el compilador garantiza que el objeto será liberado inmediatamente después de que el conteo caiga a 0. ". Si tuviera un centavo por cada vez que escuché ese mito perpetuado. OCaml tiene un GC determinista. C ++ thread safe shared_ptrno es determinista porque los destructores corren para disminuir a cero.
Jon Harrop