CURSO DE POSGRADO
In.Co. - PEDECIBA INFORMATICA
2do. semestre 1999

Instituto y Departamento Responsable:
Laboratorio de Ciencia de la Computación, Instituto de Computación de la Facultad de Ingeniería..
Nombre del Curso:
Compilación de Lenguajes Funcionales Perezosos.
Número de Horas:
Horas de aula:
Aproximadamente 30 horas de clases teóricas y 18 horas de clases prácticas.
Horas de trabajo del estudiante durante el curso:
Horas recomendadas de estudio semanales: 3-5
Horas de proyecto final/evaluación:
El proyecto final, que consiste en la implementación de un compilador para un subset del lenguaje Haskell, será incrementalmente desarrollado a lo largo del curso. Para implementar un compilador que cumpla con las exigencias mínimas se consideran adecuadas un total de 48 horas invertidas en diseño e implementación.
Objetivos de la Asignatura:
Metodologí a de Enseñanza:
Clases teóricas magistrales, presentación y discusión de artículos científicos. El aspecto práctico de la materia se centrará en el diseño e implementación de compiladores, y en particular, en el de Samba, el arriba mencionado lenguaje de programación
Temario:
  1. Introducción.


    2. Lenguajes funcionales puros y perezosos. Supercombinadores. Programación monádica. Intérpretes y compiladores. Presentación del kernel básico del lenguaje funcional Samba (un simple subset del lenguaje Haskell).

  2. Parsing.


    3. Analizadores lexicográficos y sintácticos: reglas de producción implementadas como funciones perezosas. Combinadores léxicos y de parsing. La mónada Parser.

  3. Chequeo de tipos. Sistema de Tipos Hindley-Milner. Chequeo de tipos y su importancia en la construcción de compiladores. Algoritmos de inferencia de tipos: entendimiento e implementación.
  4. Reducción en grafos. Expresiones funcionales como grafos, evaluación de programas en términos de reducciones en grafos. Evaluación perezosa. Estudio de un intérprete para el kernel básico: la máquina Template Instantiation.
  5. Lambda lifting. Abstracciones y su transformación en supercombinadores. Distintos algoritmos de lifteo.
  6. La máquina G. La ma'quina abstracta G y su correspondiente modelo computacional. Compilación y ejecución de supercombinadores. Compilación de declaraciones locales mutuamente recursivas (letrec). Tipos de datos inductivos y la compilación de funciones que han sido definidas usando pattern matching. Esquemas de compilación: cuando conviene ser completamente perezoso y cuando no.
  7. Las máquinas TIM y Spineless Tagless G. Modelos alternativos de compilación y ejecución de supercombinadores. Se hará una presentación superficial de las mencionadas máquinas y se realizará un estudio comparativo de los tres enfoques (G, TIM y STG).
  8. Recolección de residuos. Presentación y discusión de diferentes técnicas de diseño de algoritmos de recolección de residuos.
Las horas de clase se distribuirán aproximadamente de la siguiente forma: tres semanas para los temas 1 y 2, una semana para el tema 3, una 6 semanas para los temas 4, 5 y 6, una semana para el tema 7 y una semana para el tema 8. 
Conocimientos Previos Exigidos y Recomendados:
Familiaridad con los conceptos básicos de: programación funcional (por ejemplo haber tomado el curso electivo ``Introducción a la Programación Funcional'' dictado en el cuarto año de la carrera Ingeniero en Computación), reconocimiento lexicográfico y sintáctico. Es deseable que el estudiante tenga una cierta familiaridad con lenguajes de programación funcionales (ML o Haskell-like).
Modalidad de Evaluación:
Testeo del compilador implementado y eventualmente presentación por parte del estudiante del trabajo desarrollado.


File translated from TEX by TTH, version 1.41.