jueves, 15 de abril de 2010

La cadena dinámica y la cadena estática

La cadena dinámica

Supongamos el siguiente código

f(x) { return g(x) }
g(y) { return h(y) }
h(z) { return z }

Cuando ejecutamos f(3), creamos un entorno con x=3 y evaluamos "return g(x)". Esto es una llamada a g(y) por lo que creamos otro entorno con y=3 y evaluamos "return h(y)". ¡Pero esto no es todo! De alguna manera debemos saber que cuando obtengamos el resultado de "h(y)" hemos de volver al entorno que llamó a "g(y)". Es decir, el entorno inicial con "x=3".

Esto produce una cadena de entornos que se va construyendo conforme el programa se va evaluando. En el caso de antes, cuando estamos en "return z" la cadena sería:

f(3), g(3), h(3)

Esto no es más que la pila de llamadas. Nada nuevo.

La cadena estática

Modifiquemos el código anterior de la siguiente manera.

f(x) { g(y) { h(z) { return z } ; return h(y) } ; return g(x) }

Muchos lenguajes no permiten esta construcción de funciones anidadas. Esto es debido a que en este caso hay que guardar el entorno de clausura de las funciones. Para entender la clausura lo más sencillo es introducir una variable que no esté declarada. Por ejemplo, cambiando la definición de "h" por

h(z) { return z+v }

El resultado es que como no conocemos el valor de "v", no podemos calcular "z+v" y, por ende, "h(z)". Cuando esto ocurre se dice que la expresión está abierta.

La forma de poder calcular lo anterior es cerrando la expresión dándole un valor a "v". Lo más natural es que ese valor esté en un entorno exterior.

{
v=3
...
h(z) { return z+v }
}

De alguna manera hay que disponer del entorno exterior en "h(z)". Si ahora volvemos al ejemplo del inicio de esta sección, podríamos usar en vez de "v", "x".

f(x) { g(y) { h(z) { return z+x } ; return h(y) } ; return g(x) }

¿Cómo sabe ahora "h(z)" el valor de "x" cuando sea llamada? Necesita un enlace, llamado el enlace estático, al entorno de "f(x)".  Sin embargo, las cosas no son tan simples por dos razones.

La primera es que el entorno de "f(x)" va a ser distinto según se cree en una llamada o en otra. Por ejemplo, en "f(3)" vamos a tener el entorno "x=3" y en "f(7)" pues "x=7".

La segunda es que podemos devolver una referencia a la propiar función. Supóngase:

f(x) { g(y) { return y+x } ; return g }

En este caso hemos de agrupar tanto la definición de la función "g" como el entorno en el que se definió en un único objeto. Como este objeto lo que hace es darle un valor a las variables no definidas de la función (en este caso la "x") lo que hace es la clausura de tal función. Por lo tanto a este tipo de objeto se le llama una clausura o una clausura léxica.

Pues bien, la cadena formada por todos los enlaces estáticos que atraviesa las clausuras léxicas de la función actual es la cadena estática.

Ni que decir tiene que la cadena estática es bastante más difícil de implementar que la dinámica. Para esta última basta una pila, pero para la anterior hace falta usar recolección de basura si se quiere usar en toda su capacidad. Es por esta razón que el LISP (el primer lenguaje con recolección de basura) fuera también el primero en implementar la cadena estática (el llamado "lexical scoping" del Scheme).

0 comentarios:

Publicar un comentario en la entrada