Llamadas de cola: la garantía que convierte la recursión en un bucle

Casi todos los lenguajes que dicen soportar recursión de cola en realidad no lo dicen: lo insinúan. Su compilador la aplica cuando puede, la abandona cuando el código se complica, la desactiva en compilaciones de depuración y no ofrece ninguna forma de comprobar si en un punto concreto la aplicó o no. El resultado es que ningún programador razonable puede escribir un programa cuya corrección dependa de ella, y por tanto la característica, aunque exista, no cambia cómo se escribe. Lua hizo lo contrario, y lo hizo en el sitio correcto: no en el compilador sino en la definición del lenguaje. El manual de referencia establece que ciertas llamadas, escritas de una forma sintáctica precisa, no hacen crecer la pila, y esa afirmación es tan vinculante como la de que las tablas se indexan con corchetes. No es una promesa de rendimiento, es una garantía semántica, y sobre las garantías semánticas sí se puede construir. Esta lección trata de qué se puede construir exactamente.

Lo que Lua garantiza, y por qué es una garantía

La regla es la siguiente: cuando una función termina con un retorno cuyo contenido es exactamente una llamada, Lua descarta el marco de pila del llamante antes de entrar en el llamado. No hay nada que hacer al volver, porque no se vuelve: el resultado del llamado será directamente el resultado del llamante, así que conservar el marco sería guardar un contexto que nadie va a consultar. La consecuencia es que una cadena de llamadas de cola de cualquier longitud ocupa un solo marco.

-- Diez millones de niveles de profundidad, espacio constante
local function contar(n)
  if n == 0 then return "fin" end
  return contar(n - 1)
end
print(contar(10000000))        --> fin

-- La version que NO es de cola desborda enseguida
local function malo(n)
  if n == 0 then return 0 end
  return 1 + malo(n - 1)       -- queda una suma pendiente al volver
end
-- malo(10000000)  --> stack overflow

La comparación entre las dos últimas funciones aísla el criterio con nitidez. En la segunda hay trabajo pendiente después de la llamada, la suma, y ese trabajo necesita que alguien recuerde dónde continuar; el marco es precisamente ese recuerdo, y por eso no se puede tirar. En la primera no queda nada pendiente y el marco es basura desde el instante en que se prepara la llamada.

La forma exacta, y las variantes que la anulan

Aquí conviene ser literal, porque la diferencia entre calificar y no calificar es sintáctica y las variantes fallidas se parecen mucho a la buena. Solo es llamada de cola un retorno cuya lista de valores consista únicamente en una llamada a función, sin paréntesis envolventes, sin operadores, sin valores adicionales y sin conversiones.

-- SI son llamadas de cola
return f(x)
return t.metodo(a, b)
return obj:metodo(a)          -- el azucar de dos puntos no estorba
return f(...)                 -- reenvio de varargs, tambien califica

-- NO son llamadas de cola
return (f(x))                 -- los parentesis ajustan a un valor: hay trabajo
return f(x) + 1               -- queda una suma pendiente
return f(x), 0                -- la llamada no es el unico valor de la lista
return f(x) or 0              -- hay que inspeccionar el resultado
local r = f(x); return r      -- se vuelve al llamante antes de retornar

-- Caso sutil: una variable de cierre en ambito impide ceder el marco
local function con_cierre()
  local recurso <close> = abrir()
  return siguiente()          -- hay que cerrar el recurso al salir
end

El último caso es el más fácil de pasar por alto. Una variable marcada para cerrarse obliga a ejecutar su cierre cuando el ámbito termina, y ese cierre es trabajo pendiente después de la llamada; el marco debe sobrevivir para hacerlo. Lo mismo ocurre, por el mismo motivo, con cualquier construcción que necesite ejecutar algo a la salida.

Escribirla bien: mover el acumulador al argumento

Convertir una recursión corriente en una de cola no es un truco de sintaxis sino un cambio en dónde vive el resultado parcial. Si el valor se construye al volver, hay trabajo pendiente por definición; si se construye al bajar y viaja como argumento, no queda nada que hacer en el retorno.

-- Acumula en la VUELTA: no es de cola
local function suma(n)
  if n == 0 then return 0 end
  return n + suma(n - 1)
end

-- Acumula en el ARGUMENTO: si es de cola
local function suma(n, acc)
  acc = acc or 0
  if n == 0 then return acc end
  return suma(n - 1, acc + n)
end

-- Recursion mutua: tambien en espacio constante
local par, impar
function par(n)   if n == 0 then return true  end return impar(n - 1) end
function impar(n) if n == 0 then return false end return par(n - 1)   end
print(par(5000000))            --> false, sin desbordar nada

La recursión mutua es donde la garantía luce más, porque es justamente el caso que ningún bucle expresa cómodamente. Dos funciones que se llaman en cola alternándose son un autómata de dos estados, y esa lectura es la que abre la sección siguiente.

Máquinas de estados sin estructura de control

Si un salto de cola no cuesta pila, entonces una función puede ser un estado y un retorno puede ser una transición. El autómata resultante no necesita un bucle envolvente, ni una tabla de despacho, ni una variable que guarde el estado actual: el estado actual es la función que se está ejecutando, y la transición es literalmente ir a la siguiente.

-- Reconocedor de numeros con signo, un estado por funcion
local inicio, signo, digitos

function inicio(s, i)
  local c = s:sub(i, i)
  if c == "+" or c == "-" then return signo(s, i + 1) end
  return signo(s, i)
end

function signo(s, i)
  if s:sub(i, i):match("%d") then return digitos(s, i + 1) end
  return false
end

function digitos(s, i)
  if i > #s then return true end
  if s:sub(i, i):match("%d") then return digitos(s, i + 1) end
  return false
end

print(inicio("-4096", 1))      --> true
print(inicio("12a", 1))        --> false

Cada transición es un salto que no deja rastro y no consume espacio, de modo que el reconocedor procesa una entrada de cualquier tamaño con un marco de pila. Ese es el patrón que sostiene analizadores léxicos, protocolos de red, intérpretes de bytecode y bucles de servidores escritos en Lua.

flowchart LR
A[Marco del llamante] --> B{Queda trabajo tras la llamada}
B -->|Si| C[Se conserva el marco y la pila crece]
B -->|No| D[Se descarta el marco antes de entrar]
D --> E[Cadena de saltos en espacio constante y sin bucle envolvente]
style D fill:#a6e3a1,color:#11111b
style C fill:#f38ba8,color:#11111b