lunes, 27 de abril de 2009

Teorema de Inducción Matemática y Software

Para los que han tenido formación matemática, el Teorema de Inducción Matemática se utiliza para demostrar que una fórmula determinada es válida para un determinado universo de valores. En general, se enseña en el contexto de la reducción de series de números a fórmulas discretas, por ejemplo, con inducción se puede demostrar fácilmente que:

  • 1 + 3 + 5 + 7 + ... + (2n -1) = n^2 para todo n >= 1
  • 2 + 6 + 10 + ... + (4n - 2) = 2*n^2 para todo n >= 1

Este teorema es interesante porque permite de una manera simple demostrar que algo se cumple siempre, siguiendo la secuencia siguiente:

  • Demostrar para n = 0 ó 1 (según corresponda)
  • Asumir que es válido para n = n
  • Demostrar que se cumple para n = n + 1

En el mundo del software aplicado (no teórico) por suerte no hay nada que demostrar, sólo hay que programar, sin embargo, el concepto de hacer el análisis para valores conocidos, extrapolar y luego volver a hacer el análisis para valores extremos se puede utilizar fácilmente para mejorar las estrategias de programación.

Ejemplo 1 - Parámetros de un JSP
Supongamos una página JSP que recibe un parámetro que corresponde al id de una base de datos. Por ejemplo:

http://X.X.X.X:8080/procesaItem.jsp?itemID=56353

El código para procesar esta solicitud, obligatoriamente, debe tener una instrucción como la siguiente:

long iItemID = Long.parseLong( request.getParameter("itemID") );

La instrucción anterior está expuesta a muchos errores (itemID == null, itemID = "", itemID = "A,B", etc.), pero, continuando con lo expuesto acá, la primera condición de validación es sobre la existencia o no del parámetro itemID. Por lo tanto, aplicando la secuencia del teorema de inducción descrita antes para el parámetro itemID, tendríamos que:

  • Recuperar el parámetro para n = 0 (es decir, no viene)
  • Suponer para n = n
  • Recuperar el parámetro para n = n + 1 (es decir, viene más de una vez)

El caso n=0 es simple de resolver, pero, es necesario dejar establecido cuál es el comportamiento en esta situación.

El caso n=1 es el caso de éxito en estricto rigor y debiera ser simple de resolver.

El caso n=n+1, es más complejo y obedece a una llamada como la siguiente:

http://X.X.X.X:8080/procesaItem.jsp?itemID=56353&itemID=616516

En este caso, a menos que funcionalmente esté considerado algo así, la página producirá un error. Fácilmente, aplicando el proceso descrito, un programador podría percatarse de esta situación y hacer la página casi indestructible (no voy a describir cuál es la solución acá).

Ejemplo 2 - Extracción del username de un e-mail.
Supongamos que en un software se requiere obtener el username del e-mail ingresado por el usuario. Por ejemplo, de una entrada del tipo perico@prueba.com se requiere obtener "perico".

Una solución inmediata (y muy común) es la siguiente:

String sUserName = sEmail.substring( sEmail.indexOf("@") );

Si bien se resuelve el problema, este código está lleno de vulnerabilidades dado que el E-Mail es ingresado por un usuario/sistema externo y, por lo tanto, no se puede hacer ningún supuesto respecto a él (para los que han programado en Java, saben que las funciones para manipular Strings son poderosas pero a la vez muy caprichosas). Los errores posibles serían básicamente que sEmail == null, sEmail = "", sEmail = "A,B", etc.

Si recordamos el teorema de inducción, podremos fácilmente mejorar el código anterior. Claramente la variable que determina el éxito en la operación es la existencia del @. Por lo tanto, aplicamos rápidamente la secuencia del teorema considerando n como el número de ocurrencias del @ y obtenemos:

  • Recuperar el username para n = 0
  • Suponer para n = n
  • Recuperar el username para n = n + 1

En este caso, n = 0 puede ser y es responsabilidad del programador identificar el caso base. Considerar n = 1 como caso base es un error a menos que el contrato de la función indique que el email siempre traerá un @ (en mi experiencia, siempre es mejor ponerse en el peor caso). Con lo anterior, es necesario definir claramente el resultado esperado para la primera afirmación y para la última dado que son condiciones de borde.

Claramente el teorema de inducción no sirve para demostrar nada en el contexto de la programación aplicada, sin embargo, siguiendo la secuencia descrita aquí y basándose en él, creo que se logra gatillar un proceso de reflexión simple y eficiente para blindar el software ante las miles de condiciones de error que pueden ocurrir durante la ejecución... en particular... cuando el software pasa a manos de los usuarios (qué mágica capacidad que tienen de destruirlo en un segundo, je, je)

No hay comentarios.: