viernes, 9 de septiembre de 2011

¿Qué es una clausura léxica?

Expresiones abiertas

Antes de ver qué es una clausura léxica debemos saber qué es una clausura y antes de saber qué es una clausura debemos saber qué es lo que cierra la clausura. Lo que la clausura cierra son expresiones abiertas. Ahora bien, ¿qué es una expresión abierta? Para responder a esta pregunta necesitamos saber antes qué es una variable ligada y una variable libre.

La forma más sencilla de explicarlo es mediante un mínimo ejemplo. Definamos dos funciones.

f= λx.x+3
g= λx.5x

Aunque hemos usado la misma variable “x” en ambas funciones, cada “x” tiene un significado distinto en cada función. No hay más que aplicar las funciones.

f(4) = 4+3
g(7) = 5·7

La “x” de la función “f” vale 4 y la “x” de la función “g” vale 7. Esto es así porque estas “x” son variables ligadas. La “x” de “x+3” está ligada a la “λx” de “f” y la “x” de “5x” está ligada a la “ λx” de “g”.

Otro ejemplo:

h = λx. x+y

En este caso la “x” de “x+y” está ligada a la “λx” de “h”. Por otra parte la “y” no está ligada, es una variable libre.

En “a+b” tanto “a” como “b” son variables libres y en “c+c” la “c” es una variable libre que aparece dos veces.

Se llaman expresiones cerradas a las que no tienen variables libres y se llaman expresiones abiertas a las que tienen variables libres.

“5+3” es una expresión cerrada.
“λx.2x” es una expresión cerrada.
“λx.x+x” es una expresión cerrada.
“λxy.2x+5y+3” es una expresión cerrada.
“a” es una expresión abierta (la variable “a” es libre).
“λy.y+x” es una expresión abierta (la variable “x” es libre).
“1+z” es una expresión abierta (la variable “z” es libre).

Clausuras

Realizar una clausura consiste en ligar las variables libres dándoles algún valor. Una clausura podría ser la clausura cero en la cual todas las variables libres toman el valor cero.

En esta clausura la expresión “3+x” es abierta, pero se cierra a “3+0”. Igualmente, la expresión “f= λx.x+y” que tiene de variable libre a la “y”, se cierra a “f= λx.x+0”.

Pero podríamos tener otro tipo de clausura. Por ejemplo, la que se usa en matemáticas que llamaremos aquí la clausura convencional. En esta clausura las variables libres toman el valor que hayan definido por nosotros los matemáticos.

La expresión “cos(3)” es abierta porque “cos” es una variable libre. Ahora bien, todo el mundo sabe que “cos” es el coseno por lo que cerramos la expresión ligando la variable “cos” con la función coseno.
En algunos casos la clausura convencional no nos sirve. Imaginemos que nos encontramos con la expresión “K(5)”. Leyendo las bibliotecas de funciones matemáticas nos damos cuenta que podría ser la función de Bessel o la función de Sturve o la integral elíptica de primer orden o varias cosas más.

La forma de resolverlo es haciendo una clausura global. En esta clausura ligamos explícitamente las variables a su significado siempre que no se diga lo contrario. Es lo que se suele hacer cuando definimos una función. El decir “f=λx.2x” significa que “f” es la función doble y, si más adelante tenemos “f(2)”, recordamos el significado de “f” que le dimos. Este tipo de clausura global es la que se usa en lenguajes de programación como el C.

Por cierto, cuando digo “f=λx.2x” no sólo estoy ligando “f” para la clausura global, también estoy ligando “x” en la expresión “2x”. Esta es la clausura local. En este punto, el lector con conocimiento de informática habrá identificado las clausuras con los entornos. Realmente la clausura es el entorno (el ligado de variables) más la expresión que se cierra.

La clausura léxica

El adjetivo “léxico” significa “relativo a las palabras de un lenguaje”. Es decir, que haremos la clausura según nos digan las palabras del lenguaje.


En los lenguajes de ordenador (y en las matemáticas) las expresiones se anidan unas dentro de otras. Así, la expresión “1+2” está dentro de la expresión “7+g(1+2)”. Esto da lugar a una estructura del propio lenguaje. La clausura léxica es la que respeta esa estructura.

{
      define x=5 //Definimos “x”
      define g(y)=x+y //Definimos “g”. La “x” es libre aquí
}

En este programa, la expresión “define g(y)=x+y” está dentro de la estructura superior “{ define x=5; define g(y)=x+y }”. En muchos lenguajes de programación las llaves {} se usan para mostrar la estructura del programa.

Cuando se define la función “g(y)”, la variable “y” está ligada, pero la “x” no. Sin embargo, siguiendo la estructura del programa, el valor de “x” está definido un poco más arriba. Esto quiere decir que la clausura léxica liga la variable “x” (dentro de la función de “g”) a la “x” que está definida fuera de esa definición, pero estructuralmente por encima de ella.

Podría uno pensar que la clausura léxica es un descontrol porque liga las variables como le da la gana. No es así. En este ejemplo, la clausura léxica no liga la “y” y un compilador daría un error.

{
      define g(y)=y+7
      define f(x)=x+y
}

No hay ligazón porque la expresión “define g(y)=y+7” no define la “y”, define la “g”. Además, la “y” de “g(y)” ya está ligada a la de “y+7”.

El siguiente diagrama muestra cómo, al realizar la clausura léxica, se van buscando estructura arriba las ligazones de variables.



La clausura léxica como valor

Una de las claves de la clausura léxica es que se son un valor. El ejemplo típico es el siguiente:

{
      define f(x)=λy.x+y;
      define a=f(2);
      define b=f(5);
      print a(4); //Imprime 6
      print b(4); //Imprime 9
}

En este ejemplo la expresión “λy.x+y” es una expresión abierta y la clausura léxica de la misma nos dice que hemos de ligar la “x” a la de la “f(x)”. Sin embargo esta “x” es el argumento de una función así que el resultado de “f(2)” es la clausura léxica de la expresión “λy.x+y” ligando la “x” al “2”. Esto es un valor como la cadena “hola”, sólo que es algo más largo de describir.

De la misma forma “b” se define a la clausura léxica de la expresión “λy.x+y” ligando “x” al “5”. Dado que la expresión “λy.x+y” es la función que toma un “y” y devuelve “x+y”, podemos usar esa función. Es lo que se hace en los “print”.

En el primer “print” usamos la variable “a” cuyo valor era “ λy.x+y” ligando la “x” al “2”. Al aplicar “a(4)” le damos un valor a “y” así que el resultado es “x+4” ligando la “x” al “2” que a su vez es “6”. Lo que se imprime. El mismo razonamiento obtenemos para “b(4)”.

La clausura léxica y la asignación

Existe un pequeño detalle final y consiste en distinguir ligazón y asignación. Realmente, realmente al hacer “f(2)” en este último ejemplo no ligamos la “x” de “λy.x+y” a “2”. Lo que hacemos es ligar esa “x” a la de “f(x)” y, luego, al hacer “f(2)” asignamos la “x” de “f(x)” a “2”. El siguiente diagrama lo muestra.


Esta distinción es importante porque en los lenguajes imperativos se permite reasignar. Es lo que ocurre en este código.

{
      define x=5;
      define f(y)=x+y;
      print f(3); //Imprime 8
      x=7;        //Reasignación de x
      print f(3); //Imprime 10
}

Cuando el lenguaje es funcional estas distinciones no son importantes porque no se puede reasignar.

2 comentarios:

helq dijo...

Disculpa mi ignorancia, pero no entiendo porque pones esto:

“λy.y+x” es una expresión abierta (la variable “y” es libre).

No debería ser ... (la variable “x” es libre).

O es que me estoy saltando algo.

PD: muchísimas gracias por ponerte a escribir, es bastante interesante y desconocido para mí :)

Gadelan dijo...

Completamente cierto, helq. Un lapsus. Lo corrijo.

Publicar un comentario en la entrada