Unidad 2: Construcción de intérpretes

Borrador generado con IA. El texto de esta unidad fue generado automáticamente a partir de las transcripciones de las clases y está pendiente de revisión y edición por parte del equipo docente. Puede contener errores, omisiones o imprecisiones; ante cualquier discrepancia, prevalecen las presentaciones y el material oficial del curso.

Esta unidad es el núcleo del curso: aquí construimos nuestro primer intérprete ejecutable y establecemos la metodología que reutilizaremos, con variaciones, en todas las unidades siguientes. Partimos de una calculadora aritmética y la extendemos, paso a paso, hasta soportar identificadores locales. En el camino aparecen las dos ideas semánticas centrales de la unidad: la sustitución y su versión eficiente, la sustitución diferida con ambientes.

Todo el código está escrito en #lang play, el lenguaje docente basado en Racket que usamos en el curso. Encabezamos cada archivo con (print-only-errors #t) para que la salida de los tests muestre solo las fallas.

El pipeline de un lenguaje de programación

Un programa se escribe como texto, pero ningún procesador de lenguajes trabaja directamente sobre ese texto: primero lo traduce a una estructura de datos que sea fácil de manipular programáticamente. Ese flujo, común a intérpretes y compiladores, es el siguiente:

código fuente        árbol de sintaxis           resultado
(sintaxis concreta)  abstracta (AST)             del programa
      │                     │                        │
      │      parse          │      interp            │
      └────────────────────►└───────────────────────►
                            │
                            │  optimización, chequeo de tipos,
                            │  análisis, transformaciones...

Distinguimos dos niveles de sintaxis:

  • La sintaxis concreta es la apariencia del programa, lo que efectivamente escribe quien programa. Una misma operación admite muchas notaciones concretas: 3 + 4 (infija), (+ 3 4) (prefija) o (3 4 +) (postfija).

  • La sintaxis abstracta es la esencia del programa: qué operación es y sobre qué opera, sin los detalles superfluos de cómo se escribió. Se representa como un árbol de sintaxis abstracta (Abstract Syntax Tree, AST).

El parser traduce sintaxis concreta a sintaxis abstracta. El intérprete recorre el AST y produce un valor. La idea fuerza es que la sintaxis abstracta nos permite concentrarnos en la semántica —lo que realmente estudiamos en este curso— sin gastar esfuerzo en la sintaxis concreta.

Este es exactamente el esquema conceptual de cualquier lenguaje interpretado real. Un intérprete de Python escrito en C tendría un archivo .py como código fuente, un parser (probablemente separado en lexer y parser, generado con herramientas tipo lex/yacc), un AST representado con `struct`s de C, y un intérprete que recorre esas estructuras. Los lenguajes compilados reemplazan la interpretación por una fase de compilación hacia otra gramática (bytecode, ensamblador x86, etc.). Nosotros hacemos todo en Racket porque, aunque parezca sorprendente, así nos ahorramos una enorme cantidad de complejidad técnica y llegamos rápido a lo que nos interesa: la semántica.

Por qué expresiones S: parsers fáciles

Para el código fuente usaremos expresiones S (s-expressions), la notación entre paréntesis inventada en Lisp y usada en Scheme y Racket. Una expresión S es un átomo (un valor literal o un identificador) o una secuencia de expresiones S anidadas entre paréntesis.

La elección no es casual. Si escribimos {+ 1 1} (notación prefija con paréntesis, igual que Racket) el parser es fácil: la estructura de la expresión ya viene dada por los paréntesis. Si en cambio quisiéramos escribir 1 + 1 (notación infija, como los lenguajes convencionales) el parser sería difícil: habría que lidiar con precedencia de operadores, asociatividad, etc. Como en este curso no estudiamos parsing sino semántica, elegimos deliberadamente la sintaxis fácil de parsear.

Por convención, en el código fuente de los lenguajes que interpretamos usamos llaves { } en lugar de paréntesis ( ). Es solo una ayuda visual para distinguir "esto es un programa en el lenguaje fuente" de "esto es código Racket". Para Racket, {…​} y (…​) son equivalentes.

Recordatorio: la gramática manda

Antes de escribir un parser conviene recordar la metodología de tipos inductivos de la Unidad 1, porque todo nace de la gramática y este patrón se usa en el 80% del curso. Dado un tipo inductivo, su definición con deftype es casi mecánica y toda función que lo procese sigue su esquema de recursión estructural: un caso por variante, con llamadas recursivas donde haya componentes del mismo tipo.

#lang play

#|
<BinTree> ::= (leaf v)
            | (in-node v <BinTree> <BinTree>)
|#
(deftype BinTree
  (leaf v)
  (in-node v left right))

;; sum-bintree :: BinTree -> Number
(define (sum-bintree bt)
  (match bt
    [(leaf v) v]
    [(in-node v l r)
     (+ v (sum-bintree l) (sum-bintree r))]))

El parser y el intérprete que construiremos en esta unidad son, estructuralmente, funciones de este tipo: un match sobre un tipo inductivo, con un caso por variante y recursión sobre las subexpresiones. Reconocer ese patrón hace que escribirlos sea, en gran medida, "seguir la gramática".

Una calculadora: el primer intérprete

Comenzamos con un lenguaje mínimo de expresiones aritméticas con sumas.

Sintaxis concreta y abstracta

La gramática concreta describe cómo se escriben los programas. La damos en notación BNF, en un bloque literal (no es código Racket):

<s-expr> ::= <num>
           | {+ <s-expr> <s-expr>}

La gramática abstracta describe la estructura del AST. Nótese que las dos gramáticas no son iguales: la abstracta no retiene detalles superfluos (como el símbolo +, que en el AST se vuelve el tipo de nodo).

<expr> ::= (num <num>)
         | (add <expr> <expr>)

La gramática abstracta se traduce mecánicamente a un tipo inductivo con deftype:

(deftype Expr
  (num n)
  (add l r))

Esto genera automáticamente los constructores num y add, los predicados num? y add?, y los accesores correspondientes. Por ejemplo, el código fuente '{+ {+ 1 1} 2} debe parsearse al AST (add (add (num 1) (num 1)) (num 2)).

En Racket, '{+ 1 2} es un valor cuoteado: una lista cuyo primer elemento es el símbolo '+ y cuyos otros elementos son los números 1 y 2. El parser trabaja sobre esa lista.

El parser

El parser hace un análisis caso por caso de la expresión S con match y construye el nodo del AST correspondiente.

;; parse :: s-expr -> Expr
;; Traduce código fuente (s-expr) a un AST de tipo Expr.
(define (parse s-expr)
  (match s-expr
    [n #:when (number? n) (num n)]
    [(list '+ l-sexpr r-sexpr)
     (add (parse l-sexpr) (parse r-sexpr))]))

(test (parse '1) (num 1))
(test (parse '14) (num 14))
(test (parse '{+ 1 2}) (add (num 1) (num 2)))
(test (parse '{+ {+ 1 1} 2}) (add (add (num 1) (num 1)) (num 2)))

Hay dos decisiones sutiles en este parser, y ambas son fuente clásica de errores.

El predicado #:when (number? n) no es opcional

Un patrón que es solo una variable, como [n (num n)], calza con cualquier cosa, incluida la lista '{+ 1 1}. Si no restringimos ese caso con #:when (number? n), el parser nunca llegaría a analizar las listas: toda expresión caería en el primer caso. Por eso en el parser el orden de las cláusulas importa y las variables "atrapa-todo" deben ir acompañadas de un predicado.

El mismo efecto se puede lograr con el patrón (? number? n) en lugar de n #:when (number? n); son equivalentes. Cuando extendamos el lenguaje con booleanos, strings, etc., necesitaremos un predicado análogo (boolean?, string?…) para discernir cada tipo de átomo.
El parser debe ser recursivo

Si escribiéramos (add l-sexpr r-sexpr) en vez de (add (parse l-sexpr) (parse r-sexpr)), el resultado no sería un AST válido: los campos del nodo add contendrían los números crudos de Racket (1, 2) en lugar de nodos (num 1), (num 2). Según la gramática abstracta, dentro de un add debe haber otra <expr>. Por eso hay que parsear recursivamente cada subexpresión.

Metodología de extensión

Extender el lenguaje con una nueva característica sintáctica involucra siempre los mismos pasos:

  1. Extender la sintaxis concreta: ¿cómo escribirán los programas quienes usen la nueva característica?

  2. Extender la sintaxis abstracta (deftype): ¿qué información hay que capturar para interpretar luego?

  3. Extender el parser: para traducir la nueva sintaxis concreta a la abstracta.

  4. Extender el intérprete: para implementar la nueva semántica (lo veremos al llegar a interp).

Apliquémoslo para agregar la resta y un condicional if0. La resta es "más de lo mismo" (otra operación binaria); solo cambia el símbolo:

<s-expr> ::= <num>
           | {+ <s-expr> <s-expr>}
           | {- <s-expr> <s-expr>}
           | {if0 <s-expr> <s-expr> <s-expr>}
(deftype Expr
  (num n)
  (add l r)
  (sub l r)
  (if0 c t f))

;; parse :: s-expr -> Expr
(define (parse s-expr)
  (match s-expr
    [n #:when (number? n) (num n)]
    [(list '+ l r) (add (parse l) (parse r))]
    [(list '- l r) (sub (parse l) (parse r))]
    [(list 'if0 c t f) (if0 (parse c) (parse t) (parse f))]))

(test (parse '{+ {- 1 1} 2}) (add (sub (num 1) (num 1)) (num 2)))
(test (parse '{if0 0 1 2}) (if0 (num 0) (num 1) (num 2)))
(test (parse '{if0 {- 1 {+ 1 0}} 1 2})
      (if0 (sub (num 1) (add (num 1) (num 0))) (num 1) (num 2)))

La expresión if0 evalúa su primera subexpresión (la condición); si vale 0 toma la segunda rama, y si no, la tercera.

¿Por qué if0 y no un if con booleanos? Porque nuestro lenguaje todavía no tiene valores booleanos: solo números. if0 codifica una decisión ("¿es cero o no?") usando lo único que tenemos. Agregar booleanos, and, or, not y comparadores queda propuesto como ejercicio; se hace con la misma metodología de cuatro pasos.

El intérprete de aritmética

El intérprete toma un AST y produce un número. Su contrato es interp :: Expr → Number y, como Expr es un tipo inductivo, se implementa con un match caso por caso siguiendo las variantes. (En las primeras clases lo llamamos calc, por "calculadora"; a partir de ahora usamos el nombre general interp.)

;; interp :: Expr -> Number
;; Evalúa una expresión aritmética.
(define (interp expr)
  (match expr
    [(num n) n]
    [(add l r) (+ (interp l) (interp r))]
    [(sub l r) (- (interp l) (interp r))]
    [(if0 c t f) (if (zero? (interp c)) (interp t) (interp f))]))

(test (interp (parse '{+ 1 2})) 3)
(test (interp (parse '{+ {- 1 1} 2})) 2)
(test (interp (parse '{if0 0 1 2})) 1)
(test (interp (parse '{if0 1 1 2})) 2)

Observaciones clave:

  • Interpretar un (num n) es simplemente el número n: nos apoyamos en los números de Racket para representar los números de nuestro lenguaje.

  • Interpretar un (add l r) requiere interpretar recursivamente las subexpresiones y luego sumar los números resultantes con el ` primitivo de Racket. Si escribiéramos `( l r) estaríamos intentando "sumar nodos" del AST, lo que no tiene sentido. Este patrón de recursión sobre subexpresiones aparece en todos los intérpretes.

  • Interpretar (if0 c t f) usa el if primitivo de Racket para implementar la semántica condicional de nuestro if0. Como zero? recibe un número, primero hay que interpretar la condición.

Un intérprete que implementa las operaciones de un lenguaje apoyándose en las operaciones análogas del lenguaje anfitrión (la suma con la suma de Racket, el condicional con el if de Racket, los números con los números de Racket) se llama metacircular. Parseamos desde la sintaxis de Racket hacia nuestra sintaxis abstracta y el intérprete la "trae de vuelta" como valores de Racket.

Escribe los tests antes de implementar, y asegúrate de que ejerciten todas las variantes del lenguaje. Si, por ejemplo, olvidas el caso sub en el intérprete pero ningún test usa restas, no detectarás el error: la combinación de match con deftype solo garantiza exhaustividad si tus tests recorren todas las variantes.

Identificadores locales: la expresión with

Hasta aquí solo sabemos escribir programas que combinan números. Queremos ahora poder nombrar valores intermedios, de forma análoga al let de Racket. Introducimos la expresión with:

{with {x {+ 5 5}} {+ x x}}   ;; intuitivamente => 20

A diferencia de las extensiones anteriores (resta, if0, booleanos), que eran "más de lo mismo", la semántica de los identificadores locales no es directa: requiere conceptos nuevos. Deliberadamente no nos apoyaremos en el let de Racket para implementarla, porque eso sería hacer trampa y no entenderíamos el significado real de introducir identificadores.

Una expresión with tiene tres partes:

  • el identificador que se introduce (por ejemplo x);

  • la expresión nombrada, a la que queda asociado el identificador ({+ 5 5});

  • el cuerpo, el alcance en el que la asociación identificador–valor está vigente ({+ x x}).

Llamamos identificadores y no variables a propósito. El término "variable" está cargado semánticamente: sugiere que el valor asociado puede cambiar (variar). Como por ahora el lenguaje no ofrece ninguna forma de modificar ese valor, usamos el término más conservador "identificador".

Extensión de la sintaxis

Extendemos ambas gramáticas. Nótese los paréntesis internos obligatorios que delimitan {identificador expresión-nombrada}, separándolos del cuerpo:

<s-expr> ::= <num>
           | <sym>
           | {+ <s-expr> <s-expr>}
           | {- <s-expr> <s-expr>}
           | {if0 <s-expr> <s-expr> <s-expr>}
           | {with {<sym> <s-expr>} <s-expr>}

En la sintaxis abstracta agregamos dos nodos: with (que guarda el símbolo introducido, la expresión nombrada y el cuerpo) e id (para poder representar el uso de un identificador, como la x en {+ x x}).

(deftype Expr
  (num n)
  (add l r)
  (sub l r)
  (if0 c t f)
  (with x named-expr body)
  (id x))

En el parser, un símbolo se parsea como id, y la forma with se reconoce con un patrón anidado. El predicado (? symbol? x) obliga a que el identificador introducido sea efectivamente un símbolo (así {with {1 1} …​} es un error de sintaxis, como debe ser):

;; parse :: s-expr -> Expr
(define (parse s-expr)
  (match s-expr
    [n #:when (number? n) (num n)]
    [x #:when (symbol? x) (id x)]
    [(list '+ l r) (add (parse l) (parse r))]
    [(list '- l r) (sub (parse l) (parse r))]
    [(list 'if0 c t f) (if0 (parse c) (parse t) (parse f))]
    [(list 'with (list (? symbol? x) named-expr) body)
     (with x (parse named-expr) (parse body))]))

(test (parse '{with {x 1} x}) (with 'x (num 1) (id 'x)))
(test (parse '{with {x {+ 1 2}} x}) (with 'x (add (num 1) (num 2)) (id 'x)))

Nótese que el identificador introducido no se parsea: se guarda directamente como símbolo dentro del nodo with. Sí se parsean la expresión nombrada y el cuerpo, porque son programas que eventualmente habrá que interpretar.

El caso de id debe ir después del caso de num, pero puede ir antes de los casos de listas; lo importante es que las variables con predicado (num, id) no "tapen" a los patrones de lista más específicos. Este lenguaje —expresiones aritméticas con identificadores locales— se conoce como WAE (With and Arithmetic Expressions).

Ocurrencias, alcance y expresiones abiertas

La sintaxis concreta (y por lo tanto el parser) puede expresar programas con sentido y programas sin sentido. Ambos programas siguientes se parsean correctamente, pero solo el primero se puede interpretar:

{with {x 10} x}     ;; => 10
{with {x 10} z}     ;; => ??  (z no está definido)

Para precisar la diferencia necesitamos vocabulario sobre las ocurrencias de un identificador:

  • Instancia de asociación (binding occurrence): la ocurrencia que introduce el identificador en un alcance (la x en {with {x …​} …​}).

  • Ocurrencia ligada (bound occurrence): un uso del identificador dentro del alcance de su instancia de asociación.

  • Ocurrencia libre (free occurrence): un uso que no está dentro del cuerpo de ningún with que introduzca ese identificador.

Y sobre expresiones completas:

  • Expresión abierta: tiene al menos una ocurrencia libre.

  • Expresión cerrada: no tiene ocurrencias libres.

Consideremos:

{with {x {+ 5 5}} {with {y {- 3 x}} {+ x y}}}

Aquí la primera x es una instancia de asociación; las x de {- 3 x} y {+ x y} son ocurrencias ligadas (están en el cuerpo del with que introduce x); análogamente para y. En cambio, en {with {x 10} {+ x z}} la z es una ocurrencia libre: la expresión es abierta.

El alcance de la asociación introducida por un with es solo su cuerpo. Por eso {+ x {with {x 1} x}} tiene la primera x libre: no está dentro del cuerpo del with que introduce x. Solo las expresiones cerradas se pueden reducir a un valor; nuestro intérprete arrojará un error ante una ocurrencia libre. La regla es análoga a la de los cuantificadores lógicos o las integrales definidas: una variable ligada por ∀x, ∃x o ∫ …​ dx no es libre.

Shadowing

¿A qué valor debe reducir el siguiente programa?

{with {x 0} {with {x 1} x}}   ;; => 1

Cuando hay una colisión de alcances (dos with que introducen el mismo identificador), el alcance más interno tiene precedencia: la x del cuerpo se refiere al with más cercano. Este fenómeno se llama shadowing (el binding interno "ensombrece" al externo) y es una manifestación del alcance léxico: un identificador ligado se asocia a su with más cercano que lo introduce.

Esta observación es la clave de la implementación:

Al evaluar {with {id named-expr} body} debemos sustituir en body solo las ocurrencias libres de id. Las ocurrencias de id que estén ligadas por un with interno no deben tocarse, porque pertenecen a otro binding.

Semántica de with: sustitución

Reducir una expresión con identificadores es una mezcla de evaluación y sustitución. Veamos la intuición paso a paso con {with {x {+ 5 5}} {with {y {- 3 x}} {+ x y}}}:

{with {x {+ 5 5}} {with {y {- 3 x}} {+ x y}}}
  → {with {x 10} {with {y {- 3 x}} {+ x y}}}   [evalúa la expr. nombrada]
  → {with {y {- 3 10}} {+ 10 y}}               [sustituye x por 10 y desciende]
  → {with {y -7} {+ 10 y}}                      [evalúa la expr. nombrada]
  → {+ 10 -7}                                   [sustituye y por -7 y desciende]
  → 3

A medida que avanza la interpretación, los with se van "descargando": se calcula la expresión nombrada, se sustituye la asociación en el cuerpo, y el intérprete desciende al cuerpo y nunca vuelve a salir. El programa se va reduciendo hasta llegar al valor final.

Formalizamos la regla:

Evaluación de {with {id named-expr} body}

  1. Calcular el valor de named-expr.

  2. Sustituir en body las ocurrencias libres de id por ese valor (y "deshacerse" del identificador).

  3. Reducir recursivamente la expresión obtenida.

La función de sustitución

La sustitución es un transformador de AST: no evalúa, sino que transforma un árbol de sintaxis en otro. Su contrato es subst :: Expr Symbol Expr → Expr. Usamos la convención de nombres (subst in what for), que se lee: sustituye en la expresión in todas las ocurrencias libres del identificador what por la expresión for.

;; subst :: Expr Symbol Expr -> Expr
;; (subst in what for): sustituye todas las ocurrencias libres del
;; identificador 'what' en la expresión 'in' por la expresión 'for'.
(define (subst in what for)
  (match in
    [(num n) (num n)]
    [(add l r) (add (subst l what for) (subst r what for))]
    [(sub l r) (sub (subst l what for) (subst r what for))]
    [(if0 c t f) (if0 (subst c what for)
                      (subst t what for)
                      (subst f what for))]
    [(id x) (if (symbol=? x what)
                for              ;; el identificador buscado: se reemplaza
                (id x))]         ;; otro identificador: se deja intacto
    [(with x e b)
     (if (symbol=? x what)
         (with x (subst e what for) b)                    ;; (1)
         (with x (subst e what for) (subst b what for)))]));; (2)

(test (subst (id 'x) 'x (num 1)) (num 1))
(test (subst (add (id 'x) (id 'x)) 'x (num 1)) (add (num 1) (num 1)))
(test (subst (with 'x (num 4) (id 'x)) 'x (num 1)) (with 'x (num 4) (id 'x)))
(test (subst (with 'y (num 4) (id 'x)) 'x (num 1)) (with 'y (num 4) (num 1)))

Para los nodos que no involucran identificadores (num, add, sub, if0), la sustitución simplemente se propaga recursivamente a las subexpresiones. Los dos casos interesantes son id y with:

  • En id: si el símbolo coincide con what, este es el punto donde ocurre la sustitución (retornamos for); si no, dejamos el identificador intacto.

  • En with: aquí hay que decidir si sustituir dentro del cuerpo, respetando el shadowing.

El caso with: el corazón de la sustitución

El nodo with x e b introduce el identificador x. Debemos comparar x con what:

  • (1) Si (symbol=? x what): el cuerpo b está en el alcance de este with, así que todas las ocurrencias de what en b están ligadas (no libres). Por lo tanto no sustituimos en b: lo dejamos tal cual. Sí sustituimos en la expresión nombrada e, porque e no está en el alcance de este with (el binding aún no está vigente ahí) y puede contener ocurrencias libres de what.

  • (2) Si son distintos: en b sí puede haber ocurrencias libres de what, así que propagamos la sustitución tanto a e como a b.

Olvidar la guarda (symbol=? x what) rompe el shadowing: se sustituirían ocurrencias ligadas que pertenecen a otro binding, y {with {x 0} {with {x 1} x}} daría 0 en vez de 1.

El intérprete con sustitución

Ahora completamos el intérprete con los casos with e id:

;; interp :: Expr -> Number
(define (interp expr)
  (match expr
    [(num n) n]
    [(add l r) (+ (interp l) (interp r))]
    [(sub l r) (- (interp l) (interp r))]
    [(if0 c t f) (if (zero? (interp c)) (interp t) (interp f))]
    [(with x named-expr body)
     (interp (subst body x (num (interp named-expr))))]
    [(id x) (error 'interp "Open expression (free occurrence of ~a)" x)]))

;; run :: s-expr -> Number
(define (run expr) (interp (parse expr)))

El caso with es la traducción literal de la regla de tres pasos: interpretamos named-expr, envolvemos el resultado con subst en el body, y volvemos a interpretar.

El "truco" del (num …​)

(interp named-expr) devuelve un número de Racket, pero subst espera una Expr como tercer argumento. Por eso reenvolvemos el resultado con el constructor num: (subst body x (num (interp named-expr))). Este pequeño detalle es fácil de olvidar; su síntoma típico es un error no matching clause for 5 (un 5 crudo donde se esperaba un (num 5)). Sabemos que siempre funciona porque, hasta aquí, el intérprete siempre retorna números.
Por qué id es un error

Si el intérprete llega a un nodo id, significa que ese identificador nunca fue sustituido. Y si no fue sustituido, es porque no existía ningún with que lo introdujera; es decir, es una ocurrencia libre y la expresión es abierta. Una ocurrencia libre no tiene valor asociado, así que lo único correcto es fallar: Open expression. Toda ocurrencia ligada, en cambio, es eliminada por una sustitución antes de que el intérprete la alcance.

Ejemplos trabajados

Estos tests corresponden a los ejemplos desarrollados paso a paso en clase (numerados por lámina). Ilustran cómo se intercalan sustitución e interpretación, y en particular el shadowing:

(test (run '{with {x 5} {+ x x}}) 10)                     ;; slide 20
(test (run '{with {x {+ 5 5}} {+ x x}}) 20)               ;; slide 21
(test (run '{with {x 10} {with {x 1} x}}) 1)              ;; slide 22
(test (run '{with {x 10} {with {x x} {+ x x}}}) 20)       ;; slide 23
(test (run '{with {x 5} {with {y x} y}}) 5)               ;; slide 24
(test (run '{with {x 5} {+ x {with {x 3} {+ x x}}}}) 11)  ;; slide 25
(test (run '{with {x 5} {+ x {with {y 3} {+ y x}}}}) 13)  ;; slide 26
(test (run '{with {x 5} {+ {with {x 10} {+ x x}}
                          {with {y {+ x x}} {+ y x}}}}) 35);; slide 27
(test (run '{with {x {+ 5 5}}
              {with {y {- x 3}}
                {with {x {+ y x}}
                  {with {z {+ x y}}
                    {with {x z}
                      {+ x y}}}}}}) 31)                    ;; slide 28

Vale la pena detenerse en dos:

  • slide 23 — {with {x 10} {with {x x} {+ x x}}} da 20. La expresión nombrada x del with interno sí se refiere al x externo (vale 10), porque la expresión nombrada está fuera del alcance del with interno. El cuerpo {+ x x} usa el x interno (también 10). Resultado: 20.

  • slide 28 — la cadena anidada da 31. Trazando las asociaciones: x=10, luego y=x-3=7, luego x=y+x=17, luego z=x+y=24, luego x=z=24; el cuerpo {+ x y} usa el x más interno (24) y la y vigente (7): 24+7=31.

Sustitución diferida: ambientes

La sustitución explícita es correcta pero ineficiente. Cada with (y más adelante, cada aplicación de función) dispara una llamada a subst que recorre el árbol de sintaxis completo en profundidad. En el peor caso esto es de orden cuadrático en el tamaño del AST. Peor aún: podríamos recorrer todo el árbol en vano, como en {with {x {+ 5 5}} 42}, donde x no se usa y la sustitución no cambia nada.

La idea para mejorarlo es diferir las sustituciones en lugar de realizarlas de inmediato: en vez de sustituir, registramos la sustitución pendiente en una estructura de datos —un repositorio de sustituciones diferidas— que llamamos ambiente (environment, abreviado env).

La estrategia cambia así:

  • Comenzamos con un ambiente vacío.

  • Cuando habría que sustituir (al evaluar un with), en lugar de sustituir extendemos el ambiente con la asociación identificador → valor, y continuamos evaluando el cuerpo con ese nuevo ambiente.

  • Cuando el intérprete se encuentra con un identificador, ese es el momento de resolver la sustitución que veníamos postergando: buscamos el identificador en el ambiente. Ya no es un error: es una consulta.

El tipo de dato Env

El ambiente es un tipo de dato abstracto con tres operaciones: crear el ambiente vacío, extenderlo con una asociación, y buscar el valor de un identificador. Lo implementamos como un tipo inductivo, estructuralmente idéntico a una lista enlazada de pares (identificador, valor):

<env> ::= (mtEnv)
        | (aEnv <id> <value> <env>)
(deftype Env
  (mtEnv)
  (aEnv id val env))

;; empty-env :: Env
(define empty-env (mtEnv))

;; extend-env :: Symbol Value Env -> Env
(define extend-env aEnv)

;; env-lookup :: Symbol Env -> Value
(define (env-lookup x env)
  (match env
    [(mtEnv) (error 'env-lookup "free identifier: ~a" x)]
    [(aEnv id val rest) (if (symbol=? id x)
                            val
                            (env-lookup x rest))]))

empty-env invoca el constructor del ambiente vacío; extend-env es (literalmente) el constructor aEnv; y env-lookup es una búsqueda recursiva: si el identificador en el nodo coincide, retorna su valor, y si no, continúa en el resto del ambiente.

Ahora el error de identificador libre se traslada al caso mtEnv de env-lookup. Si la búsqueda recursiva agota el ambiente sin encontrar el identificador, es porque nunca fue introducido por un with: era una ocurrencia libre. El razonamiento es el mismo que antes; solo cambia dónde se detecta.

El intérprete con ambientes

El intérprete pasa a llevar un parámetro adicional, el ambiente: `interp

Expr Env → Number`. Compárese caso a caso con la versión por sustitución explícita:

;; interp :: Expr Env -> Number
(define (interp expr env)
  (match expr
    [(num n) n]
    [(add l r) (+ (interp l env) (interp r env))]
    [(sub l r) (- (interp l env) (interp r env))]
    [(if0 c t f) (if (zero? (interp c env)) (interp t env) (interp f env))]
    [(with x named-expr body)
     ;; en vez de sustituir: extender el ambiente y seguir
     (def new-env (extend-env x (interp named-expr env) env))
     (interp body new-env)]
    [(id x)
     ;; en vez de fallar: buscar la sustitución diferida
     (env-lookup x env)]))

;; run :: s-expr -> Number
(define (run expr) (interp (parse expr) empty-env))

Los casos num, add, sub e if0 solo propagan el ambiente sin usarlo. Los dos casos que cambian de raíz son:

  • with: ya no llamamos a subst. Interpretamos la expresión nombrada, extendemos el ambiente con x → valor y evaluamos el cuerpo en new-env.

  • id: ya no es un error. Consultamos env-lookup, que devuelve el valor diferido (o falla si el identificador es realmente libre).

Este intérprete reconoce exactamente el mismo lenguaje WAE y produce los mismos resultados que el de sustitución explícita para todos los ejemplos anteriores, pero sin recorrer el AST repetidamente. La sustitución diferida con ambientes es el mecanismo que usaremos durante el resto del curso.

La sustitución diferida abre además la puerta a decisiones semánticas que estudiaremos más adelante:

  • Cómo se resuelven los identificadores al aplicar funciones da lugar a la distinción entre alcance estático y alcance dinámico (Unidad 3).

  • Qué guardamos en el ambiente —el valor ya calculado de la expresión nombrada, o la expresión sin evaluar— da lugar a la distinción entre evaluación temprana (eager) y evaluación perezosa (lazy) (Unidad 4).

Ejercicios propuestos

  1. Más aritmética. Extender el lenguaje con multiplicación y división, siguiendo los cuatro pasos de la metodología (sintaxis concreta, abstracta, parser, intérprete). ¿Qué decisión de diseño tomas para la división por cero?

  2. Booleanos y lógica. Agregar valores booleanos (usando los literales #t y #f de Racket, con el predicado boolean? en el parser) y las operaciones and, or, not. Implementar and y or con semántica de cortocircuito: and no evalúa su segundo operando si el primero es falso, y or no lo evalúa si el primero es verdadero.

  3. Condicional general y comparadores. Agregar un if arbitrario {if c t f} (que ramifica según un booleano) y los comparadores numéricos <, ⇐, =, >, >=.

  4. Identificadores libres. Escribir una función free-ids :: Expr → (Listof Symbol) que retorne el conjunto de identificadores con ocurrencias libres en una expresión. Cuidado con el caso with: debe remover de las ocurrencias libres del cuerpo el identificador que ese with introduce.

  5. with (bindings múltiples).* Diseñar la expresión {with* {[x e1] [y e2] …​} body}, donde cada binding puede usar los anteriores (como let* de Racket). Basta con extender el parser para "desazucararla" a with anidados.

  6. subst vs. ambientes. Tomar el intérprete por sustitución explícita y el de ambientes, y para el programa {with {x {+ 5 5}} 42} (que no usa x) argumentar cuántas veces cada versión recorre el subárbol del cuerpo. ¿Qué ocurre con {with {x 1} {with {y 2} {with {z 3} {+ {+ x y} z}}}}?

  7. Índices de De Bruijn (distancia léxica). Diseñar un lenguaje intermedio en el que los identificadores se reemplazan por índices que indican cuántos with hacia afuera hay que mirar para encontrar el binding (0 = el más cercano). Por ejemplo, {with {x 5} {with {y 6} {+ y x}}} se transforma en {with 5 {with 6 {+ 0 1}}}. Implementar la función unname que hace esta transformación; nótese que el resultado no depende de los nombres de los identificadores.