08.14.09
Principia ha muerto
Si necesitabas usar un programa al estilo del que se estaba creando, quizás te sirva la web http://www.wolframalpha.com/ Muchas veces muestra una opción “show steps” que muestra los pasos intermedios.
Gracias por tu visita.
03.17.09
Visión general de Principia
Llevo tiempo sin tocar el proyecto por una mezcla de desmotivación y de falta de tiempo. Ahora que he vuelto a mirar el código me he sorprendido de lo poco que me acordaba sobre cómo he hecho las cosas, ¡menos mal que todo está bien comentadito! Realmente creo que es la primera vez que he visto hasta qué punto es imprescindible comentar y documentar.
Al abordar de nuevo el código “desde la distancia”, he conseguido ver de una vez por todas qué es Principia. Parece raro, pero me puse a programar con una vaga idea de lo que quería, porque tampoco sabía qué era posible y qué no, ni qué era fácil y qué era difícil, así que el programa ha ido tomando forma; a pesar de todo ha quedado bastante ordenadito.
La idea original era hacer una especie de libro de ejercicios resueltos interactivo: el usuario introduciría un enunciado, y el ordenador lo resolvería con una “explicación”; por otro lado, un usuario experto en una materia (¿profesor?) debería definir unos axiomas, unos pasos, y unas condiciones de terminación para cada tipo de ejercicio. Por supuesto todo esto hay que enfocarlo de un modo realista y no demasiado complicada (¡que está uno empezando a programar!), y es en ese sentido que el programa ha ido tomando forma.
¿Qué es Principia hoy?
En dos palabras: un trasformador.
El usuario experto (¿profesor?) define una lista de trasformaciones, que podríamos interpretar como “si en la expresión introducida hay alguna parte de la forma F1, entonces sustituye esta parte por una expresión de la forma F2″, donde F1 y F2 son dos expresiones. Una vez definidas esas trasformaciones, cualquier otro usuario puede introducir una expresión y el ordenador mostrará el resultado final de haber trasformado la expresión todas las veces posibles, además de los pasos intermedios para llegar a dicho resultado.
Limitaciones
- ¿Existen ejercicios que no se puedan solucionar siguiendo una lista de trasformaciones?
- Es posible que el resultado final pueda variar según el orden en que se apliquen las trasformaciones. El programa solo muestra el resultado de haberlas aplicado recursivamente en el orden en que fueron escritas.
- Sin embargo, sería muy fácil (cuestión de minutos) modificar el programa para que se muestre el resultado de aplicar las trasformaciones en otro orden si fuera necesario. No se permite tan solo por no complicar el uso del programa con más opciones.
- Actualmente, las trasformaciones no pueden contener patrones aritméticos.
- Ejemplo: no se puede definir una trasformación del tipo “2n -> 2n+1″ para que sume uno a todo número par (solo conseguiríamos que sustituya partes de expresiones donde aparezca explícitamente el 2)
- En este momento no se definen condiciones de terminación. Eso significa que el ordenador aplica las trasformaciones de manera recursiva y regurgita lo que quede:
- Si el resultado buscado era un paso intermedio, no para ahí sino que continúa hasta que no se pueda aplicar ninguna trasformación.
- Esto también aumenta la probabilidad de definir una lista de trasformaciones que produzca bucles infinitos.
- Si las trasformaciones no conducen al resultado buscado, el programa no avisa.
- Si el resultado buscado era un paso intermedio, no para ahí sino que continúa hasta que no se pueda aplicar ninguna trasformación.
Aplicaciones
En su estado actual (alfa1) es difícil imaginar aplicaciones más allá de lógica proposicional: encontrar la forma clausulada de una expresión (lista de cosas que se pueden deducir de ella), o su forma NAND, o su minterms, etc.
En cambio, añadiendo la posibilidad de usar patrones ariméticos en las expresiones podría aplicarse a las ciencias exactas en general; o también a la verificación de expresiones en Haskell: detectar si las mónadas cumplen las famosas leyes es algo que no suele hacerse por engorroso. En este momento no sé cómo incarle el diente a esto de los patrones aritméticos, y en realidad creo que hasta viene bien que el programa madure un poco en el ámbito de la lógica proposicional primero.
Futuro de Principia
Darlo a conocer es el paso que hay que dar ahora. La posibilidad pasa por traducir toda la documentación y todo el código al inglés, ya que no veo que haya comunidad alguna en torno a Haskell en español (algo hubo por 2006, pero parece muerta). Ésto es además experanzador respecto a usar patrones aritméticos en las trasformaciones: Haskell los usa, así que tiene que haber alguien que sepa como aprobechar ésta característica del lenguaje o cómo duplicarla.
12.30.08
Mónadas: documento informativo en la forja
Las mónadas son una clase de tipo de datos abstracto que se utilizan para tratar datos de forma indirecta. Suelen utilizarse 3 operaciones para manejarlos:
- fmap (o también liftM): introduce una función en una mónada. Cada mónada hará una cosa distinta con la función, pero lo más normal es que la aplique al dato o los datos que encapsula. Ejemplos:
- fmap (*2) [1,2,7] == [2,4,14]
- fmap (*2) (Just 5) == Just 10
- fmap (*2) Nothing == Nothing
- join: simplifica una mónada que tenga dentro otra mónada del mismo tipo. Su comportamiento se define de forma distinta en cada mónada. Ejemplos:
- join [[5,4],[7,2,9]] == [5,4,7,2,9]
- join (Just (Just 5)) == Just 5
- join (Just (Nothing)) == Nothing
- (>>=) : se puede definir como m >>= f = join (fmap f m) o de manera directa. Como puede observarse, se parece a fmap (aplica una función f a la monada m), pero con la particularidad de que la función f ha de devolver una mónada. La función f puede verse como un valor monádico que depende de un valor de m; este punto de vista se utiliza para simular programación imperativa, por lo que a veces se dice que >>= es “un punto y coma programable”.
En Principia ya se usa una mónada: Traza. Si envolvemos un valor en una traza, al aplicarle una función se guarda también el valor anterior (en realidad, en Principia Alfa1 no funciona de forma tan automática ni guarda exactamente eso).
Hay otra buena candidata a mónada, aunque necesitaría una buena remodelación, Expresion; pero no le veo la utilidad clara, ni la manera de plantearlo. Creo que es mejor candidata a flecha, un tema que quiero estudiar antes de hacer modificaciones importantes en la estructura de Principia, porque veo muy posible que resulte práctico.
He añadido a la sección Documentos de la forja, una exposición sobre el uso y la creación de mónadas. La he escrito en inglés porque se la envié a alguien con quien me comunico en ese idioma. De todos modos, a medio plazo pienso traducir Principia al inglés, tanto código como documentación; así podré informar a la comunidad que hay en torno a Haskell (que yo sepa, toda ella en inglés) sin que caiga en saco roto .
12.28.08
Principia Alfa1: programa y documentación
Hoy se ha publicado:
- La primera versión alfa del proyecto.
- Documentación para el usuario final.
- Documentación para los desarrolladores.
En el blog he añadido enlaces a todo ello. También he añadido un bonito efecto de nueve navideño, aunque le va a durar pocos días.
12.24.08
Recortes de código, y un poco de Haskell
En la forja de RedIRIS hay un apartado que me parece muy útil, aunque un poco desierto: Recortes de código. He añadido el módulo Algoritmos a esa sección.
El módulo Algoritmos es el lugar donde se almacenan algoritmos de propósito general, implementados como funciones de orden superior. Por el momento contiene un algoritmo voraz (que de momento no se ha usado en Principia) y un algoritmo de vuelta atrás.
Las funciones de orden superior son las que tienen como parámetros otras funciones; por ejemplo, el algoritmos de vuelta atrás lo escribo como una sola función así:
vueltaAtras :: (a->Bool) -> (a->[a]) -> (a->Bool) -> a -> [a] vueltaAtras valido hijos condicionesDePoda ensayo | valido ensayo = [ensayo] | otherwise = [nodo| hijo<-hijos ensayo, condicionesDePoda hijo, nodo<-vA hijo] where vA = vueltaAtras valido hijos condicionesDePoda
Voy a aprovechar éste código para comentar algunas cosillas de Haskell.
Línea 1
Indica de qué tipo es la función; su signatura. No es obligatorio escribirlo, pero evita errores. El tipo de cada parámetro está separado de los demás por una flecha; salvo la última de ellas, que separa los parámetros de la salida. Un ejemplo más simple sería:
f :: a -> Bool
donde se está indicando que “f” es una función que, dado un parámetro de cualquier tipo, devuelve un valor booleano. “a” representa a cualquier tipo, por lo que podría considerarse una variable cuyos valores son tipos. Así se indica el polimorfismo.
En el caso de vueltaAtras, el parámetro “válido” es una función del mismo tipo que f; así, con los paréntesis en la signatura, se expresa que vueltaAtras es una función de orden superior.
Líneas 3 y 4
Según si el ensayo es válido o no, la función se define de forma distinta. El valor absoluto de un número podría definirse como:
valorAbsoluto x
| x >= 0 = x
| otherwise = -x
Línea 4
Aparece una lista comprensiva, un formato muy práctico para definirlas. La notación es muy parecida a la usada en matemáticas para conjuntos. Por ejemplo, los números pares podrían expresarse como,
todosLosPares = [n| n<-[1..], even n]
o incluso como,
todosLosPares' = [2*n| n<-[1..]]
Los conjuntos equivalentes habrían sido {n|n<-[1..infinito), n par} y {2*n|n<-[1..infinito)}. Como es evidente, [1..] representa todos los números enteros del 1 en adelante. Se trata de listas infinitas, pero están permitidas en Haskell, y en ocasiones es muy cómodo tener esa posibilidad.
Para saber más sobre Haskell, un manual muy bueno que hay desde hace poco y con licencia Creative Commons es Real World Haskell, aunque para nosotros tiene la pega de estar en inglés.
12.23.08
Otro propósito de Principia
Otro propósito de Principia: que cualquier usuario pueda añadir ejercicios
Los ejercicios que no podrá resolver Principia serán: la mayoría. Como cualquier otro programa de éste tipo, por mucho esfuerzo que se ponga en que pueda resolver muchísimos seguirán siendo minoría. Sería un desperdicio que alguien no pudiera usar Principia solamente porque ese tipo de ejercicio para el que lo quiere usar no ha tenido la fortuna de estar entre los elegidos por el programador.
Ésta reflexión se puede generalizar: por mucho código que se cree, siempre faltará algún algoritmo o algún tipo en el que basarse para resolver algún ejercicio. Por eso el nombre de Principia, para evitar la tentación de crear un programa de lógica muy grande pensando que así podrían resolverse ejercicios de física sin modificar nunca el programa.
La solución (hasta el límite de lo posible) para ambas cosas es que cualquier añadido se haga en Haskell, usando el resto del programa como una librería que dé hechas muchas cosas. Así será. Sin embargo, para facilitar las cosas a la gente que no sabe Haskell, se intentará que muchos ejercicios puedan definirse con poco más que añadir unos axiomas en una plantilla.
Por cierto que al principio pensaba crear otro lenguaje para ésto, pero es un poco absurdo hacerlo, porque Haskell ya tiene un aspecto bastante matemático, y todo lo que sea crear otro lenguaje para que después lo use Haskell sería limitar las posibilidades.
12.22.08
Simplificación por axiomas: casi hecho
Escribir el anterior post me aclaró las ideas. Ya puedo dar un ejemplo de ejecución real (faltan los pasos intermedios, pero no creo que eso me lleve mucho tiempo).
Partimos de unos operadores AND OR y NOT, y de dos axiomas:
axiomas = [ (Op NOT [Op AND [Var "p",Var "q"]] ,
Op OR [Op NOT [Var "p"],Op NOT [Var "q"]]),
(Op NOT [Op NOT [Var "p"]],
Var "p") ]
De momento estoy utilizando expresiones muy generales para que abarquen todos los ámbitos posibles. Cuando se particularice para lógica (o para aritmética…) se adaptará para que sea más legible. Por el momento lo traduzco a mano; los axiomas son:
- ¬(p^q) <-> ¬p v ¬q [no (p y q) "equivale a" no p o no q]
- ¬¬p <-> p [no (no p) "equivale a" p]
El programa asume que la segunda forma de la equivalencia es la que deseamos tener. Con esos datos se obtiene, por ejemplo, siendo test1 (a v ¬(b ^ ¬c):
Operador> simplificar axiomas test1
[Op OR [Var "a",Op OR [Op NOT [Var "b"],Var “c”]]]
Traduzco; simplificar axiomas test1 es una función con dos parámetros que devuelve una sola forma simplificada (a priori podría haber más): a v (¬b v c) . Se llama desde un módulo Operador que he usado solo para el ejemplo.
Subversion me está dando un poco de lata. Hasta que aprenda a manejarlo con más soltura, las últimas novedades del blog pueden no estar reflejadas en la forja.
12.21.08
¿Qué falta?
¡Muchas cosas! xD Pero lo más inmediato es:
- Añadir funciones al módulo Expresion.
Ya hay una función tieneForma que dice, por ejemplo, que (x-y)+z tiene forma a+b; y una función tieneForma’ que además devuelve el valor que tendría cada variable de la forma (en este ejemplo: “a=x-y” y “b=z”). Ahora falta usarlas para transformar la forma de una expresión, como por ejemplo en los ejercicios de escribir una sentencia en forma clausulada; ésto abrirá las puertas para el uso de axiomas en los cálculos. - Hacer otro módulo que utilice a los anteriores para algún fin concreto (por ejemplo, pasar a forma clausulada), definiendo los operadores, la función eval y/o los axiomas necesarios.
12.20.08
¿GHC o Hugs?
Hugs tiene algunas limitaciones respecto a GHC: no se puede hacer que los módulos se importen de forma recursiva (algo a evitar, pero que en la práctica ayuda de vez en cuando siempre que se haga de forma temporal), no encuentro el modo de acceder a módulos que estén en otro directorio, no trae añadidos interesantes de GHC (como un debugger, o una utilidad para ver a fondo cómo de eficiente es el programa), y de vez en cuando aparece un bug con tipos monádicos (aunque fácil de sortear, y que podría no estar en la última versión de Hugs, solo que yo uso la que trae la distribución estable de Debian).
Aún así, Hugs tiene una diferencia importante respecto a GHC, que a veces es muy ventajosa: es un interprete, no un compilador. Cierto que GHC trae GHCi, que permite hacer todo lo que se puede hacer con Hugs, pero nunca con la velocidad de Hugs. [Nota a 6 de Enero de 2009: hay ocasiones en que efectivamente es lento en arrancar (unos segunditos), pero es algo más bien raro; parece que aquel día tuve mala suerte con las pruebas que hice. A día de hoy, recomendaría GHC].
Cuando uno está programando, si puede comprobar rápidamente si el último cambio que ha hecho funciona, entonces lo prueba. Si no lo va a poder comprobar tan rápidamente, lo deja para más adelante, cuando haya más cambios. Esto es un lastre de GHC, y hacer el código incompatible con Hugs obligaría a todo el mundo a llevarlo encima.
Creative Commons: reconocimiento - sin obras derivadas. Autor: It'sGreg (click en imagen)
Otra consecuencia, quizás más importante, es el modo en que se va a hacer público el programa. Con el intérprete (Hugs) tan solo habría el código fuente, y se le pediría al usuario que descargara el interprete. Con el compilador (GHC) habría que publicar además unos binarios, y en ese caso sería eso lo que la gente descargaría normalmente. La consecuencia es clara: con Hugs se está facilitando que quien descargue el programa “curiosee” el código y añada algo, porque tiene descargadas en el ordenador todas las herramientas necesarias.
Hay una última ventaja para Hugs, y es que se puede aprovechar el propio intérprete como interfaz con el usuario, sin tener que crear una nueva. En el futuro, muy en el futuro, podría ser interesante añadir cosas (por ejemplo, un modo ventana), pero hasta entonces Hugs puede ser incluso mejor solución. GHCi hace lo mismo, pero no creo que guste la idea de hacer descargar un compilador para ejecutar unas fuentes, en lugar de dar el binario: daría la impresión de programa incompleto, y está de nuevo el tema de la lentitud de GHCi (para éste propósito, solo al iniciar).
Por todo ello, me he decidido por Hugs, como estaba desde el principio. Pero con cuidado de que, si se introduce algo que no funcione en GHC, debe modificarse para que se puedan utilizar esporádicamente las ventajas de éste compilador durante el desarrollo. De todos modos es muy improbable que algo escrito en Hugs no funcione en GHC, ya que Hugs es más limitado y los dos respetan el estandar Haskell 98 si no se usan las extensiones. Lo arriesgado sería lo contrario, hacer código GHC compatible con Hugs.
12.19.08
Run Principia (Enter)
Hasta ahora lo que he hecho casi se puede resumir en una palabra: estudiar. Estudiar Haskell, mónadas y un poco de Subversion. No sé como me atreví a elegir Haskell para el proyecto, ¡si no sabía nada de ese lenguaje al empezar el concurso! xD
Pensé que no tenía nada que escribir en el blog, puesto que no estaba haciendo código, pero ahora he pensado que, ya que muchos programadores no conocen Haskell, podría escribir un poco sobre éste lenguaje funcional. Lo haré más adelante, ahora voy a hablar un poco sobre lo que hay hecho y lo que quiero del proyecto. Para saber más, click aquí (me acabo de dar cuenta de que no está el enlace a la derecha, lo añado en cuanto pueda).
Creo que la mejor manera de entender de que va éste programa es con un ejemplo de ejecución (entiéndase como una declaración de intenciones, no como una ejecución real a día de hoy):
(trazaInversa.eval) (True AND ((True AND True) AND False) )
Salida:
True AND ((True AND True) AND False <=> False
(True AND True) AND False <=> False
True AND True <=> True
Uno de los propósitos del proyecto queda claro: no solo se trata de que salga “False”; se trata de que si no se entiende directamente, se pueda seguir leyendo pasos más pequeños.
Creí que ésto iba a ser muy difícil de conseguir, pero hay una herramienta matemática que en Haskell se usa mucho, las mónadas. Cada mónada es un tipo de datos (normalmente abstracto) que contiene a otros tipos; lo más importante sobre ellas es que sirven para contener datos y para añadir efectos secundarios a las operaciones que se hagan sobre esos datos.
Con ellas, uno puede ocuparse de crear la función eval casi olvidándose por completo de que la mónada se encarga de ir guardando la traza. Esto hace que, sea muy fácil modificar de forma independiente el código relacionado con la traza y el código relacionado con el cálculo del valor de la expresión.
Puede leerse más sobre las mónadas en éste artículo de la Universidad de Glasgow. La mónada Traza que utilizo en Principia es una modificación de una de las que ahí aparece. Creo que, al tratarse de un artículo académico, ésto no provoca ningún problema de licencia; si no, no podríamos aplicar a ningún programa casi nada de lo que aprendiéramos en la universidad 
Además, es una mónada “con nombre propio” (Traza) altamente utilizada y divulgada.
