Un poco de Teoría de la Computación (parte 2)

Buen día a todos, bueno continuamos con la divulgación de algunos conceptos computacionales interesantes, ahora con respecto a cómo trabajan los compiladores para entender nuestro código: las estrategias de evaluación de código y la transparencia referencial de las funciones.

Estrategias de Evaluación

En ciencias de la computación, una estrategia de evaluación es un conjunto de reglas que determinarán el valor de cualquier expresión, dentro de algún lenguaje de programación. Se dividen principalmente en dos grupos: Estrictos (strict evaluation) y No estrictos (lazy evaluation).

A ver, veamos un ejemplo sencillo, imaginemos que tenemos la función:

funcion retornaCinco( parametro_opcional )

retornar  5

fin_funcion

¿Cuál sería el resultado si lo llamamos así?

retornaCinco()  -- 5, obvio
retornaCinco(1 / 0) -- 5, en realidad, siempre será 5, no?

Pues resulta que depende, porque en el segundo caso, si el lenguaje de turno es estricto, evaluará la expresión1/0 antes de pasarla como parámetro, así que ocurrirá un error de división por cero, que seguramente detendrá nuestra aplicación.

Aquí la diferencia con un lenguaje no estricto, el cual sólo evalúa el valor de la expresión si es que ésta es utilizada dentro de la función.

Sin embargo, en realidad vamos a encontrar que los lenguajes de la actualidad combinan ambas estrategias de manera peculiar. Por ejemplo, los lenguajes estrictos como C# o Java, tienden a utilizar algún tipo de evaluación no-estricta cuando evalúan bloques IF o Booleanos.

Transparencia Referencial

Dentro de algún programa de computadora, se dice que una expresión es referencialmente transparente si ésta puede ser reemplazada por su valor, sin cambiar el resultado del programa. Por definición, este tipo de expresiones son determinísticas.

Por ejemplo, en las matemáticas, todas las funciones son referencialmente transparentes, ante un mismo parámetro devuelven el mismo resultado, veamos:

Raiz_Cuadrada(4) = 2 -- porque 2 * 2 = 4
Raiz_Cuadrada(4) = 2 -- porque 2 * 2 = 4
Raiz_Cuadrada(4) = 2 -- porque 2 * 2 = 4

Sin embargo, en los programas de computadora, no es lo mismo:

Numero_Dia_Hoy() = 2 -- porque HOY es viernes 2 de octubre
Numero_Dia_Hoy() = 3 -- porque HOY es sábado 3 de octubre
Numero_Dia_Hoy() = 4 -- porque HOY es domingo 4 de octubre…

Vemos que varía, porque la función utiliza una variable libre (el tiempo) que es tomada del entorno o contexto. (ver artículo acerca de las variables libres).

Esto tema es muy importante para conocer y predecir el comportamiento de un programa, lo cual ayuda a los compiladores a tratar de corregir los programas, simplificar los algoritmos, poder modificar el código sin pausar su ejecución, o realizar optimizaciones como la memorización, la eliminación de subexpresiones, o la paralelización de la ejecución del código (ver artículo anterior).

Un ejemplo puede ilustrar estos conceptos, supongamos que tenemos el siguiente código:

X = Raiz_Cuadrada(4) – 4 + (Raiz_Cuadrada(4) * Raiz_Cuadrada(4))

El compilador podría realizar el cálculo de la primera raíz cuadrada de 4, para luego implementar la siguiente optimización, reemplazando la función por su valor:

X = 2 – 4 + (2 * 2)
X = 2                    

Con lo cual tenemos un código que se ejecutará más rápido. Sin embargo, si tenemos:

X = Numero_Dia_Hoy() – 4 + (Numero_Dia_Hoy() * Numero_Dia_Hoy() )

Calculando la primera llamada a Numero_Dia_Hoy() tenemos 2 (para el 2 de octubre, ciertamente) pero, ¿podríamos reemplazarlo en las subsiguientes llamadas? Quizás a veces sea correcto, pero ¿qué pasa si lo estamos ejecutando a las 12 pm? podría tener luego el valor de 3 en el milisegundo siguiente. Con esto se haceimposible efectuar la optimización por reemplazo. Aquí estamos ante una función no determinística, ya que no podemos asegurar que su valor siempre será 2.

La transparencia referencial asegura la no existencia de efectos paralelos, y son la base fundamental para la programación funcional (ver artículo anterior). Este tipo de funciones también son conocidas con el nombre de funciones puras (e impuras las que no lo son, consecuentemente).

Lenguajes como Haskell son totalmente puros. OCaml y F# combinan ambos tipos de funciones.

Aplicación práctica

Si venimos desarrollando con algún lenguaje en particular, es importante saber qué tipo de evaluación y optimización está realizando el compilador del mismo, para ayudarle a generar un código más eficiente y contar con aplicaciones más rápidas y robustas.

Muchas gracias por tu lectura, nos vemos en el siguiente post