sábado, 24 de abril de 2010

El algoritmo de la playa de agujas

Existe una gran variedad de posibles traducciones para el nombre de este algoritmo. El original en inglés es "shunting-yard algorithm". Esto de "shunting-yard" se podría traducir como patio de maniobras, playa de maniobras, playa de agujas o estación de clasificación. Como el nombre "shunting-yard" no es común, he elegido otro nombre poco común como "playa de agujas".
Las estaciones clasificadoras
Bueno, y a todo esto, ¿qué es una playa de agujas o una playa de maniobras? Es un tipo de estación de tren que sirve para desensamblar y ensamblar trenes. Su modo de funcionamiento es muy simple.
Tenemos dos haces de vías que convergen en una única vía. Las agujas son el mecanismo que permite conmutar entre dos vías convergentes. De ahí el nombre de este tipo de patio. La vía común, además, suele estar en lo alto de un montículo. La gravedad, como veremos, es importante. Un pequeño esquema de cómo funciona (con unas modestas dos vías por haz) está aquí abajo.

Primero se sube el tren que queremos desensamblar a la colina. Entonces se seleccionan las vías por las que queremos que caigan los vagones. Finalmente, se sueltan los vagones y se quitan los frenos. La gravedad hace el resto.

Todo esto está muy bien, pero ¿qué tiene que ver con la algoritmia?
Las prioridades de los operadores
Cuando escribimos una expresión como 1+3*5 el significado es realmente 1+(3*5). Esto es así porque decimos que la multiplicación tiene más precedencia (o más prioridad) que la suma y por eso se hace antes. Un humano rápidamente va detectando y evaluando primero los operadores con mayor precedencia, pero cuando le introducimos a un algoritmo una cadena como 1+3*5 la cosa no es tan sencilla.
Uno de los padres de la informática, E.W.Dijkstra, ideó el algoritmo que permite calcular estas expresiones teniendo en cuenta las prioridades de los operadores involucrados. El algoritmo terminó siendo llamado "shunting-yard algorithm" porque funcionaba como una playa de agujas.
La idea principal del algoritmo es muy simple. Vamos clasificando la entrada en operadores y operandos, cual si fueran vagones de primera o de segunda. Cuando tenemos dos operadores, comparamos las prioridades y vamos ensamblando los vagones de mayor prioridad (es decir, calculamos las operaciones).

Por partes, como decía mi profesor de matemáticas.
Calculando 1+3*5
Introduzcamos 1+3*5 en el algoritmo. Pondremos los vagones con la entrada abajo a la derecha.
El algoritmo empieza clasificando los operadores y los operandos. Los primeros irán arriba a la izquierda y los segundos abajo a la izquierda.


El punto clave ocurre cuando tenemos que introducir el vagón con * junto al vagón con +. Como * tiene más prioridad que el +, no ocurre nada y la clasificación termina normalmente.

En este punto realizamos todas las operaciones. Esto suele forzarse introduciendo un "vagón fantasma" con la menor prioridad posible pero en esta explicación, y para no liarnos, sencillamente completamos los cálculos cuando no haya más entrada.

Las operaciones se realizan ensamblando dos operandos (los vagones amarillos) con el último operador (el vagón azul más a la derecha de los operadores). El resultado 15 es un operando para el siguiente operador, la suma +.

La suma se realiza de la misma manera sacando dos operandos amarillos y ensamblando los vagones con el operador + en medio. El resultado es otro vagón amarillo que, en nuestro caso, ya tiene el resultado final: 16.
Calculando 2*4+6
Ahora vamos a poner el operador de más prioridad delante. Todo empieza igual, clasificando los vagones en operadores azules y operandos amarillos.  Sin embargo, cada vez que intentemos introducir un operador en la vía de arriba a la izquierda, hemos de comprobar las prioridades.
En este caso, el + tiene menos prioridad que el * lo que significa que antes de introducir el + hemos de calcular la multiplicación.


Como siempre que realizamos una operación, el resultado se guarda en un vagón amarillo que será un operador para la siguiente operación. ¡Pero espera! No hay operadores azules en la vía de arriba a la izquierda, hemos de seguir clasificando la entrada. Esto significa pasar el + y el 6 a la izquierda.

Finalmente, se nos acaba el tren de la derecha, la entrada, y hay que completar los cálculos. El resultado es el que esperábamos en un principio. ¡El algoritmo funciona!

Este algoritmo es relativamente importante cuando estamos trabajando con un reconocedor (parser) de un lenguaje de programación. En este caso en vez de calcular la operación, vamos construyendo el AST de la expresión. Esto es equivalente a obtener las versiones con paréntesis de las expresiones anteriores: 1+(3*5)   o   (2*4)+6.

Edit: He realizado una implementación recursiva del algoritmo en esta entrada.

jueves, 22 de abril de 2010

El patrón de elemento compuesto

Hace algún tiempo hablé del patrón decorador y me quedé con las ganas de comentar otros patrones de diseño. Ahora le voy a hincar el diente al patrón de elemento compuesto que es muy simple y que en parte está relacionado con el decorador.

Cuando hablamos del patrón decorador, también introdujimos (aunque sin mencionarlo) el patrón de elemento compuesto para tener decoradores múltiples sobre un único elemento. Esto puede observarse por la relación de agregación hacia arriba en la jerarquía de clases

Si realmente no necesitamos decorar (es decir, evitar modificar la clase original "concrete component" en el diagrama) podemos eliminar el propio decorador "decorator" y añadir las operaciones directamente.

Como algunas de estas operaciones pueden requerir más de un operando, flexibilizamos el número de la relación de agregación. El resultado es el patrón de compuesto.


Realmente lo que tenemos aquí es similar a lo que teníamos con el decorador. Una interfaz común "component" que puede ser o bien un elemento hoja "leaf" en nuestro árbol de composición o un elemento compuesto "composite" que contiene a otros elementos en él.

A diferencia del patrón decorador, el elemento compuesto es parte del sistema y no un parche posterior. Si tuviéramos que modificar "Leaf", lo cambiaríamos.


lunes, 19 de abril de 2010

Un pequeño vuelo

Como otras veces, voy a hacer un pequeño cambio de tema para descansar de tanta computación. Hoy hablaré de la estructura de las historias.

Las historias, cuando siguen la arquitrama, se dividen en tres actos. Comúnmente se llaman planteamiento, nudo y desenlace. Para comprender estos tres actos voy a asemejar la historia a un pequeño vuelo en avión.

Despegue

El primer acto sería el despegue. En el despegue, como en una historia, se empieza en tierra firme. Esta tierra firme es una zona conocida. No hay nada nuevo. Hay seguridad. Hay estabilidad. Por otra parte, se van sucediendo acciones que nos informan del nuevo entorno o de la nueva situación: los pasajeros van entrando en el avión, guardan sus bolsas, se sientan, los motores arrancan y el aparato empieza a moverse.

Todo esto nos está dando información anticipada de cómo va a ser el resto del vuelo o de la historia. Estamos viendo el avión, vemos a los asistentes de vuelo, miramos por la ventana.

Conforme se desarrolla el primer acto, se va adquiriendo más y más tensión. El despegue progresa aumentando la velocidad, el sonido y la vibración. Finalmente, ocurre un hecho. Un punto de inflexión que nos hace saber que estamos en una nueva situación definitivamente. Se acabó estar en tierra. Estamos volando.

Tanto en el despegue como en el primer acto de nuestra historia el punto de inflexión ha de ser claro y fuerte. No debe dar lugar a dudas.

Travesía

El segundo acto consiste en el disfrute (o sufrimiento) de la nueva situación. Como ocurre en los vuelos, el segundo acto suele ser bastante más largo que los otros dos y, asimismo, suelen ocurrir en él hechos clave.

El primero es la bienvenida a este nuevo mundo. En una historia aparece la figura del mentor o del maestro que guía al héroe. En el vuelo suele ser la voz del capitán dándonos información del vuelo o la campanilla que da permiso para desabrochar los cinturones. Esto hace que podamos empezar por una parte a disfrutar del vuelo algo más repantigados en el sillón o sentir añoranza por la tierra firme mirando por la ventanilla.

(Foto por Robert Campbell)

La travesía no es ni mucho menos sencilla. De hecho, con el tiempo las molestias se acrecientan. Igual pasa con la historia en la que hemos de ver que se acerca el final y nuestro héroe tiene cada vez más dificultades. Puede haber incluso turbulencias, momentos de gran tensión en los que no sabremos si acabaremos bien el viaje.

Otra parte fundamental del segundo acto es la consecución de un regalo u oportunidad que no se puede encontrar en otro sitio más que en la zona más profunda e inhóspita del vuelo: los duty free, la meticulosamente empaquetada comida del avión, las extrañas revistas de las compañías aéreas, quizá un periódico abandonado por algún pasajero anterior o, quién sabe, alguna persona atractiva que tengamos a la vista.

El segundo acto se acaba con otro momento que profundiza la crisis. De repente, sentimos una sensación de caída y el avión empieza a descender. No hay duda que el final de la historia está cerca y es inevitable. Este es otro punto de inflexión.

Aterrizaje

Conforme el avión baja y la historia progresa, aumenta el ruido en el exterior. Estamos entrando en capas de aire más denso. La gente empieza a ponerse algo más nerviosa. Todos saben que se acerca el momento del aterrizaje.

Los hechos del tercer acto son una cuesta abajo en la que el pasajero no tiene el control. Todo está ya dispuesto y las dificultades con las que se encuentra el héroe son tan insuperables que no le queda más remedio que afrontarlas.

Vuelven los vaivenes y turbulencias. Son conocidas, pero ahora estamos mucho más cerca de tierra. Se oye el tren de aterrizaje salir. El héroe cuenta con un arma. Se abren los flaps, los slats y la velocidad del avión baja. ¡Ahora que vemos el suelo amenazante! ¡Y baja la velocidad! Sube el morro del avión. Miras por la ventana y el suelo está ahí. El héroe se agarra al sillón y ¡llega el final! El clímax.

Entonces, todo ha salido bien. Estamos frenando. La gente está aliviada. En algunos vuelos incluso aplauden por la liberación de la tensión. Exactamente igual que la resolución de una historia. Después del clímax de la historia, que no debe ser muy largo, la resolución redondea la historia haciéndola volver al mundo conocido. Hemos tocado tierra. Tierra firme. Aunque la resolución no debe ser muy larga tampoco. Baste recordar con la velocidad con la que los pasajeros quieren salir del avión.

Fuera, nos llegan las primeras bocanadas de un aire nuevo. Hemos conseguido algo con el vuelo. El héroe es distinto ahora. El pasajero ha llegado a su destino.


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).

lunes, 12 de abril de 2010

¿Cómo prefiere la lista el señor? Equirrecursiva o isorrecursiva

Supongamos que tenemos un constructor tipos producto (el tipo de los pares ordenados) y un tipo suma (el tipo de un valor opcional entre dos). Entonces, una lista de enteros sería algo como

[$$ List = Empty + ( Integer \times List ) $$]

Una lista es o bien un valor de lista vacía o bien un entero y el resto de la lista. Ahora bien, ¿qué tipo cumple la ecuación anterior? Sencillamente, ninguno. Esto es así porque si sólo tenemos los constructores de tipos producto y suma. Hagamos lo que hagamos, jamás vamos a satisfacer la ecuación de arriba.

Equirrecursividad

La equirecursividad consiste en modificar el modelo en el cual se comprueba la ecuación. Esto viene a ser una modificación del significado de igualdad, de ahí el nombre.

La ecuación de arriba no se puede satisfacer porque sólo podemos usar tipos finitos (usamos el universo de Herbrand). Sea lo que sea el tipo List, al agregarle 

[$$ Empty + ( Integer \times ... ) $$]

al alrededor, hemos generado un tipo distinto.

[$$ List \ne Empty + ( Integer \times List ) $$]

La idea es permitir tipos infinitos (usamos el universo de árboles regulares) de manera que, al tener una extensión infinita, añadir o quitar el contexto

[$$ Empty + ( Integer \times ... ) $$]

del tipo, el resultado sea el mismo.

[$$ List $$]
[$$ = Empty + ( Integer \times ( Empty + ( Integer \times ( Empty + ... ) ) ) ) ) $$]
[$$ = Empty + ( Integer \times List ) $$]

La equirrecursividad permite definir listas, pero este cambio de modelo permite que ciertas expresiones tengan tipo aunque sean algo extrañas.

[$$ \lambda x. x x\ :\ \forall Y. (\mu X. X \rightarrow Y) \rightarrow Y $$]

Una solución es controlar cuándo introducimos o quitamos el contexto

[$$ Empty + ( Integer \times ... ) $$]

Isorecursividad

Volvemos a prohibir que la ecuación

[$$ List = Empty + ( Integer \times List ) $$]

tenga solución. Es decir, volvemos al universo de Herbrand.

Pero lo que vamos a hacer es introducir un isomorfismo entre los tipos de manera que el tipo List sea isomorfo al tipo

[$$ Empty + ( Integer \times List ) $$]

Esto lo escribimos como

[$$ List \equiv\ Empty + ( Integer \times List ) $$]

Ahora tenemos que introducir los isomorfismos. Estos los vamos a llamar fold y unfold. Son funciones que sólo modifican el tipo, no el valor. En este aspecto serían funciones identidad con un tipado especial.

[$$ fold\ :\ Empty + ( Integer \times List ) \rightarrow List $$]
[$$ unfold\ :\ List \rightarrow Empty + ( Integer \times List ) $$]

Afortunadamente estas funciones bastan aplicarlas cuando construimos o destruimos un valor de tipo List. Si tengo el constructor de valores del tipo suma

[$$ inj_l\ empty\ :\ Empty + ( Integer \times List ) $$]

tras aplicarle fold tendríamos

[$$ fold\ inj_l\ empty\ :\ List $$]

He construido una lista. Para destruirla primero hay que usar unfold.

[$$ case\ (unfold l)\ (\lambda .\ ...caso\ Empty...) (\lambda v. ...caso \times ...) $$]

El hecho de que los tipos isorrecursivos usen los isomorfismos fold/unfold justo en la construcción y destrucción ha provocado que se desarrollen los tipos algebraicos (ADT) que aúnan ambos tipos de funciones en una. Pero eso ya es otra historia.

jueves, 8 de abril de 2010

Cambios en las etiquetas

He cambiado la lista de etiquetas y he puesto una nube. Así ocupa menos espacio en el lateral y da relevancia a las etiquetas más importantes (no escribe las de una entrada únicamente).

Comparativa de lenguajes de programación

Veremos tres comparativas. La primera es la comparativa de uso de TIOBE. Esta empresa hace una lista de los lenguajes de programación por la cantidad de desarrollos. Los lenguajes más usados están delante de los menos usados.

Es curioso observar que justamente este mes de abril del 2010 el lenguaje de programación C vuelve a estar en primera posición. Puesto que perdió durante un tiempo frente a Java. Es meritorio que el C siga dando guerra después de casi cuarenta años.

La segunda es la comparativa de velocidad Shootout. La gente de Debian realiza esta comparativa ejecutando los mismos programas en distintos lenguajes y compilados en ciertas plataformas. Después de usar la mediana como estimador más robusto, los ordena en las tablas que aparecen en el enlace.

Es sorprendente que justamente este mes de abril del 2010 el lenguaje de programación C sea el segundo más rápido. Sólo por detrás del C++, que es el primo hermano. Sorprende precisamente que en cuarenta años no se haya conseguido un lenguaje al menos tan eficiente como el C. Aunque es cierto que el ATS, el Java y el LUA con JIT están cerca.

Finalmente, una comparativa neutra es la que aparece en la Wikipedia. Es neutra porque no compara numéricamente los lenguajes, lo hace por sus capacidades. Así, compara la sintaxis, instrucciones básicas, cómo funcionan arreglos y arreglos asociativos, cadenas, comprensión de listas, orientación a objetos, metaprogramación y demás.


sábado, 3 de abril de 2010

Las proyecciones de Futamura

Parcialización

En los lenguajes funcionales acostumbramos a escribir las funciones currificadas. No se escribe algo como

[$$ f(x,y) $$]

que sería una función con tipo

[$$ f :: X \times Y \rightarrow R $$]

Este tipo significa que f es una función que toma un par de árgumentos y devuelve un resultado. De hecho, se usa el tipo producto de X por Y (producto cartesiano).

Lo que se suele escribir es

[$$ f x y $$]

que significa realmente

[$$ f(x)(y) $$]

y cuyo tipo es

[$$ f :: X \rightarrow (Y \rightarrow R) $$]

Este tipo indica que f es una función que toma un argumento y devuelve otra función que toma el siguiente argumento y que, por fin, devuelve el resultado.

A pasar del primer caso al segundo se llama currificar la función.

Si en vez de escribir

[$$ f x y $$]

que nos da el resultado, escribimos

[$$ f x $$]

obtenemos una función que toma un argumento "y" y devuelve el resultado. El tipo de f x es

[$$ f x :: Y \rightarrow R $$]

A esta función se la llama una parcialización o una evaluación parcial de f. De cierta forma, lo que hacemos es calcular un caso particular de f para cuando sabemos el valor x.

Parcialización explícita

Generalmente parcializamos cuando no introducimos todos los argumentos que la función requiere. Esta parcialización se realiza de forma automática. En parte gracias a la nomenclatura. Sin embargo, esto no suele ser así a la hora de computar realmente. Lo que se suele hacer es usar una función auxiliar que llamaremos "mix" y que obtiene la parcialización de una función con su primer argumento.

En notación matemática:

[$$ f(x,y)=r $$]
[$$ mix(f,x)=p $$]
[$$ p(y)=r $$]
[$$ mix(f,x)(y)=r $$]

De esta forma hemos hecho explícita la parcialización de la función f.

Turing completitud

Una de las características de los modelos de computación tales como el lambda cálculo, la máquina de Turing o un ordenador, es que se pueden simular a sí mismos. Entonces decimos que ese modelo es Turing completo.

Antes de nada, empezaremos viendo cómo funciona un programa cuando queremos ejecutarlo. La idea es que tenemos el programa "prog" y se lo pasamos a otro programa "interp" para que lo interprete. Generalmente también le pasamos una entrada "entrada" y el resultado es una salida.

Todo esto se puede poner en notación metemática ya que, grancias a la Turing completitud, el intérprete no es más que un programa.

[$$ interp(prog, entrada)=salida $$]

Las proyecciones de Futamura

En este punto fue cuando a Futamura (por cierto, significa "dos villas") se le ocurrió parcializar. El resultado es que obtenemos una compilación del programa.

[$$ interp(prog,entrada)=mix(interp, prog)(entrada)=salida $$]
[$$ mix(interp, prog)=compilado $$]
[$$ compilado(entrada)=salida $$]

Esta es la primera proyección de Futamura: La parcialización de un intérprete y un programa es el programa compilado.

Pero este buen hombre no quedó ahí, vio que ¡mix también puede parcializarse!

[$$ mix(interp, prog)(entrada)=mix(mix, interp)(prog)(entrada)=salida $$]
[$$ mix(interp,prog)=mix(mix, interp)(prog)=compilado $$]
[$$ mix(mix, interp)=compilador $$]
[$$ compilador(prog)=compilado $$]
[$$ compilado(entrada)=salida $$]

Así que mix(mix, interp) no es más que el compilador relacionado con el intérprete "interp". Esta es la segunda proyección de Futamura.

Pero podemos seguir y obtener

[$$ mix(mix, interp)(prog)(entrada)
=mix(mix,mix)(interp)(prog)(entrada)=salida $$]
[$$ mix(mix, mix)(interp)=compilador $$]
[$$ compilador(prog)=compilado $$]
[$$ compilado(entrada)=salida $$]

Así que llegamos a la tercera y última proyección de futamura. Es un generador de compiladores que, dado un intérprete, obtiene el compilador correspondiente.

[$$ mix(mix, mix)=generador $$]
[$$ generador(interp)=compilador $$]

jueves, 1 de abril de 2010

Polimorfismo de rango superior

Abstracción de tipos

Cuando escribimos una abstracción lambda, la idea subyacente es que quién elige el argumento es el llamador y quién elige el retorno es el llamado. En

[$$ (\lambda x:Int.x)3 $$]

el llamador elige que sea 3 el argumento y el llamado elige que sea x(=3) el resultado. Eso sí, el tipo está fijado a

[$$ Int \rightarrow Int $$]

Llamamos "flecha" a la flecha que indica que el tipo es una función de enteros en enteros. Esto es realmente un constructor de tipos.

Cuando usamos un tipo polimórfico el llamador también elige el tipo al que quiere instanciar un término. Para eso usamos una abstracción de tipos (lambda mayúscula). En la versión polimórfica de la función identidad sería:

[$$ (\Lambda T.\lambda x:T.x)Int\ 3 $$]

El llamador debe decidir qué tipo usar (el Int) y qué valor aplicar (el 3). Para expresar que una abstracción requiere un tipo (que puede ser cualquiera), le asignamos un tipo para todo. Así que el tipo de las abstracciones anteriores sería

[$$ \forall X.X \rightarrow X
$$]

Formas canónicas

Es interesante comprobar el hecho inverso. Cuando tenemos un valor cuyo tipo es

[$$ T \rightarrow S $$]

este valor debe ser una abstracción lambda como

[$$ s=\lambda x:T.r $$]

En la anotación del tipo (detrás de la x) tenemos lo que hay a la izquierda de la flecha del tipo. Es decir, el tipo T en la expresión de arriba.

Además, la forma de usarlo es aplicando un valor del propio tipo T. Algo como

[$$ s\ t $$]

donde t tiene tipo T.

Por otra parte, si tenemos un valor cuyo tipo es

[$$ \forall X.T $$]

este valor debe ser una abstracción de tipos como

[$$ s=\Lambda X.t $$]

Y el uso de s sería aplicándole un tipo. Por ejemplo, el tipo R.

[$$ s\ R $$]

Estas son las llamadas formas canónicas y la manera que tenemos de usarlas.

Rango uno

Ahora veamos qué forma puede tener una expresión de tipo

[$$ \forall X. \forall Y. X \rightarrow Y \rightarrow X $$]

Para empezar empieza por un para todo así que debe ser

[$$ \Lambda X.t $$]

Ese término t también empieza por para todo (el de la Y) así que tendríamos

[$$ \Lambda X. \Lambda Y.s $$]

Y el término s una función de dos argumentos que debe tener por tanto dos abstracciones lambda. Para no complicar el término, haremos que el cuerpo final retorne la propia x.

[$$ \Lambda X. \Lambda Y.\lambda x:X. \lambda y:Y. x $$]

Lo interesante de esta expresión es que, al usarla, es el llamador quién elige todos los tipos y argumentos. Podría ser algo como

[$$ (\Lambda X. \Lambda Y.\lambda x:X. \lambda y:Y. x)Int\ String\ 3\ ''hola'' $$]

Siempre que ocurra esto, nuestra expresión será de rango uno. Esto es muy importante porque no hay dependencias de ningún tipo. Dados los argumentos que apliquemos (sean tipos o valores) sabremos, directamente, cómo se van a usar dentro del cuerpo de la función (basta sustituir).

Si modificamos el tipo que hemos usado bajando un para todo a la derecha de una flecha, sólo intercambiamos el orden de los argumentos. Siguen dependiendo todos del llamador.

[$$ \forall X. X \rightarrow \forall Y. (Y \rightarrow X) $$]
[$$ \Lambda X. \lambda x:X. \Lambda Y. \lambda y:Y. x $$]

Seguimos en rango uno.

Rango superior

Ahora vamos a ver qué ocurre cuando ponemos el para todo a la izquierda de una flecha.

[$$ (\forall X.X \rightarrow X)\rightarrow Int $$]

Vemos que lo más exterior es una flecha. Es decir, la forma canónica empezará por lambda minúscula con una anotación de tipo igual a lo que haya a la izquierda de la flecha.

[$$ \lambda x:(\forall X.X \rightarrow X).t $$]

Esto significa que es el llamado el que debe pasarle el tipo a la x dentro de la t. Podría ser algo como

[$$ \lambda x:(\forall X.X \rightarrow X).(x\ Int\ 3) $$]

Entonces, no basta con sustituir, también hemos de calcular con lo que hay dentro del cuerpo de la aplicación. Hemos aumentado en un grado la complejidad con la que tiene que trabajar el sistema de tipos por el mero hecho de escribir un para todo a la izquierda de una flecha.

Si la aparición de este para todo está anidado a la izquierda de las flechas menos de N veces, decimos que el tipo es de rango N. En nuestro caso, como está sólo una vez, es de rango dos.

Es decidible el inferir tipos en rango uno y dos, pero en rango tres y superiores no es decidible. Esa es la razón por la que muchos lenguajes hacen únicamente inferencia de rango dos o, incluso, uno; donde todos los para todos están por fuera de cualquier flecha.