Unidad 3: Funciones

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.

La abstracción de comportamiento mediante funciones (o métodos, procedimientos, subrutinas) es el mecanismo que, en casi todos los lenguajes, permite mejorar la modularidad y reutilización del código. En esta unidad extendemos el lenguaje de expresiones aritméticas con identificadores locales (WAE, ver Unidad 2) para dotarlo de funciones, y descubrimos por qué esa extensión —aparentemente inocente— reabre una pregunta central de todo el curso: ¿cómo obtiene su valor un identificador? Esa pregunta es la del alcance (scope), y su respuesta correcta nos obligará a inventar una estructura nueva: la clausura.

Seguiremos dos etapas, tal como aparecen en el libro de PLAI y en los apuntes de Tanter:

  • Funciones de primer orden (F1WAE): las funciones se definen aparte, tienen nombre obligatorio y se invocan por nombre. No son valores.

  • Funciones de primera clase (FAE): las funciones son valores; pueden ser anónimas, pasarse como argumento, retornarse y almacenarse en estructuras.

En todo momento perseguimos un mismo objetivo de diseño, que enunciamos desde ya porque será nuestra brújula:

El buen default que queremos preservar a lo largo de todo el curso es la combinación de:

  1. Alcance estático (léxico).

  2. Evaluación temprana (eager).

  3. Sustitución diferida (mediante ambientes).

Cada nueva característica que agreguemos (funciones de primera clase, recursión, mutación) deberá ser compatible con estas tres decisiones. Cuando choque con ellas, tendremos que introducir un mecanismo nuevo. La primera vez que ocurre es en esta unidad, con las clausuras.

Todo el código usa #lang play y encabeza los archivos con (print-only-errors #t) para que los test que pasan no impriman ruido.

Funciones de primer orden

Queremos ejecutar programas como {+ 1 {double 2}}, donde double es una función definida en otro lugar. Conceptualmente la situación es la misma que en DrRacket: hay una ventana de definiciones (a la izquierda) y una expresión a evaluar en el REPL (a la derecha). En nuestro modelo, la lista de definiciones de funciones cumple el rol de la ventana de definiciones, y el programa a interpretar cumple el del REPL.

Las funciones de primer orden tienen restricciones deliberadas:

  • No son valores: no pueden pasarse como argumento, retornarse ni guardarse en estructuras.

  • No pueden ser anónimas: se definen en una porción designada del código, donde reciben un nombre.

  • Existen "antes" de que el programa se ejecute.

Sintaxis: definiciones y aplicación

Una definición de función queda determinada por su nombre, el nombre de su único parámetro y su cuerpo, que es un AST cualquiera (pero que no puede contener otras definiciones de función). Al igual que en Racket, asumimos que toda expresión que comienza con un identificador es una aplicación.

<fundef> ::= (fundef <sym> <sym> <expr>)

<s-expr> ::= <num>
           | {+ <s-expr> <s-expr>}
           | {- <s-expr> <s-expr>}
           | {if0 <s-expr> <s-expr> <s-expr>}
           | {with {<sym> <s-expr>} <s-expr>}
           | <sym>
           | {<sym> <s-expr>}          ;; aplicación de función (por nombre)
(deftype FunDef
  (fundef name arg body))

(deftype Expr
  (num n)
  (add l r)
  (sub l r)
  (if0 c t f)
  (with x named-expr body)
  (id x)
  (app f-name f-arg))    ;; f-name es un símbolo: la aplicación es por nombre

El parser sigue la gramática concreta. Note que el caso de aplicación va al final, porque es el patrón más general (cualquier lista de dos elementos que no haya calzado antes):

(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))]
    [(list f-name f-arg) (app f-name (parse f-arg))]))

Buscar una definición: lookup

Para aplicar una función necesitamos recuperar su definición a partir del nombre. La búsqueda es secuencial sobre la lista de FunDef:

;; lookup :: symbol Listof(FunDef) -> FunDef
(define (lookup f-name defs)
  (match defs
    ['() (error 'lookup "Function ~a not found" f-name)]
    [(cons (fundef h-name h-arg h-body) t)
     (if (symbol=? f-name h-name)
         (fundef h-name h-arg h-body)
         (lookup f-name t))]))
Como la búsqueda avanza de izquierda a derecha y retorna la primera coincidencia, si una función está definida varias veces, prevalece la definición más a la izquierda de la lista.

Semántica de la aplicación mediante sustitución

En este primer intérprete interpretamos with y la aplicación de funciones usando sustitución explícita (la función subst de la Unidad 2). Solo hay que agregar el caso de la aplicación a subst: sustituir dentro de una aplicación simplemente propaga la sustitución hacia la expresión del argumento (el nombre de la función no es un identificador ligable).

(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 (id x))]
    [(with x e b)
     (if (symbol=? x what)
         (with x (subst e what for) b)               ;; with anidado: el cuerpo ya está ligado
         (with x (subst e what for) (subst b what for)))]
    [(app f-name f-arg) (app f-name (subst f-arg what for))]))

Aplicar una función f a un argumento significa, en cuatro pasos:

  1. Buscar la definición de f en la lista (lookup), obteniendo el nombre de su parámetro y su cuerpo.

  2. Interpretar la expresión del argumento para obtener su valor (esto es evaluación temprana).

  3. Sustituir en el cuerpo las ocurrencias libres del parámetro por ese valor (reinstalado como nodo num).

  4. Interpretar el cuerpo ya sustituido.

;; interp :: Expr Listof(FunDef) -> number
(define (interp expr f-list)
  (match expr
    [(num n) n]
    [(add l r) (+ (interp l f-list) (interp r f-list))]
    [(sub l r) (- (interp l f-list) (interp r f-list))]
    [(if0 c t f) (if (zero? (interp c f-list)) (interp t f-list) (interp f f-list))]
    [(with x named-expr body)
     (interp (subst body x (num (interp named-expr f-list))) f-list)]
    [(id x) (error 'interp "Open expression (free occurrence of ~a)" x)]
    [(app f-name f-arg)
     (def (fundef _ the-arg the-body) (lookup f-name f-list))
     (interp (subst the-body the-arg (num (interp f-arg f-list))) f-list)]))

(define (run expr f-list)
  (interp (parse expr) f-list))

Si el intérprete se encuentra con un (id x), es un error: significa que x nunca fue sustituido, es decir, era un identificador libre (una expresión abierta). Los resultados dependen de las definiciones disponibles:

(test (run '{+ 1 {double 2}}
           (list (fundef 'double 'n (parse '{+ n n}))))
      5)

(test (run '{+ 1 {double 2}}
           (list (fundef 'double 'n (parse '{+ n 1}))))
      4)

(test (run '{with {x 1} {double x}}
           (list (fundef 'double 'n (parse '{+ n n}))))
      2)

La recursión sale "gratis"

Como toda función puede invocar a cualquier otra por su nombre —incluida ella misma, y sin importar el orden en que aparezcan en la lista—, la recursión no requiere maquinaria adicional. Realicemos la función my-S que suma los primeros n naturales, definida por my-S(0) = 0 y my-S(n+1) = (n+1) + my-S(n):

(test (run '{my-S 3}
           (list (fundef 'my-S 'n
                         (parse '{if0 n 0 {+ n {my-S {- n 1}}}}))))
      6)

Funciona porque lookup encuentra a my-S en la lista cada vez que se la invoca, y la sustitución reemplaza n por el argumento concreto antes de continuar. Veremos en la Unidad 5 que, en cambio, la recursión no es gratis cuando pasamos a funciones de primera clase con ambientes: allí hará falta un ambiente cíclico.

Esta "gratuidad" es engañosa: es consecuencia directa de que las funciones no son valores y viven en un repositorio global preexistente. El precio es la falta de expresividad: sin funciones como valores no hay funciones de orden superior (map, filter, fold).

Sustitución diferida: ambientes

La sustitución explícita es correcta pero ineficiente. Cada sustitución recorre el árbol completo en profundidad, y para reducir una cascada de with anidados se realizan muchas sustituciones sucesivas: en el peor caso el costo es cuadrático en la profundidad del árbol. Peor aún, podríamos recorrer todo el árbol en vano si el identificador nunca se usa.

;; Para reducir esto, la sustitución explícita camina el árbol una y otra vez:
{with {x 3} {with {y 4} {with {z 5} {+ x {+ y z}}}}}

La idea de la sustitución diferida es posponer las sustituciones en lugar de realizarlas apenas se encuentra un with o una aplicación. Para ello mantenemos un repositorio de sustituciones pendientes que llamamos ambiente (environment, abreviado env):

  • Comenzamos con un ambiente vacío.

  • Cuando correspondería sustituir, en vez de hacerlo agregamos una entrada al ambiente que asocia el identificador con su valor, y seguimos evaluando.

  • Al encontrar un identificador, ese es el momento de "cobrar" la sustitución: buscamos su valor en el ambiente.

Así, (id x) deja de ser un error automático: solo es error si la búsqueda en el ambiente falla (porque entonces sí era un identificador libre).

El TDA Ambiente

El ambiente es una estructura tipo lista enlazada, muy parecida a la lista de Racket pero con constructores propios. Su interfaz tiene tres operaciones: crear el ambiente vacío, extenderlo con una asociación y buscar en él. No hay mutación: extender construye un ambiente nuevo.

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

(define empty-env (mtEnv))
(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))]))
Distinga las dos búsquedas. lookup opera sobre la lista de FunDef (funciones de primer orden por nombre); env-lookup opera sobre el Env (valores de identificadores). Son mecanismos separados y coexisten en el intérprete de primer orden con ambientes.

El intérprete con ambientes

El contrato del intérprete gana un parámetro: el ambiente. En los casos que no ligan identificadores el ambiente simplemente se propaga. Los casos interesantes son with, id y app:

;; interp :: Expr Listof(FunDef) Env -> number
(define (interp expr f-list env)
  (match expr
    [(num n) n]
    [(add l r) (+ (interp l f-list env) (interp r f-list env))]
    [(sub l r) (- (interp l f-list env) (interp r f-list env))]
    [(if0 c t f) (if (zero? (interp c f-list env)) (interp t f-list env) (interp f f-list env))]

    [(with x named-expr body)
     ;; en vez de sustituir, extendemos el ambiente ACTUAL con x -> valor
     (def new-env (extend-env x (interp named-expr f-list env) env))
     (interp body f-list new-env)]

    [(id x)
     ;; ya no es error automático: cobramos la sustitución pendiente
     (env-lookup x env)]

    [(app f-name f-arg)
     (def (fundef _ the-arg the-body) (lookup f-name f-list))
     ;; extendemos el ambiente VACÍO con arg -> valor  (esto da alcance estático)
     (def new-env (extend-env the-arg (interp f-arg f-list env) empty-env))
     (interp the-body f-list new-env)]))

(define (run expr f-list)
  (interp (parse expr) f-list empty-env))

Este intérprete con sustitución diferida produce exactamente los mismos resultados que el de sustitución explícita; solo cambia (y mejora) el costo. La diferencia crucial, que analizamos a fondo en la próxima sección, está en qué ambiente extiende la aplicación de función: with extiende el ambiente actual, pero app extiende el ambiente vacío.

Índices de de Bruijn (nota lateral, suele aparecer en controles). Una alternativa para eliminar por completo los nombres es reemplazar cada identificador por su distancia léxica: un número que indica cuántos with hacia afuera hay que "saltar" para encontrar su definición (el 0 es siempre la definición más reciente). Una función unname transforma el AST con nombres en un AST intermedio con índices, que luego es más simple de interpretar. Es la técnica que usan los compiladores reales; en el curso interesa sobre todo la construcción correcta de los índices.

Régimen de evaluación: eager vs lazy

Ortogonal al alcance existe otra decisión: cuándo se evalúa la expresión que se va a asociar a un identificador. Al interpretar {with {x e} b} (o una aplicación) tenemos dos opciones:

  • Evaluación temprana (eager): interpretar e primero y asociar su valor. Es lo que hace nuestro código ((interp named-expr …​)).

  • Evaluación perezosa (lazy): posponer y asociar la expresión e sin evaluar, forzándola solo si se necesita.

En nuestro lenguaje ambas estrategias producen el mismo resultado final, pero no la misma cantidad de cómputo. Considere:

{with {x {+ 5 5}} {+ x x}}    ;; eager calcula {+ 5 5} una vez; lazy lo calcula dos veces
{with {x {+ 5 5}} 3}          ;; eager lo calcula una vez; lazy, cero veces (x no se usa)

Ninguna estrategia es siempre mejor: como resume el profesor, "el flojo a veces trabaja el doble, y a veces no trabaja y gana porque no tenía que hacerlo". Retomaremos la evaluación perezosa en detalle en la Unidad 4.

Una pregunta típica de control muestra el código de un intérprete y pide identificar su régimen de evaluación. La pista está en el nodo with/app: si asocia (interp e …​) es eager; si asocia la expresión e cruda, es lazy.

Alcance estático vs. dinámico

El alcance de una asociación identificador–valor responde a: ¿en qué partes del programa está vigente esa asociación? O, de forma dual: dado un identificador, ¿a qué valor está ligado, si es que lo está? El problema aparece cuando una función hace referencia a un identificador que no es su parámetro. Considere:

;; ¿A qué valor reduce este programa?
{with {n 5} {f 10}}          ;; con def: f toma x y su cuerpo es simplemente  n

La función f menciona n, que no es su parámetro x. Hay dos respuestas posibles:

  • Error: n es un identificador libre respecto del cuerpo de f. Esto es alcance estático (léxico).

  • 5: la asociación n = 5, vigente en el momento de la llamada, alcanza al cuerpo de f. Esto es alcance dinámico.

En nuestro intérprete la elección se reduce a qué ambiente extiende la aplicación:

;; Alcance ESTÁTICO: extender el ambiente vacío en la aplicación
(def new-env (extend-env the-arg (interp f-arg f-list env) empty-env))

;; Alcance DINÁMICO: extender el ambiente actual en la aplicación
(def new-env (extend-env the-arg (interp f-arg f-list env) env))

Un mismo programa distingue ambas semánticas: sirve como test discriminante.

;; Con la versión estática (extiende empty-env):
(test/exn (run '{with {n 5} {f 10}} (list (fundef 'f 'x (parse 'n))))
          "free identifier")

;; Con la versión dinámica (extiende env), el mismo programa daría:
;; (test (run '{with {n 5} {f 10}} (list (fundef 'f 'x (parse 'n)))) 5)

Un cambio de menos de una línea altera la semántica del lenguaje. Extender empty-env versus env en la aplicación es la única diferencia entre alcance estático y dinámico. En el primer caso "olvidamos" todas las asociaciones pendientes del flujo de ejecución y consideramos únicamente el parámetro; en el segundo, las arrastramos. Este es uno de los puntos más importantes del curso.

Reglas de alcance, contrastadas

Alcance estático (léxico) Alcance dinámico

  • Se basa en la estructura del código tal como está escrito.

  • El alcance se determina al escribir el código; no hay que ejecutarlo.

  • Es predecible: basta leer el texto fuente.

  • El default adecuado de los lenguajes modernos (C, Scheme, Haskell, Python, Java…).

  • Mejor soporte de herramientas y escalabilidad.

  • Se basa en el historial de llamadas durante la ejecución.

  • El alcance se determina en tiempo de ejecución, según la pila de llamadas.

  • Es difícil de predecir: produce bugs extraños que a veces aparecen y a veces no.

  • Útil como característica opcional y explícita, no como default.

  • Permite pasar parámetros arbitrarios sin cambiar las firmas de las funciones.

La razón técnica del alcance estático es que la vigencia de un with está delimitada sintácticamente: {with {n 5} {f 10}} liga n solo dentro del texto {f 10}, y como ese texto no menciona n literalmente, la asociación no tiene efecto sobre el cuerpo de f. Al extender el ambiente vacío estamos diciendo: "para esta aplicación, olvidemos las sustituciones pendientes; en el cuerpo de la función solo consideremos su parámetro".

Alcance dinámico en la práctica

Aunque lo rechazamos como default, el alcance dinámico existe en lenguajes muy usados. El profesor lo demuestra con dos ejemplos reales:

  • Bash: una variable global y referenciada por una función showy toma el valor de la redefinición local vigente en el punto de llamada, no el del punto de definición.

  • TeX/LaTeX: exactamente el mismo comportamiento; la salida del documento depende del orden de ejecución.

En ambos, imprimir el "mismo" valor da resultados distintos según el contexto de invocación —el síntoma clásico del alcance dinámico—. Krishnamurthi es tajante al respecto:

[…] dynamic scope is entirely unreasonable. The problem is that we simply cannot determine what the value of a program will be without knowing everything about its execution history […] We will therefore regard dynamic scope as an error and reject its use.

— Shriram Krishnamurthi
PLAI

La postura del curso, matizando a partir de la nota A Note on Dynamic Scope de Éric Tanter, es que el alcance dinámico no es un error en sí mismo, sino un mal default: resulta útil de forma opt-in (como en Common Lisp, Scala o Racket) para configuración (p. ej. redirigir un STDOUT a nivel de sistema) o adaptación al contexto (comportarse distinto en escritorio vs. móvil). La clave es que esa dependencia del contexto sea explícita e intencionada.

Racket ofrece precisamente eso con los parámetros: un mecanismo de alcance dinámico controlado y explícito.

(define y (make-parameter 0))
(define (showy)  (display "y is equal to: ") (display (y)))
(define (showy2)
  (parameterize ([y 1])   ;; redefine y solo dentro de este cuerpo
    (showy)))             ;; imprime 1, no 0

Con un let común (alcance léxico) la redefinición no afectaría a showy. Para lograr el efecto dinámico hay que diseñarlo de antemano con make-parameter y usar parameterize explícitamente en el punto de la sobreescritura.

Funciones de primera clase

Damos ahora el salto expresivo: las funciones son valores, con todos los derechos de cualquier otro valor. Pueden definirse anónimamente, almacenarse en estructuras, retornarse y pasarse como argumentos. Esto es lo que habilita los patrones de orden superior. Un ejemplo que aplica dos veces una función:

;; {{ {fun {f} {fun {z} {f {f z}}}}   {fun {x} {+ x 1}} } 10}   ==>  12
;;      apply-twice                        add1

Pasamos del lenguaje WAE al lenguaje FAE (First-class functions + Arithmetic Expressions). En FAE, una función puede aparecer en cualquier posición donde quepa un valor: en la posición de función de una aplicación, como expresión nombrada de un with, como cuerpo de otra función, como argumento efectivo, etc.

with como azúcar sintáctico

Con funciones de primera clase, las definiciones locales dejan de ser primitivas: son azúcar sintáctico. Toda expresión

{with {x e} b}   ≡   {{fun {x} b} e}

puede reescribirse como la aplicación inmediata de una función anónima. Por eso eliminamos with de la sintaxis abstracta y lo aceptamos solo en la concreta, dejando que el parser haga la traducción. El núcleo del lenguaje se vuelve más pequeño: ya no hay que dar semántica separada a with y a la aplicación; basta con la aplicación.

Sintaxis abstracta y parser

Cambio clave respecto de primer orden: el nodo app ya no lleva un símbolo en posición de función, sino una expresión arbitraria que debe reducir a una función aplicable (podría ser anónima, así que no podemos exigir un nombre).

<expr> ::= (num <num>) | (id <sym>)
         | (add <expr> <expr>) | (sub <expr> <expr>)
         | (if0 <expr> <expr> <expr>)
         | (fun <sym> <expr>)          ;; función anónima de un argumento
         | (app <expr> <expr>)         ;; en F1WAE era (app <sym> <expr>)
(deftype Expr
  (num n) (add l r) (sub l r) (if0 c t f)
  (id x)
  (fun arg body)
  (app f arg))

(define (parse s-expr)
  (match s-expr
    [(? number? n) (num n)]
    [(? 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) e) b)     ;; azúcar: {with {x e} b} -> {{fun {x} b} e}
     (app (fun x (parse b)) (parse e))]
    [(list 'fun (list (? symbol? x)) b)
     (fun x (parse b))]
    [(list f a) (app (parse f) (parse a))]))

¿Qué son ahora los valores?

Antes, todo programa reducía a un número. Ahora una expresión puede reducir a un número o a una función. Por ejemplo, {with {y 3} {fun {x} {+ x y}}} reduce a algo parecido a la función {fun {x} {+ x 3}}. Como veremos, ese "algo parecido a una función" es más rico que una función pelada: es una clausura. Pero lleguemos ahí por descubrimiento, examinando qué falla si somos ingenuos.

Dos intentos ingenuos que fallan

Primera idea: interpretar una función es retornarse a sí misma (no reducimos su cuerpo, porque eso solo tiene sentido al aplicarla), y al aplicar extendemos algún ambiente. Usaremos el siguiente programa como piedra de toque, cuyo valor correcto —comprobable en Racket— es 12:

(define p '{with {x 3}
                 {with {f {fun {y} {+ x y}}}
                       {with {x 5}
                             {+ x {f 4}}}}})   ;; debiera dar 12

;; Referencia en Racket (alcance estático):
(test (let ([x 3])
        (let ([f (lambda (y) (+ x y))])
          (let ([x 5])
            (+ x (f 4)))))
      12)

El resultado correcto es 12 porque f captura el x = 3 vigente donde se define: f(4) = 4 + 3 = 7, y el cuerpo suma el x = 5 externo: 5 + 7 = 12.

Intento A — extender el ambiente vacío. La función se retorna a sí misma y app extiende (mtEnv):

(define (interp-mtEnv expr env)
  (match expr
    [(num n) n]
    [(id x) (env-lookup x env)]
    [(add l r) (+ (interp-mtEnv l env) (interp-mtEnv r env))]
    [(sub l r) (- (interp-mtEnv l env) (interp-mtEnv r env))]
    [(if0 c t f) (if (zero? (interp-mtEnv c env)) (interp-mtEnv t env) (interp-mtEnv f env))]
    [(fun id body) (fun id body)]                          ;; se retorna a sí misma
    [(app f arg-expr)
     (def (fun arg-name body) (interp-mtEnv f env))
     (interp-mtEnv body (extend-env arg-name (interp-mtEnv arg-expr env) (mtEnv)))]))

(test/exn (interp-mtEnv (parse p) (mtEnv)) "free identifier")

Falla con identificador libre. Como cada aplicación (y recuerde que cada with es una aplicación) parte del ambiente vacío, al llegar a evaluar el cuerpo de f el ambiente solo contiene el parámetro y: la referencia a x no se encuentra. Se perdió el alcance estático; peor, el programa ni siquiera corre.

Intento B — extender el ambiente actual. Idéntico al anterior salvo que app extiende env:

[(app f arg-expr)
 (def (fun arg-name body) (interp-envActual f env))
 (interp-envActual body (extend-env arg-name (interp-envActual arg-expr env) env))]  ;; env, no mtEnv

(test (interp-envActual (parse p) (mtEnv)) 14)   ;; ¡alcance dinámico!

Ahora sí corre, pero da 14 en vez de 12. Al aplicar f, el ambiente actual ya tiene x = 5 (la redefinición más reciente), de modo que f(4) = 4 + 5 = 9 y el cuerpo da 5 + 9 = 14. Obtuvimos alcance dinámico por defecto, justamente lo que no queremos.

Con sustitución explícita este problema no existiría: al interpretar {with {x 3} …} sustituiríamos x por 3 de inmediato y quedaría "grabado". Pero queremos conservar la sustitución diferida (por eficiencia), el alcance estático y las funciones de primera clase a la vez. Ni empty-env ni env lo logran. Falta un mecanismo nuevo.

Clausuras

La observación central es que el alcance estático liga cada identificador con la ocurrencia ligadora más cercana en el texto del programa fuente. Para respetarlo con sustitución diferida, cada función debe recordar las sustituciones pendientes vigentes al momento de su definición. En el programa p, cuando se define f, el ambiente es {x → 3}; f debe acordarse de que x estaba pendiente de sustituir por 3, y no por "lo que sea que haya en el ambiente al aplicar".

La estructura que empaqueta una función junto con el ambiente de su punto de definición se llama clausura (closure):

clausura = definición de la función (parámetro + cuerpo) + ambiente en el lugar de definición

La clausura pasa a ser un tipo de valor más, junto a los números. Y como los números ahora vienen envueltos en un constructor, agregamos auxiliares para operarlos:

(deftype Value
  (numV n)
  (closureV arg body env))     ;; función + ambiente capturado

(define (num+ n1 n2)
  (def (numV v1) n1) (def (numV v2) n2) (numV (+ v1 v2)))
(define (num- n1 n2)
  (def (numV v1) n1) (def (numV v2) n2) (numV (- v1 v2)))
(define (num-zero? n)
  (def (numV v) n) (zero? v))

El intérprete correcto difiere de los intentos ingenuos en solo dos líneas, resaltadas abajo: interpretar fun captura el ambiente actual creando una clausura, y app extiende el ambiente clausurado (ni el vacío ni el actual):

;; interp :: Expr Env -> Value
(define (interp expr env)
  (match expr
    [(num n) (numV n)]
    [(id x) (env-lookup x env)]
    [(add l r) (num+ (interp l env) (interp r env))]
    [(sub l r) (num- (interp l env) (interp r env))]
    [(if0 c t f) (if (num-zero? (interp c env)) (interp t env) (interp f env))]

    [(fun id body) (closureV id body env)]            ;; <-- captura el ambiente de definición

    [(app f arg-expr)
     (def (closureV arg-name body closed-env) (interp f env))
     (interp body (extend-env arg-name (interp arg-expr env) closed-env))]))  ;; <-- extiende el capturado

(define (run p)
  (match (interp (parse p) (mtEnv))
    [(numV n) n]
    [x x]))

Con esto, el programa p reduce correctamente a 12:

(test (interp (parse p) (mtEnv)) (numV 12))

Un segundo programa discriminante, más directo, deja ver el punto: f cierra sobre n en su definición.

(define p-scope '{with {n 5}
                       {with {f {fun {x} {+ x n}}}
                             {with {n 3}
                                   {f 1}}}})

(test (run p-scope) 6)     ;; estático: f recuerda n=5, entonces f(1)=1+5=6
;; (test (run p-scope) 4)  ;; dinámico habría usado n=3 del punto de llamada: 1+3=4

La captura es de una vez y para siempre. Cuando una función referencia un identificador externo, la clausura encierra la definición vigente en ese instante; redefiniciones posteriores del mismo nombre no la afectan. Es exactamente el comportamiento de las clausuras de JavaScript, Racket, Python o cualquier lenguaje con funciones de primera clase y alcance estático:

let x = 10;
let f = (y) => x + y;   // captura x = 10
let x2 = 100;           // no afecta a f
f(1);                   // 11, no 101

El nodo app concentra las decisiones semánticas

Vale la pena subrayar cuánto poder tiene un solo nodo del AST. En la aplicación de función conviven las dos grandes decisiones de diseño del lenguaje:

  • Qué ambiente se extiende fija el alcance: closed-env da estático; env daría dinámico; empty-env rompe el lenguaje.

  • Con qué se extiende fija el régimen de evaluación: (interp arg-expr env) da eager; almacenar la expresión cruda daría lazy (tema de la Unidad 4).

Además, como with es azúcar que se traduce a una aplicación, estas semánticas se heredan automáticamente para with: ya no son piezas separadas que podríamos configurar de forma inconsistente.

Repaso para el Control 1

Conviene ver el recorrido completo como una progresión de lenguajes, cada uno agregando una característica y, con ella, un concepto:

Lenguaje Agrega Concepto clave

AE

Expresiones aritméticas

deftype + match

WAE

Identificadores locales (with)

Sustitución; alcance léxico; eager vs lazy

F1WAE

Funciones de primer orden (por nombre)

FunDef, lookup; recursión gratis; sustitución diferida (ambientes)

FAE

Funciones de primera clase

closureV; alcance estático con captura

Taxonomía: primer orden vs. primera clase

Funciones de primer orden Funciones de primera clase

  • No son valores.

  • No pueden ser anónimas.

  • Se definen en una sección designada, antes de ejecutar.

  • Se aplican por su nombre.

  • No permiten patrones de orden superior.

  • Sí son valores.

  • Pueden ser anónimas.

  • Se definen durante la ejecución del programa.

  • Se aplican reduciendo una expresión a una función.

  • Habilitan orden superior (map, filter, fold).

Existe un punto intermedio ilustrativo: los punteros a función de C. Permiten pasar y retornar funciones (int (f)(int)), pero solo funciones *ya existentes: no se pueden crear funciones nuevas durante la ejecución. Son, por tanto, un poco más que primer orden pero sin llegar a primera clase.

Preguntas y errores frecuentes

  • Identificar el régimen de evaluación a partir del código del intérprete: mire si el nodo with/app asocia el valor interpretado (eager) o la expresión cruda (lazy).

  • Escribir un programa discriminante que distinga alcance estático de dinámico: debe contener una función que referencie un identificador externo que sea redefinido entre la definición y la aplicación (como p, p-scope o {with {n 5} {f 10}}).

  • Enumerar diferencias entre alcance estático y dinámico (ver tabla comparativa).

  • Confundir lookup con env-lookup: el primero busca definiciones de primer orden; el segundo, valores de identificadores en el ambiente.

  • Olvidar que with es azúcar en FAE: no tiene nodo propio en el AST; su alcance y su régimen de evaluación los hereda de la aplicación.

  • Recordar que el alcance es ortogonal al régimen de evaluación: se pueden combinar libremente; el buen default es estático + eager + diferida.

Ejercicios propuestos

  1. Dado el intérprete de primer orden con ambientes, escriba un programa FAE (usando with y una función) cuyo resultado sea distinto bajo alcance estático y bajo alcance dinámico, e indique ambos valores.

  2. Implemente el caso app del intérprete con clausuras y verifique con test que el programa p reduce a (numV 12). Luego modifique una sola subexpresión para obtener alcance dinámico y prediga el nuevo resultado antes de ejecutarlo.

  3. A partir del intérprete con clausuras, reemplace closed-env por empty-env en la aplicación y explique, con un ejemplo mínimo, por qué el lenguaje deja de ser utilizable (no solo cambia de alcance).

  4. Agregue un nodo de multiplicación (mul) al lenguaje FAE: extienda deftype Expr, el parser y el intérprete (defina num* análoga a num+). Incluya al menos dos test.

  5. Implemente la currificación: represente una función de dos argumentos {fun {x} {fun {y} …​}} y verifique con un test que {{sumar 3} 4} da 7, siendo sumar una función de primera clase.

  6. Escriba la función libres :: Expr → Listof(Symbol) que calcule el conjunto de identificadores libres de una expresión FAE. Recuerde que fun liga su parámetro en el cuerpo.

  7. Modifique el intérprete de primer orden para que, ante una función definida varias veces en la lista de FunDef, prevalezca la definición más a la derecha en lugar de la más a la izquierda. Muestre el test que evidencia el cambio.

  8. (Avanzado) Realice la función unname :: Expr → IExpr que traduzca un with/id con nombres a un AST con índices de de Bruijn (distancia léxica), y su intérprete interp-i :: IExpr → number. Verifique que produce los mismos resultados que el intérprete con nombres sobre tres programas con with anidados.