Unidad 4: Estrategias de evaluación

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.

Hasta ahora nuestros intérpretes han evaluado los argumentos de una función antes de aplicarla. Esa es una decisión de diseño, no una obligación: existe toda una familia de estrategias de evaluación que difieren en un único punto, ¿cuándo se evalúa el argumento de una aplicación de función? En esta unidad estudiamos esa pregunta desde tres ángulos complementarios. Primero fijamos la intuición con el lenguaje Haskell, que lleva la evaluación perezosa a su extremo (es perezoso por defecto, para todo el lenguaje) y que gracias a ello admite estructuras de datos infinitas. Luego volvemos a nuestro intérprete en Racket y implementamos la evaluación perezosa sobre el intérprete con alcance estático, sustitución diferida y funciones de primera clase. Finalmente distinguimos las dos variantes de la evaluación perezosa: call-by-name y call-by-need.

Regímenes de evaluación

Las estrategias (o regímenes) de evaluación determinan cuándo se evalúa el argumento de una invocación a función. Como el with es azúcar sintáctico para la aplicación de una función anónima, la misma pregunta aplica a la expresión nombrada de un with.

Consideramos dos estrategias fundamentales:

  • Evaluación temprana (eager, strict): el argumento formal se liga al valor del argumento actual. Es decir, los argumentos se evalúan antes de entrar a evaluar el cuerpo de la función. Es el default en la mayoría de los lenguajes: Racket, Python, Java, C, Scheme.

  • Evaluación perezosa (lazy, non-strict): los argumentos se evalúan sólo si son requeridos durante la evaluación del cuerpo de la función. Si un argumento nunca se usa, nunca se evalúa. Es el default en Haskell.

El discriminador: un experimento para distinguirlas

Dado un lenguaje cualquiera, podemos construir un pequeño programa que revela qué estrategia usa. Es un patrón que conviene memorizar, porque es una pregunta recurrente en controles y exámenes (análogo al experimento que distingue alcance estático de dinámico). La receta tiene tres pasos:

  1. Encontrar una expresión que siempre arroje un error.

  2. Definir una función que reciba un argumento pero no lo use.

  3. Aplicar esa función usando como argumento la expresión que da error.

Si el programa arroja el error, el lenguaje evaluó el argumento antes de aplicar: es temprano. Si el programa retorna normalmente, el argumento nunca se evaluó: es perezoso.

En Racket, (/ 1 0) (o (first empty)) es una expresión que siempre falla:

(define (f x) 0)
(f (/ 1 0))

  • Con evaluación temprana (Racket real): error, se evalúa (/ 1 0) antes de invocar f.

  • Con evaluación perezosa: retorna 0, el argumento nunca se necesita.

La intuición clave: bajo evaluación temprana el argumento se evalúa aunque no se use, lo que en este caso es trabajo innecesario que además propaga un error. Bajo evaluación perezosa la evaluación se posterga "hasta el último minuto", y puede que nunca ocurra. El mismo programa fuente puede terminar con un valor o fallar dependiendo únicamente de la estrategia de evaluación del lenguaje.

Haskell: la evaluación perezosa llevada al límite

Racket es eager por defecto y no nos deja usar evaluación perezosa de forma transparente para todo el lenguaje. Para ver hasta dónde llega la idea usamos Haskell, un lenguaje funcional puro cuyo eslogan lo describe como "an advanced, purely functional programming language". Sus características centrales son:

  • Estáticamente tipeado: todos los tipos se determinan en tiempo de compilación y se verifican; nunca se compila un programa mal tipeado.

  • Inferencia de tipos: no es necesario anotar todos los tipos; el compilador los infiere. Las anotaciones son voluntarias y, cuando están, toman precedencia sobre el inferidor.

  • Puramente funcional: cada función es una función en el sentido matemático (misma entrada, misma salida). Los efectos (entrada/salida) se expresan en el sistema de tipos.

  • Perezoso por defecto: las funciones no evalúan sus argumentos hasta que se necesitan. En Haskell la evaluación temprana simplemente no existe.

El lenguaje debe su nombre a Haskell Curry (1900–1982), lógico y matemático célebre por la lógica combinatoria, la correspondencia de Curry–Howard (los tipos son proposiciones y los programas, demostraciones) y la currificación.

Table 1. Comparación entre Racket y Haskell
Aspecto Racket Haskell

Estrategia de evaluación

Temprana (eager)

Perezosa (lazy)

Sistema de tipos

Dinámico

Estático, con inferencia

Currificación

Manual

Automática

Sintaxis

Prefija, paréntesis

Infija, "más natural"

Listas

Heterogéneas

Homogéneas

Estructuras infinitas

Requieren streams

Nativas
Se trabaja con el compilador GHC y su modo interactivo GHCI. En GHCI, :t <expr> muestra el tipo inferido de una expresión y :load Archivo.hs compila un archivo .hs y deja sus definiciones disponibles. Las anotaciones de tipo usan :: ("tiene tipo").

Tipos primitivos, sintaxis y funciones

Haskell tiene una sintaxis infija tradicional que respeta la precedencia de operadores. Los tipos primitivos incluyen enteros, booleanos, caracteres (comillas simples) y strings (comillas dobles):

ghci> :t 3
3 :: Num a => a          -- un número, sin comprometerse aún a Int o Double
ghci> :t True
True :: Bool
ghci> :t 'c'
'c' :: Char
ghci> :t "hola"
"hola" :: String

Las funciones se definen con una firma de tipo (la flecha → separa argumento de retorno) y una implementación. Una forma muy usada de definir funciones por casos son las guardas (|), que se comportan como un cond: se evalúan de arriba hacia abajo y gana la primera condición verdadera. La palabra clave otherwise es el caso por defecto:

scoreToLetter :: Int -> Char
scoreToLetter n
  | n > 90    = 'A'
  | n > 80    = 'B'
  | n > 70    = 'C'
  | otherwise = 'F'
ghci> scoreToLetter 91
'A'
ghci> scoreToLetter 40
'F'

Listas homogéneas y pattern matching por ecuaciones

Al igual que en Racket, la estructura secuencial por excelencia es la lista, con lista vacía [] y constructor : (cons). La diferencia es que las listas de Haskell son homogéneas: todos los elementos deben tener el mismo tipo.

ghci> 1 : 2 : 3 : []
[1,2,3]
ghci> [True, False, True]
[True,False,True]
ghci> [1, 'a']
<error de tipos>            -- 1 y 'a' no tienen el mismo tipo

Un dato importante: en Haskell String es simplemente un alias de [Char], una lista de caracteres. No son tipos distintos.

Además de las guardas, las funciones pueden definirse con pattern matching directamente sobre los argumentos, escribiendo una ecuación por caso, sin necesidad de una expresión match como en Racket. El guion bajo _ ignora partes del patrón que no se usan:

listCopy :: [a] -> [a]
listCopy []     = []
listCopy (x:xs) = x : listCopy xs

myLength :: [a] -> Int
myLength []     = 0
myLength (_:xs) = 1 + myLength xs

Polimorfismo paramétrico

En las firmas anteriores aparece una letra minúscula a: es una variable de tipo. Todas las variables de tipo están cuantificadas universalmente de forma implícita: listCopy :: [a] → [a] se lee "para todo tipo a, toma una lista de a y retorna una lista de `a`". Este mecanismo se llama polimorfismo paramétrico. El tipo de la lista vacía lo ilustra bien:

ghci> :t []
[] :: [a]                   -- lista vacía de cualquier tipo
ghci> :t map
map :: (a -> b) -> [a] -> [b]

A veces una firma tiene restricciones de tipo antes de una flecha doble ⇒, por ejemplo Ord a ⇒ …​ o Num a ⇒ …​. Corresponden a las type classes (las mismas que se ven en Scala): restringen el tipo pero al mismo tiempo indican qué operaciones están disponibles sobre él. No profundizaremos en type classes; para esta unidad basta saber leer las variables de tipo.

Currificación automática

En Haskell todas las funciones están currificadas automáticamente: una función de "dos argumentos" es en realidad una función de un argumento que retorna otra función. La firma lo revela, pues → asocia a la derecha:

add :: Int -> Int -> Int      -- en realidad: Int -> (Int -> Int)
add x y = x + y

add3 :: Int -> Int
add3 = add 3                  -- aplicación parcial: fija el primer argumento
ghci> add3 5
8

La currificación automática combina de forma muy elegante con las funciones de orden superior. Al aplicar map a un solo argumento obtenemos una nueva función que espera la lista:

scoresToLetters :: [Int] -> [Char]
scoresToLetters = map scoreToLetter    -- map aplicado parcialmente
ghci> scoresToLetters [83, 51, 99]
"BFA"                          -- una lista de Char se imprime como String

El discriminador en Haskell

Apliquemos la receta de la sección anterior. La expresión que siempre falla es head [] (tomar el primer elemento de la lista vacía). La función que ignora su argumento es la función anónima \x → 3 (el \ es el lambda de Haskell):

ghci> head []
*** Exception: Prelude.head: empty list
ghci> (\x -> 3) (head [])
3

El resultado es 3, no un error: Haskell no evaluó el argumento head [] porque x nunca se usa. El mismo experimento en Racket falla, porque Racket evalúa el argumento antes de aplicar la función:

((lambda (x) 3) (first empty))   ; error: Racket es eager

Estructuras de datos infinitas

La consecuencia más vistosa de que todas las funciones sean perezosas es que podemos definir estructuras de datos infinitas. El operador : (cons) es perezoso en su segundo argumento: agrega el primer elemento al frente sin forzar la evaluación del resto de la lista. Eso permite definiciones auto-referenciales:

ones :: [Int]
ones = 1 : ones          -- lista infinita de unos

nats :: [Integer]
nats = [0..]             -- rango infinito: 0, 1, 2, 3, ...
Si intentamos imprimir ones o nats completas, el programa no termina nunca: en cada paso se muestra un elemento y luego se necesita el siguiente, indefinidamente. La gracia de una estructura infinita no es consumirla entera, sino poder consumir tantos elementos como necesitemos, sabiendo que siempre habrá más.

Consumo finito: take (y su reimplementación front)

Para consumir un prefijo finito de una lista infinita usamos take n, que retorna los primeros n elementos. Podemos reimplementarla (la llamamos front para no chocar con la de la biblioteca estándar) por casos con pattern matching:

front :: Int -> [a] -> [a]
front _ []     = []                   -- caso 1: lista vacía
front 0 _      = []                   -- caso 2: pedir 0 elementos
front n (x:xs) = x : front (n - 1) xs -- caso 3: caso recursivo
ghci> front 0 ones
[]
ghci> front 4 ones
[1,1,1,1]
ghci> take 10 nats
[0,1,2,3,4,5,6,7,8,9]

¿Por qué front 4 ones termina, si ones es infinita? La combinación de evaluación perezosa (que impide que ones se expanda por completo) y pattern matching (que obliga a desarmar un cons a la vez) hace avanzar la reducción elemento por elemento. Sigamos la reducción paso a paso:

front 4 ones
  = front 4 (1 : ones)             -- pattern matching: se desarma UN cons de ones
  = 1 : front 3 ones               -- caso 3
  = 1 : front 3 (1 : ones)         -- pattern matching
  = 1 : 1 : front 2 ones           -- caso 3
  = 1 : 1 : 1 : front 1 ones       -- caso 3 (+ pattern matching)
  = 1 : 1 : 1 : 1 : front 0 ones   -- caso 3 (+ pattern matching)
  = 1 : 1 : 1 : 1 : front 0 (1 : ones)
  = 1 : 1 : 1 : 1 : []             -- caso 2: pedir 0 elementos
  = [1,1,1,1]

En cada paso el pattern matching (x:xs) evalúa sólo el primer 1 y deja el resto de ones sin evaluar. Al llegar al caso base (front 0 o front _ []) no queda nada pendiente y obtenemos el resultado. Escribir esta secuencia de reescrituras, indicando en cada paso por qué regla ocurre, es lo que se conoce como hacer la reducción de un programa.

Esta misma idea de productor infinito, consumidor finito está en el shell de Unix. El programa yes emite el string y para siempre; un consumidor lo limita:

yes | head -5        # 'yes' produce infinito; 'head' consume un prefijo finito

Los pipes conectan la salida de un comando con la entrada del siguiente, y cada comando consume tanta entrada como necesita y nada más. head/more cumplen el rol de take.

Listas cíclicas: cycle

La función cycle transforma una lista finita en una versión infinita y cíclica de sí misma:

hours   :: [Int]
hours   = cycle [0..23]      -- 0,1,...,23, 0,1,...,23, 0,1,...

minutes :: [Int]
minutes = cycle [0..59]      -- 0,1,...,59, 0,1,...,59, ...

colors  :: [String]
colors  = cycle ["rojo", "verde", "azul"]
ghci> take 27 hours
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,0,1,2]
Es exactamente el truco de la rueda de alarma del iPhone: parece un ciclo infinito de horas y minutos, pero por dentro es una lista finita repetida muchas veces. Con cycle obtenemos el ciclo de verdad y podemos consumir de él tantos elementos como haga falta (una paleta de colores para pintar un gráfico, un patrón que se repite, etc.) sin preocuparnos de que se acabe.

Combinando listas: zip y zipWith

Un patrón muy usado es combinar dos listas posición por posición. La función zip las une en tuplas, y zipWith las combina aplicando una función binaria:

myZip :: [a] -> [b] -> [(a, b)]
myZip []     _      = []          -- si se acaba la primera, terminamos
myZip _      []     = []          -- si se acaba la segunda, terminamos
myZip (a:as) (b:bs) = (a, b) : myZip as bs

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ []     _      = []
zipWith' _ _      []     = []
zipWith' f (a:as) (b:bs) = f a b : zipWith' f as bs

Nótese que el largo del resultado lo domina la lista más corta. Esto permite combinar una lista infinita con una finita sin problemas. Por ejemplo, para asignar bonos a los tres primeros lugares de una carrera y cero al resto, los puntajes son una lista infinita (concatenación ++ más cycle) y el largo final lo fija la lista finita de participantes:

ghci> scores = [20, 12, 8] ++ cycle [0]          -- 20,12,8,0,0,0,...
ghci> myZip ["ana","ben","cai","dan"] scores
[("ana",20),("ben",12),("cai",8),("dan",0)]
ghci> zipWith' (+) [1,2,3,4] [9,8,7,6]
[10,10,10,10]

Fibonacci como lista infinita

Uniendo todo lo anterior podemos definir la lista infinita de los números de Fibonacci con una definición sorprendentemente compacta:

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
ghci> take 10 fibs
[1,1,2,3,5,8,13,21,34,55]

La intuición: fibs y tail fibs son la misma lista desfasada en una posición. Al sumarlas con zipWith (+), cada elemento nuevo resulta ser la suma de los dos anteriores, que es justamente la recurrencia de Fibonacci. La evaluación perezosa es esencial: fibs se refiere a sí misma, y cada elemento se va calculando sólo en la medida en que take lo pide.

Construir un proveedor de datos que "no se acaba" es difícil en lenguajes eager como Racket: hay que introducir una estructura especial, los streams, con toda su maquinaria de suspensión. En Haskell la lista nativa ya sirve, porque la pereza está en el lenguaje mismo, no en la estructura de datos.

Un intérprete escrito en Haskell

Las mismas ideas de las Unidades 2 y 3 pueden implementarse en Haskell. Con alias de tipo (type) y tipos inductivos (data) definimos un mini-intérprete para expresiones aritméticas con with:

type Id    = String
type Value = Int
type Env   = [(Id, Value)]

data Expr = Num Int
          | Add Expr Expr
          | Ident Id
          | With Id Expr Expr

interp :: Expr -> Env -> Value
interp (Num n)      _   = n
interp (Add l r)    env = interp l env + interp r env
interp (Ident x)    env = lookupEnv x env
interp (With x e b) env = interp b (extend env x (interp e env))

lookupEnv :: Id -> Env -> Value
lookupEnv x []          = error ("free identifier: " ++ x)
lookupEnv x ((y,v):rest) = if x == y then v else lookupEnv x rest

extend :: Env -> Id -> Value -> Env
extend env x v = (x, v) : env

El pattern matching de interp sobre los constructores es el mismo match que haríamos en Racket, escrito como ecuaciones. Al probarlo, interp (With "x" (Add (Num 3) (Num 5)) (Add (Ident "x") (Ident "x"))) [] retorna 16. Esto deja planteada una pregunta que suele aparecer en evaluaciones.

Si Haskell es perezoso por defecto y usamos funciones de Haskell para implementar las funciones de nuestro lenguaje interpretado, ¿qué estrategia de evaluación tendrá el lenguaje interpretado? La respuesta depende de dónde fuerza la evaluación el intérprete. Ese es justamente el problema que resolvemos a continuación, de vuelta en Racket.

Implementando evaluación perezosa en el intérprete

Volvemos a nuestro intérprete de Racket (#lang play) con alcance estático, sustitución diferida (ambientes) y funciones de primera clase. Queremos agregarle evaluación perezosa. Ya teníamos la intuición de cómo hacerlo en intérpretes con sustitución explícita; el desafío nuevo es combinarla con funciones de primera clase manteniendo el alcance estático.

Consideremos el programa (notación de nuestro lenguaje):

{{fun {x} {{fun {y} {+ y 2}} {+ x 1}}} {+ 4 5}}

Bajo evaluación temprana, los argumentos se evalúan antes de guardarse en el ambiente:

Ambiente []      : se evalúa el argumento {+ 4 5} => 9, y se liga x
Ambiente [x->9]  : {{fun {y} {+ y 2}} {+ x 1}}
                   se evalúa el argumento {+ x 1} => 10, y se liga y
Ambiente [x->9, y->10] : {+ y 2} => 12

Bajo evaluación perezosa, en cambio, guardamos en el ambiente la expresión sin evaluar. Pero no basta con la expresión: hay que recordar también el ambiente vigente al momento de capturarla, o de lo contrario introduciríamos alcance dinámico (el mismo problema que resolvimos con las clausuras de función):

Ambiente [] : se posterga el argumento {+ 4 5}, ligando x a «expr + ambiente»
Ambiente [x -> «{+ 4 5}», []]
            : se posterga {+ x 1}, ligando y a «expr + ambiente»
Ambiente [x -> «{+ 4 5}», [] ;  y -> «{+ x 1}», [x -> «{+ 4 5}»]]
            : {+ y 2}: el '+' FUERZA y => fuerza {+ x 1} => (necesita x) => 9,
              luego 10, y finalmente 12

Clausuras de expresión

Con las funciones de primera clase aprendimos a postergar la evaluación de una función capturándola junto a su ambiente en una closureV. Ahora necesitamos postergar la evaluación de una expresión arbitraria, y lo resolvemos igual: capturamos la expresión junto a su ambiente en una nueva variante de Value, la clausura de expresión exprV:

(deftype Value
  (numV n)
  (closureV arg body env)
  (exprV expr env))       ;; clausura de expresión: expr + ambiente capturado

La regla de aplicación

El único cambio semántico crucial está en el caso de la aplicación de función. En lugar de evaluar el argumento y ligar su valor, lo postergamos envolviéndolo en una exprV que captura el ambiente actual:

[(app f arg-expr)
 (def (closureV arg-name body closed-env) (strict (interp f env)))

 ;; (def new-env (extend-env arg-name (interp arg-expr env)  closed-env)) ; <- eager
 (def new-env (extend-env arg-name (exprV arg-expr env) closed-env))      ; <- lazy
 (interp body new-env)]
La diferencia entre temprano y perezoso es literalmente media línea de código: (interp arg-expr env) versus (exprV arg-expr env). Un cambio mínimo a nivel de código produce un cambio conceptual enorme en el comportamiento del lenguaje.

Puntos de strictness

Si sólo hacemos ese cambio, el intérprete queda demasiado perezoso: posterga todo y nunca fuerza nada, de modo que (run '{{fun {x} x} 3}) retorna una exprV en vez de 3. Postergamos correctamente, pero olvidamos la otra mitad de la estrategia: usar el valor cuando es estrictamente necesario.

Los lugares donde el valor de una expresión postergada es indispensable se llaman puntos de strictness. En nuestro intérprete son cuatro:

  • las dos operaciones aritméticas (add, sub): para sumar o restar hay que saber qué números son;

  • la condición del if0: hay que reducirla a un número para saber si es cero;

  • la posición de función de una app: hay que obtener la closureV para poder aplicarla.

En esos puntos aplicamos una función strict, que fuerza la reducción de una clausura de expresión hasta obtener un valor "real" (numV o closureV). Como las clausuras de expresión pueden estar anidadas, strict debe ser recursiva:

;; strict :: Value -> Value  [sin exprV]
;; Reduce un Value hasta un numV o un closureV.
(define (strict v)
  (match v
    [(exprV expr env) (strict (interp expr env))]
    [_ v]))
Usar puntos de strictness no equivale a volver a la evaluación temprana. Seguimos postergando la evaluación de los argumentos; sólo forzamos donde el valor es imprescindible. Si un argumento nunca llega a un punto de strictness, su expresión queda postergada para siempre y no se evalúa jamás (ese es, precisamente, el comportamiento perezoso que buscamos).

El intérprete completo, con los puntos de strictness marcados:

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

    [(app f arg-expr)
     (def (closureV arg-name body closed-env) (strict (interp f env)))  ; strict
     (def new-env (extend-env arg-name (exprV arg-expr env) closed-env)); lazy
     (interp body new-env)]))

Forzar en el nivel superior

Queda un caso borde: si el resultado final de un programa es una expresión que nunca necesitó forzarse (p. ej. {{fun {x} x} 3}, donde x se retorna sin sumarse), el intérprete devolvería una exprV. Por usabilidad, run fuerza la evaluación también en el top level antes de entregar el resultado:

(define (run p)
  (define (unwrap val)
    (match val
      [(numV n) n]
      [(exprV expr env) (unwrap (strict (interp expr env)))]  ; forzar en top-level
      [x x]))
  (unwrap (interp (parse p) (mtEnv))))

Con esto obtenemos el comportamiento esperado. Nótese el último test: es el discriminador aplicado a nuestro propio lenguaje. Como y es un identificador libre, evaluarlo produciría el error "free identifier"; bajo evaluación perezosa nunca se evalúa, y el programa retorna 3:

(test (run '{{fun {x} x} 3}) 3)
(test (run '{{fun {x} {+ x x}} 3}) 6)
(test (run '{{fun {x} 3} y}) 3)   ;; perezoso: el argumento libre 'y' nunca se evalúa

Call-by-name vs. call-by-need

La evaluación perezosa que acabamos de implementar tiene un problema de eficiencia. Consideremos:

{{fun {x} {+ x x}} {+ 4 5}}

Aquí x se liga a la clausura de expresión de {+ 4 5}. Al evaluar {+ x x}, el ` fuerza `x` *dos veces*, y cada vez `strict` vuelve a interpretar `{ 4 5} desde cero. El argumento se evalúa tantas veces como aparezca en el cuerpo. Esta variante de la evaluación perezosa se conoce como call-by-name: los argumentos se evalúan cada vez que se requieren.

Call-by-name es correcto y tiene usos interesantes (por ejemplo, permite definir estructuras de control como while mediante funciones normales, algo que en Scala se hace con parámetros by-name), pero repetir cálculos costosos es ineficiente.

Memoización con cajas: call-by-need

La solución es cachear el valor del argumento la primera vez que se reduce, y en usos posteriores devolver directamente el valor guardado. Esta variante se llama call-by-need: los argumentos se evalúan una sola vez.

Para el caché usamos las cajas (box) de Racket: celdas mutables de tamaño 1, con operaciones box, unbox y set-box!.

(let ([b (box 5)])
  (unbox b)        ; => 5
  (set-box! b 8)
  (unbox b))       ; => 8

Extendemos la clausura de expresión con un tercer campo, cache:

(deftype Value
  (numV n)
  (closureV arg body env)
  (exprV expr env cache))    ;; cache: caja, inicialmente vacía

En la aplicación inicializamos el caché con una caja "vacía". Como nuestro lenguaje no tiene booleanos, usamos #f de Racket como marca de "caché vacío" (cualquier valor distinto de #f cuenta como "lleno"):

[(app f arg-expr)
 (def (closureV arg-name body closed-env) (strict (interp f env)))
 (def new-env
   (extend-env arg-name (exprV arg-expr env (box #f)) closed-env))  ; caché vacío
 (interp body new-env)]

Toda la lógica del caché vive en strict. Si la caja está vacía, se reduce la expresión, se almacena el valor con set-box! y se retorna. Si ya tiene un valor, se retorna directamente sin recalcular:

;; strict :: Value -> Value  [sin exprV]
(define (strict v)
  (match v
    [(exprV expr env cache)
     (if (not (unbox cache))                    ; caché vacío: nunca evaluado
         (let ([val (strict (interp expr env))]) ; se reduce la expresión
           (set-box! cache val)                  ; se guarda en el caché
           val)                                  ; se retorna el valor calculado
         (unbox cache))]                         ; caché lleno: se reutiliza
    [_ v]))

Como la caja es mutable y vive dentro de la clausura de expresión (que está compartida en el ambiente), la primera reducción queda visible para todos los usos posteriores del mismo argumento. Así {+ 4 5} del ejemplo se evalúa una sola vez.

Esta implementación se apoya en mutación (set-box!), un mecanismo que estudiaremos formalmente en la Unidad 5. Por ahora la usamos como una caja negra para memoizar.

Resumen de estrategias

Table 2. Estrategias de evaluación
Estrategia ¿Cuándo se evalúa el argumento? ¿Memoiza?

Call-by-value (temprana / eager)

Antes de evaluar el cuerpo de la función. Los argumentos formales se ligan al valor del argumento actual. Es el default en Scheme, C, Java.

N/A

Call-by-name (perezosa)

Sólo si se requiere, y cada vez que se requiere (se re-evalúa en cada uso).

No

Call-by-need (perezosa)

Sólo si se requiere, y una sola vez (la primera); luego se cachea. Es el default en Haskell.

Sí
Ideas fundamentales de la unidad. (1) Implementar evaluación perezosa requiere clausuras de expresión que posterguen la evaluación capturando el ambiente para preservar el alcance estático. (2) La evaluación perezosa debe implementarse con cuidado (call-by-need) para evitar la re-evaluación repetida de los argumentos. (3) Call-by-value es un buen default; el comportamiento perezoso, cuando se ofrece, conviene que sea explícito para no llevarse sorpresas.

Ejercicios propuestos

  1. Discriminadores. Escriba, para Racket y para Haskell, el programa mínimo que permite determinar si el lenguaje es eager o lazy. Explique el resultado esperado en cada caso e indique qué expresión juega el rol de "error seguro" en cada lenguaje.

  2. Predicción de resultados. Para cada uno de los siguientes programas de nuestro lenguaje, indique el resultado bajo evaluación temprana y bajo evaluación perezosa, justificando: {{fun {x} 0} {+ z 1}} (con z libre), {with {x {+ 1 2}} {+ x x}}, {{fun {x} {if0 x 1 x}} 0}.

  3. take, drop y cycle en Haskell. Implemente myTake, myDrop y myCycle por ecuaciones con pattern matching. Verifique que myTake 5 (myCycle [1,2,3]) produce [1,2,3,1,2].

  4. Fibonacci en dos mundos. Defina la lista infinita de Fibonacci en Haskell con zipWith (+). Luego intente reproducirla en Racket: explique por qué la lista nativa no basta y qué estructura (stream) haría falta.

  5. Call-by-name en el intérprete. A partir del intérprete eager, modifique únicamente el caso app para postergar el argumento con una exprV. Agregue la función strict y los cuatro puntos de strictness. Escriba tests que distingan el comportamiento perezoso del temprano.

  6. Call-by-need con memoización. Extienda la solución anterior agregando el caché con box. Diseñe un experimento que evidencie la diferencia entre call-by-name y call-by-need (por ejemplo, un argumento que, al evaluarse, incremente un contador externo, y una función que lo use varias veces).

  7. Reducción paso a paso. Desarrolle la reducción completa de front 3 fibs (con fibs = 1 : 1 : zipWith (+) fibs (tail fibs)), indicando en cada paso la regla aplicada (pattern matching, caso base/recursivo). Observe cómo la pereza evita que fibs se expanda infinitamente.

  8. Reflexión sobre el meta-lenguaje. Considere el intérprete escrito en Haskell de este capítulo. ¿Qué estrategia de evaluación hereda el lenguaje interpretado del hecho de que Haskell sea perezoso? Justifique identificando en qué punto del intérprete se fuerza (o no) la evaluación de la expresión nombrada de un with.