: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
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_
.. _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
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
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,
+de 2007 salió su `versión 1.0`_. Poco tiempo después se continúo el
+desarrollo del lenguaje en la `versión 2.0`_, aún inestable y en la
+cual se está experimentando principalmente sobre *const-correctness*
+(ya sea como una forma de programación por contratos como para mejorar
+las oportunidades de optimización del compilador, en especial con
+código multi-hilo), reflexión y características para soportar mejor
+programación funcional (como *clausuras* completas) y programación
+genérica.
+
+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
experience implementing compilers.
.. _D: http://www.digitalmars.com/d/
-.. _`versión 1.0`: http://www.digitalmars.com/d/changelog2.html#new1_00
+.. _`versión 1.0`: http://www.digitalmars.com/d/1.0/changelog.html
+.. _`versión 2.0`: http://www.digitalmars.com/d/changelog.html
.. _`Walter Bright`: http://www.walterbright.com/
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
+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 D_ provee muchas construcciones
+de alto nivel, lo que hace que la necesidad de utilizar construcciones de
+bajo nivel sea muy escasa, por lo tanto brinda un campo importante a
+explorar en cuanto a mejoras para el recolector de basura.
+
+Por lo tanto el objetivo del presente trabajo puede resumirse en los
+siguientes puntos:
+
+- Investigar y analizar la viabilidad de mejoras al recolector de
+ basura de D_, tanto mejoras menores dentro de las limitaciones actuales
+ del lenguaje (incluyendo pero no limitado a mejoras en el algoritmo
+ actual de recolección y soluciones en *espacio de usuario* -como
+ biblioteca-), como proponiendo mejoras al lenguaje que permitan la
+ implementación recolectores más precisos y eficientes.
+- Elegir un conjunto de las mejores soluciones halladas e implementarlas.
+ Las soluciones que necesiten modificaciones en el lenguaje serán
+ implementadas modificando el compilador libre de D_ GDC_, que
+ también será utilizado como plataforma principal de desarrollo y
+ prueba (debido a la disponibilidad completa del código fuente y
+ la libertad de usarlo y modificarlo libremente). De todas formas,
+ siempre se priorizarán las modificaciones al *frontend* [#frontend]_
+ sobre las modificaciones al *backend*, permitiendo así que las mejoras
+ puedan ser probadas eventualmente en otros compiladores que utilicen
+ el *frontend* publicado por DigitalMars_, como DMD_.
+- Realizar pruebas sobre aplicaciones lo más variadas y reales posible
+ sobre todas las soluciones implementadas, de manera de determinar de
+ forma fehaciente las ventajas de unas y otras en cuanto a latencia,
+ consumo de memoria, consumo de procesador, tiempos de pausa, etc.
+- Presentar las conclusiones obtenidas del análisis y las pruebas
+ realizadas, tanto en el ámbito académico de la facultad como a la
+ comunidad de D_ (con el objetivo de sumar lo construido en este trabajo
+ al lenguaje).
+
+.. [#frontend] El *frontend* es el módulo del compilador que realiza el
+ análisis sintáctico y semántico del lenguaje. GDC_ utiliza como
+ *frontend* el que provee libremente DigitalMars_.
+.. [#backend] El *backend* es el módulo del compilador que emite
+ el código binario (o *assembly*, o el lenguaje que produzca el
+ compilador como resultado final). GDC utiliza el *backend* del GCC_
+ (*GNU Compiler Collection*), uno de los compiladores más populares.
+
+
+.. 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 o
+necesitar un manejo especial.
+
+De no plantear esta limitación se llegaría indefectiblemente a un recolector
+conservativo 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
---------------------
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*)
-------------------------------------------------
.. [#abi] Interfaz de Aplicación Binaria (del inglés *Application Binary
Interface*).
+.. EL LENGUAJE DE PROGRAMACION D .............................................
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
--------------------------------
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
----------------------
.. _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
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
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
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
[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:
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
.. 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
projects / z.facultad / 75.00 / informe.git / blobdiff