Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza: • main
compiladores:main

Tabla de Contenidos

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.

Novedades

  1. Se suspenden las clases presenciales hasta el 24 de marzo del 2020
  2. 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.
  • 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

  • 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. Filminas del eje 1
  • Audio: El problema de dar semántica a las ecuaciones recursivas
  • 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. Filminas del eje 2
  • Audios: El uso del TMPF para dar semántica a la recursión

Material Complementario: 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

  • 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. Filminas del eje 2
  • 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. Filminas del eje 3

Material complementario

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.

Prácticos

Prácticos 2020

  1. Guía del 11 de marzo Gramática abstracta y semántica denotacional, composicionalidad y dirección por sintaxis.
  2. Guía del 17 de marzo Variables, ligaduras, sustitución, renombre. Todo esto en la lógica de predicados.
  3. Guía del 25 de marzo Predominios y dominios. Funciones continuas, teorema del menor punto fijo.
  4. Guía del 01 de abril Semántica denotacional del lenguaje imperativo simple.
  5. Guía del 10 de abril Fallas. Semántica operacional del lenguaje imperativo simple.
  6. Guía del 17 de abril Productos y uniones disjuntas de predominios. Dominios recursivos. Output e Input.
  7. Guía del 6 de mayo Cálculo Lambda, sintaxis. Reducción. Formas canónicas y normales. Evaluación Normal e eager.
  8. Guía del 20 de mayo Semántica denotacional del Cálculo Lambda, la evaluación normal y la evaluación eager.
  9. Guía del 03 de junio Lenguaje aplicativo. Evaluación eager y normal.
  10. Guía del 10 de junio Lenguaje aplicativo. Semántica denotacional eager y normal.

Prácticos 2019

  1. Guía del 5 de junio Lenguaje aplicativo con referencias y asignación.

Ejercicios resueltos

  1. Guía del 17 de marzo de 2020, Ej. 6, caso Para Todo
  2. Ejemplo desarrollando el cálculo de un punto fijo
  3. Caso while para el teorema de coincidencia
  4. Guía 4 Ejercicio 2 (c)
  5. Guía 4 Ejercicio 10
  6. Guía 5 Ejercicio 4

Lab 2020

  • Primera semana. 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. Lab2. La tarea consiste en extender el lenguaje implementado en el Lab1 con variables enteras.
  • Lab3. Implementar la semántica denotacional para el lenguaje imperativo simple con fallas e input-output (LIS + Fallas + IO).
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

  1. 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).
  2. Implementación de semántica denotacional para un lenguaje aplicativo básico (Autor: Martín)
  3. Reducción en orden normal para cálculo lambda (Autor: Martín)

Exámenes Parciales de años anteriores

2018
2017
2016
2015
2013
2012
2011
2010
2009

Exámenes Finales de años anteriores

compiladores/main.txt · Última modificación: 2020/07/21 13:38 por gramagli