Estrategias de evaluación

Estrategias de evaluación

Una de las cosas interesantes en la computación es que un mismo cálculo se puede efectuar de muchas maneras ¡incluso cuando es el mismo programa!

Un ejemplo sería el siguiente:

f(x)= 2*x

g(x)= 3*x

g(f(4)) = ?

Hay dos maneras de proceder. La primera sería pensar "como no conozco f(4), voy a calcularla y luego la sustituyo".

f(4)=2*4=8

g(f(4))=g(8)

Otra manera de pensar sería "como sé cómo funciona g, voy a usar esa receta haya lo que haya en su argumento".

g(f(4))=3*f(4)

Esto, que parece una tontería, tiene hasta varios nombres. La primera forma de proceder es lo que se llama el orden aplicativo, evaluación estricta o paso por valor de los argumentos. La segunda forma de proceder es lo que se llama el orden normal o paso por nombre de los argumentos.

Computaciones infinitas

¿Realmente merece la pena tanto follón por esta sutileza? La respuesta es que, si los programas de ordenador no se colgasen, no importaría. Pero los programas de ordenador pueden entrar en computaciones infinitas que no acaban.

Supongamos una función que no acaba ω(x). Es mejor nunca calcularla porque no vamos a terminar. Ahora, supongamos una función constante que ignora su argumento y siempre retorna 7. Es decir:

constante(x)=7

¿Qué ocurre si calculo  constante(ω(1))? Si uso el orden normal he de sustituir sin ver lo que hay dentro de los argumentos y, por tanto

constante(ω(1))=7

He llegado al resultado. Si uso el orden aplicativo, he de calcular primero los argumentos.

constante(ω(1))=constante( ...y se queda colgado calculando ω

No puedo calcular el valor de ω porque no termina. Así que dependiendo de la estrategia de evaluación que use podré o no podré calcular ciertos valores.

De la pereza y otros vicios

El orden normal es magnífico porque no evalúa lo que no tiene que evaluar, pero es muy ineficiente. Esto lo vamos a comprobar en el siguiente ejemplo en el que hemos definido la función h y usamos el orden normal:

h(x)=x*x*x*x

h(f(3))=f(3)*f(3)*f(3)*f(3)

Hemos de calcular f(3) cuatro veces cuando realmente sólo hacía falta una. Esto con el orden aplicativo no habría ocurrido:

h(f(3))=h(6)=6*6*6*6

La solución es modificar ligeramente el orden normal para obtener lo que se llama la evaluación perezosa (hay diversos tipos, este es uno de ellos). La evaluación perezosa registra cuando una misma expresión se usa en varios sitios a la vez de manera que, cuando se evalúa una de esas expresiones, automáticamente todas pasan a tener el valor del resultado. En el caso de arriba sería:

h(f(3))=f(3)*f(3)*f(3)*f(3)=6*6*6*6

He puesto en gris las copias que no se calculan sino que se ponen con el resultado que da la copia que sí se evalúa (en negro). De esta manera, se evitan los problemas de la evaluación estricta y del orden normal.

Como detalle final, existen otras estrategias de evaluación: paso por referencia, paso compartido, expansión de macros, etc. Hay un interesante (aunque algo confuso en algunos aspectos) artículo en la wikipedia.