Muchos se han sentado en numerosas ocasiones delante del ordenador, para pelearse con lenguajes funcionales tales como Gopher o Haskell. Estos lenguajes tienen la particularidad de poder resolver de una forma muy clara y directa algunos problemas que en otros lenguajes como C, Fortran o Pascal, serían computacionalmente algo más complicados.

Lo que ocurre sin embargo es que cuando se oye hablar de estos lenguajes, se los prejuzga desfavorablemente, sobre todo cuando se comenta que son lenguajes altamente recursivos. ¿Porqué existe ese miedo a la recursión?. Pues la verdad es que la mayoría de las veces se esta mal acostumbramos a resolver problemas informáticos con lenguajes de propósito general y aportando soluciones bastante chapuceras "algunos mantienen que eficientes" y puede que sea verdad, pero ¿Que hay de malo en dominar una parcela más de la programación informática, que esta basada en definiciones formales?. En cierto modo los informáticos, han que echar mano de las ciencias matemáticas para casi cualquier cosa que se quiere resolver, por ejemplo:

Si se necesita regular el flujo en una red de datos; por ahí que aparecen las teorías de colas y los algoritmos de optimización.
Si se quieren implementar complicados sistemas de visión para robots, surgen las teorías de los gradientes luminosos, mediante los cuales es posible saber si un objeto esta delante, detrás, formando esquinas, etc.
Si es necesario crear programas para el diseño tridimensional. Algoritmos de cálculo de figuras y perspectivas mediante matrices homogéneas, técnicas de renderizado mediante algoritmos de cortes lineales, técnicas radioxity, etc.

Pero volviendo al tema que interesa. ¿Que es la máquina G?. Bueno, la verdad es que se puede entender como un evaluador gráfico de expresiones funcionales.

Como características de la Máquina G, cabe destacar:

Que trabaja con expresiones escritas en Lambda Cálculo enriquecido.
Que es un evaluador perezoso.
Que esta implementación ofrece la posibilidad de ver como se realizan todas las reducciones, gracias a la representación gráfica que permite realizar la Máquina G.

Existen otros métodos para implementar evaluadores de expresiones funcionales, mucho más eficientes que la Máquina G, en cuanto a velocidad y espacio, pero sin embargo el propósito de esta implementación es que todo aquel que se sienten un rato delante del evaluador, se haga una idea clara y llegue a comprender de forma didáctica como funciona.

REGRESAR A LA PÁGINA PRINCIPAL

 

 

 

 

 

 

¿Que es la recursión?

Podemos definir la recursión, como la capacidad que una función tiene de hacer referencia a ella misma.

Ejemplo:

Factorial (X) = Si (x<2) entonces 1, sino (X * Factorial(X-1))

En la notación de la máquina G:

Factorial: \x. if (< x 1) 1 (* x (Factorial (- x 1))!

Regresar al punto de la referencia.

 

 

 

 

 

 

 

 

 

 

 

¿Que es el Lambda Cálculo?
¿Como lo aplicamos en este evaluador?

El Lambda cálculo, ante todo ha de verse como una forma de expresar ideas. Es cierto que dicho así puede resultar un poco utópico, pero a medida que se vaya leyendo, se vera, que no lo es tal.

Elementos del Lambda Cálculo.

Cualquier expresión matemática funcional, se puede representar en Lambda Cálculo mediante Aplicaciones y Funciones Lambda. La notación que este interprete sigue, es prefija.

Se presentan a continuación una serie de ejemplos.

Ejemplo 1: ¿Como es la Aplicación?.

Se entiende por aplicar un elemento a una función, a la acción por la cual se opera la función con el elemento. ¿Y esto que quiere decir?. Supóngase la función suma (+). Esta función ha de tener forzosamente dos argumentos para poder ser operada.

+ : X,Y -> X + Y.
Si se define la aplicación suma de esta forma, esta claro que lo que se pretende es sumar los dos elementos que se aplican sobre la función suma. Así, si dr escribe 2+3, se esta aplicando 2 y 3, sobre la suma.

F(3).
En este caso se esta aplicando el valor 3, a la función F, que se comportara conforme a la definición que se haya hecho de esta.

G(3,4,5).
Este es otro ejemplo en el que se aplican 3 argumentos a una función G.

Pues bien, una vez aclarado lo que se entiende por aplicación, se mostrara como se realizan estas aplicaciones en Lambda Calculo, y cual es su representación en la Máquina G.

X + Y
En Lambda Calculo: + X Y

F(3)
En Lambda Calculo: F 3

G(3,4,5)
En Lambda Calculo: G 3 4 5

G(3) + F(4)
En Lambda Calculo: + (G 3) (F 4)

Ejemplo 2: ¿Como se define una función?.
Es conocida la definición de una simple función, del tipo:

F: X -> X + 2 o bien F(X) = X + 2.

Esto no son más que normas por las cuales se representa una función que tiene un argumento y que nos devuelve como resultado la suma del valor 2 a dicho argumento.

¿Como se escribe esta función en Lambda Cálculo?.

\X. + X 2

Y ¿Como se aplica un valor a esta función?.

(\ X. + X 2) 5


Ejemplo 3: Una aplicación sobre una función más complicada.

Supóngase que se desea expresar una función con 3 argumentos, que realice la suma del tercero con el producto de los dos primeros.

F(X,Y,Z) = Z + (X * Y)

Posteriormente, se quiere aplicar los valores 1, 2 y 3 a esta función.

F(1,2,3) = 3 + (1 * 2)

Esto mismo, expresado mediante Lambda Cálculo y representado con la Máquina G, se mostraría de la siguiente manera.

(\X. \Y. \Z. + Z (* X Y) ) 1 2 3

Las representaciones de la máquina G, se realizan en Arboles o Grafos -ya que en ocasiones las ramas pueden estar compartidas-, donde en los nodos podemos encontrar:

El nombre de una función: F, G, Cons, +, -, etc.
Un valor concreto: 2, 5, true, false.
El símbolo de aplicación @.
El símbolo de definición de función l.

Regresar al punto de la referencia.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

¿Que es un Evaluador Perezoso?

Un evaluador perezoso, es aquel que solo efectúa operaciones cuando es totalmente necesario.

Supongase que ha de evaluarse la siguiente expresión:

(\ X. if (< x 4) (* X (+ X 4)) 1 ) 7

La expresión en Máquina G, es:

Como primer paso, el evaluador tomara el parámetro de la función '7', y lo sustituirá en cada uno de los nodos donde aparece la variable 'X'.

En segundo lugar, el evaluador se encuentra con la función condicional 'if', esta función tiene 3 argumentos, que son los 3 nodos @ mas externos. Pero de estos 3 argumentos, solo el primero mas cercano a 'if' es estricto, por este motivo este argumento será el primero en reducirse, de forma que si el resultado es 'true' se devolverá el segundo argumento y si es 'false' se devolverá el tercero.

Por ultimo, como la evaluación del primer argumento es 'false', se devuelve directamente el tercer argumento que es '1', sin evaluar el segundo.

Regresar al punto de referencia.

Para más información a cerca de como es al algoritmo de la Máquina G, ver el apartado ¿Como funciona?.