El algoritmo que sigue la Máquina G, para evaluar las expresiones, es el siguiente.

1) Si en el nodo raíz, hay un valor reducido totalmente por ejemplo: 1,2, true, false, etc, entonces la expresión esta reducida.

2) Comenzando desde el nodo raíz, se recorre el árbol hacia la izquierda hasta encontrar un nodo que no sea de tipo @.

3) Si se encuentra un nodo que contiene un valor totalmente reducido, por ejemplo: 1,2, true, false, etc, entonces es un caso de error, ya que no es posible aplicar nada sobre un valor.

4) Si el redex es de tipo l, entonces pueden ocurrir dos cosas:

 

 4.1) Que sea el nodo raíz, en cuyo caso la lambda esta parcializada y por tanto no puede ser reducida.

4.2) Que tenga su argumento, en cuyo caso la forma de operar es la siguiente:
4.2.1) Si el argumento es un valor concreto o bien una función cuyo nodo no esta siendo compartido, se sustituyen todas las apariciones de la variable de la función por el nodo argumento.

En el dibujo anterior, se observa que dentro de la lambda definición, existe otra definición de función lambda con el mismo nombre de variable. En estos casos, no se sustituye esta otra variable por el valor del argumento.

El paso presentado, muestra como la variable ha sido sustituida y la definición interna, respetada.

A continuación se ve otro ejemplo de como se sustituye una variable por su argumento. En este caso el argumento es un valor concreto, 7, y por eso el nodo que lo contiene puede ser compartido por todos aquellos nodos que hacen referencia a la variable de la lambda definición.El paso presentado, nos muestra como la variable ha sido sustituida y la definición interna ha sido respetada.

4.2.2) Podría ocurrir que el argumento fuese una función lambda (en la que posteriormente habría que hacer sustituciones) y cuyo nodo fuese compartido;parcializada En estos casos no es posible sustituir directamente sobre la función, lo que se ha de hacer es copiar la función y hacer la sustitución sobre la copia. Veamos un ejemplo de esto.


Sea la expresión: (\x. + (x 1) (x 2)) (\y. + y 1)

Ahora se reduce segun las reglas dichas:


Se puede observar como el nodo (lambda) esta siendo compartido. Pero si se hiciese sobre este nodo la sustitución por el valor 1, luego no podría hacerse la sustitución por el valor 2. Por eso se ha de copiar el cuerpo de la función (lambda) y hacer la sustitución sobre la copia.

Se observa como lo explicado anteriormente se lleva a cabo. Ahora solo hemos de seguir aplicando las reglas del algoritmo.

5) Si el nodo contiene una función primitiva, se evalúa si el numero de nodos por los que se ha pasado hasta llegar al nodo actual, es mayor o igual al numero de argumentos que posee la función primitiva.

5.1) Si es menor, entonces la función primitiva esta parcializada.

Se observa como lo explicado anteriormente se lleva a cabo. Ahora solo hemos de seguir aplicando las normas.

5.2) En otro caso, se reducen todos los argumentos estrictos de la función primitiva utilizando este mismo algoritmo, y por ultimo se operan los argumentos.

El resultado final es 27.

 

REGRESAR A LA PÁGINA PRINCIPAL