====== Lenguajes y Compiladores ====== * Profesores: Alejandro Gadea, Héctor Gramaglia, Demetrio Vilela. * Lista de Mail: compiladores-2020 arroba googlegroups punto com * Para incorporarse al grupo enviar un mail a cualquier miembro de la cátedra. * IMPORTANTE: La información completa sobre la materia y los turnos de exámenes la encontrará en el aula virtual de la materia: https://www.famaf.proed.unc.edu.ar/course/view.php?id=587 ====== Novedades ====== - Se suspenden las clases presenciales hasta el 24 de marzo del 2020 - **Sobre el laboratorio**: La fecha de entrega será un par de semanas después del primer parcial y consistirá en la implementación del lenguaje LIS + Fallas + IO. ===== Generalidades ===== * Parciales: 2 * Promoción: obteniendo al menos 7 en cada uno de los parciales, aprobando el taller y coloquio final. * Regularidad: aprobando 2 parciales (es posible recuperar 1) y aprobando el taller. * Taller: se implementarán intérpretes o compiladores de lenguajes de programación. * Examen: examen con parte escrita y parte oral. * Alumnos libres: examen con ejercicios/preguntas adicionales + defensa del taller. * {{ :compiladores:lenguajes_y_compiladores.docx |Programa de la Asignatura}} ===== Exámenes Parciales ===== * PRIMER PARCIAL: miércoles 6 de mayo de 2020 * SEGUNDO PARCIAL: miércoles 10 de junio de 2020 ===== Teórico ===== ==== Bibliografía ==== * Reynolds, Theories of Programming Languages, Cambridge University Press, 1998. ==== Apuntes de Clase ==== **Primera parte:** Lenguajes imperativos * {{:compiladores:sintaxis_semantica_variables_2014.pdf|Apunte del Eje 1}}: Introducción a la sintaxis y la semántica de lenguajes. Sintaxis abstracta. Función semántica. Composicionalidad y dirección por sintaxis. Variables y metavariables. Ligadura. Sustitución y captura en el Cálculo de Predicados. Propiedades de la semántica denotacional. {{ :compiladores:filminas_1_compactas.pdf |Filminas del eje 1}} * Audio: El problema de dar semántica a las ecuaciones recursivas - {{https://www.famaf.unc.edu.ar/~gadea/SemRec.mp3| }} *{{:compiladores:recursion_punto_fijo.pdf|Apunte del Eje 2}}: El problema de dar significado a la recursión. Ordenes parciales, predominios y dominios. Funciones monótonas, morfismos y funciones continuas. Espacio de Funciones. Teorema del Menor Punto Fijo. Aplicación del TMPF para el estudio de las soluciones de una ecuación recursiva. {{:compiladores:filminas_2_compactas.pdf|Filminas del eje 2}} * Audios: El uso del TMPF para dar semántica a la recursión - {{https://www.famaf.unc.edu.ar/~gadea/TMPF1.mp3| TMPF1}} - {{https://www.famaf.unc.edu.ar/~gadea/TMPF2.mp3| TMPF2}} - {{https://www.famaf.unc.edu.ar/~gadea/TMPF3.mp3| TMPF3}} - {{https://www.famaf.unc.edu.ar/~gadea/TMPF4.mp3| TMPF4}} *{{:compiladores:imperativo.pdf|Apunte del Eje 3}}: El Lenguaje Imperativo Simple (LIS). Sintaxis abstracta. El problema de dar semántica a la iteración. Semántica denotacional de LIS. Propiedades de la semántica. Fallas. Output. Producto y suma de dominios. Dominios recursivos. Input. Semántica operacional de LIS y sus extensiones. Corrección de la semántica operacional. {{ :compiladores:filminas_3_lis_compactas.pdf |Filminas del Eje 3 Primera parte: Lenguaje Imperativo Simple}} {{:compiladores:filminas_3_fallas_2017_compactas.pdf|Filminas del Eje 3 Segunda parte: Lenguaje Imperativo Simple con fallas}} {{:compiladores:filminas_3_io_2017_compactas.pdf|Filminas del Eje 3 Tercera parte: Lenguaje Imperativo Simple con input y outoput}} * Audios: "Filminas del Eje 3 Segunda parte: Lenguaje Imperativo Simple con fallas". - Operadores *, + y † (6 a 9): - {{https://www.famaf.unc.edu.ar/~gadea/operadores.mp3| operadores}} - Semántica operacional (12 al final): - {{https://www.famaf.unc.edu.ar/~gadea/semanticaoperacional.mp3| semanticaoperacional}} Material Complementario: {{ :compiladores:teorema_de_correccion.pdf | Prueba del Teorema de Corrección de la semántica operacional respecto de la denotacional}} **Segunda parte:** Lenguajes aplicativos puros, lenguajes aplicativos con referencias y asignación *{{:compiladores:calculo-lambda.pdf|Apunte del Eje 1}}: Cálculo Lambda. Sintaxis. Semántica Operacional: reducción y evaluación eager y normal. Semántica Denotacional. {{:compiladores:2017:calculo-lambda.pdf|Filminas del eje 1}} {{:compiladores:calculo-lambda-denotacional.pdf|Filminas del eje 1 (continuación)}} *{{:compiladores:2017:lenguaje-aplicativo.pdf|Apunte del Eje 2}}: Lenguaje Aplicativo. Sintaxis abstracta. Semántica operacional (Evaluación) normal e eager. Semántica denotacional normal e eager. Tuplas y Patrones. Recursión. {{ :compiladores:aplicativo.pdf | Filminas del eje 2}} *{{:compiladores:iswim2012.pdf|Apunte del eje 3}}: Lenguaje Aplicativo eager con referencias y asignación (Iswim). Sintaxis abstracta de las expresiones que involucran referencias. Semántica denotacional. Semántica operacional (Evaluación). Propiedades del fragmento imperativo. {{{:compiladores:2017:iswim.pdf|Filminas del eje 3 }} *{{ :compiladores:ejemplos_de_evaluacion.pdf |Ejemplos de evaluación}} **Material complementario** *{{:compiladores:apuntes120608.pdf|Continuaciones en el lenguaje imperativo simple y el lenguaje imperativo con extensiones}}: ==== Contenidos de cada Clase - Año 2020 ==== * **Miércoles 11/3**. Distintas formas de dar significado a los lenguajes de programación. Sintaxis abstracta: gramáticas abstractas. Definición de la función semántica: ecuaciones semánticas, dirección por sintaxis y composicionalidad. * ** Semana del 16 al 20 de marzo. ** * Propiedades de la semántica: Teoremas de Coincidencia y Renombre. Demostraciones: Teorema de coincidencia. Un lenguaje imperativo simple (sin iteración). Sintaxis abstracta. Semántica denotacional. Filminas Eje 1 de 45 a 73. * Dificultades para dar significado a un programa recursivo de Haskell. Ecuaciones recursivas y sus soluciones. Ordenes parciales. Orden discreto y llano. Cadenas. Supremo de un subconjunto. Posets de funciones. Predominios y dominios. Ejemplos. Supremo de cadenas en el posets de funciones. Funciones continuas. Filminas Eje 2 de 1 a 20 * ** Semana del 25 al 27 de marzo. ** * Supremo de cadenas en el posets de funciones. Funciones continuas. Dominios de funciones continuas. Teorema del Menor Punto Fijo. Aplicacion del TMPF para caracterizar la solución buscada de una ecuación recursiva. Resto de las Filminas del eje 2. * El lenguaje Imperativo Simple (LIS). Sintaxis abstracta. Semántica denotacional. El problema de dar semántica dirigida por sintaxis a la iteración. Uso del TMPF para la semántica de la iteración. Filminas del eje 3, desde la 1 a la 21. * ** Semana del 1 al 3 de abril. ** * Uso del TMPF para la semántica de la iteración. Desarrollo de ejemplos. Propiedades de la semántica denotacional: Teoremas de renombre y coincidencia. Noción de sustitución para el LIS. Teorema de sustitución (enunciado). Prueba del Teorema de Coincidencia para LIS. * ** Semana del 8 al 10 de abril. ** Sintaxis abstracta y semántica denotacional del Lenguaje Imperativo Simple con Fallas. Semántica operacional de LIS. La relación "small-step". Configuraciones. Definición axiomática de la relación "small-step".Semántica de transiciones de LIS. Noción de Ejecución. * ** Semana del 15 al 17 de abril. ** Corrección de la semántica de transiciones de LIS respecto de la semántica denotacional. (Ver apunte en Material ccomplementario de la primera parte) Semántica de transiciones de LIS con fallas. (Filminas del Eje 3 Segunda parte) Producto de dominios. Uniones disjuntas de predominios. Definiciones, cadenas y supremos en estas construcciones. (Filminas del Eje 3 tercera parte, diapositivas 1 a 7) * ** Semana del 22 al 24 de abril ** Sintaxis y semántica del lenguaje imperativo con fallas y output. Definición del dominio semántico mediante ecuaciones recursivas de dominio. Ejemplos. * ** Semana del 29 al 1 de mayo ** Sintaxis y semántica del lenguaje imperativo con fallas, input y output. Definición del dominio semántico mediante ecuaciones recursivas de dominio. Ejemplos. * ** Semana del 6 al 8 de mayo ** Cálculo Lambda, su sintaxis. Sustitución. Conversión alpha. Redex beta. Noción de contracción y reducción. Formas normales. Distintos órdenes de reducción. Noción de ejecución: definición de la semántica small-step. Propiedades y ejemplos. * ** Semana del 11 al 15 de mayo ** Noción de evaluación. Evaluación normal e eager. Reglas axiomáticas. * ** Semana del 18 al 22 de mayo ** Semántica denotacional del CL: el dominio D infinito. Ecuaciones semánticas. Propiedades de la semántica: reglas beta y eta, Teorema de Coincidenia, Sustitución y Renombre. Ejemplos. * ** Semana del 26 al 29 de mayo ** Semántica denotacional para las evaluaciones eager y normal del CL. Ecuaciones semánticas. Ejemplos. Análisis de la validez de propiedades de la semántica: regla beta, eta, Teoremas de Coincidencia, renombre y sustitución. * ** Semana del 1 al 5 de junio ** Lenguajes aplicativos eager y normal. Fragmento básico. Sintaxis abstracta. Semántica operacional big-step: reglas para las evaluaciones eager y normal. (Los contenidos no reproducen el orden de las diapositivas: ver Diap. 4 a 11, 26 a 29 y 37 a 40) * ** Semana del 8 al 12 de junio ** Semántica denotacional eager y normal del lenguaje aplicativo (fragmento básico) Diapositivas 12-25 * ** Semana del 16 al 19 de junio ** Semántica denotacional eager y normal de la recursión en el lenguaje aplicativo. Diapositivas 40 al final. /* ==== Contenidos de cada Clase - Año 2019 ==== * **Miércoles 13/3**. Distintas formas de dar significado a los lenguajes de programación. Sintaxis abstracta: gramáticas abstractas. Definición de la función semántica: ecuaciones semánticas, dirección por sintaxis y composicionalidad. * **Viernes 15/3**. Lenguaje de la lógica de predicados. Sintaxis y semántica denotacional. Variables como frase abstracta. Noción de estado. Variables y metavariables. Ocurrencias ligadoras, ligadas y libres de una variable. Ejemplos. Variables libres. Teoremas de Coincidencia y Renombre. Sustitución. El problema de la captura. * **Miércoles 20/3**. Propiedades de la semántica: Teoremas de Coincidencia y Renombre. Demostraciones: Teorema de coincidencia. Un lenguaje imperativo simple (sin iteración). Sintaxis abstracta. Semántica denotacional. * **Viernes 22/3**. Dificultades para dar significado a un programa recursivo de Haskell. Ecuaciones recursivas y sus soluciones. Órdenes parciales. Orden discreto y llano. Cadenas. Supremo de un subconjunto. Posets de funciones. Predominios y dominios. Ejemplos. Supremo de cadenas en el posets de funciones. Funciones continuas. * **Miércoles 27/3**. Supremo de cadenas en el posets de funciones. Funciones continuas. Dominios de funciones continuas. Teorema del Menor Punto Fijo. Aplicacion del TMPF para caracterizar la solución buscada de una ecuación recursiva. * **Viernes 29/3**. El lenguaje Imperativo Simple (LIS). Sintaxis abstracta. Semántica denotacional. El problema de dar semántica dirigida por sintaxis a la iteración. Uso del TMPF para la semántica de la iteración. * **Miércoles 3/4**. Ejemplos del Cálculo de semántica. Uso del TMPF para la semántica de la iteración. Desarrollo de un ejemplo. Propiedades de la semántica denotacional: Teoremas de renombre y coincidencia. Noción de sustitución para el LIS. El problema del alias. Teorema de sustitución (enunciado). * **Viernes 5/4**. Prueba del Teorema de Coincidencia para LIS. Sintaxis abstracta y semántica denotacional del Lenguaje Imperativo Simple con Fallas. Ejemplos. * **Miércoles 10/4**. Semántica operacional de LIS. La relación "small-step". Configuraciones. Definición axiomática de la relación "small-step".Semántica de transiciones de LIS. Noción de Ejecución. * **Viernes 12/4**. Corrección de la semántica de transiciones de LIS respecto de la semántica denotacional. Semántica de transiciones de LIS con fallas. * **Miércoles 17/4**. Producto de dominios. Uniones disjuntas de predominios. Definiciones, cadenas y supremos en estas construcciones. Ejemplos. * **Viernes 19/4**. Sintaxis y semántica del lenguaje imperativo con fallas y output. Definición del dominio semántico mediante ecuaciones recursivas de dominio. Ejemplos. * **Miércoles 24/4**. La cátedra se adhiere al paro de ADIUC * **Viernes 26/4**. Sintaxis y semántica del lenguaje imperativo con fallas, input y output. Definición del dominio semántico mediante ecuaciones recursivas de dominio. Ejemplos. * **Miércoles 1/5**. Feriado. * **Viernes 3/5**. Primer Parcial. * **Miércoles 8/5**. Comienzo de la Parte II. El Cálculo Lambda, su sintaxis. Conversión alpha. Redex beta. Noción de contracción y reducción. Formas normales. Distintos órdenes de reducción. Noción de evaluación. * **Viernes 10/5**. Noción de evaluación. Evaluación normal e eager. Reglas axiomáticas. Ejemplos. El problema de dar semántica denotacional al CL. * **Miércoles 15/5**. Semántica denotacional del CL: el dominio D infinito. Ecuaciones semánticas. Propiedades de la semántica: reglas beta y eta, Teorema de Coincidenia, Sustitución y Renombre. Ejemplos. * **Viernes 17/5**. Semántica denotacional para las evaluaciones eager y normal del CL. Ecuaciones semánticas. Ejemplos. Análisis de la validez de propiedades de la semántica: regla beta, eta, Teoremas de Coincidencia, renombre y sustitución. Proyección para el resto del cuatrimestre: * **Miércoles 22/5**. Lenguajes aplicativos eager y normal. Fragmento básico. Sintaxis abstracta. Semántica operacional big-step: reglas para las evaluaciones eager y normal. * **Viernes 24/5**. No se dictan clases. * **Miércoles 29/5**. Lenguajes aplicativos eager y normal. Fragmento básico. Semántica denotacional: ecuaciones semánticas eager y normal. * **Viernes 31/5**. Extensiones de los lenguajes aplicativos egaer y normal: tuplas, patrones y recursión. Reglas de evaluación y ecuaciones semánticas. * **Miércoles 5/6**. Extensiones de los lenguajes aplicativos egaer y normal: recursión, referencias y asignación. Reglas de evaluación y ecuaciones semánticas. * **Viernes 7/5**. Extensiones de los lenguajes aplicativos egaer y normal: referencias y asignación. Reglas de evaluación y ecuaciones semánticas. * **Miércoles 12/5**. Referencias y asignación. Propiedades del fragmento imperativo. */ ===== Prácticos ===== === Prácticos 2020 === - {{:compiladores:2020:1_2020.pdf| Guía del 11 de marzo}} Gramática abstracta y semántica denotacional, composicionalidad y dirección por sintaxis. - {{:compiladores:2020:2_2020.pdf| Guía del 17 de marzo}} Variables, ligaduras, sustitución, renombre. Todo esto en la lógica de predicados. - {{:compiladores:2020:3_2020.pdf| Guía del 25 de marzo}} Predominios y dominios. Funciones continuas, teorema del menor punto fijo. - {{:compiladores:2020:4_2020.pdf| Guía del 01 de abril}} Semántica denotacional del lenguaje imperativo simple. - {{:compiladores:2020:5_2020.pdf| Guía del 10 de abril}} Fallas. Semántica operacional del lenguaje imperativo simple. - {{:compiladores:2020:6_2020.pdf| Guía del 17 de abril}} Productos y uniones disjuntas de predominios. Dominios recursivos. Output e Input. - {{:compiladores:2020:7_2020.pdf| Guía del 6 de mayo}} Cálculo Lambda, sintaxis. Reducción. Formas canónicas y normales. Evaluación Normal e eager. - {{:compiladores:2020:8_2020.pdf| Guía del 20 de mayo}} Semántica denotacional del Cálculo Lambda, la evaluación normal y la evaluación eager. - {{:compiladores:2020:9_eval_2020.pdf| Guía del 03 de junio}} Lenguaje aplicativo. Evaluación eager y normal. - {{:compiladores:2020:9_deno_2020.pdf| Guía del 10 de junio}} Lenguaje aplicativo. Semántica denotacional eager y normal. === Prácticos 2019 === - {{:compiladores:10_2019.pdf| Guía del 5 de junio}} Lenguaje aplicativo con referencias y asignación. === Ejercicios resueltos === - {{:compiladores:fv_p_sus_d_caso_para_todo.pdf | Guía del 17 de marzo de 2020, Ej. 6, caso Para Todo}} - {{:compiladores:2020:ejemplotmpf.pdf| Ejemplo desarrollando el cálculo de un punto fijo}} - {{:compiladores:2020:tcwhile.pdf| Caso while para el teorema de coincidencia}} - {{ :compiladores:practico4_ejercico_2c.docx |Guía 4 Ejercicio 2 (c)}} - {{:compiladores:2020:p4e10.pdf |Guía 4 Ejercicio 10}} - {{ :compiladores:practico_5_ejercicio_4_.pdf |Guía 5 Ejercicio 4}} ===== Lab 2020 ===== * **Primera semana**. {{:compiladores:2020:lab1_2020.tar.gz|Lab1}}, allí se encuentra la definición de la gramática abstracta para un lenguaje simple de expresiones aritméticas y booleanas. La tarea consiste en definir la función ''sem'' que define la semántica para cada una de las construcciones sintácticas. * **Segunda semana**. {{:compiladores:2020:lab2_2020.tar.gz|Lab2}}. La tarea consiste en extender el lenguaje implementado en el Lab1 con variables enteras. * {{:compiladores:2020:lab3_2020.tar.gz|Lab3}}. Implementar la semántica denotacional para el lenguaje imperativo simple con fallas e input-output (LIS + Fallas + IO). * Ver [[compiladores:main#Novedades|Novedades]]. /* * **Cuarta semana**. Implementar la semántica denotacional para el lenguaje imperativo extremadamente simple (LIES) extendiendo el lenguaje simple de expresiones (implementado en el laboratorio 2) con asignación de variables enteras, secuencia y expresión condicional. * **Quinta semana**. {{:compiladores:Lab4_2019.tar.gz|Lab4}}. Implementar la semántica denotacional para el lenguaje imperativo simple con fallas (LIS + Fallas) extendiendo el lenguaje imperativo extremadamente simple (LIES). * **11º semana**. {{:compiladores:Lab5_2019.tar.gz|Lab5}}. Implementar la semántica denotacional para el lenguaje imperativo simple con fallas, input y output (LIS + Fallas + IO) extendiendo el lenguaje imperativo simple con fallas (LIS + fallas). */ == Entrega == Entregar por mail a las direcciones de gmail hector.gramaglia, alex.aegf y demetriomeister. El asunto del mail debe ser ''lyc-2020: ApellidoNombre'' y debe contener un archivo adjunto ''ApellidoNombre.tar.gz''. Recordar todas las buenas prácticas que aprendieron a lo largo de la carrera: modularización, abstracción, consistencia en el estilo de programación, comentarios. ===== Extras ===== - [[http://pdf.aminer.org/000/210/722/initial_algebra_semantics.pdf]] “Initial algebra semantics and continuous algebras” Artículo que explica qué es la sintaxis abstracta de una manera amena (en la introducción). - [[http://cs.famaf.unc.edu.ar/~mpagano/cursos/lyc/2014/Lambda.hs| Implementación de semántica denotacional para un lenguaje aplicativo básico (Autor: Martín) ]] - [[http://cs.famaf.unc.edu.ar/~mpagano/cursos/lyc/2014/LambdaT.hs| Reducción en orden normal para cálculo lambda (Autor: Martín) ]] /* ===== Lab Opcional 2019 ===== {{:compiladores:coqlabenunciado_2019.pdf|Enunciado del Lab}} | **Resumen**: Introducirse en la mecanización de resultados matemáticos utilizando asistentes de prueba basados en tipos dependientes, particularmente formalizando los teoremas de Coincidencia y Substitución para expresiones enteras y booleanas. ===== Taller ===== Descargar el {{:compiladores:2016:taller.tar.gz|archivo}}, allí se encuentra la definición de la gramática abstracta (o una representación en Haskell de ella, existe algo así como la gramática abstracta?) junto con otros módulos útiles como la representación de Ω y funciones para manipular el estado. La tarea consiste en definir las funciones semánticas para cada categoría sintáctica ''IntExp'', ''Assert'' y ''Comm''. Asegurarse que el proyecto puede cargarse con GHCi o compilarse con GHC. Mandar por mail antes del 15 de mayo a las direcciones hector.gramaglia arroba gmail punto com, miguel.pagano arroba gmail punto com y demetriomeister arroba gmail punto com. El asunto del mail debe ser ''lyc-2016: ApellidoNombre'' y debe contener un archivo adjunto ''ApellidoNombre.tar.bz2''. Recordar todas las buenas prácticas que aprendieron a lo largo de la carrera: modularización, abstracción, consistencia en el estilo de programación, comentarios. */ ===== Exámenes Parciales de años anteriores ===== == 2018 == * {{ :compiladores:1_2018.pdf |Parcial 1}} * {{ :compiladores:2_2018.pdf | Parcial 2}} (Versión borrador, el original fue corregido y acortado) == 2017 == * {{ :compiladores:1_2017_bis.pdf | Parcial 1}} * {{ :compiladores:2_2017.pdf |Parcial 2}} == 2016 == * {{ :compiladores:1_2016.pdf |Parcial 1}} * {{ :compiladores:2_2016.pdf |Parcial 2}} == 2015 == * {{:compiladores:1_2015.pdf|Parcial 1}} * {{:compiladores:2_preliminar.pdf|Parcial 2}} == 2013 == * {{:compiladores:1.pdf| Parcial 1}} * {{:compiladores:2013:p2.pdf| Parcial 2 }} == 2012 == * {{:compiladores:parcial1_2012.pdf| Parcial 1}} * {{:compiladores:2p.pdf| Parcial 2}} * {{:compiladores:2012:3p.pdf| Parcial 3}} == 2011 == * {{:compiladores:parcial1.pdf|Parcial 1}} * {{:compiladores:parcial2_2011.pdf| Parcial 2}} * {{:compiladores:parcial3_2011.pdf| Parcial 3}} == 2010 == * {{http://www.cs.famaf.unc.edu.ar/~mpagano/cursos/lyc/2010/parciales/parcial1.pdf | Parcial 1}} * {{http://www.cs.famaf.unc.edu.ar/~mpagano/cursos/lyc/2010/parciales/parcial2.pdf | Parcial 2}} * {{http://www.cs.famaf.unc.edu.ar/~mpagano/cursos/lyc/2010/parciales/parcial3.pdf | Parcial 3}} == 2009 == * {{http://www.cs.famaf.unc.edu.ar/~mpagano/cursos/lyc/2009/parciales/parcial1.pdf | Parcial 1}} * {{http://www.cs.famaf.unc.edu.ar/~mpagano/cursos/lyc/2009/parciales/parcial2.pdf | Parcial 2}} * {{http://www.cs.famaf.unc.edu.ar/~mpagano/cursos/lyc/2009/parciales/parcial3.pdf | Parcial 3}} ===== Exámenes Finales de años anteriores ===== * {{ :compiladores:18_12.pdf| 18 de diciembre de 2018}} * {{ :compiladores:11_8.pdf | 11 de agosto de 2017}}