Programación invariante en el mundo real

Ahora que ya sabemos como emplear la programación invariante para diseñar soluciones recursivas eficientes, es momento de complicar un poco las cosas, aplicándola sobre un ejemplo más grande. Implementemos una función que calcule para dos argumentos xx y nn, el valor de xnx^n (n≥0n \geq 0).

Esta es la definición simple de lo que buscamos: x0=1 x^0 = 1

xn=x⋅xn−1 cuando n>0 x^n = x \cdot x^{n-1} \text{ cuando } n > 0

Podríamos, como ya hemos visto, implementar esta definición directamente:

fun Pow(x, n):
  if n == 0 then return 1
  else
    return x * Pow(x, n-1)
  end
end

Sin embargo, ya sabemos que esta solución es bastante ineficiente, tanto en tiempo de ejecución como en el espacio de memoria que utiliza. La razón es que no implementa la recursividad por cola, así que hace uso desmedido de la pila, y que realiza demasiadas multiplicaciones que nos podriamos ahorrar. Si por ejemplo el exponente fuera 16, tendría que realizar 16 multiplicaciones, cuando claramente sería mucho mejor ir duplicando el exponente en cada iteración para así realizar menos multiplicaciones (x1⇒x2⇒x4⇒x8⇒x16x^1 \Rightarrow x^2 \Rightarrow x^4 \Rightarrow x^8 \Rightarrow x^{16}). Así que, efectivamente, podemos mejorar esta función en dos sentidos: en su tiempo de ejecución y su uso de la memoria.

Comencemos mejorando su tiempo de ejecución. Esta es otra definición para el cálculo del exponente que es mucho mejor en cuánto al número de computaciones:

x0=1 x^0 = 1

xn=x⋅xn−1 cuando n>0∧n es impar  x^n = x \cdot x^{n-1} \text{ cuando } n > 0 \wedge n \text{ es impar }

xn=y2(y=xn/2) cuando n>0∧n es par  x^n = y^2 (y = x^{n/2}) \text{ cuando } n > 0 \wedge n \text{ es par }

Esta definición implica muchas menos multiplicaciones, ya que cuando el exponente es par, este se reduce inmediatamente a la mitad. Por cierto, ambas definiciones que hemos mostrados son especificaciones. Las especificaciones son descripciones puramente matemáticas de lo que queremos calcular sin nada de código de por medio. Bueno, en este caso podemos implementar esta definición de forma casi literal también:

fun Pow(x, n):
  if n == 0 then return 1
  elseif n mod 2 == 1
    return x * Pow(x, n-1)
  else
     var y = Pow(x, n/2)
     return y*y
  end
end

Ahora contamos con una solución mucho mejor, que minimiza en gran medida las multiplicaciones, pero que aún no es recursiva por cola. Aún podemos mejorarla aún más. Pero ¿Cómo la convertirmos a una que use recursividad por cola?. Como siempre, lo primero que necesitamos es definir una invariante. La invariante es la clave para un buen programa, y en específico, necesitamos una que conste de dos partes, una que sirva como un acumulador del resultado que buscamos, y otra que se vaya reduciendo poco a poco y limite la ejecución del bucle. Afortunadamente, la invariante para este problema no es complicada de encontrar. Sabiendo de antemano que una potencia es un serie de productos consecutivos, podemos definir nuestra invariante como un producto entre yy elevado a algún entero i≥0i \geq 0 y otro entero aa (el acumulador) tal que el total sea igual a xnx^n.

xn=yi⋅a x^n = y^i \cdot a

En esta invariante tanto yy, ii y aa corresponden a valores que van variando en cada iteración. Y cabe prestar atención a este hecho, pues muestra que la definición de una invariante no se tiene porque limitar a dos variables, aún cuando esté compuesta de sólo dos partes.

Revisemos ahora como ir modificando los valores de las tres variables de modo que la expresión anterior sea verdadera en cada iteración del bucle. Antes, para facilitar el análisis de los valores que irán tomando las tres variables, podemos representarlas de forma compacta como una coleccion de tres valores (y,i,a)(y, i, a). Bien, consideremos que estamos en el inicio del bucle, ¿Qué valores deberían tener (y,i,a)(y, i, a) en esta situación? Esta pregunta es fácil, como resulta que a esta altura sólo tenemos los valores iniciales xx y nn pasados como argumentos, no hay ciencia en deducir que (x, n, 1) deben ser los valores al inicio del bucle. Bien, ya estamos dentro de nuestra primera llamada, y llega el momento de hacer una llamada recursiva. ¿Qué argumentos pasamos a esta nueva llamada? bueno, en cuanto a ii resulta claro que debe ir disminuyendo, pero ¿en cuanto?, depende de la paridad!. Como ya vimos con la solución anterior, podemos reducir el número de multiplicaciones si reducimos a la mitad el número cuando el exponente sea par. Así que si ii es par simplemente lo reducimos a la mitad y si es impar, lo reducimos en uno.

(x,n,1) Si n es impar ⇒(?,n−1,?) (x, n, 1) \text{ Si n es impar } \Rightarrow (?, n - 1, ?)

 Si n es par ⇒(?,n/2,?) \text{ Si n es par } \Rightarrow (?, n/2, ?)

Ahora, si al exponente le quitamos 1, ¿Cuanto debiera aumentar el acumulador?. Depende del valor de yy, por supuesto. Pero para que nos vamos a complicar las cosas modificando a yy en este caso. Simplemente podemos mantener a yy constante, y entonces simplemente debemos multiplicar el acumulador por este valor. ¿Y si reducimos el exponente a la mitad? En este caso nuevamente va a depender del valor que definamos para yy, pero tratemos de pensar en un valor sencillo, basado en la solución anterior. La solución anterior definía a y=xn/2y = x^{n/2}. Podríamos por lo tanto, aumentar yy de modo que tome el valor y⋅yy \cdot y y como (x⋅x)n/2=xn(x \cdot x)^{n/2} = x^n no tendríamos motivo para aumentar el multiplicador. A fin de cuentas, no importa si yy aumenta o no, pues es el valor de ii el que importa que se reduzca lo más rápido posible. Es ii el valor que define cuando terminar el bucle.

(x,n,1) Si n es impar ⇒(x,n−1,1⋅x)(xn=xn−1⋅x) (x, n , 1) \text{ Si n es impar } \Rightarrow (x, n - 1, 1 \cdot x) (x^n = x^{n-1} \cdot x)

 Si n es par ⇒(x⋅x,n/2,1)(xn=(x⋅x)n/2⋅1) \text{ Si n es par } \Rightarrow (x \cdot x, n/2, 1) (x^n = (x\cdot x)^{n/2} \cdot 1)

Una vez que definimos como transformar los valores de (y,i,a)(y, i, a) para la primera llamada recursiva, ya sabemos, de hecho, como realizar todas las demás llamadas recursivas. Adicionalmente, el bucle finalizará una vez i=0i = 0, y el acumulador ya almacena la respuesta que buscamos. Con eso dicho, ya tenemos todo lo necesario, y ahora simplemente nos queda escribir la implementación:

fun Pow(y, i, a):
  if(i == 0) then return a
  elseif(i mod 2 == 1)
    return Pow(y, i-1, a*y)
  else
    return Pow(y*y, i/2, a)
  end
end

Finalmente, aplicando programación invariante hemos obtenido una adaptación del algoritmo con un número mucho menor de multiplicaciones, que además es mucho más eficiente en el uso de memoria gracias a emplear la recursividad por cola. El proceso general, de hecho, desde la definición matemática hasta la definición de nuestra invariante ha sido bastante elegante.

Ejercicio:
Reescribe Pow de modo que sólo tome un argumento.

Ejercicio:
Usando programación invariante escribe una función que retorne el n-ésimo número de fibonacci. La función debe tomar un sólo argumento nn.

Pista: Las invariantes no se tienen porque limitar a un sólo acumulador.

Invariantes y metas

Habiendo comprendido los ejemplos y habiendo resuelto los ejercicios propuestos, ya deberías contar con un dominio significativo de la técnica de la programación invariante. Para finalizar esta sección, vale la pena recalcar ciertas características que acompañan a esta técnica que siempre se deberían tener en cuenta.

  • Si una parte de la invariante cambia, eso fuerza al resto a cambiar también, ya que la invariante permanecer verdadera. Esta propiedad es el motor que lleva al programa hacia la respuesta.

  • Programar un bucle significa encontrar una buena invariante. Una vez que se encuentra una invariante, la codificación es sencilla. Todo el truco está en aprender a pensar en términos de invariantes!, no pienses en los bucles cómo código que se repite, sino cómo en fórmulas que se mantienen ciertas.

  • Programar con invariantes nos lleva a una técnica más general y poderosa llamada programación orientada a metas. En este técnica definimos una meta y el programa se mantiene trabajando hacia esa meta. Ya veremos otro ejemplo de esta técnica más adelante cuando comencemos a programar con árboles. (Las invariantes son un caso particular de esta técnica)

Debate:

¿Qué piensas sobre los programas funcionales y imperativos?

¿Qué utilidad crees que tienen las invariantes?¿Consideras que los programadores realmente las necesitan?¿Crees que en algunos casos son inútiles y otros una obligación?