Fundamentos de Interpretación y Compilación de Lenguajes de Programación¶
Universidad del Valle, sede Tuluá · Escuela de Ingeniería de Sistemas y Computación · Agosto – Diciembre de 2026
Este sitio guarda lo que se hizo en clase: notas, intérpretes y ejemplos trabajados. El cronograma, el material de lectura previa, los quices, las entregas y las notas están en el Campus Virtual.
Horario¶
| Grupo | Día | Hora | Salón |
|---|---|---|---|
| 50 | Martes | 8:00 a. m. – 12:00 m. | Sede Príncipe, salón 7 |
Cada sesión son cuatro horas: las dos primeras son de exposición y las dos siguientes se dedican a resolver un ejercicio en Racket, que se entrega antes de salir.
Notas de clase¶
Se publican después de cada sesión.
Corte 1¶
-
Clase 1. Inducción y recursión — 8 de septiembre — conjuntos definidos por reglas y sus reconocedores, gramáticas BNF, recorrer siguiendo la gramática, recursión sobre árboles, declaración, referencia y alcance, ocurrencia libre y ligada, y
let,let*yletrec. Incluye el código escrito en clase. El repaso del lenguaje va aparte, en Racket, lo que hace falta para empezar. -
Clase 2. Estrategias para representar datos — 15 de septiembre — interfaz e implementación, el natural en representación unaria y en bignum con un solo
suma, la receta que saca constructores, predicados y extractores de una gramática, el TAD ambiente con listas y con procedimientos, y las expresiones del cálculo lambda conoccurs-free?yoccurs-bound?. Incluye el código escrito en clase. -
Clase 3. Datatypes y árboles de sintaxis abstracta — 22 de septiembre — el árbol binario escrito a mano y después con
define-datatype, los campos con su predicado ylist-of, el análisis por variante concases, el árbol de sintaxis abstracta y el que Python construye de sus propios programas, sintaxis concreta y abstracta, y el parser y el unparser del cálculo lambda y de un lenguaje de comandos. Incluye el código escrito en clase y los apuntes del tablero. -
Clase 4. Del texto al resultado — 29 de septiembre — el reparto del trabajo entre scanner, parser e interpretador, qué separa a un compilado de un interpretado con un programa en C llevado hasta su binario, la especificación léxica y la gramática de SLLGEN con la restricción que obliga a escribir
+(x, y), el primer interpretador completo repartido en archivos, yletcon sus cadenas de ambientes. Incluye el código de la demostración y los apuntes del tablero. -
Clase 5. Condicionales, procedimientos y alcance — 6 de octubre — el condicional con su chequeo de booleano, los tres valores expresados, la clausura y sus tres campos, la regla de la aplicación y el alcance estático, con los ejercicios de cadenas de ambientes que se trabajaron en el tablero. Incluye los apuntes de la sesión.
-
Clase 6. Procedimientos recursivos y letrec, 13 de octubre El factorial que no se deja escribir con
let, la dependencia circular entre el ambiente y la clausura, el ambiente extendido recursivo con sus tres listas, la clausura que nace al buscar el nombre, las tres condiciones que crean un ambiente y la recursión mutua en un solo marco. Incluye los apuntes del tablero.
Corte 2¶
-
Clase 7. Asignación y paso por referencia, 27 de octubre El contador que no se puede escribir sin estado, el almacén y sus celdas numeradas, las referencias explícitas con
newref,derefysetref, el aliasing, las referencias implícitas conset, y las dos políticas de paso de parámetros con los programas que las distinguen. -
Clase 8. Tipos y chequeo de tipos, 10 de noviembre La regla de la aplicación y la del
letrec, el factorial tipado paso a paso, cinco intentos que el chequeador rechaza con el mensaje que da cada uno, y las cinco cosas que hay que verificar siempre. -
Clase 9. Inferencia de tipos, 17 de noviembre El hueco que deja
?, la variable de tipo con su contenedor de una sola escritura, las ecuaciones que genera cada forma del lenguaje, la unificación con sus seis casos y los tres errores con el mensaje de cada uno, por qué la identidad no admite dos usos distintos, y dos exámenes viejos resueltos.
Actividades interactivas¶
Se trabajan en el navegador, sin instalar nada. Cada sesión deja la suya, y quedan disponibles después para volver sobre el tema.
-
Racket: notación prefija, recursión y listas simbólicas — cinco actividades y veintiocho procedimientos por escribir, sobre el lenguaje mismo: el operador que va adelante, los condicionales con
ify concond, la recursión lineal frente a la de cola, las ligaduras locales conlet,let*yletrec, y las listas de símbolos hasta llegar amapeayfiltra. Acompañan el material de lectura y conviene resolverlas antes de la primera sesión de contenido. -
Ejercicios de la clase 1: inducción y recursión — siete actividades, una por tema de la sesión: qué entra en un conjunto definido por reglas, los reconocedores que salen de esas reglas, las gramáticas BNF con sus cerraduras, recorrer listas, s-lists y árboles siguiendo la gramática, declaración, referencia y alcance, y las ligaduras locales que el recorrido necesita. El código corre en la misma página.
-
Ejercicios de la clase 2: estrategias para representar datos — ocho actividades, dos por tema de la sesión, una de analizar y una de escribir: qué clientes sobreviven a un cambio de representación y cómo se arreglan los que no, una cola con tres clientes contra dos representaciones y un contrato con ecuaciones para juzgar candidatas, un mismo dato leído bajo cinco representaciones del natural y la bignum en base 10 con acarreo y préstamo, y
apply-envpredicho sobre una cadena con nombres repetidos y cinco clientes del ambiente por la interfaz. -
Ejercicios de la clase 3: datatypes y árboles de sintaxis abstracta — once actividades, en el orden de los temas de la sesión: una expresión lambda leída como lista con
carycdry lo que se rompe al cambiar la representación, declaraciones condefine-datatypepara juzgar y para escribir, dos datatypes recorridos concases, los comandos de un robot y las expresiones booleanas, producciones de gramáticas casadas con sus variantes y gramáticas escritas a partir de los árboles dibujados, árboles de sintaxis abstracta para reconocer y para construir a mano, y el parser y el unparser de los dos lenguajes, uno con la palabra clave adelante y otro con el conectivo en medio, con el árbol esperado de cada prueba dibujado junto al que construye el código. -
Ejercicios de la clase 4: del texto al resultado — ocho actividades, una por tema de la sesión, casi todas de analizar y predecir: el reparto del trabajo entre scanner, parser e interpretador y en qué etapa se detiene cada programa, lo que se nota al usar un lenguaje compilado o interpretado, cuántos tokens deja cada programa y de qué clase es cada lexema, cómo se lee una especificación de SLLGEN, los valores expresados y denotados con el punto de entrada, el reparto del trabajo al evaluar y la ligadura local con su cadena de ambientes. La central es el simulador: se predice qué hará el interpretador y después la página abre sus tres etapas sobre ese mismo programa, con los tokens, el árbol dibujado y la traza fila por fila.
-
Ejercicios de la clase 5: condicionales, procedimientos y alcance — siete actividades, una por tema de la sesión: qué encargos no se podían escribir con el lenguaje anterior, el condicional y su verificación con
boolean?, elletde varias ligaduras y sus casos al borde, la cadena de ambientes dibujada con el ambiente vacío al final, qué guarda una clausura y qué verifica el interpretador antes de aplicar, los procedimientos que reciben y devuelven procedimientos, y el mismo programa bajo alcance estático y dinámico, con las dos trazas lado a lado. -
Ejercicios de la clase 6: procedimientos recursivos y letrec — nueve actividades, una por tema de la sesión: los cinco intentos de recursión con
letyproc, la producción nueva trabajada en los dos sentidos —de la gramática a los programas y del árbol que no se genera a la producción que falta—, qué guarda el marco recursivo y por qué la clausura captura el marco y no lo que el marco extiende, el momento en que nace cada clausura, cuatro trazas completas, la cadena dibujada con dos marcos recursivos a la vez, la recursión mutua en un solo marco, el TAD del ambiente escrito con listas etiquetadas, y el conteo de clausuras más la extensión del lenguaje con una forma nueva. -
Ejercicios de la clase 7: asignación y paso por referencia Dieciocho actividades, en el orden de los temas de la sesión: valor y efecto con el orden de evaluación, el almacén con sus operaciones y escrito en código, las referencias explícitas para predecir y para dibujar, las producciones de
setybegin, las clausuras que comparten celdas, las cláusulas del intérprete con asignación, la cadena dibujada con referencias, trazas completas, las celdas que reserva unletrec, el ambiente y un intérprete pequeño escritos a mano, y el paso por valor frente al paso por referencia, con los alias, su dibujo yevaluar-operandoen código. Casi todas dibujan la cadena de ambientes con el almacén debajo y una flecha de cada referencia a su celda. -
Ejercicios de la clase 8: chequeo de tipos Cuatro actividades en el orden de los temas de la sesión. Las dos primeras se responden escogiendo: qué tipo tiene cada expresión y cómo se escribe el tipo de un procedimiento, y luego qué exige cada regla, cuál falla en siete programas que el chequeador rechaza y qué habría hecho la máquina con ellos si los dejaran correr. Las dos últimas piden escribir código que corre en la página: el TAD tipo con su escritura, los asteriscos entre los parámetros y
apply-tenv, y después la regla del condicional y la de la aplicación con los tipos ya calculados. -
Ejercicios de la clase 9: inferencia de tipos Cinco actividades en el orden de los temas de la sesión: qué cambia cuando la anotación se escribe
?y el tipo se deduce, qué es una variable de tipo y cuándo dos partes del programa tienen que llevar la misma, cómo se genera el sistema de ecuaciones de un programa ecuación por ecuación, cómo se resuelve ese sistema unificando, y qué tipo infiere el interpretador para una expresión dada. La de ecuaciones sube de una sola ecuación hasta cinco, y la de unificación cierra con el chequeo de ocurrencia, que es lo que hace fallar aproc (? x) (x x).
Ejercicios de clase¶
Cada sesión tiene su repositorio. Se resuelve haciendo un fork, y la entrega es la dirección del fork con el identificador del último commit, que se reporta en el Campus Virtual antes de terminar la clase.
Uno por tema, en el orden en que se vieron:
- Recursión y ligadura:
https://github.com/EjerciciosClasesCardel/flp-2026-2-tema-01-recursion-y-ligadura - Representación de datos:
https://github.com/EjerciciosClasesCardel/flp-2026-2-tema-02-representacion-datos - Sintaxis abstracta:
https://github.com/EjerciciosClasesCardel/flp-2026-2-tema-03-sintaxis-abstracta - Literales y primitivas:
https://github.com/EjerciciosClasesCardel/flp-2026-2-tema-04-literales-primitivas - Procedimientos:
https://github.com/EjerciciosClasesCardel/flp-2026-2-tema-05-procedimientos - Recursión:
https://github.com/EjerciciosClasesCardel/flp-2026-2-tema-06-recursion - Asignación:
https://github.com/EjerciciosClasesCardel/flp-2026-2-tema-07-asignacion - Chequeo de tipos:
https://github.com/EjerciciosClasesCardel/flp-2026-2-tema-08-chequeo-tipos - Inferencia de tipos:
https://github.com/EjerciciosClasesCardel/flp-2026-2-tema-09-inferencia
Cada uno llega con el interpretador de su sesión resuelto hasta donde iba, los
huecos por llenar y la batería que dice si va bien. Las pruebas corren con
raco test pruebas/, y al hacer fork hay que entrar a la pestaña Actions y
habilitar los workflows para que se ejecuten solas en cada push.
Clases en video¶
Las grabaciones de cada sesión están en la lista de reproducción del curso, en orden cronológico: la sesión más reciente queda al final y la lista se va llenando a medida que avanza el semestre. Cada sesión se parte en varios videos cortos, para volver a un tema puntual sin recorrer la clase entera. El reproductor de abajo va sobre la lista completa; la barra que lo encabeza la abre en YouTube, en una pestaña nueva.
Reglas del código¶
Todo el código del curso se escribe en #lang eopl. Las representaciones de
sintaxis abstracta y de valores se declaran con define-datatype, y el
análisis por casos se hace con cases, nunca destructurando a mano con
car y cdr. Se resuelve con recursión estructural, sin set! salvo en
los capítulos donde la asignación es el tema.
Una regla que se aplica a todos los intérpretes del curso: al evaluar un
if-exp se calcula el valor de la prueba, se verifica que sea booleano y
solo entonces se escoge la rama. Nunca se delega en el if de Racket sobre
el resultado de value-of.
Referencias¶
- Friedman y Wand. Essentials of Programming Languages, 3.ª edición. MIT Press, 2008.
- Sebesta. Concepts of Programming Languages. Pearson.
- Pierce. Types and Programming Languages. MIT Press, 2002.
- The Racket Reference y The Racket Guide.