En lenguajes como C, se espera que el programador inserte llamadas gratis. ¿Por qué el compilador no hace esto automáticamente? Los humanos lo hacen en un tiempo razonable (ignorando los errores), por lo que no es imposible.

EDITAR: Para referencia futura, aquí hay otra discusión que tiene un ejemplo interesante.

Porque no se puede decidir si el programa usará la memoria nuevamente. Esto significa que ningún algoritmo puede determinar correctamente cuándo llamar free()en todos los casos, lo que significa que cualquier compilador que intentó hacer esto necesariamente produciría algunos programas con pérdidas de memoria y / o algunos programas que continuaron utilizando la memoria que se había liberado. Incluso si se aseguró de que su compilador nunca hizo el segundo y permitió que el programador inserte llamadas para free()corregir esos errores, saber cuándo llamar free()a ese compilador sería aún más difícil que saber cuándo llamar free()cuando se usa un compilador que no intentó ayudar.

Como David Richerby señaló correctamente, el problema es indecidible en general. La vida del objeto es una propiedad global del programa y, en general, puede depender de los aportes al programa.

¡Incluso la recolección de basura dinámica precisa es un problema indecidible! Todos los recolectores de basura del mundo real usan la accesibilidad como una aproximación conservadora a si se necesitará o no un objeto asignado en el futuro. Es una buena aproximación, pero no obstante es una aproximación.

Pero eso solo es cierto en general. Una de las evasiones más notorias en el negocio de la informática es "es imposible en general, por lo tanto, no podemos hacer nada". Por el contrario, hay muchos casos en los que es posible avanzar.

Las implementaciones basadas en el recuento de referencias están muy cerca del "compilador que inserta las desasignaciones", por lo que es difícil notar la diferencia. El conteo automático de referencia de LLVM (utilizado en Objective-C y Swift ) es un ejemplo famoso.

Inferencia región y la recolección de basura en tiempo de compilación son áreas actuales de investigación activos. Resulta mucho más fácil en lenguajes declarativos como ML y Mercury , donde no puedes modificar un objeto después de que se haya creado.

Ahora, sobre el tema de los humanos, hay tres formas principales en que los humanos manejan las vidas de asignación manualmente:

1. Al comprender el programa y el problema. Los humanos pueden poner objetos con vidas similares en el mismo objeto de asignación, por ejemplo. Los compiladores y los recolectores de basura deben inferir esto, pero los humanos tienen información más precisa.
2. Mediante el uso selectivo de la contabilidad no local (por ejemplo, el recuento de referencias) u otras técnicas especiales de asignación (por ejemplo, zonas) solo cuando sea necesario. Una vez más, un humano puede saber esto donde un compilador debe inferirlo.
3. Mal. Todos saben de los programas implementados en el mundo real que tienen fugas lentas, después de todo. O si no lo hacen, a veces los programas y las API internas deben reestructurarse en función de la vida útil de la memoria, lo que disminuye la reutilización y la modularidad.

Es un problema de incompletitud, no un problema de indecidibilidad.

Si bien es cierto que la ubicación óptima de las declaraciones de desasignación es indecidible, ese no es el problema aquí. Dado que es indecidible tanto para humanos como para compiladores, es imposible seleccionar a sabiendas la ubicación óptima de desasignación, independientemente de si se trata de un proceso manual o automático. Y dado que nadie es perfecto, un compilador suficientemente avanzado debería ser capaz de superar a los humanos al adivinar ubicaciones aproximadamente óptimas. Por lo tanto, la indecidibilidad no es la razón por la que necesitamos declaraciones de asignación explícitas .

Hay casos en los que el conocimiento externo informa la colocación de la declaración de desasignación. Eliminar esas declaraciones es equivalente a eliminar parte de la lógica operativa, y pedirle a un compilador que genere automáticamente esa lógica es equivalente a pedirle que adivine lo que estás pensando.

Por ejemplo, supongamos que está escribiendo un Read-Evaluate-Print-Loop (REPL) : el usuario escribe un comando y su programa lo ejecuta. El usuario puede asignar / desasignar memoria escribiendo comandos en su REPL. Su código fuente especificará qué debe hacer el REPL para cada posible comando de usuario, incluida la desasignación cuando el usuario escribe el comando para ello.

Pero si el código fuente C no proporciona un comando explícito para la desasignación, entonces el compilador necesitaría inferir que debe realizar la deslocalización cuando el usuario ingresa el comando apropiado en el REPL. ¿Es ese comando "desasignar", "libre" o algo más? El compilador no tiene forma de saber cuál quiere que sea el comando. Incluso si programa en lógica para buscar esa palabra de comando y el REPL la encuentra, el compilador no tiene forma de saber que debe responder con desasignación a menos que se lo indique explícitamente en el código fuente.

tl; dr El problema es que el código fuente C no proporciona al compilador conocimientos externos. La indecidibilidad no es el problema porque está ahí si el proceso es manual o automatizado.

Actualmente, ninguna de las respuestas publicadas es totalmente correcta.

¿Por qué los compiladores no insertan automáticamente las desasignaciones?

1. Algunos lo hacen. (Lo explicaré más tarde).

2. Trivialmente, puede llamar free()justo antes de que salga el programa. Pero hay una necesidad implícita en su pregunta de llamar free()lo antes posible.

3. El problema de cuándo llamar free()a cualquier programa C tan pronto como no se pueda acceder a la memoria es indecidible, es decir, para cualquier algoritmo que proporcione la respuesta en un tiempo finito, hay un caso que no cubre. Esto, y muchas otras imposibilidades de los programas arbitrarios, se pueden probar a partir del Problema de detención .

4. Un problema indecidible no siempre puede ser resuelto en tiempo finito por ningún algoritmo, ya sea un compilador o un humano.

5. Los humanos (intentan) escribir en un subconjunto de programas en C que pueden verificarse para la corrección de la memoria por su algoritmo (ellos mismos).

6. Algunos idiomas logran el n. ° 1 al incorporar el n. ° 5 en el compilador. No permiten programas con usos arbitrarios de asignación de memoria, sino un subconjunto decidible de ellos. Foth y Rust son dos ejemplos de lenguajes que tienen una asignación de memoria más restrictiva que los C malloc(), que pueden (1) detectar si un programa está escrito fuera de su conjunto decidible (2) insertar automáticamente desasignaciones.

"Los humanos lo hacen, así que no es imposible" es una falacia bien conocida. No necesariamente entendemos (y mucho menos controlamos) las cosas que creamos: el dinero es un ejemplo común. Tendemos a sobreestimar (a veces dramáticamente) nuestras posibilidades de éxito en asuntos tecnológicos, especialmente cuando los factores humanos parecen estar ausentes.

El rendimiento humano en la programación de computadoras es muy pobre , y el estudio de la informática (que carece de muchos programas de educación profesional) ayuda a comprender por qué este problema no tiene una solución simple. Algún día, quizás no muy lejos, seremos reemplazados por inteligencia artificial en el trabajo. Incluso entonces, no habrá un algoritmo general que haga que la desasignación sea correcta, automáticamente, todo el tiempo.

La falta de administración automática de memoria es una característica del lenguaje.

Se supone que C no es una herramienta para escribir software fácilmente. Es una herramienta para hacer que la computadora haga lo que le diga. Eso incluye asignar y desasignar memoria en el momento de su elección. C es un lenguaje de bajo nivel que utiliza cuando desea controlar la computadora con precisión, o cuando desea hacer las cosas de una manera diferente a la que esperaban los diseñadores de lenguaje / biblioteca estándar.

El problema es principalmente un artefacto histórico, no una imposibilidad de implementación.

La forma en que la mayoría de los compiladores de C construyen código es para que el compilador solo vea cada archivo fuente a la vez; nunca ve todo el programa a la vez. Cuando un archivo fuente llama a una función desde otro archivo fuente o una biblioteca, todo lo que ve el compilador es el archivo de encabezado con el tipo de retorno de la función, no el código real de la función. Esto significa que cuando hay una función que devuelve un puntero, el compilador no tiene forma de saber si la memoria a la que apunta el puntero necesita liberarse o no. La información para decidir que no se muestra al compilador en ese momento. Un programador humano, por otro lado, es libre de buscar el código fuente de la función o la documentación para averiguar qué debe hacerse con el puntero.

Si observa lenguajes de bajo nivel más modernos como C ++ 11 o Rust, encontrará que en su mayoría resolvieron el problema al hacer explícita la propiedad de la memoria en el tipo de puntero. En C ++, usaría un en unique_ptr<T>lugar de un plano T*para mantener la memoria y unique_ptr<T>se asegura de que la memoria se libere cuando el objeto llegue al final del alcance, a diferencia del plano T*. El programador puede pasar la memoria de uno unique_ptr<T>a otro, pero solo puede haber uno unique_ptr<T>apuntando a la memoria. Por lo tanto, siempre está claro quién posee la memoria y cuándo debe liberarse.

C ++, por razones de compatibilidad con versiones anteriores, todavía permite la gestión de memoria manual de estilo antiguo y, por lo tanto, la creación de errores o formas de eludir la protección de a unique_ptr<T>. Rust es aún más estricto ya que impone las reglas de propiedad de la memoria a través de errores del compilador.

En cuanto a la indecidibilidad, el problema de detención y similares, sí, si se adhiere a la semántica en C, no es posible decidir para todos los programas cuándo se debe liberar la memoria. Sin embargo, para la mayoría de los programas reales, no para ejercicios académicos o software con errores, sería absolutamente posible decidir cuándo liberar y cuándo no. Después de todo, esa es la única razón por la cual los humanos pueden decidir cuándo liberarse o no en primer lugar.

Otras respuestas se han centrado en si es posible recolectar basura, algunos detalles de cómo se hace y algunos de los problemas.

Sin embargo, un problema que aún no se ha cubierto es la demora inevitable en la recolección de basura. En C, cuando un programador llama a free (), esa memoria está inmediatamente disponible para su reutilización. (¡Al menos en teoría!) De modo que un programador puede liberar su estructura de 100 MB, asignar otra estructura de 100 MB un milisegundo más tarde y esperar que el uso general de la memoria siga siendo el mismo.

Esto no es cierto con la recolección de basura. Los sistemas recolectados de basura tienen algún retraso en devolver la memoria no utilizada al montón, y esto puede ser significativo. Si su estructura de 100 MB se sale del alcance, y un milisegundo después su programa configura otra estructura de 100 MB, puede esperar razonablemente que su sistema use 200 MB por un período corto. Ese "período corto" puede ser milisegundos o segundos dependiendo del sistema, pero todavía hay un retraso.

Si está ejecutando en una PC con gigas de RAM y memoria virtual, por supuesto, probablemente nunca lo note. Sin embargo, si está ejecutando en un sistema con recursos más limitados (por ejemplo, un sistema integrado o un teléfono), esto es algo que debe tomar en serio. Esto no es solo teórico: personalmente he visto que esto crea problemas (como al bloquear el tipo de problemas del dispositivo) cuando se trabaja en un sistema WinCE utilizando .NET Compact Framework y se desarrolla en C #.

La pregunta supone que una desasignación es algo que el programador debe deducir de otras partes del código fuente. No es. "En este punto del programa, la referencia de memoria FOO ya no es útil" es información que solo el programador conoce hasta que se codifica en (en lenguajes de procedimiento) una declaración de desasignación.

Teóricamente no es diferente de ninguna otra línea de código. ¿Por qué los compiladores no insertan automáticamente "En este punto del programa, verifique el registro BAR para entrada" o "si la llamada de función devuelve un valor distinto de cero, salga de la subrutina actual" ? Desde el punto de vista del compilador, la razón es la "incompletitud", como se muestra en esta respuesta . Pero cualquier programa sufre de incompletitud cuando el programador no le ha contado todo lo que sabe.

En la vida real, las desasignaciones son trabajo duro o repetitivo; nuestros cerebros los llenan automáticamente y se quejan al respecto, y el sentimiento "el compilador podría hacerlo igual o mejor" es cierto. En teoría, sin embargo, ese no es el caso, aunque afortunadamente otros lenguajes nos dan más opciones de teoría.

Qué se hace: hay recolección de basura, y hay compiladores que usan el conteo de referencias (Objective-C, Swift). Aquellos que hacen recuento de referencias necesitan ayuda del programador al evitar ciclos de referencia fuertes.

La verdadera respuesta al "por qué" es que los escritores de compiladores no han descubierto una forma que sea lo suficientemente buena y rápida como para poder utilizarla en un compilador. Dado que los escritores de compiladores suelen ser bastante inteligentes, se puede concluir que es muy, muy difícil encontrar una forma lo suficientemente buena y rápida.

Una de las razones por las que es muy, muy difícil es, por supuesto, que es indecidible. En informática, cuando hablamos de "capacidad de decisión" nos referimos a "tomar la decisión correcta". Por supuesto, los programadores humanos pueden decidir fácilmente dónde desasignar la memoria, porque no se limitan a las decisiones correctas . Y a menudo toman decisiones que están mal.

En lenguajes como C, se espera que el programador inserte llamadas gratis. ¿Por qué el compilador no hace esto automáticamente?

Porque la vida útil de un bloque de memoria es decisión del programador, no del compilador.

Eso es. Este es el diseño de C. El compilador no puede saber cuál era la intención de asignar un bloque de memoria. Los humanos pueden hacerlo, porque conocen el propósito de cada bloque de memoria y cuándo se cumple este propósito para que pueda liberarse. Eso es parte del diseño del programa que se está escribiendo.

C es un lenguaje de bajo nivel, por lo que las instancias de pasar un bloque de su memoria a otro proceso o incluso a otro procesador son bastante frecuentes. En casos extremos, un programador puede asignar intencionalmente una porción de memoria y nunca volver a usarla solo para ejercer presión sobre otras partes del sistema. El compilador no tiene forma de saber si el bloque aún es necesario.

En lenguajes como C, se espera que el programador inserte llamadas gratis. ¿Por qué el compilador no hace esto automáticamente?

En C y en muchos otros lenguajes, existe una posibilidad de hacer que el compilador haga el equivalente de esto en aquellos casos en los que está claro en el momento de la compilación cuándo debe hacerse: uso de variables de duración automática (es decir, variables locales ordinarias) . El compilador es responsable de organizar el espacio suficiente para tales variables y de liberar ese espacio cuando finaliza su vida útil (bien definida).

Dado que las matrices de longitud variable son una característica de C desde C99, los objetos de duración automática cumplen, en principio, sustancialmente todas las funciones en C que hacen los objetos asignados dinámicamente de duración computable. En la práctica, por supuesto, las implementaciones de C pueden establecer límites prácticos significativos en el uso de VLA, es decir, su tamaño puede estar limitado como resultado de su asignación en la pila, pero esto es una consideración de implementación, no una consideración de diseño de lenguaje.

Aquellos objetos cuyo uso previsto impide darles una duración automática son precisamente aquellos cuya vida útil no puede determinarse en tiempo de compilación.