Lenguajes de Programación III (CI-4722)

Esta es la segunda materia de la cadena de especialización del área de Lenguajes de Programación que se ofrece cada dos años, los años pares, en el trimestre Abril-Julio. Como se trata de una electiva de especialización supongo que Ud. está interesado en el tema, así que no se trata de «pasar» sino de ver cuán dedicado e interesado está en el tema, y la calidad del resultado de su trabajo.

Los tópicos fundamentales de estudio son:

Técnicas de Generación de Código.
Mejoramiento («Optimización») de Código.
- Mejoras dependientes e independientes de la máquina.
- Mejoramiento global.
- Mejoramiento local.
Análisis de Flujo.
Elementos del back-end de un compilador.

Evaluación

La materia tiene un componente teórico cuya evaluación corresponde al 60% del total. La evaluación será completada en dos exámenes escritos individuales de 30% y 30% respectivamente. Consulte el calendario de la materia para conocer las fechas definitivas y contenido a evaluar en cada caso.

La materia tiene un componente práctico cuya evaluación corresponde al 40% del total y se manifiesta en el proyecto de programación. La evaluación es continua con dos hitos resumen de 15% y 25%. Note que durante las sesiones de laboratorio Ud. deberá exhibir los avances de su proyecto de manera concreta mediante la exposición y discusión de sus decisiones de diseño e implementación; llegada la fecha hito, simplemente se resumirán los resultados parciales alcanzados y se redondeará la calificación final.

En síntesis, todas las semanas tiene que entregar algo.

El Proyecto

Su proyecto de programación, que se extiende durante dos trimestres continuos, consiste en la implantación del generador de código y el ambiente de ejecución para el lenguaje diseñado por usted en CI-4721.

Herramientas de Programación

El compilador para su lenguaje puede desarrollarse con:

GNU C/C++ (4.7 o superior), usando Flex (2.5 o superior) y Bison (2.5 o superior) como herramientas auxiliares para la generación del analizador lexicográfico y sintáctico, además de las librerías que Ud. considere adecuadas para el manejo de tabla de símbolos y grafos (aunque comenzar con STL y Boost es conveniente).
Haskell (GHC 7.6/7.8), usando Alex (3.0.1 o superior) y Happy (1.18 o superior) como herramientas auxiliares para la generación del analizador lexicográfico y sintáctico, además de las librerías Data.Map para el manejo de tabla de símbolos y Data.Graph para el manejo de grafos. Note que debe dominar el uso de Functor, Monad y Monad Transformers para poder considerar el uso de Haskell para este proyecto.

Este curso no es un tutorial de C/C++, Haskell o ninguna de las librerías. Puedo ofrecer orientación general y conducirlos a la documentación, sin embargo se espera que Ud. tenga razonable dominio del lenguaje y de las técnicas de programación asociadas.

Independientemente del lenguaje de programación que Ud. haya escogido, se espera que el desarrollo de su proyecto ocurra apoyado en el sistema de control de versiones Git, con repositorios sobre los cuales yo pueda supervisar que en efecto hay trabajo en curso. Su repositorio debe albergar tanto su código (documentado) como también los documentos de soporte y notas de implantación.

La generación de código de máquina tendrá como objetivo la arquitectura MIPS de 32 bits, tomando todas las consideraciones necesarias para que los programas producidos por su compilador puedan ser ejecutados directamente en el emulador spim.

Los equipos son de dos (2) personas.

Bibliografía

El curso estará basado sobre cuatro libros de texto.

   Scott, Michael
   Programming Language Pragmatics
   Morgan Kaufmann
   ISBN 0-12-633951-1

Pueden usar la Tercera (tapa blanca, como el que muestro el primer día de clase), la Edición (tapa negra) o primera edición por igual. En los cronogramas y material de apoyo hago referencia a la tercera edición de ese libro como [Scott].

El [Scott] asiste en los elementos de diseño del lenguaje y su manifestación en el diseño del compilador. A diferencia de lo que ocurre en CI-3641, en la cadena de lenguajes se utiliza casi todo el contenido del libro.

   Sudkamp, Thomas
   Languages and Machines
   Addison-Wesley Publishing
   ISB 0-321-32221-5
   QA267.3.S83

Pueden usar la Tercera Edición (tapa verde, como el que muestro el primer día de clase) o la Segunda Edición (tapa roja) por igual. En los cronogramas y material de apoyo hago referencia a la tercera edición de ese libro como [Sudkamp].

El [Sudkamp] asiste en los elementos de teoría matemática relacionados con análisis sintáctico generalizado. A diferencia de lo que ocurre en CI-3725, en la cadena de lenguajes solamente se desarrollan los capítulos relacionados con reconocedores LL y LR pero en toda su extensión (k arbitrario).

    Aho, Sethi & Ullman
    Compilers: Principles, Techniques and Tools
    Addison-Wesley Publishing
    ISBN 0-201-10088-6

    Aho, Lam, Sethi & Ullman
    Compilers: Principles, Techniques and Tools
    Addison-Wesley Publishing
    ISBN 0-321-48681-1

Estos son, respectivamente, las dos últimas ediciones de «el dragón», por la imagen que tiene en la portada. La Primera Edición (tapa blanca) es útil para CI-4721, pero se queda corta para CI-4722. La Segunda Edición (tapa morada) no incluye algunos tópicos de CI-4721, pero es completo para CI-4722. En los cronogramas hago referencia a estos libro como [ASU] y [ALSU], respectivamente.

Cronograma habitual y Láminas de Clase

Sigue el cronograma habitual del curso. Cada una de las sesiones de clase incluye el enlace a las versiones más recientes de las láminas que uso para dirigir las clases, adeḿas de las referencias al material de lectura necesario.

Las versiones de cursos anteriores no están disponibles. Si durante alguna clase se hacen correcciones o agregados, espere encontrar la versión corregida aquí eventualmente.

Teoría

Generación de Código — [AHU] 8.1 y 8.2
- Problema de la Generación de Código.
- Máquina hipotética para generación.
- Modelo de Costo para las instrucciones.
Grafos de Flujo — [AHU] 8.3 y 8.4
- Bloques Básicos.
- Grafos de Flujo.
- Mejoramiento local en Bloque Básico.
Generador Inocente — [AHU] 8.6 y 8.7
- Generador de Código Inocente.
- Descriptor de Asignación.
- Descriptor de Disponibilidad.
- Asignación optimista de registros.
- Mejoramiento local.
Generadores Astuto — [AHU] 8.8
- Asignación local de registros.
- Asignación global de registros.
- Asignación cromática.
Generadores Astutos — [AHU] 8.9 y 8.10
- Selección de instrucciones.
- Selección usando «Tree Tiling».
- Selección «Perfecta» de Ershov.
Generadores Astutos — [AHU] 8.11
- Generador por Programación Dinámica.
- Generador de código para saltos.
Generación de Sub-programas]
- Registro de Activación.
- Pasaje de Parámetros.
Mejoramiento de Código — [AHU] 9.1
- Mejoramiento local independiente.
- Mejoramiento global independiente.
- Motivación al Análisis de Flujo.
Mejoramiento de Código — [AHU] 9.2
- Restricciones de Flujo.
- Funciones de Transferencia.
- Resolución del Sistema de Restricciones.
Mejoramiento de Código — [AHU] 9.5
- Eliminación de redundancia local.
- «Lazy Code Motion»
Mejoramiento de Código — [AHU] 9.6
- Dominadores.
- Depth First Spanning Tree.
- Detección de Ciclos Naturales.
- Impacto en la convergencia del Análisis de Flujo.
Mejoramiento de Código — [AHU] 9.6
- Mejoramiento de ciclos.
- Detección de variables de inducción.
- Reducción de fuerza de inducción.
- Eliminación de variables de inducción.
Mejoramiento de Código — [AHU] 9.6
- Detección de Alias.
- Mejoramiento entre procedimientos.
Análisis Interprocedural — [ALSU] 12.1 y 12.2
- Motivación.
- Influencia del contexto.
- Sensibilidad vs. Insensibilidad contextual.
Análisis Interprocedural — [ALSU] 12.3 a 12.7
- Datalog.
- Análisis de apuntadores usando Datalog.
Semántica Operacional — [W] Cap. 2
- Pasos Cortos.
- Pasos Largos.
Semántica Denotacional — [W] Cap. 5

Laboratorio

El cronograma del laboratorio varía según el desempeño de los equipos. En cada sesión presentaré algún tópico relevante a su trabajo práctico, estableciendo el hito de entrega para la siguiente sesión (aparece destacado en cada sesión).

En general, el cronograma consiste en:

Primer Corte — Generador de Código Intermedio.
Segundo Corte — Generación MIPS con Ambiente de Ejecución.

Si bien cada equipo diseño su propio lenguaje de programación, todos son suficientemente expresivos como para resolver problemas interesantes de programación. La «corrida» de su compilador será considerada «exitosa» si Ud. provee un conjunto específico de programas de prueba que demuestran las capacidades de su lenguaje.