LUA / Llamada de tails adecuadas

Bienvenidos sean a este post, otra importante caracteristica que nos provee Lua con sus funciones es la posibilidad de eliminacion de llamadas de tails (tails-calls), lo cual significa que Lua es una opcion correcta a los tails recursivos, aunque esto no envuelve directamente a recursion.

Una llamada de tail (tail-call) es una funcion goto direccionada como una llamada, estas ocurren cuando una funcion llama a otra como su ultima accion que es lo mismo que decir que no hay mas nada para hacer, veamos el siguiente ejemplo:

function f(x) return g(x) end

En este ejemplo la tail-call es la llamada a g porque despues de llamado a g no hay nada mas para hacer entonces el programa no necesita volver a la funcion de llamada cuando la funcion llamada termina, por lo tanto el programa no necesita mantener ninguna informacion sobre la funcion llamadora en el stack (pila de memoria), cuando g devuelve el control puede regresar directamente al punto donde f fue llamada, algunas implementaciones de lenguajes, como el interprete de Lua, pueden tomar provecho de esto y no utilizar ningun espacio extra en el stack, es decir en la memoria, cuando llaman a un tail-call, por esto decimos que estas implementaciones hacen eliminacion de llamadas de tails.

Como las llamadas a tails no utilizan espacio en memoria no tendremos un limite en el numero llamadas al tail anidadas que el programa puede hacer, veamos el siguiente ejemplo:

function foo(n)
	if n > 0 then return foo(n-1) end
end

Nosotros podriamos llamar a la funcion anterior pasando cualquier numero como argumento y nunca obtendriamos un overflow (sobrecarga) en el stack de memoria, un punto sutil cuando asumimos la eliminacion de un llamada de tail es que llamada es de tail pero veremos que algunos candidatos a este tipo de tipo de llamada fallan al momento de aplicar el criterio que no hay nada mas que hacer despues de esa llamada, veamos el siguiente ejemplo:

function f(x) g(x) end

En este caso g no es una llamada de tail porque a pesar de ser la ultima llamada, f todavia tiene que descartar resultados ocasionales de g antes de retornarlo, de similar forma a continuacion veremos algunos ejemplos mas:

return g(x) + 1		=>	Debe hacer la adicion
return x or g(x)	=>	Debe ajustarse a un resultado
return (g(x))		=>	Debe ajustarse a un resultado

En Lua solo una llamada con la forma return funcion(argumentos) es una llamada de tail, sin embargo tanto funcion con argumentos pueden ser expresiones complejas porque Lua las evalua antes de la llamada, veamos el siguiente ejemplo:

return x[i].foo(x[j] + a*b, i + j)

En esta linea tenemos una llamada al tail valida para LUA, esto es debido a como dijimos al principio este tipo de llamada es un goto, como tal una utilidad practica de este tipo de llamadas en Lua es para programar maquinas de estado. esta aplicacion puede representar cada estado por una funcion, para cambiar el estado lo hace ir a (goto) a funcion especifica.

Vamos a considerar el siguiente ejemplo, tenemos un juego de laberinto, el cual tiene muchos cuartos y cada uno con cuatro puertas: norte, sur, este y oeste, con cada paso el usuario ingresa una direccion de movimiento, si hay una puerta en esta direccion el usuario va al cuarto correspondiente, de lo contrario el programa muestra un mensaje de alerta, en este juego nuestra meta es ir del cuarto inicial al cuarto final, nosotros iniciamos el juego con la llamada al cuarto inicial:

room1()

Sin la eliminacion de llamada de tail, cada movimiento del usuario creara un nuevo nivel en el stack y despues de una cantidad de movimientos tendremos un overflow del stack lo cual ocasionara un error en el juego y lo cerrara, en cambio con la eliminacion de llamada de tail, no tendremos un limite un numero de movimientos porque cada movimiento que efectue el usuario ejecutara un goto a la funcion, se considera como ir a la funcion, y no la llamada convencional a la funcion. para este juego simple vamos a descubrir que un programa de datos dirigidos donde se describen los cuartos y los movimientos con tablas es un mejor diseño, sin embargo si el juego tiene muchas situaciones especiales en cada cuarto puede no serlo tanto, aunque este diseño de maquina-estado es apropiado para este ejemplo, veamos un codigo simple de este tipo de juego:

function room1()
	local move = io.read()
	if move == "sur" then return room3()
	elseif move = "este" then return room2()
	else
		print("Movimiento invalido")
		return room1()
	end
end

function room2()
	local move = io.read()
	if move == "sur" then return room4()
	elseif move == "oeste" then return room1()
	else
		print("Movimiento invalido")
		return room2()
	end
end

function room3()
	local move = io.read()
	if move == "norte" then return room1()
	elseif move == "este" then return room4()
	else
		print("Movimiento invalido")
		return room3()
	end
end

function room4()
	print("Felicitaciones!!!")
end

En este caso tenemos cuatro funciones, una para cada cuarto, en cada uno de los casos tendremos un condicional que chequeara dos direcciones en caso de ser verdaderas te enviara a un cuarto o a otro, en caso contrario te mostrara un mensaje de advertencia y se quedara en el cuarto pero como nosotros usamos a return para llamar a la funcion podremos usarlo infinitamente sin tener problemas con la memoria, salvo en room4() que es el cuarto final y te mostrara un mensaje de victoria.

En resumen, hoy hemos visto un metodo para hacer llamadas al tail, hemos visto su sintaxis, como ttrabaja, como aplicarlo, como identificarlo correctamente y un ejemplo de como ponerlo en practica, espero te haya sido util sigueme en Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.