Saltar a contenido

Clase 4. Del texto al resultado: el proceso completo del interpretador

Martes 29 de septiembre de 2026.

Hasta ahora los programas llegaban ya partidos en piezas: listas simbólicas que el parser recorría con car y cdr. Un programa de verdad llega como texto, una cadena de caracteres y nada más. Esta sesión recorre lo que pasa entre esa cadena y el valor que se imprime, y al final construye el primer interpretador completo del curso: uno que evalúa números, variables, primitivas y let.

Las diapositivas están en el Campus Virtual. Aquí quedan las notas, el código de la demostración en C, en la carpeta codigo/, y los apuntes del tablero.

Referencia: Friedman y Wand, Essentials of Programming Languages, 3.ª edición, §3.1 y §3.2.

Del texto al resultado

La pregunta que abre la sesión. Dado este texto:

let x = 5 in -(x, 3)

la respuesta es 2. ¿Quién convierte el texto en árbol, y el árbol en esa respuesta? Hay cuatro trabajos distintos ahí dentro: separar la cadena en unidades con sentido, reconocer que la forma es let … in …, anotar que x quedó ligada a 5, y calcular \(5 - 3\).

Esos trabajos se reparten en tres etapas:

Etapa Recibe Produce
Scanner una cadena de caracteres una lista de tokens
Parser una lista de tokens un árbol de sintaxis abstracta
Interpretador un árbol y un ambiente un valor

El scanner agrupa caracteres en unidades, descarta los espacios y los comentarios, y etiqueta cada unidad con su clase. De estructura no entiende nada. El parser sí: decide que -(x, 3) es una primitiva con dos operandos. El significado lo pone el interpretador, que averigua cuánto vale x y hace la resta.

De ahí sale en qué etapa se detiene cada programa que no llega a dar un valor. Tokens legales en un orden que la gramática no genera, o tokens que sobran al final, los para el parser: +(x, 3) 4 termina con un reclamo por los símbolos que quedaron sueltos. Un carácter que ninguna regla léxica reconoce tampoco para al scanner, que corta la lista de tokens ahí mismo y sigue; el que falla es otra vez el parser, ahora por lo que le falta. Y una variable que nadie ligó no la detecta ninguno de los dos: está bien escrita, y solo falla cuando el interpretador va a buscar su valor.

Interpretación y compilación

Las dos primeras etapas son las mismas en un compilador y en un interpretador. Lo que cambia es qué se hace con el árbol: el interpretador lo recorre y produce la respuesta; el compilador lo traduce a código de máquina y no ejecuta nada.

Compilado Interpretado
Quién ejecuta la CPU, directamente un programa intermedio
Cuándo se ven los errores antes de ejecutar hasta que la ejecución llega ahí
Otra arquitectura hay que volver a construirlo basta tener el interpretador
Un cambio en una línea recompilar se prueba de inmediato

De ahí sale lo que se nota al usarlos. Un error en la última línea de un programa compilado impide que se ejecute la primera; en uno interpretado, las tres primeras líneas alcanzan a correr antes de fallar en la cuarta.

Java está en el medio: compila a bytecode una sola vez, y ese .class no lo ejecuta ninguna CPU real sino la máquina virtual, que es un interpretador. El JIT compila durante la ejecución los pedazos que más se usan, y por eso se acerca a la velocidad de un compilado sin alcanzarla.

Python plantea la pregunta contraria: si el interpretador es lento, por qué es el lenguaje del aprendizaje de máquina. Porque el intermediario se puede saltar: las librerías que hacen el trabajo pesado están escritas en C y ejecutan código de máquina directamente.

Lo que produce un compilador, visto de verdad

Para que el binario deje de ser una palabra, la sesión bajó a C. El programa, en codigo/ejemplo.c:

#include "stdlib.h"

int main() {

  int *arr = malloc(10 * sizeof(int));
  if (arr != NULL) {
    for (int i = 0; i < 10; i++) {
      *(arr + i) = i;
    }
  }
}

Diez espacios de tipo int, y un int ocupa 4 bytes: 40 bytes reservados. Ese número aparece literalmente en el ensamblador que produce el compilador, en codigo/ejemplo.s:

    subq    $16, %rsp
    movl    $40, %edi
    call    malloc@PLT
    movq    %rax, -8(%rbp)
    cmpq    $0, -8(%rbp)
    je  .L2

$40 es el argumento que se le pasa a malloc, y el cmpq $0 con el salto je es la comparación contra NULL del programa en C. El bucle queda más abajo, con el índice en -12(%rbp) y el cltq que extiende el entero a 64 bits para poder sumarlo a la dirección base.

Un paso más y ya no hay texto que leer. El volcado del ejecutable, en codigo/volcado-del-binario.txt, empieza así:

0000000 457f 464c 0102 0001 0000 0000 0000 0000
0000010 0003 003e 0001 0000 1040 0000 0000 0000

Esos primeros cuatro bytes, 7f 45 4c 46, son \x7fELF: la firma que dice que el archivo es un ejecutable de Linux. De ahí en adelante son números que la CPU sabe ejecutar y una persona no sabe leer. Eso es lo que entrega un compilador y lo que nunca produce un interpretador.

Lo que ve el scanner

Sobre el programa de arriba, los tokens son once:

let   x   =   5   in   -   (   x   ,   3   )

Los espacios no aparecen: el scanner los usa para saber dónde termina cada token y los tira. Lo mismo con los comentarios, que en el lenguaje del curso empiezan con % y llegan hasta el fin de la línea; una línea que empieza con % no produce ningún token.

Cada token lleva su clase. let e in son palabras reservadas, porque la gramática las nombra como literales; x es un identificador; 5 es un número; el resto son literales. Y ahí está la sorpresa que se repite todos los semestres: add1 no es un identificador sino un literal de la gramática, así que no sirve como nombre de variable. En cambio zero? sí sirve, mientras esa primitiva no exista, porque el identificador admite el signo de interrogación.

La regla que decide dónde corta es la del bocado más largo: el scanner toma la cadena más larga que alguna regla reconozca, sin mirar hacia atrás ni preguntarle al parser. Por eso x5 es un solo token y 5x son dos, un número y un identificador. Y por eso el espacio cambia la cuenta: -7 es un token, porque el signo hace parte del número negativo, mientras que - 7 son dos.

Cuando el scanner encuentra un carácter que ninguna regla reconoce, como #, no levanta un error: corta ahí y devuelve la lista de tokens que alcanzó a formar. El reclamo llega después, del parser, que se queda esperando un token que ya no viene.

SLLGEN: la especificación léxica y la gramática

Escribir el scanner y el parser a mano es trabajo de miles de líneas. SLLGEN los genera a partir de dos listas.

La especificación léxica tiene una regla por clase de token, y cada regla lleva tres cosas: un nombre arbitrario, una expresión regular y una acción.

(define especificacion-lexica
  '(
    (espacio-blanco (whitespace) skip)
    (comentario ("%" (arbno (not #\newline))) skip)
    (identificador (letter (arbno (or letter digit "?" "$"))) symbol)
    (numero (digit (arbno digit)) number)
    (numero ("-" digit (arbno digit)) number)
    (numero (digit (arbno digit)"." digit (arbno digit)) number)
    (numero ("-" digit (arbno digit)"." digit (arbno digit)) number)
    )
  )

Las acciones son cuatro y no hay más: skip para lo que se reconoce solo para descartarlo, y symbol, number y string para lo que se convierte en un dato de Racket. Los operadores de la expresión regular son or, arbno (cero o más), concat, y las clases letter, digit y whitespace.

La gramática tiene una producción por forma del lenguaje, y cada una termina con el nombre de la variante que SLLGEN va a generar:

(define especificacion-gramatical
  '(
    (programa (expresion) a-program)
    (expresion (numero) lit-exp)
    (expresion (identificador) var-exp)
    (expresion (primitiva "(" (separated-list expresion ",") ")") prim-exp)
    (primitiva ("+") sum-prim)
    (primitiva ("-") minus-prim)
    (primitiva ("*") mult-prim)
    (primitiva ("/") div-prim)
    (primitiva ("add1") add-prim)
    (primitiva ("sub1") sub-prim)
    )
  )

Lo que queda entre comillas es un literal y no se captura; cada no terminal es un campo de la variante. arbno y separated-list producen los dos una lista, y la diferencia está en el separador: separated-list es la que admite comas entre los elementos sin coma al final.

Con las dos listas, sllgen:make-define-datatypes genera los define-datatype que en la sesión anterior se escribían a mano, y sllgen:make-string-scanner y sllgen:make-string-parser generan las dos primeras etapas.

La gramática tiene una restricción, y explica una rareza de la notación del curso. El parser decide qué producción usar mirando el no terminal que busca y el primer token de la cadena, nada más. Dos producciones del mismo no terminal no pueden empezar con el mismo token: var x y var x = 10 chocan. Esa es la razón de que las primitivas del curso se escriban con el operador adelante, +(x, y): con el operador en medio, todas las producciones de expresión empezarían igual.

Un primer lenguaje interpretado

Dos nombres que hay que separar desde ahora. Los valores expresados son los que el programador ve; los valores denotados son los que se guardan en los ambientes. En este primer lenguaje coinciden, y son números. Cuando entren los booleanos y después las referencias, dejan de coincidir.

La gramática entra por un envoltorio:

(define-datatype programa programa?
  (a-program (exp expresion?)))

programa tiene un solo caso, que recibe una expresión. Es una limitación de SLLGEN: hace falta un punto de entrada único, y expresion tiene muchos casos. Más adelante, cuando el lenguaje tenga clases, el punto de entrada serán las declaraciones de clase más una expresión. Todo empieza siempre por programa.

Y el interpretador ya no vive en un archivo:

Archivo Qué tiene
sintaxis las dos especificaciones, los datatypes, el scanner y el parser
ambiente ambiente-vacio, ambiente-extendido y apply-env
primitivas evaluar-primitiva y su auxiliar de plegado
interprete evaluar-programa y evaluar-expresion
interfaz el punto de entrada y el REPL

Los interpretadores del curso están en el Campus Virtual repartidos así, y es la misma estructura del proyecto final. Quien ya hizo el fork lo sincroniza.

Primitivas y evaluación

El punto de entrada abre el envoltorio y arranca:

(define evaluar-programa
  (lambda (pgm)
    (cases programa pgm
      (a-program (exp) (evaluar-expresion exp ambiente-inicial))
      ))
  )

ambiente-inicial es el ambiente con el que arranca cualquier programa: dos eslabones de ligaduras, x = 1, y = 2, z = 3 sobre a = 4, b = 5, c = 6, y el vacío al final de la cadena.

evaluar-expresion tiene un caso por variante de expresión. Un literal devuelve su número; una variable se busca en el ambiente; una primitiva evalúa primero todos sus operandos y después aplica la operación:

(define evaluar-expresion
  (lambda (exp amb)
    (cases expresion exp
      (lit-exp (dato) dato)
      (var-exp (id) (apply-env amb id))
      (prim-exp (prim args)
                (let
                    (
                     (lista-numeros (map (lambda (x) (evaluar-expresion x amb)) args))
                     )
                  (evaluar-primitiva prim lista-numeros)
                  )
                )
      )
    )
  )

Las primitivas reciben una lista de operandos, no dos, y de ahí sale una decisión que conviene conocer porque no es la aritmética de siempre:

  • la suma y la multiplicación se aplican a toda la lista, con neutro 0 y 1;
  • la resta es el primero menos la suma del resto, de modo que \(a - b - c\) es \(a - (b + c)\);
  • la división es el primero dividido por la multiplicación del resto;
  • add1 y sub1 trabajan sobre el primero.

La razón es que solo se recorre con recursión lo que es asociativo. La resta y la división se convierten en una suma y una multiplicación del resto, y así la regla queda definida para cualquier cantidad de operandos.

El ambiente guarda sus valores con un predicado que siempre responde verdadero. Un valor puede ser cualquier cosa que Racket reconozca, y combinar number?, symbol? y los demás sería más frágil que aceptarlos todos.

En el REPL, sobre ese ambiente:

+(x, 3)       4
+(x, x)       2
add1(x)       2
sub1(x)       0
+(x, y, z)    6
-(c, y, x)    3

Las dos últimas usan la lista de operandos: +(x, y, z) suma los tres, y -(c, y, x) le resta a c la suma de los otros dos, \(6 - 3 = 3\). La c sale del segundo eslabón, que se consulta porque en el primero no está.

(parser "x") devuelve el árbol con su envoltorio a-program, y (evaluar-programa (parser "x")) devuelve 1. Con algo más largo, +(1, +(x, y)) produce una primitiva de suma cuyo primer operando es el literal 1 y cuyo segundo es otra suma de dos variables. Partir el texto en varias líneas no cambia nada: el salto de línea es espacio en blanco.

Agregar una operación cuesta dos cambios y nada más. Para el módulo: una producción nueva de primitiva en la gramática, con su nombre de variante, y su caso en evaluar-primitiva. No hay que programar el módulo, porque modulo ya es de Racket. Ahí está la distinción que conviene tener presente: una cosa es lo que hace el lenguaje que se está construyendo, y otra lo que hace Racket cuando lo procesa. La suma del lenguaje es la suma de Racket.

Ligadura local

Con lo anterior solo se pueden usar las variables del ambiente inicial. let extiende el ambiente:

let {<identificador> = <expresion>}* in <expresion>

La variante guarda tres campos: la lista de identificadores, la lista de expresiones ligadas y el cuerpo. Y la regla de evaluación tiene dos mitades que conviene no confundir:

  • las expresiones ligadas se evalúan en el ambiente actual, el de antes del let;
  • el cuerpo se evalúa en el ambiente extendido, el que ya incluye las ligaduras nuevas.

Por eso let x = x in … no tiene ningún problema: la x de la derecha se busca en el ambiente anterior. Y por eso el orden importa al dibujar.

Tres let anidados

Con el ambiente inicial, \(\rho_0 = [x = 1,\; y = 2,\; z = 3]\) sobre \([a = 4,\; b = 5,\; c = 6]\):

let m = sub1(c)
in let n = *(m, y)
   in let m = +(n, b)
      in -(m, +(n, y))

Cada let crea un eslabón:

Ambiente Ligadura De dónde sale
\(\rho_0\) x = 1, y = 2, z = 3 sobre a = 4, b = 5, c = 6 el inicial
\(\rho_1\) m = 5 sub1(c) con c = 6
\(\rho_2\) n = 10 *(m, y) con m = 5, y = 2
\(\rho_3\) m = 15 +(n, b) con n = 10, b = 5

El cuerpo se evalúa en \(\rho_3\): -(m, +(n, y)) es -(15, +(10, 2)), o sea \(15 - 12 = 3\).

La m del último let tapa a la del primero, y la n del segundo sigue visible porque la búsqueda va de adentro hacia afuera. La y y la b nunca se ligaron aquí: salen de los dos eslabones del inicial. El ambiente vacío va siempre al inicio de la cadena; sin él, el diagrama está mal desde el principio.

Cuando la ligadura nueva se llama igual

let a = +(a, 1) in let a = +(a, 2) in a

Con a = 4 en el ambiente inicial, el resultado es 7 y no 6. La expresión ligada del segundo let se evalúa en \(\rho_1\), donde a ya vale 5, no en \(\rho_0\) donde valía 4. La cadena queda a = 4, a = 5, a = 7, y cada eslabón tapa al anterior sin borrarlo.

Un let con tres ligaduras y lets adentro

El último ejercicio de la sesión, con x, y, z ligadas a 1, 2 y 3 en el primer eslabón del inicial:

El programa del tablero: un let con tres ligaduras, cada una con un let adentro, y el cuerpo que suma las tres

let x = let x = +(x, y) in +(x, y)
    y = let p = *(x, z) in +(x, p)
    z = let k = let p = 3 in +(x, p) in +(k, x)
in +(x, y, z)

Las tres expresiones ligadas se evalúan en \(\rho_0\), así que las tres ven x = 1, y = 2, z = 3, y ninguna ve lo que las otras dos están ligando. Cada una abre su propia cadena lateral:

El diagrama del tablero: el ambiente vacío, el inicial con x y z en 1 2 3, los ambientes laterales de cada ligadura y el extendido con 5 4 5

Ligadura Cadena lateral Cuerpo Valor
x x = 3, de +(x, y) +(x, y) con x = 3, y = 2 5
y p = 3, de *(x, z) +(x, p) con x = 1, p = 3 4
z p = 3, luego k = 4 +(k, x) con k = 4, x = 1 5

En la primera, la x del cuerpo vale 3 porque el let interno la tapó, mientras que la y sigue viniendo de \(\rho_0\). En la tercera hay dos niveles: p = 3 sirve para calcular k = +(x, p) = 4, y recién entonces +(k, x) da 5.

El ambiente extendido queda con x = 5, y = 4, z = 5, y el cuerpo +(x, y, z) da 14.

Un let siempre se reduce a un valor. Por eso puede ir donde vaya una expresión: dentro de una primitiva, dentro de otro let, o como la expresión ligada de una declaración, que es lo que pasa aquí tres veces.

Ejercicios de la segunda mitad

La segunda mitad fue sobre las actividades interactivas de la sesión, y varias se resolvieron en el tablero.

En las de leer una especificación de SLLGEN, lo que se juzga es qué captura cada producción. (expresion (numero) lit-exp) deja un solo campo; la del let, con la lista de identificadores, la de expresiones ligadas y el cuerpo, deja tres; y lo que va entre comillas no deja campo. Saber cuántos campos vienen y en qué orden es lo que después permite escribir el cases.

En las de contar llamadas, la cuenta sale de recorrer el árbol: cada literal, cada variable y cada primitiva son una llamada a evaluar-expresion, y solo las variables llaman a apply-env. +(*(y, b), add1(z)) evalúa a 14 con seis llamadas y tres búsquedas.

En las de cadenas de ambientes, la pregunta que más discusión tuvo fue si una ligadura vieja se sigue alcanzando después de que otra con el mismo nombre la tapó. No se alcanza: la búsqueda para en la primera coincidencia yendo de adentro hacia afuera. Y sobre si el ambiente inicial llega a consultarse, en varios de estos programas la respuesta es que no, porque todo lo que el cuerpo nombra lo ligó algún let.

Los apuntes del tablero

La hoja de la sesión, con los tres ejercicios de let y sus cadenas de ambientes, y el recuadro que separa lo que se evalúa en el ambiente actual de lo que se evalúa en el extendido.

Lo que sigue

El lenguaje solo tiene números. Al agregar las comparaciones ==, < y > y el condicional aparecen los booleanos, y con ellos los valores expresados dejan de ser una sola clase: if evalúa la prueba, comprueba que sea booleana y solo entonces escoge la rama. Las dos sesiones siguientes son de diagramas de ambientes, que es lo que se acaba de empezar aquí.