Desarrollo iterativo de programas Prolog César Ballardini * Introducción La metodología de desarrollo iterativo propuesta invita a escribir pequeños programas que funcionan (no contienen errores), pero con una funcionalidad reducida, y luego se va agregando funcionalidad paso a paso, hasta que se obtiene toda la funcionalidad requerida. En cada paso de esta tarea, se agrega un poquito de funcionalidad pero una se asegura que el programa funciona correctamente y que no se ha roto nada de la funcionalidad que ya estaba en su lugar. En lugar de escribir un programa grande y complejo, y después habérnosla con la lista de errores que aparecen, la propuesta iterativa apunta a introducir pequeñas cantidades de código cada vez. De esta manera se introducirán como mucho pequeñas cantidades de errores, que luego se procede a detectar y eliminar. Como el área de programa alterada por los cambios ha sido pequeña, los errores estarán confinados en la misma, con suerte ;-) * Ejemplo Problema: Buscar el máximo elemento de una lista de enteros. 1) Definir la estrategia de la solución. En este ejemplo la estrategia es trivial, pues solamente vamos a definir un predicado, y el nombre será maximo_entero. Note que elegí un nombre bastante específico, porque no voy a solucionar un problema general, al menos no será mi intención. Cuántos argumentos debe tener maximo_entero? Si lo pensamos desde la programación funcional, es claro que debe tener un argumento, que será la lista de enteros, y la función debe devolver el entero resultante máximo como su valor. En Prolog los predicados devuelven verdadero o falso (aciertan o fallan), así que no se puede hacer que devuelvan un entero. Lo que se hace en estos casos es poner un argumento extra para devolver el resultado. Entonces nos queda: maximo_entero(+lista_enteros,?entero) Note que "lista_enteros" está precedida por un más, lo que indica que siempre será instanciada antes de invocar a maximo_entero/2. En el caso de la variable "entero" hay un ? lo cual indica que puede o no estar instanciada. 2) Definir los casos de prueba Ahora debemos pulir nuestra comprensión de lo que hay que escribir. Definamos con precisión qué entra y qué sale de este predicado. Cuando "entero" esté instanciada, máximo_entero/2 debe acertar si el valor de "entero" coincide con el máximo entero de la lista "lista_enteros", y fallar en caso contrario. Cuando "entero" no esté instanciada, estará ligada a una variable, y en ese caso cuando se invoque a maximo_entero/2 dicha variable será instanciada con el valor del entero más grande de "lista_enteros". Si "lista_enteros" no tuviese ningún elemento entero, se espera que maximo_entero/2 falle. Así que ya podemos elaborar unos casos de prueba: p01: maximo_entero([],X) -> falla p02: maximo_entero([],2) -> falla p03: maximo_entero([a,b,c],X) -> falla p04: maximo_entero([a,b,c],c) -> falla p05: maximo_entero([a,b,c],2) -> falla p06: maximo_entero(4,X) -> falla p07: maximo_entero([1,2,3],3) -> acierta p08: maximo_entero([4,3,2,1,0],4) -> acierta p09: maximo_entero([4,3,2,4,6,0,2,6,0],6) -> acierta p10: maximo_entero([1,1,1,1],1) -> acierta p11: maximo_entero([1,6,3,7,8,0],X) -> X=8 y acierta p01 y p02 comprueban que falle en caso que la lista esté vacía; p03, p04, p05 y p06 comprueban que el primer argumento no es otra cosa que una lista de enteros; p07 comprueba si funciona cuando el mayor es el último; p08 comprueba si funciona cuando el mayor es el primero; p09 comprueba si anda cuando el mayor está en el medio y repetido, p10 prueba cuando todos los elementos son iguales; p11 comprueba la asignación del resultado en la variable. 3) Escribir la maquinaria de comprobación Estamos interesados en correr todos los casos de prueba, así que vamos a escribir unos predicados triviales que nos ayuden en esta tarea. ----------------- /* prueba_maximo_entero_1(+lista_enteros, ?simbolo, +resultado_logico) * el "simbolo" puede ser un entero o una variable * el "resultado_logico" es una cadena de caracteres que puede tomar * uno de dos valores: "acerto" ó "fallo" */ p01( [], _, 'fallo'). p02( [], 2, 'fallo'). p03( [a,b,c], _, 'fallo'). p04( [a,b,c], c, 'fallo'). p05( [a,b,c], 2, 'fallo'). p06( 4, _, 'fallo'). p07( [1,2,3], 3, 'acerto'). p08( [4,3,2,1,0], 4, 'acerto'). p09( [4,3,2,4,6,0,2,6,0], 6, 'acerto'). p10( [1,1,1,1], 1, 'acerto'). /* prueba(+lista_enteros, ?simbolo, +resultado_logico) * el "simbolo" puede ser un entero o una variable * el "resultado_logico" es una cadena de caracteres que puede tomar * uno de dos valores: "acerto" ó "fallo" * Se escribe en la pantalla el resultado de una comprobación. */ prueba(NroPrueba, ListaEnteros, MaximoEntero, AcertoFallo) :- write('prueba '), write(NroPrueba), write(': maximo_entero('), write(ListaEnteros), write(', '), write(MaximoEntero), write(') -> esperado='), write(AcertoFallo), write('/real='), maximo_entero(ListaEnteros,MaximoEntero), !, write('acerto'), nl,nl. prueba(_,_,_,_) :- write('fallo'), nl,nl. /* todas_las_pruebas/0 -- es para abreviar cuando deseo * correr todo el lote de pruebas ininterrumpidamente */ todas_las_pruebas :- prueba_01, prueba_02, prueba_03, prueba_04, prueba_05, prueba_06, prueba_07, prueba_08, prueba_09, prueba_10, prueba_11. /* prueba_1/0 es el punto de entrada para hacer la comprobación * del caso p01 */ prueba_01 :- p01(L, M, C), prueba( 1, L, M, C). prueba_02 :- p02(L, M, C), prueba( 2, L, M, C). prueba_03 :- p03(L, M, C), prueba( 3, L, M, C). prueba_04 :- p04(L, M, C), prueba( 4, L, M, C). prueba_05 :- p05(L, M, C), prueba( 5, L, M, C). prueba_06 :- p06(L, M, C), prueba( 6, L, M, C). prueba_07 :- p07(L, M, C), prueba( 7, L, M, C). prueba_08 :- p08(L, M, C), prueba( 8, L, M, C). prueba_09 :- p09(L, M, C), prueba( 9, L, M, C). prueba_10 :- p10(L, M, C), prueba(10, L, M, C). prueba_11 :- ListaEnteros = [1,6,3,7,8,0], write('prueba 11: maximo_entero('), write(ListaEnteros), write(', '), write(MaximoEntero), write(') -> esperado=acerto/real='), maximo_entero(ListaEnteros,MaximoEntero), !, write('acerto'), nl, write('El maximo es: '), write(MaximoEntero), nl,nl. prueba_11 :- write('fallo'), nl,nl. /* maximo_entero/3 se pone solamente como esqueleto para empezar a * trabajar */ maximo_entero(_,_). ------------- Bueno, si bien los predicados son triviales, nos llevó bastante tiempo el escribirlos. Se trata de un caso de problema demasiado sencillo, y hemos elegido un buen lote de casos de prueba. Si nos encargan un trabajo práctico, o cuando un ejercicio de la guía de prácticas se nos ponga complicado para depurar, entonces éste es el camino más corto: escribir los casos de prueba mejora nuestra comprensión de lo que debe hacer el programa. Además los casos de prueba automáticos nos permiten escribir modificaciones sin preocuparnos demasiado --- nos permite tener coraje para cambiar las cosas --- porque sabemos que cuando nos equivoquemos allí estará un caso de prueba que fallará, avisándonos sin demora así del problema que ocasionamos. Y la mejor oportunidad que tenemos de corregir un error es cuando todavía tenemos en mente lo que estábamos pensando cuando escribimos el código. Sin casos de prueba la depuración es más tediosa, larga, y con frecuencia ocurre cuando ha pasado cierto tiempo: el tiempo que media entre que rompemos algo y que esa rotura se hace ver al llamar a otro módulo. En nuestro caso específico del maximo_entero/2, todo esto que escribimos es demasiado, pero vale como ejemplo para problemas más complejos. En maximo_entero/2 tal vez nos conformaríamos con probar: maximo_entero([],X). maximo_entero([1,2,3],3). maximo_entero([1,2,3],X). y listo. Para correr tres metas, no hace falta tanta maquinaria extra: ------------------------ todas_las_pruebas_2 :- write('cte en el resultado:'), maximo_entero([1,2,1,3],3), write('acerto'), nl, write('variable en el resultado (debe dar 4):'), maximo_entero([1,4,3],X), write(X), nl, write('lista vacia (debe fallar):'), maximo_entero([],Y), write(Y), nl. todas_las_pruebas_2 :- write('fallo'), nl. /* maximo_entero/3 se pone solamente como esqueleto para empezar a * trabajar */ maximo_entero(_,_). ------------------------ Cuánto escribir de maquinaria de comprobación, se deja al gusto de la lectora. Como regla general, cuanto más fácil le resulte hacer una nueva comprobación, más comprobaciones podrá hacer en la práctica, y eso le dará más seguridad de que las cosas andan como se espera que lo hagan. Si decide no escribir ninguna comrobación, y usar el método del tanteo, no hay problema: cada una decide como quiere gastar su tiempo. 4) Piense una solución. Como ya lo expresamos en las consideraciones generales, una buena heurística para resolver problemas en Prolog es pensarlos de manera funcional y recursiva. Si tengo una lista de enteros, la forma iterativa de resolver la búsqueda del mayor es revisar cada elemento de la lista y compararlos con "el mayor hasta ahora"; si el elemento de la lista es mayor que "el mayor hasta ahora" lo guardo como el nuevo ël mayor hasta ahora", y si no continúo con la revisión. El algoritmo iterativo usa la asignación a una variable auxiliar, y por lo tanto no es funcional puro. Busquemos otra alternativa. Si tengo una lista de elementos, puedo quitarle un elemento y me quedaré con dos cosas: un elemento y el resto de la lista. Cuál es el mayor elemnto de la lista original? Sin duda puede ser uno de dos: - el elemento que separé - el mayor elemento del resto de la lista O sea que si los comparo, puedo retornar inmediatamente el resultado. Veamos el seudocódigo: Definir MayorElemento(Lista) Primero= primer_elemento(Lista) RestoLista= resto_elemntos(Lista) MayorResto= MayorElemento(RestoLista) Si Primero > MayorResto Entonces Retornar Primero SiNo Retornar MayorResto FinSi FinDefinir Pero esto no está completo aún. Cada vez se llama a MayorElemento() con un elemento menos en la lista argumento. Cuál es el caso base o embrionario en esta recursión? Puede ser cuando quede solamente un único elemento, y eso se puede postular como "Si una lista tiene un único elemento, ese elemento es el mayor". Nuestro seudocódigo queda: Definir MayorElemento(Lista) Si cardinalidad(Lista) == 1 Entonces Retornar primer_elemento(Lista) FinSi Primero= primer_elemento(Lista) RestoLista= resto_elemntos(Lista) MayorResto= MayorElemento(RestoLista) Si Primero > MayorResto Entonces Retornar Primero SiNo Retornar MayorResto FinSi FinDefinir 5) Escríbala en Prolog Si la solución no se podía pensar en Prolog, usted habrá saltado el paso 4). El Si/Entonces/SiNo se transforma en una cláusula para cada caso del Si. El valor retornado en programación funcional se transforma en un argumento adicional en Prolog. Una versión completamente lógica sería como sigue: maximo_entero([X], X). maximo_entero([X|Xs], X) :- maximo_entero(Xs,M), X > M. maximo_entero([X|Xs], M) :- maximo_entero(Xs,M), X < M. La primer cláusula captura el caso base de la recursión, cuando la lista está compuesta por un único elemento, que la claúsula denomina X. La segunda cláusula verifica el caso en el cual el primer elemento de la lista es el más grande; se llama recursivamente a maximo_entero/2 para descubrir el máximo elemento de la sublista Xs, que se asocia a M. La tercer cláusula considera el último caso posible, que el primer elemento de la lista no sea el mayor, sino que el mayor esté en la sublista restante Xs. 6) Depure el código Las pruebas 3 y 4 causan el levantamiento de una excepción porque los elementos de la lista no son números y se los somete a una comparación con < y con >. La solución es verificar que el primer elemento es un número. Prolog nos proporciona la primitiva number/1 que acierta si su argumento es un número. Entonces nos queda: maximo_entero([X], X) :- number(X). maximo_entero([X|Xs], X) :- number(X), maximo_entero(Xs,M), X > M. maximo_entero([X|Xs], M) :- number(X), maximo_entero(Xs,M), X < M. Bueno, con eso desaparecen las excepciones de las comparaciones. Pero todavía quedan cosas sin funcionar. Hay un error oculto que es difícil de percatarse a simple vista. Cuando el elemento mayor está repetido, ambas comparaciones XM fallan en algún momento, porque un número no es ni mayor ni menor a sí mismo. Las pruebas 9 y 10 fallan por esta razón. La solución es hacer que alguno de los dos casos considere el caso de la comparación por igual. Arbitrariamente tomamos uno de las cláusulas y entonces finalmente nos queda: maximo_entero([X], X) :- number(X). maximo_entero([X|Xs], X) :- number(X), maximo_entero(Xs,M), X >= M. /* si no hay elementos duplicados no hace falta el = */ maximo_entero([X|Xs], M) :- number(X), maximo_entero(Xs,M), X < M. 7) Optimice (este paso es sólo para programadores expertos) Lo que sigue es una mera optimización, que no altera el resultado del predicado, sino que recorta el árbol de búsqueda en situaciones específicas. Básicamente uno debe preguntarse en cada cláusula si luego de haber llegado hasta allí tiene sentido encontrar soluciones alternativas. Si no hay manera de encontrar soluciones alternativas, entonces no tiene sentido usar el backtracking para volver a dicho punto. La forma que tenemos de recortar o podar el árbol de búsqueda es mediante el cut que se representa con el signo !. - Si la lista tiene un único elemento, ese elemento es el mayor, y no hay otra manera de conseguir una solución alternativa. Entonces la primer cláusula puede quedar: maximo_entero([X], X) :- !, number(X). - Si la segunda cláusula determina el mayor número, entonces no hay manera de obtener soluciones alternativas, con lo cual se puede agregar el cut al final, de la siguiente manera: maximo_entero([X|Xs], X) :- number(X), maximo_entero(Xs,M), X >= M, !. Note que tanto en prueba_11/0 como en prueba/4 se ha usado el cut luego de la llamada a maximo_entero/2: esto es razonable porque estamos usando esos predicados de prueba de manera que si maximo_entero/2 acierta se escribirá en pantalla lo que dice el write/1 que le sigue, y si maximo_entero/2 falla, entonces el motor de Prolog ejecutará la siguiente cláusula que pone el mensaje de 'fallo' en pantalla. EOF