jueves, 29 de septiembre de 2011

Todas las funciones están en CPS

Hace algún tiempo hablé del CPS y las continuaciones. Había un detalle que hacía completamente incompatible el estilo CPS con el estilo normal de programación: toda función en CPS requiere un parámetro extra que es la continuación. Una función normal se definiría más o menos así:

doble(x) = x+x

Al hacer el cambio a CPS, y suponiendo que la suma es una operación predefinida que no se pasa a CPS, obtendríamos lo siguiente:

doble_CPS(x,k) = k(x+x)

La nueva función requiere ese argumento extra que es la continuación k. La continuación es una función que no regresa y que representa el resto de la computación. Lo que vamos a hacer con el resultado del doble.

Nota: El que una continuación no regrese es muy interesante desde el punto de vista de la teoría de tipos. Su tipo sería [$T\rightarrow \bot$] que es igual a [$¬ T$], pero dejaré una explicación más profunda para otra entrada más adelante.

Bien. Ahora pensemos qué pasa si tengo un lenguaje de programación en el cual la compilación va a un ensamblador genérico. Una llamada a la función doble, en ensamblador, sería algo así:

PUSH x
CALL doble

Primero insertamos el parámetro en la pila y luego llamamos a doble. Si la llamada fuera la versión CPS tendríamos algo así:

PUSH x
PUSH k
CALL doble_CPS

Esto impediría que un lenguaje cuyo compilador transformase el código a CPS interactuase con otro que no usase la transformación a CPS. En un caso se espera un argumento y en el otro dos.

Sin embargo, esto no es así. Prácticamente todos los procesasores reales (incluyendo el x86) son de estilo CPS y hay que decir, en cada llamada, cuál es la continuación. ¿Cómo? Observando con detenimiento la instrucción de llamada CALL de estos procesadores. La instrucción

CALL f


es equivalente a

PUSH l
JUMP f
l:

Donde l es una etiqueta, un indicador de dirección de código en ensamblador y JUMP una instrucción de salto. Esa es la continuación. La dirección de código l. Eso significa que podríamos llamar a la función doble en modo CPS de la siguiente forma.

PUSH x
PUSH k
JUMP doble

Las dos últimas instrucciones son el equivalente al CALL, pero diciendo que queremos que regrese, no a la instrucción inmediatamente posterior al salto, sino a la que sea k.


De esta manera se pueden mezclar funciones usuales con funciones en CPS. De hecho, las funciones usuales ya están en CPS sólo que "disfrazadas" por el uso de CALL.

Nota: Existe un pequeño detalle extra que es el uso exhaustivo que hace la transformación a CPS de las clausuras léxicas. Las funciones usuales guardan su entorno en la pila por lo que se destruye al salir de la función. Existen técnicas para evitar esto: los upvalues de LUA o en análisis de escape de la función para crear los entornos en el montículo en vez de la pila. 

lunes, 26 de septiembre de 2011

Semántica formal para clausuras léxicas

El lambda cálculo es una herramienta asombrosa. En pocas líneas puedes definir un modelo de computación. Esta simplicidad permite transmitir ideas de manera formal con relativa facilidad. Por esa razón estuve pensando cómo explicar la clausura léxica de manera matemática.

El lambda cálculo con semántica natural

Empezaré por el lambda cálculo con semántica natural (también llamada operacional de paso grande). La sintaxis del lambda cálculo es muy sencilla. [$$t::=x\mid tt\mid \lambda x.t$$] Este tipo de definiciones sintácticas se leen así:

[$t::=$]Un término (o expresión) es
[$x$]o bien una variable
[$tt$]o bien una aplicación de un término sobre otro
[$\lambda x.t$]o bien una función que toma una variable y devuelve un valor calculado por un término. Esto es a lo que se llama una abstracción lambda o función anónima.


Nota: La aplicación se asocia por la izquierda. Entonces, en vez de escribir [$(((t_1 t_2) t_3) t_4)$] escribimos [$t_1 t_2 t_3 t_4$]. 

Lo que es la semántica es también muy fácil de expresar: un término se convierte en un valor mediante una relación binaria [$t\Downarrow v$]. Los valores [$v$] sólo son un tipo especial de término que se denominan formas normales (nosotros vamos a usar WNF). [$$v::= \lambda x.t \mid x v_1 \cdots v_n$$]  Estas formas normales no se pueden reducir más con las reglas de evaluación con las que vamos a expresar la semántica. Estas reglas son las siguientes:
   
Regla E-VAR[$$x\Downarrow x$$]Regla E-ABS[$$\lambda x.t \Downarrow \lambda x.t $$]
Regla E-APVAL[$$\frac{\begin{array}{c}t_1 \Downarrow x v_1 \cdots v_k\\t_2 \Downarrow v \end{array}}{t_1 t_2 \Downarrow x v_1 \cdots v_k v}$$] Regla E-APABS [$$\frac{\begin{array}{c}t_1 \Downarrow \lambda x.t\\t_2 \Downarrow v \\ [x\leftarrow v]t\Downarrow  v'\end{array}}{t_1 t_2 \Downarrow v'}$$]
Como se comprobará, las reglas E-VAR y E-ABS no son complicadas ya que tanto las variables como las abstracciones son valores. El núcleo de todo está en las aplicaciones.
Tanto la regla E-APVAL como la regla E-APABS tienen una forma que recuerda a las fracciones. Esta es una notación usual en lógica para especificar reglas de inferencia e indica que si lo de arriba, que es el antecedente, se cumple, entonces lo de abajo, el consecuente, se debe cumplir.

La regla E-APVAL toma dos términos aplicados el [$t_2$] al [$t_1$]. Si resulta que [$t_1$] tras evaluar tiene un valor que no es una abstracción, lo único que podemos hacer es poner el valor de [$t_2$] detrás de la forma normal, haciéndola un poco más larga. Esto tiene algo más de sentido si, por ejemplo, usamos una variable que se llame [$lista$] y evaluemos algo como [$(lista\ 1\ 7) (2+3)$]. El resultado es la propia [$lista\ 1\ 7$] con un añadido que es el valor de [$2+3$]. Es decir, que [$  (lista\ 1\ 7) (2+3) \Downarrow lista\ 1\ 7\ 5$].

La regla E-APABS también toma dos términos aplicados. Esta vez tiene que ocurrir que [$t_1$] se evalúa a una función [$\lambda x.t$]. Entonces, hay que aplicar el resultado de [$t_2$] que es [$v$] a la función. La forma de hacerlo es sustituir todas las apariciones de [$x$] en [$t$] por [$v$] y calcular el valor que nos da esto. La sustitución la hemos escrito como [$[x\leftarrow v]$].

Entonces, si queremos calcular el doble de 1+3, sería evaluar [$(\lambda x.x+x)(1+3)$]. Usando la regla E-APABS vemos que, efectivamente, [$t_1=  \lambda x.x+x$] y que [$t_1 \Downarrow   \lambda x.x+x $] gracias a la regla E-ABS. Entonces, [$t=x+x$]. Por otra parte, [$t_2=1+3$] y [$t_2 \Downarrow 4$]. Finalmente, la sustitución a realizar es [$[x\leftarrow  4]t = 4+4$]. La evaluación es [$4+4\Downarrow 8$] por lo que [$v'=8$] y podemos decir que ocho es el doble de cuatro: [$$(\lambda x.x+x)(1+3)\Downarrow 8$$]

Nota: ¿Cómo es que estamos usando sumas y números si no los hemos definido? Realmente, sí que lo están. El lambda cálculo permite codificar los números (y muchas más cosas) como funciones. Esta es la llamada codificación de Church.



El lambda cálculo sin sustituciones

El lambda cálculo es Turing completo. Esto quiere decir que cualquier función calculable se puede calcular en él. Esto, por otra parte, no significa que sea eficiente computacionalmente. De hecho, la sustitución es una operación muy costosa: hay que recorrer todo el término en el que queremos sustituir y comparar las variables y manipular grandes trozos de expresión. Las reglas exactas son estas:


[$$[x\leftarrow t]x=t$$][$$\frac{x\ne x'}{[x\leftarrow t]x'=x'}$$]
[$$[x\leftarrow t](t_1 t_2)=(  [x\leftarrow t] t_1 ) (   [x\leftarrow t]  t_2 )$$][$$[x\leftarrow t]\lambda x.t' =  \lambda x. t' $$]

La última regla está más abajo y es la más divertida porque tiene que evitar capturar las variables. Para hacer esto debe explorar además del término donde se sustituye el término a sustituir. Más coste.
[$$\frac{\begin{array}{c}x\ne x'\\x'\notin fv(t)\end{array}}{[x\leftarrow t]\lambda x'.t' =  \lambda x'. [x\leftarrow t] t' }$$] Todos los creadores de compiladores e intérpretes buscan los métodos más curiosos para evitar la sustitución. Uno de estos métodos es la evaluación por entornos, aunque hay más como las máquinas G, los supercombinadores, etc.

Nosotros vamos a usar la evaluación por entornos que es más simple. La idea es sencilla: no sustituimos, sólo apuntamos lo que hay que sustituir. Lo apuntamos en un entorno que es una colección de vinculaciones de ese tipo. [$$ E::= \emptyset \mid E, x=v $$] Añadimos el entorno a nuestra relación de evaluación de esta manera [$$ E \vdash t \Downarrow v$$] Se podría leer "bajo el entorno [$E$] el término [$t$] se evalúa a [$v$]".

La idea es sencilla, ahora hay que establecer las reglas de evaluación. Un primer intento podría ser éste:

   
Regla E-VAR[$$\frac{x=v \in E}{E\vdash x\Downarrow v}$$]Regla E-ABS[$$E\vdash\lambda x.t \Downarrow \lambda x.t $$]
Regla E-APVAL[$$\frac{\begin{array}{c}E \vdash t_1 \Downarrow x v_1 \cdots v_k\\ E \vdash t_2 \Downarrow v \end{array}}{E \vdash t_1 t_2 \Downarrow x v_1 \cdots v_k v}$$] Regla E-APABS [$$\frac{\begin{array}{c} E \vdash t_1 \Downarrow \lambda x.t\\ E \vdash t_2 \Downarrow v \\   E,x=v \vdash t\Downarrow  v'\end{array}}{ E \vdash t_1 t_2 \Downarrow v'}$$]
El truco está en la nueva regla E-VAR que mira en el entorno el valor de la variable encontrada y en la regla E-APABS que introduce en el entorno la vinculación.

Desafortunadamente estas reglas no funcionan.

El problema se observa en la siguiente evaluación [$$\emptyset \vdash (\lambda y.\lambda x.y) 3 \Downarrow v'$$] La regla a aplicar sería E-APABS que me diría que [$$ y=3 \vdash \lambda x.y \Downarrow v'$$] La regla E-ABS terminaría la evaluación incorrectamente [$$ y=3 \vdash \lambda x.y \Downarrow \lambda x.y$$] en vez de la correcta [$\lambda x.3$]. Hay que evitar que se pierda el entorno en la regla E-ABS. Al perder el entorno la expresión [$\lambda x.y$] queda abierta con la variable [$y$] libre. La solución es cerrarla con una clausura. La clausura será léxica porque hemos ido descendiendo por las estructuras sintácticas arrastrando los entornos hasta aquí.

Incluyamos entonces un nuevo término a nuestra sintaxis: las clausuras léxicas. Que son la combinación de una abstracción lambda y un entorno. [$$ t::= x\mid tt \mid \lambda x.t \mid \lambda^E x.t $$] Ahora los valores son [$$ v::= \lambda^E x.t \mid x v_1 \cdots v_k$$] y las reglas de evaluación correctas serían
   
Regla E-VAR[$$\frac{x=v \in E}{E\vdash x\Downarrow v}$$]Regla E-ABS[$$E\vdash\lambda x.t \Downarrow \lambda^E x.t $$]
Regla E-APVAL[$$\frac{\begin{array}{c}E \vdash t_1 \Downarrow x v_1 \cdots v_k\\ E \vdash t_2 \Downarrow v \end{array}}{E \vdash t_1 t_2 \Downarrow x v_1 \cdots v_k v}$$] Regla E-APABS [$$\frac{\begin{array}{c} E \vdash t_1 \Downarrow \lambda^{E'} x.t\\ E \vdash t_2 \Downarrow v \\   E',x=v \vdash t\Downarrow  v'\end{array}}{ E \vdash t_1 t_2 \Downarrow v'}$$]
He cambiado la regla E-ABS convirtiendo la abstracción (que es código) en la clausura léxica (que es un valor) y la regla E-APABS que ahora usa el entorno de la clausura en vez del entorno de llamada.

Si evaluamos otra vez   [$$\emptyset \vdash (\lambda y.\lambda x.y) 3 \Downarrow v'$$] obtenemos que [$ v'=\lambda^{y=3}x.y$]. Lo cual me dice que hay una sustitución pendiente de [$y$] por el valor [$3$]. Esta sustitución se hará cuando se aplique la función. No se perderá.

Nota: Hay un pequeñísimo detalle a tener en cuenta en estas nuevas reglas. Si queremos hacer una lista como hicimos antes [$lista\ 1\ (1+1)$] no podremos evaluarla. Eso es así porque la variable [$lista$] no está en el entorno y no podremos aplicar la regla E-VAR. Una solución a esto es añadir un entorno inicial donde [$lista=lista$] de manera que [$ lista=lista \vdash lista\ 1\ (1+1) \Downarrow   lista\ 1\ 2$]. Esto nos debe llevar a pensar que hay dos tipos de variables las de código ([$lista$][$=lista$]) y las de valor ([$lista=$][$lista$]). Haciendo que las variables de valor tengan también entorno ([$x^E$]) abrimos la puerta a las macros higiénicas.

sábado, 24 de septiembre de 2011

miniSL parte 15 - Funciones auxiliares de evaluación

En la última entrada sobre miniSL estuvimos estudiando la evaluación. La evaluación es directa en casi todos los casos. Únicamente cuando tenemos que ejecutar una función definida por el usuario (celda de tipo LAMBDA_VAL) necesitamos una función auxiliar.

Esta función es ApplyLambda() y lo que hace es tomar
  • El código del usuario que hay que ejecutar (esto está en la celda LAMBDA_VAL) que contiene también el nombre de los parámetros. 
  • El código de los argumentos que se le pasa a la función (esto está en el código, en la celda COMBINE_CODE) 
  • El entorno de clausura donde queremos que se evalúe el código del usuario (también está en la celda LAMBDA_VAL)
  • El entorno donde hay que evaluar los argumentos, ya que estos se evalúan en el entorno de llamada y no en el local.

CELL& Script::ApplyLambda(CELL& code, CELL& args, CELL& closure, CELL& envir)
{

Con estos valores, la función ApplyLambda() crea un entorno nuevo. El entorno local.
CELL& new_envir=CreateEnvir(&closure);

Luego, evalúa los argumentos en el entorno de llamada y los va introduciendo en este entorno local con los nombres de los parámetros que se declararon en el código. Si la función era f(a,b,c) y se llama con f(1+2,3+4,5+6), lo que ApplyLambda() hace es evaluar 1+2, obteniendo el valor 3, y vincular la variable a al valor 3 recién obtenido. Luego hace lo mismo vinculando b a 7 y c a 11. Esto se hace con este bucle.

CELL* params=code.head;
 CELL* arguments=&args;
 while(params->type==CONS_CTOR && arguments->type==CONS_CTOR)
 {
  (*new_envir.envir_table)[params->head]=&Evaluate(*arguments->head, envir);
  params=params->tail, arguments=arguments->tail;
 }

Bien podría ocurrir que nos sobren argumentos o parámetros. Es decir, que la aridad de la función no coincida con la de la llamada. Eso es un error.

if((params->type!=CONS_CTOR) != (arguments->type!=CONS_CTOR))
  throw L"Invalid arity";

Finalmente, evaluamos el código. El código es una secuencia y se debe evaluar como tal usando otra función auxiliar.

return EvaluateInSequence(*code.tail->head, new_envir);
}

La función auxiliar EvaluateInSequence() es sumamente sencilla. Evalúa una lista en secuencia y retorna el valor de la última expresión evaluada.

CELL& Script::EvaluateInSequence(CELL& c, CELL& envir)
{
 CELL* aux=&CreateCell(EMPTY_LIT);
 for(CELL* p=&c; p->type==CONS_CTOR; p=p->tail)
  aux=&Evaluate(*p->head, envir);
 return *aux;
}

Como se observa, lo más complicado (y lento) es ir vinculando en el entorno local los valores de los argumentos a los parámetros. De hecho, en los lenguajes de programación reales, se buscan convenios de llamada que eviten esto. Por ejemplo, introduciendo los valores de los argumentos en pila con cierto orden. De esta manera, la función llamada no tiene que buscar las variables por su nombre, que también es lento, sino por su posición en memoria que es mucho más rápido.

Con esto acabamos el núcleo del lenguaje. En la siguiente entrada pondré el código escrito hasta ahora y, a partir de entonces, empezaremos con el reconocimiento sintáctico del programa.

miércoles, 21 de septiembre de 2011

La intuición tras la transformada de Laplace

Imaginemos que queremos hacer una derivada de una señal [$x(t)$].[$$\frac{d}{dt}x(t)$$] Las derivadas son operadores lineales. Eso quiere decir que si dividimos la señal en dos términos [$A_1 x_1(t)+A_2 x_2(t)$] tenemos [$$  \frac{d}{dt}x(t)=    A_1 \frac{d}{dt}x_1(t)  +  A_2 \frac{d}{dt}x_2(t)  $$] Ya que estamos, seamos astutos. Busquémonos unos términos que se deriven con facilidad. Por ejemplo, [$A e^{st}$]. Si estos fueran los términos, tendríamos [$$x(t)=A_1 e^{s_1t} + A_2 e^{s_2t}$$] y entonces  [$$  \frac{d}{dt}x(t)=    A_1 \frac{d}{dt}x_1(t)   +  A_2 \frac{d}{dt}x_2(t)  = A_1 s_1 e^{s_1t} + A_2 s_2 e^{s_2t} $$]Mucho más fácil.

Todo esto está muy bien; pero es raro que una señal sea suma de dos exponenciales (bueno, quizás no sea tan raro). Una opción es hacer la suma infinita, lo cual abarca muchas más señales. Sin embargo, la opción buena, buena, buena es que sea una suma de densidades. Una integral. [$$ x(t)=\int_C{A(s)e^{st}ds}$$] El único truquillo es que la amplitud depende de la constante [$s$] que usemos en la exponencial. El contorno de integración [$C$] no nos interesa ahora. Cuando este contorno existe es que la señal puede representarse así. A veces, no existe. Es decir, que tampoco abarcamos todas las señales posibles, pero sí muchísimas. Todas las de interés.

¿Qué pasa cuando derivamos la señal [$x(t)$] descompuesta como una integral de exponenciales? La integral es lineal, la derivada también, la variable de derivación no está relacionada con la variable del diferencial... Todo esto nos permite mover la derivada bajo el signo de la integral. [$$  \frac{d}{dt}x(t)=  \frac{d}{dt}\int_C{A(s)e^{st}ds} =   \int_C{ \frac{d}{dt} A(s)e^{st}ds}  $$] Y ya tenemos lo que queríamos, la derivada de una exponencial que es ella misma por la derivada de su exponente. [$$  \frac{d}{dt}x(t)=  \int_C{A(s)\ s\ e^{st}ds} $$] Buscando la similitud con   [$$ x(t)=\int_C{A(s)e^{st}ds}$$] es fácil ver que la derivada lo único que hace es multiplicar [$A(s)$] por [$s$]. ¡Mucho más fácil multiplicar que hacer la derivada!

Esa [$A(s)$] es casi la transformada de Laplace. Digo casi porque el contorno [$C$] introduce un factor de [$2\pi j$] que hay que compensar. Entonces, si llamo [$\mathcal{L}_{x(t)}(s)$] a la transformada de Laplace de [$x(t)$], tendré que    [$$ x(t)=\frac{1}{2\pi j}\int_C{ \mathcal{L} _{x(t)}(s)e^{st}ds}$$] Concretamente la expresión de arriba es la transformada inversa de Laplace. La transformada directa es más sencilla.   [$$   \mathcal{L}_{x(t)}(s)=\int_0^\infty{x(t)e^{-st}dt}$$]

jueves, 15 de septiembre de 2011

Incompatibilidades sintácticas

Los operadores prefijos e infijos no pueden ser a la vez identificadores

Si ese fuera el caso, tendríamos la siguiente ambigüedad.

a b c //=> (a) b (c) si b fuera infijo
a b c //=> a (b c) si b fuera prefijo

Una solución a esto es restringir o bien los operadores infijos o bien los prefijos para que no puedan ser identificadores.
 
Las palabras clave de las sentencias no pueden ser identificadores

Parece una perogrullada, pero hay una razón para que sea así.

return + a //=> return (+a) si es palabra clave
return + a //=> (return) + (a) si es identificador

Una solución a esto es reservar ciertos identificadores como palabras clave. Otra solución es marcar de alguna manera los identificadores que queramos que sean introductores de sentencias.
 
La tensión entre la llamada por yuxtaposición y los operadores como identificadores

No pueden compartir la misma categoría sintáctica (identificadores) ya que su asociatividad es distinta.

a b c //=> (a b) c  si es llamada por yuxtaposición (currificación)
a b c //=> a (b c)  si b es un operador prefijo
a b c //=> (a) b (c) si b es un operadores infijo

Una solución es no tener llamada por yuxtaposición. Otra solución es restringir los operadores a símbolos.

+ - c //=> + (- c)  OK. No se confunde. Si son símbolos, son prefijos.

Un operador no puede ser infijo, prefijo y postfijo a la vez

Si ese fuera el caso, tenemos la siguiente ambigüedad. Incluso con una categoría sintáctica distinta.

a + + b //=> (a +) + b  si el primer más es tomado como postfijo
a + + b //=> a + (+ b)  si el segundo más es tomado como prefijo

Llamada por yuxtaposición y tuplas son incompatibles con la sintaxis usual de llamada

Esto sólo es relevante si la semántica es distinta. Si la semántica es la misma, la ambigüedad confluye en un mismo significado.

f(a,b,c) //=> La función f aplicada por yuxtaposición a un argumento que es la tupla (a,b,c)
f(a,b,c) //=> La función f aplicada a tres argumentos que son a, b y c

Una solución a esto es usar otra sintaxis para las tuplas, por ejemplo [a,b,c].

Tuplas y parentización

Es una ambigüedad muy usual.

(1) //=> El número uno
(1) //=> Una tupla con un elemento que es el número uno

Algunos lenguajes como Python solucionan esto añadiendo una coma extra en el caso de ser una tupla y no una parentización.

(1,) //=> Una tupla en Python

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.