Evaluación

Objetivo de aprendizaje

Al concluir este tema, el estudiante será capaz de:

1. Describir la evaluación de una expresión como una secuencia de reducciones e identificar en cada paso la parte que se reduce (el redex).
2. Distinguir las estrategias estricta (orden aplicativo), por nombre (orden normal) y por necesidad (perezosa con compartición), y predecir cuál realiza más trabajo o no termina.
3. Explicar qué es un thunk, por qué la compartición evita repetir cálculos y cómo la evaluación perezosa permite estructuras infinitas.
4. Reconocer dónde Python es estricto y dónde es perezoso (iteradores, generadores, cortocircuito) y comparar con Haskell.
5. Aplicar la currificación y la aplicación parcial para construir funciones nuevas a partir de funciones existentes.

Ruta de trabajo del tema

1. Planteamiento inicial

Considere este programa en Python:

def costoso(n):
    print("calculando", n)
    return n * n


def primero(a, b):
    return a


print(primero(1, costoso(5)))

La función primero devuelve su primer argumento y nunca usa el segundo.

Esta hipótesis se retomará en la sección 4.

2. Evaluar es reducir

Definición — Reducción: paso de evaluación que reescribe una expresión en otra equivalente más simple. Redex (reducible expression) es la parte de la expresión a la que se aplica una regla en ese paso. La evaluación termina cuando ya no quedan redexes: se llegó a un valor (forma normal).

Como en el álgebra, evaluar doble (1 + 2) con doble x = x + x es reescribir paso a paso:

doble (1 + 2)  →  (1 + 2) + (1 + 2)  →  3 + (1 + 2)  →  3 + 3  →  6

Cada flecha aplica una regla: desplegar la definición, calcular una suma. La clave es que hay más de un camino posible: no es obligatorio reducir primero 1 + 2 ni hacerlo después de desplegar doble. La estrategia de evaluación es la regla que decide qué redex se reduce primero.

Definición — Confluencia: en un lenguaje sin efectos laterales, todos los caminos de reducción que terminan llegan al mismo valor. Lo que cambia entre estrategias no es el resultado, sino (a) cuánto trabajo se realiza y (b) si el cálculo termina.

La corrida siguiente muestra la evaluación de una función con la estrategia por necesidad, la de Haskell. Observe la parte marcada, la regla que se aplica y la derivación que se va escribiendo abajo.

3. Tres estrategias de evaluación

Definición — Thunk: expresión suspendida: un cálculo que todavía no se ha hecho, guardado junto con lo necesario para hacerlo después. Cuando alguien necesita su valor, se evalúa y el resultado reemplaza al thunk, de modo que no se repite.

Las tres estrategias, sobre el mismo programa doble (1 + 2):

Compare las tres estrategias con distintas expresiones. Cada caso tiene una enseñanza: el trabajo repetido, un argumento que no se usa, una lista infinita, un cálculo que no termina.

Preste atención a cuatro hechos que muestra la tabla:

1. La estricta puede fallar o no terminar donde las perezosas terminan (un argumento que nunca se usa, una lista infinita).
2. La evaluación por nombre puede repetir muchísimo trabajo (caso «repetido»: cuando las llamadas se anidan, el número de pasos crece mucho más rápido).
3. La evaluación por necesidad conserva la ventaja de no calcular lo innecesario y evita la repetición.
4. Cuando las tres terminan, dan el mismo valor: es la confluencia.

Clasifique ahora estas descripciones.

4. Evaluación perezosa y compartición

Retome el planteamiento inicial. En Python, primero(1, costoso(5)) sí muestra «calculando 5»: el argumento se evalúa antes de entrar a la función aunque nunca se use.

En un lenguaje perezoso, el mismo programa no calcula nada. Observe cómo la función constante de Haskell descarta un argumento que fallaría si se evaluara (una división entre cero) y devuelve 7.

Estructuras infinitas

La pereza permite describir una colección sin fin y usar solo una parte. La lista [1 ..] describe todos los enteros positivos; take 4 solo pide los primeros cuatro.

Una lista que se define a sí misma

-- fibs es una lista infinita definida en términos de sí misma.
-- Cada elemento se calcula UNA sola vez, gracias a la compartición.
fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

5. La pereza en Python

Python es estricto por omisión, pero ofrece «islas» de pereza: los iteradores y las expresiones generadoras. Un iterador no calcula ningún elemento hasta que se lo piden.

La diferencia con una lista se ve cuando el cálculo es costoso. La corrida siguiente calcula los tres valores con una comprensión (estricta); la que viene después calcula solo uno con map (perezosa).

Las expresiones generadoras permiten, como en Haskell, trabajar con una secuencia infinita:

Importante: los iteradores de Python no son el equivalente exacto de la pereza de Haskell: se consumen y no comparten sus resultados. Son una forma explícita de evaluación perezosa; la de Haskell es implícita y compartida.

6. Los costos de la pereza

La pereza no es gratuita. Tiene dos costos que conviene conocer.

Primer costo: los cálculos pendientes ocupan memoria. Observe lo que hace foldl (+) 0 [1,2,3,4]: no suma mientras recorre la lista; va acumulando sumas pendientes (thunks) y solo las calcula al final.

Segundo costo: es difícil razonar sobre el rendimiento. Con evaluación estricta, se sabe cuándo se ejecuta cada línea. Con pereza, el momento depende de quién consume el resultado.

Tercer punto, más profundo: la pereza exige pureza. Si las funciones tuvieran efectos laterales (imprimir, modificar), el orden en que se evalúan los thunks sería visible y el programa sería impredecible. Por eso Haskell, que es perezoso, es también puro: separa las funciones puras de las que tienen efectos mediante los tipos (IO). Python puede ser estricto con efectos sin problema, porque el orden de evaluación está claro.

7. Currificación y aplicación parcial

Definición — Currificación: técnica por la cual una función de varios argumentos se trata como una cadena de funciones de un argumento. En Haskell, toda función tiene exactamente un argumento: suma 1 2 significa (suma 1) 2, es decir, se aplica suma a 1, lo cual devuelve una función que espera el segundo argumento. El nombre honra al matemático Haskell Curry.

Definición — Aplicación parcial: aplicar una función a menos argumentos de los que espera; el resultado es una función que espera los restantes.

En la firma, la flecha se asocia a la derecha: Int -> Int -> Int es Int -> (Int -> Int): una función que recibe un entero y devuelve una función de entero a entero. Aplique los argumentos de uno en uno y observe qué se tiene en cada paso.

La aplicación parcial es lo que hace que las secciones funcionen: (+ 1) y (subtract 3) son funciones listas para pasarlas a map. En la corrida siguiente, suma 1 no es un error: es una función.

En Python no hay currificación automática, pero se obtiene el mismo efecto de dos maneras: con functools.partial o escribiendo las funciones anidadas a mano.

Nota — ¿para qué sirve? Permite configurar funciones: suma 1 es «la función sumar uno», lista para usarse con map sin escribir una lambda. Y permite componer funciones de varios argumentos con el operador ., porque cada una, una vez aplicada parcialmente, tiene un solo argumento.

8. Errores conceptuales frecuentes

Error común: creer que evaluación perezosa significa «más lenta» o «más rápida». Evita cálculos innecesarios, pero puede acumular cálculos pendientes. Depende del programa.

Error común: confundir «por nombre» con «por necesidad». Por nombre repite el cálculo cada vez que se usa el argumento; por necesidad lo comparte.

Error común: creer que map en Python (versión 3) devuelve una lista. Devuelve un iterador perezoso que se consume una sola vez.

Error común: pensar que, con pereza, el orden de las líneas del programa es el orden de ejecución. Una expresión se evalúa cuando se necesita, no donde está escrita.

Error común: creer que suma 1 en Haskell es un error por «faltar un argumento». Es una aplicación parcial perfectamente válida.

9. Libreta de trabajo

10. Preguntas de reflexión

1. Escriba una expresión para la que la evaluación estricta no termine y la perezosa sí. Explique por qué.
2. Un colega afirma que «la evaluación perezosa siempre es mejor porque nunca hace trabajo inútil». ¿Qué le respondería? Mencione al menos un costo.
3. ¿Por qué Haskell necesita ser puro para poder ser perezoso? Imagine qué ocurriría si una expresión con efecto de impresión estuviera dentro de un thunk.
4. Escriba, con functools.partial, una función que sume 10 a su argumento. ¿Qué diferencia hay con lambda x: x + 10?
5. Dé un ejemplo de problema en el que le interesaría una secuencia infinita y cómo la consumiría con un iterador de Python.

11. Lecturas recomendadas

• Peyton Jones, S. L. (1987). The implementation of functional programming languages. Prentice Hall. (Disponible libremente en línea.)
• Launchbury, J. (1993). A natural semantics for lazy evaluation. En POPL '93 (pp. 144–154). ACM.
• Hughes, J. (1989). Why functional programming matters. The Computer Journal, 32(2), 98–107.
• Hutton, G. (2016). Programming in Haskell (2nd ed.), capítulo sobre estrategias de evaluación. Cambridge University Press.
• Python Software Foundation. Documentación de itertools y functools. Acceso libre en docs.python.org.