From 1c1c1fec4cad2318bd82688f8bdb7ed3ba48ccec Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Sat, 28 Apr 2007 01:16:22 +0000 Subject: [PATCH] =?utf8?q?Se=20completa=20la=20introducci=C3=B3n,=20al=20m?= =?utf8?q?enos=20en=20principio.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- informe.rst | 242 +++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 193 insertions(+), 49 deletions(-) diff --git a/informe.rst b/informe.rst index 34d2de3..416c113 100644 --- a/informe.rst +++ b/informe.rst @@ -17,15 +17,20 @@ Tesis :Revisión: 1 :Estado: Borrador + .. contents:: +.. =========================================================================== + + Introducción ============ .. Presenta el problema y temas a ser tratados en el trabajo. + ESTADO: TERMINADO -Los lenguajes modernos tienen una tendencia cada vez más marcada -a adoptar técnicas más sofisticadas, haciéndolos más ricos y +Los lenguajes de programación modernos tienen una tendencia cada vez +más marcada a adoptar técnicas sofisticadas, haciéndolos más ricos y convirtiéndolos realmente en lenguajes, no en meros preprocesadores que convierten de una forma muy directa el código en *assembly*, permitiendo construcciones semánticamente más ricas y permitiendo al programar una @@ -35,20 +40,20 @@ del *hardware*. Estos conceptos supuestamente avanzados provienen, en general, de lenguajes académicos (muchos de ellos funcionales) que implementan estas funcionalidades hace mucho tiempo, pero que para su época, o bien no -tuvieron suficiente difusión en el ambiente empresarial, o bien eran -muy lentos por la baja capacidad de procesamiento de la época o incluso +tuvieron suficiente difusión en el ambiente comercial, o bien eran muy +lentos por la baja capacidad de procesamiento de la época o incluso demasiado *revolucionarios* para ser adoptados por programadores que no podían ver las ventajas que esos nuevos conceptos proveen. El caso de la recolección de basura (*garbage collection* en inglés) es uno de los más representativos. Lisp_ introdujo a principio de los -'60 el concepto de recolección de basura como un mecanismo para alocar -y liberar recursos de forma automática, pero no fue hasta avanzados los +'60 este concepto, como un mecanismo para alocar +y liberar recursos de forma automática. Pero no fue hasta avanzados los '90 que esta técnica se empezó a utilizar en lenguajes de programación de uso comercial, cuando fue popularizado por Java_. Incluso luego de más de 30 años para Java_ era costosa la recolección de basura, lo que sumado a la presencia de una máquina virtual para ejecutar los programas -producidos condujo a que estos lenguajes sean notablemente lentos. Aún +producidos, condujo a que estos lenguajes sean notablemente lentos. Aún así Java_ creció y entre las mejoras introducidas hubieron mejoras en la recolección de basura. Otros lenguaje de programación populares que utilizan alguna forma de recolección de basura son Python_, Ruby_, PHP_ @@ -61,15 +66,13 @@ y `C#`_, entre otros. .. _PHP: http://www.php.net/ .. _`C#`: http://www.ecma-international.org/publications/standards/Ecma-334.htm - -Recolección de Basura -===================== -.. Introducción a la importancia de la recolección de basura y sus - principales técnicas, con sus ventajas y desventajas. También se da - un breve recorrido sobre el estado del arte. +.. INTRODUCCION .............................................................. Importancia de la Recolección de Basura --------------------------------------- +.. Breve descripción de la utilidad de la recolección de basura + ESTADO: TERMINADO + La recolección de basura es muchas veces vista por sus críticos de una forma bastante *naive*. Muchas veces se argumenta que sólo es útil para programadores descuidados o que su necesidad es sólo una @@ -93,17 +96,17 @@ Muchas veces se aduce también que la recolección de basura impide el desarrollo de programas eficientes. Si bien es innegable que la recolección de basura impone una carga extra, ésta es, en la mayoría de los casos, imperceptible. Incluso algunos algoritmos de recolección -de basura pueden aumentar la eficiencia en casos determinados, como -los recolectores que compactan, que pueden minimizar considerablemente -la cantidad de páginas de memoria referenciadas por el programa, -mejorando el *hit-ratio* tanto de la memoria virtual como del *cache*. -Aún si este no fuera el caso, o en casos de sistemas de tiempo real o -zonas muy críticas en cuanto a la eficiencia, muchas veces es posible -suspender el recolector de basura en dicho fragmento de código. Es -cierto que esto rompe un poco con la idea de ganar abstracción, pero -es necesario sólo en casos donde hay que realizar optimizaciones y las -optimizaciones son, en general, oscuras de por sí y tienden a perder -abstracción y a depender del *hardware* y otras particularidades. +de basura pueden aumentar la eficiencia en casos determinados, como los +recolectores que compactan, que pueden minimizar considerablemente la +cantidad de páginas de memoria referenciadas por el programa, mejorando +el *hit-ratio* tanto de la memoria virtual como del *cache*. Aún si +este no fuera el caso, o en casos de sistemas de tiempo real o zonas muy +críticas en cuanto a la eficiencia, muchas veces es posible suspender +el recolector de basura en dicho fragmento de código. Es cierto que esto +rompe un poco con la idea de ganar abstracción, pero es necesario sólo +en casos donde hay que realizar optimizaciones y las optimizaciones son, +en general, dependientes de la plataforma (*hardware*) y por lo tanto +de difícil abstracción. El recolector de basura debe tener un comportamiento correcto y predecible para que sea útil, si el programador no puede confiar en el recolector @@ -112,18 +115,21 @@ introduce nuevos puntos de falla en los programas, y lo que es peor, puntos de falla no controlados por el programador, volviendo mucho más difícil la búsqueda de errores. +.. INTRODUCCION .............................................................. El Lenguaje de Programación D -============================= -.. Introducción y breve reseña del lenguaje de programación D. También - se presentan las necesidades particulares de D con respecto al - recolector de basura y su estado actual. +----------------------------- +.. Breve descripción del lenguaje de programación D + ESTADO: TERMINADO D_ es un lenguaje de programación joven. Nació en 1999 y el 2 de enero -de 2007 salió su `versión 1.0`_, aunque han quedado algunas cosas -importantes en el tintero. Su creador, `Walter Bright`_, desarrollador -principal de Zortech C++, el primer compilador de C++ a código nativo, -dice bien claro como nace el lenguaje, citando en su sitio web: +de 2007 salió su `versión 1.0`_. A pesar de alcanzar una versión que podría +suponerse estable, D_ conserva algunas falencias y sigue siendo activamente +desarrollado (incluyendo nuevas características en prácticamente todas la +versiones nuevas, muchas de ellas, además, moviéndose en direcciones muy +experimentales) . Su creador, `Walter Bright`_, desarrollador principal de +Zortech C++, uno de los primeros compilador de C++ que compilaba a código +nativo, dice bien claro como nace el lenguaje, citando en su sitio web: It seems to me that most of the "new" programming languages fall into one of two categories: Those from academia with radical new @@ -145,18 +151,125 @@ Lo que podría traducirse como: D_ es un lenguaje de programación con sintaxis tipo C, multiparadigma, compilado, con tipado fuerte y estático, con buenas capacidades tanto de -programación de bajo nivel (*system programming*) como de alto nivel. Y -este es tal vez el punto más fuerte de D, brindar lo mejor de los 2 -mundos. Si bien tiene herramientas de muy bajo nivel, que por lo tanto -son muy propensas a errores, da una infinidad de mecanismos para evitar -el uso de estas herramientas a menos que sea realmente necesario. -Además pone mucho énfasis en la programación confiable, para lo cual -provee muchos mecanismos para detectar errores en los programas de forma -temprana. +programación de bajo nivel (*system programming*) como de alto nivel, +siendo incluso compatible binariamente con C (se puede enlazar código +objeto C con código objeto D). Y este es tal vez el punto más fuerte +de D_, brindar lo mejor de los 2 mundos. Si bien tiene herramientas +de muy bajo nivel, que por lo tanto son muy propensas a errores, da +una infinidad de mecanismos para evitar el uso de estas herramientas +a menos que sea realmente necesario. Además pone mucho énfasis en +la programación confiable, para lo cual provee muchos mecanismos para +detectar errores en los programas de forma temprana. + +Si puede pensarse en C++ como un "C mejor", podría decirse que D_ es +un "C++ mejor", ya que el objetivo del lenguaje es muy similar a C++, +pero implementa muchas características que jamás pudieron entrar en +el estándar de C++ y lo hace de una forma mucho más limpia, ya que +no debe lidiar con problemas de compatibilidad hacia atrás, y cuenta +se con la experiencia del camino recorrido por C++, pudiendo extraer de +él los mejores conceptos pero evitando sus mayores problemas también. + +Una de las características que nunca pudo entrar en el estándar de C++ +es la recolección de basura. D_ no comete el mismo error. + +.. INTRODUCCION .............................................................. + +Objetivo +-------- +.. Objetivo de la tesis + ESTADO: TERMINADO, EN REVISION + +La recolección de basura en D_ es un problema prácticamente nuevo. Si bien +pueden considerarse válidos todos los modelos propuestos para recolección +de basura en C, estos son muy restrictivos y poco eficientes, por lo +promiscuo que este lenguaje. + +Por otro lado, la recolección de basura en C y C++ está prácticamente +restringida a implementaciones a nivel de bibliotecas, ya que la inclusión +de un recolector de basura en el estándar de C/C++ es algo que no va a +pasar por largo tiempo. Entonces quedan dos caminos posibles: + +1. Quedarse con las limitaciones de un recolector de basura a nivel de + bibliotecas, lo que es muy restrictivo. +2. Construir una solución a nivel de compilador que no cumpla con el + estándar y que no pasará de ser una curiosidad académica. + +La primera opción está ya bastante desarrollada y es casi un sinónimo de un +recolector de basura conservativo. La segunda, no es un objetivo viable para +una Tesis de Ingeniería, donde se pretende llegar a un resultado lo más +práctico posible (hacer un aporte más ingenieril que científico). + +Por lo tanto el objetivo es abordar la segunda opción sobre un lenguaje que +es propenso a absorver nuevas ideas y cambios. Un lenguaje que es además, +mucho más rico sintáctica y semánticamente, sin perder utilidad práctica ni +eficiencia para cumplir las tareas para las cuales C y C++ fueron +diseñados. + +Se propone entonces en este trabajo, desarrollar un recolector de basura +para un lenguaje de programación imperativo compilado, con tipado estático +y enlazable con C (siendo esto último probablemente uno de los desafíos más +importantes), agregando soporte al lenguaje o al compilador (de ser +necesario) y utlizando las características avanzadas que el lenguaje +provee. + +.. INTRODUCCION .............................................................. + +Alcance +------- +.. Alcance de la tesis, qué se pretende hacer + ESTADO: TERMINADO, EN REVISION + +En esta tesis se plantea desarrollar un recolector de basura para el +lenguaje de programación D, utilizando como plataforma el compilador GDC_. +El objetivo es conseguir un recolector de basura eficiente, en tiempo y +espacio, aunque priorizando lo primero. Como objetivo secundario se propone +obtener una recolector configurable, para poder elegir los parámetros que +mejor se ajusten al problema particular. + +.. _GDC: http://dgcc.sourceforge.net/ + +.. INTRODUCCION .............................................................. + +Limitaciones +------------ +.. Cosas que no se pretenden hacer en esta tesis + ESTADO: TERMINADO, EN REVISION + +Dado que el lenguaje de programación D_ puede ser enlazado con código +objeto C, y por lo tanto interactuar directamente con éste, habrán +limitaciones en el recolector resultante con respecto a esto. En este +trabajo se busca lograr un recolector que sea eficiente para casos en donde +el código que interactúa con C esté bien aislado, por lo que estas +porciones de código pueden quedar por fuera del recolector de basura. + +De otra forma probablemente se llegaría a un recolector conservativo y +simple como el que está disponible en la actualidad. + +.. =========================================================================== + + +Recolección de Basura +===================== +.. Introducción a la importancia de la recolección de basura y sus + principales técnicas, con sus ventajas y desventajas. También se da + un breve recorrido sobre el estado del arte. + ESTADO: SIN EMPEZAR + + +.. =========================================================================== + + +El Lenguaje de Programación D +============================= +.. Introducción y breve reseña del lenguaje de programación D. También + se presentan las necesidades particulares de D con respecto al + recolector de basura y su estado actual. + ESTADO: SIN EMPEZAR, REVISAR LO HECHO A continuación se enumeran las principales características de D_, agrupadas por unidades funcional o paradigmas que soporta: +.. EL LENGUAJE DE PROGRAMACION D ............................................. Programación Genérica --------------------- @@ -194,6 +307,7 @@ Programación Genérica sobre los parámetros de las plantillas. Más información en http://www.digitalmars.com/d/expression.html#IsExpression +.. EL LENGUAJE DE PROGRAMACION D ............................................. Programación de Bajo Nivel (*system programming*) ------------------------------------------------- @@ -217,6 +331,7 @@ Programación de Bajo Nivel (*system programming*) .. [#abi] Interfaz de Aplicación Binaria (del inglés *Application Binary Interface*). +.. EL LENGUAJE DE PROGRAMACION D ............................................. Programación de Alto Nivel -------------------------- @@ -255,6 +370,7 @@ Programación de Alto Nivel de basura. .. [#dalias] Análogo al ``typedef`` de C/C++. +.. EL LENGUAJE DE PROGRAMACION D ............................................. Programación Orientada a Objetos -------------------------------- @@ -273,6 +389,7 @@ Programación Orientada a Objetos sintácticamente como campos de esa clase/estructura. Más información en http://www.digitalmars.com/d/property.html#classproperties +.. EL LENGUAJE DE PROGRAMACION D ............................................. Programación Confiable ---------------------- @@ -304,11 +421,17 @@ Programación Confiable .. _Eiffel: http://www.eiffel.com/ +.. =========================================================================== + + Definición del Problema ======================= .. Describe más detalladamente los problemas actuales del recolector de basura de D, sentando las bases para el análisis de los requerimientos - de recolección de basura en dicho lenguaje. + de recolección de basura en dicho lenguaje (se explica por qué las + particularidades descriptas en la sección anterior complican la + recolección de basura). + ESTADO: SIN EMPEZAR, REVISAR LO HECHO Como se ha visto, D_ es un lenguaje de programación muy completo, pero aún tiene algunos aspectos inconclusos. Su recolector de basura @@ -342,6 +465,19 @@ ya mencionada de que el manejo de memoria tenga que pasar a ser parte de las interfaces y la complejidad que esto agrega al diseño -y uso- de una biblioteca). + +.. =========================================================================== + + +Análisis de la Solución +======================= +.. Describe los resultados del análisis y explica los fundamentos para + elegir los algoritmos seleccionados para implementar, en base a los + requerimientos hallados anteriormente. + ESTADO: SIN EMPEZAR, REVISAR LO HECHO + +.. ANALISIS DE LA SOLUCION ................................................... + Soluciones Propuestas --------------------- Para poder implementar un recolector de basura no conservativo es @@ -365,6 +501,8 @@ consideraciones a las que otros lenguajes no deben enfrentarse) y no es sencillo pensar en otras implementaciones sin hacer modificaciones de base al lenguaje. +.. ANALISIS DE LA SOLUCION ................................................... + Problemas para Implementar Colectores con Movimiento ---------------------------------------------------- El principal problema es la capacidad de D_ de manipular punteros y @@ -373,6 +511,8 @@ de interactuar con C. Al mover un objeto de un área de memoria a otro, es necesario actualizar todos los punteros que apuntan a éste. En D_ esta tarea no es trivial [DNG42564]_ +.. ANALISIS DE LA SOLUCION ................................................... + Problemas para Implementar Conteo de Referencias ------------------------------------------------ Este tipo de recolectores reparten la carga de la recolección de forma @@ -386,11 +526,7 @@ difíciles de proveer con el conteo de referencias, entre otros problemas [DNG38704]_. -Análisis de la Solución -======================= -.. Describe los resultados del análisis y explica los fundamentos para - elegir los algoritmos seleccionados para implementar, en base a los - requerimientos hallados anteriormente. +.. =========================================================================== Implementación de la solución: @@ -400,6 +536,10 @@ Implementación de la solución: biblioteca o si fue necesario modificar el compilador y de ser así si se modificó el *frontend* o el GDC y se comentan problemas y limitaciones encontradas. + ESTADO: SIN EMPEZAR + + +.. =========================================================================== Conclusiones @@ -407,13 +547,17 @@ Conclusiones .. Se presentan las conclusiones del trabajo, comparando los resultados obtenidos con el punto de partida. Se mencionan puntos pendientes o nuevas líneas de investigación. + ESTADO: SIN EMPEZAR + -.. ============== FIN DOCUMENTO =========== +.. =========================================================================== +.. ============================ FIN DEL DOCUMENTO ============================ +.. =========================================================================== -.. Pone links "offline". -.. target-notes:: +.. Pone links "offline" (para generar PDF para imprimir). +.. .. target-notes:: .. Macros: .. |date| date:: %e de %B de %Y -- 2.43.0