Lapsus: anatomía de un corrector ortográfico VII

Hay otros métodos de corrección ortográfica, de los cuales me gustaría hablar. Uno de ellos es en base a las posibles sílabas legales que se presentan en el español. La idea es muy simple: se toma una palabra, se analiza y se descompone en sílabas y se busca si hay alguna sílaba que no sea legal, que no corresponda al español. El problema aquí es saber ¿cuáles son las sílabas legales del español? ¿Dónde podré hallar semejante lista?

Hurgando en la red (otros dicen "navegando"), hallé este sitio, el cual asegura haber hallado todas las sílabas legales del idioma castellano. Hasta donde entiendo, quien desarrolló este trabajo, lo que hicieron fue un programa para hacer la división silábica correcta de todas las palabras en español. Como las reglas de división silábica son muy específicas, es posible escribir un programa de esta naturaleza, asunto no muy complicado.

Una vez hecho esto, el o los investigadores hicieron una lista de todas las sílabas que hallaron utilizando para ello 36,070 textos de la enciclopedia Encarta (en español, evidentemente). Sin duda el trabajo empezó realmente después, pues hubo que depurar y además, hallar posibles errores. Hubo pues que hacer una buena labor de programación para automatizar este pesado trabajo de clasificación y no me cabe duda que el autor, Jerónimo Armario Toro, con Diplomado en Magisterio y Licenciado en Psicopedagogía, hizo un fuerte trabajo que sin duda vale la pena.

En el documento que presenta en la red, hallamos lo siguiente: "El objetivo principal de este artículo es el de hacer público el resultado de una investigación que nos ha llevado a realizar un listado, esperamos que totalmente completo, de todas las sílabas del español. En efecto, este listado de sílabas será lo que presentemos en subsiguientes entregas, ordenadas convenientemente en una tabla en la que, debido a consideraciones de espacio, sólo aparecerán estas últimas sílabas, sin las palabras que las ejemplifican".

El autor presenta una tabla de las sílabas válidas del español, pero ¡ay! es una imagen y no un archivo de texto (o mejor aún, una tabla en Excel) que contenga esta información. ¿Por qué no dejó el enlace como un simple archivo .txt? En vista de esto, decidí tomar la tabla mencionada y transcribir todas las sílabas válidas del español. Cabe decir que cuando estaba pasando las sílabas a un archivo de texto, en muchas no hallé ninguna palabra que contuviera esa sílaba. Sin embargo, debido al tamaño de la empresa que realizó en investigador, no hubo lugar para ejemplos de muchísimas de las sílabas. En principio, le creo que su trabajo es correcto, aunque habrá que contrastarlo más adelante con los documentos a corregir. A todo esto, el archivo de texto, con todas las sílabas de la tabla mencionada, se puede descargar de aquí.

Así entonces, el procedimiento de revisión de palabras, en una primera instancia es revisar si cada palabra del texto a corregir tiene sílabas válidas. Si no es así, ya no tenemos que buscar en diccionario alguno porque podemos asegurar que la palabra en cuestión está mal escrita. En caso de que la palabra a revisar esté correctamente en términos de sílabas válidas, tendremos que pasar a buscar en un diccionario o usar alguna otra técnica de corrección.

Cabe señalar que Andrés Aldana, mi ayudante en la UNAM, me mandó una serie de sílabas válidas en el español, que halló en este sitio. Este archivo puede bajarse de aquí. Nótese lo que dice el autor de esa página:

Para evitar duplicidades, hemos clasificado las sílabas por fonética, de manera que hemos sustituido algunas sílabas por otras:

•     "ce" por "ze".
•     "ci" por "zi".
•     "ve" por "be".
•     "h" por "(cádena vacia)".
•     "gue" (de guerra) por "ge".
•     "ge" (de geranio" por "je"
•     "ca" (de casa) por "ka".
•     No se tienen en cuenta los acentos.
•     Sílabas como "rio" (imperio) y "rrio" (me rio de algo gracioso) se consideran diferentes.
•     Etc etc etc...

Debe entenderse que un corrector ortográfico es tan bueno como su capacidad de corrección. Un corrector que se le vayan algunas palabras desmerece en su desempeño y entonces ¿cómo podríamos garantizar que los documentos que revisamos están correctos? El asunto es que un verdadero corrector no puede pasar nada por alto.

Proyecto con un microcontrolador Pic: un reloj de ajedrez

Los microcontroladores no son otra cosa que computadoras en miniatura. A diferencia de los microprocesadores, que requieren de todo un complejo sistema de electrónica para funcionar, el microcontrolador contiene todo lo que una moderna computadora necesita: puertos de entrada y salida, memoria interna, convertidores analógico-digitales, etc. Estos microcircuitos son parte de hornos de microondas, lavadoras, refrigeradores, reproductores de mp3, algunas cafeteras, etc. Son en cierta medida computadoras en miniatura para usos muy específicos. Ya he hablado de ello antes. Si buscan "microcontrolador" en este blog, podrán ver algunos artículos míos pasados al respecto).

Como los microcontroladores son computadoras en miniatura, éstas deben poderse programar. Para ello, se necesitan algunos elementos:

• Una tarjeta (un circuito impreso que contenga al microcontrolador, botones, leds, pantalla de cristal líquido LCD, en la cual podemos ver  el funcionamiento del programa que estamos escribiendo.
• Un editor de código con su correspondiente compilador (hay C, basic, e incluso Forth).
• Una interfaz (que es una caja negra), que vía el USB conecta la tarjeta de desarrollo con la PC y los programas compilados se pueden pasar a la memoria del microcontrolador. Eso es lo que se llama un "programador de microcontroladores".

En mi caso, trabajé con una tarjeta con un microcontrolador Pic y usamos el Pic Basic Pro (PBP) como lenguaje de desarrollo. Cabe decir que algunos compiladores tienen costo. No todos son gratuitos, aunque existen interesantes alternativas en ese sentido.

Usando todos los elementos, es decir, creación del programa, compilado del mismo, uso del programador PicKit2 para copiar el código a la memoria del PIC, traslado del chip a la tarjeta de prácticas, cableado de las patas correspondientes del microcontrolador a los leds y al botón que usaremos para controlar el despliegue (encendido y apagado de LEDs), tenemos un programa que hace exactamente lo que le pedimos, como puede verse en este video, lo cual es un programa que a través de los leds de la tarjeta de prácticas, cuenta en binario encendiendo los foquitos leds al oprimir el botón.

Las capacidades de los microcontroladores lo hacen el candidato justo para una serie de proyectos de electrónica, en donde precisamente la parte del hardware puede obviarse. Por ejemplo, se me ocurrió que sería interesante hacer un reloj de ajedrez electrónico. Los relojes de ajedrez son dos cronómetros que llevan el control de tiempo para pensar las jugadas por cada jugador. Actualmente estos relojes electrónicos ya existen pero quizás su costo es elevado (unos 1000 pesos más o menos). Así, me di a la tarea de diseñar mi propio prototipo.

Le pedí a un ingeniero en electrónica que me hiciese el circuito impreso con los elementos que necesitaba: una serie de botones y una pantalla de cristal líquido. En el caso del prototipo, el “display” es de cuatro líneas. Si el proyecto tiene éxito y se sigue a una fase de comercialización, se tendría que poner en una pantalla más adecuada para la naturaleza del ajedrez (números más grandes, por ejemplo). Pero por el momento un prototipo no necesita de más cosas.

He escrito parte del software ya, pero hay muchos detalles que pulir. Lo importante aquí es que el proyecto se puede desarrollar de manera fácil y simple, porque finalmente es como programar una computadora -pero de uso específico- con limitaciones en capacidad de memoria, despliegue, etc. Se parece en ese sentido a programar un teléfono con iOS o Android, por ejemplo. Seguiremos informando de los avances de este proyecto.

Lapsus: anatomía de un corrector ortográfico VI

Un corrector ortográfico tiene otras dificultades a resolver. Una de ellas es si el programa será implementado como una aplicación independiente o si bien, interactuará con algún otro sistema. En la primera versión de Lapsus, la cual se escribió en Turbo Prolog 2.0, de Borland, el sistema contenía su propio editor de textos, es decir, quien usara el software estaba obligado a escribir sus documentos en el editor que yo proveía. Sin embargo, es claro que este enfoque tiene una oposición importante: es difícil que la gente cambie el editor de palabras que use por utilizar la herramienta de corrección ortográfica, aunque ésta suene muy poderosa.

Debido a esto, decidí entonces hacer que Lapsus corriera como una aplicación que se pegaba de alguna manera a MsWord, que es el procesador de palabras que la mayoría usa, pues la suite informática de Microsoft es muy popular. Entonces, habría que ver cómo enlazar ambas aplicaciones, por una parte MsWord y por otra Lapsus, para que ambas de platicaran y se intercambiaran información.

La idea básica era simple: Úsese Word y Lapsus -ya ejecutándose- estará al pendiente de cada palabra que se escriba, la cual será enviada al corrector para evaluar si está bien o mal escrita y si se encuentra algún error, mándese algún mensaje de error (desde Lapsus), que permita al usuario hacer la corrección correspondiente.

La idea es simple pero la implementación de la idea no lo fue. Por una parte, había que ver qué mecanismos permitían entablar un proceso de comunicación entre ambos programas. Hallé que Windows tiene un mecanismo llamado DDE - Data Dynamic Exchange, el cual permite intercambiar datos entre aplicaciones.

De acuerdo a la Wikipedia: Dynamic Data Exchange(DDE) es una tecnología de comunicación entre varias aplicaciones bajo Microsoft Windows y en OS/2. Aunque es apto para las últimas versiones de Windows, ha sido reemplazado por su mucho más poderoso sucesor Object Linking and Embedding, COM y OLE Automation. Sin embargo, todavía se usa en varios sitios dentro de Windows, por ejemplo en la asociación de archivos. En particular, DDE permite que una aplicación abra una sesión con otra, enviar comandos al servidor de aplicaciones y recibir respuestas. Sin embargo, este no permite incorporar una interfaz del servidor dentro de la aplicación cliente, tampoco soporta la incorporación de un servidor de datos dentro del archivo cliente (por ejemplo: almacenamiento estructurado); y para usar DDE se tienen que conocer los comandos de DDE que el servidor soporta, lo cual no ha sido generalmente estandarizado (si bien existieron algunos estándares, como la especificación spyglass para navegadores web), Así, para emplear toda la funcionalidad del DDE, se debe agregar código especial en cada aplicación cliente para cada servidor que este quiera controlar, o la aplicación cliente debe facilitar un lenguaje de script o macro. Un uso común de DDE fue para desarrollar aplicaciones personalizadas para controlar software disponible, ejemplo: un aplicación escrita en C o algún otro lenguaje debía usar DDE para abrir una hoja de cálculo Microsoft Excel y llenarla con datos, por medio de una conversación con Excel y el envío de comandos DDE. Sin embargo, hoy se usa el modelo de objeto de Excel con OLE Automation (automatización OLE) (esto es una parte de COM). Windows tiene la habilidad de llamar NetDDE, el cual posibilita que los mensajes DDE sean enviados entre aplicaciones que corren en máquinas diferentes. Su uso es raramente utilizado, pero todavía tiene soporte. El cuaderno de Microsoft (Microsoft Clipbook) y el juego de cartas Corazones (Microsoft Hearts) son algunas de las aplicaciones que usan NetDDE.

Cabe señalar que DDE además, resulta un monstruo difícil de enfrentar. La documentación: unos 60 megabytes, es oscura e impenetrable. Cuando hice mis primeras pruebas de Lapsus con DDE hallé que una vez no funcionaba bien y otra vez tampoco. Aparte de oscuro resultó francamente inestable. Así que después de unos meses de padecer a DDE me declaré incompetente (o lo declaré más bien incompetente) y decidí buscar otra opción.

Por suerte hallé que OLE automation es la solución a muchas de las dificultades. El protocolo de comunicación entre procesos es mucho más claro y además, para Office ya está implementado en muchísimas plataformas, inclusive Delphi. Curiosamente los ejemplos que hallé sobre cómo pasar una palabra desde Word a Lapsus y regresarla corregida son inexistentes. Hay muchos ejemplos de cómo hacer para que Word, a través de una aplicación en Delphi, abra el menú para leer un archivo, o para guardarlo, pero nada de la manipulación de las palabras.

Buscando en la red hallé que la revista Delphi Informant (septiembre y octubre del 2000), traía probablemente esa información. Y aunque la revista había desaparecido, estaba a la venta el CD con todos los artículos en PDF. Tuve dificultades con los que venden el CD (ya lo mencioné en algún artículo pasado), pero finalmente me hice de esos artículos y entonces Lapsus podía entonces cobrar vida, pues la parte medular había sido resuelta.

Ya hablaremos más adelante de los detalles al respecto.

Lapsus: anatomía de un corrector ortográfico V

La búsqueda binaria

Una de las cosas que hacen inevitablemente los correctores ortográficos es buscar en un diccionario si la palabra que buscan existe. Es claro que hay diferentes técnicas para hacer estas búsquedas, pero sin duda la más eficiente es la llamada "búsqueda binaria".

Por ejemplo, supongamos que tenemos 1000 palabras. Asumamos que la lista está desordenada. ¿Cuántas búsquedas tengo que hacer? A lo más 1000, porque la palabra que buscamos pudiese ser la última de la lista. Ahora bien, supongamos que la misma lista está ordenada alfabéticamente, de la A a la Z. ¿Cuántas búsquedas tengo que hacer? 10, porque lo que hacemos es dividir y conquistar, algo así como el procedimiento común que usamos cuando queremos hallar una palabra en un diccionario físico, real: Lo abrimos a la mitad y vemos si ya nos pasamos (es decir, la palabra que buscamos tiene que estar antes), o bien, nos quedamos cortos. Si nos pasamos, tomamos la primera mitad y volvemos a dividir en dos. Vemos de nuevo si nos pasamos o no. Hacemos este procedimiento hasta ver si  está la palabra que buscamos. (La ilustración al inicio de este artículo muestra este procedimiento al tratar de ver si el número 3 está en una lista ordenada de números).

Tratar de encontrar una palabra usando una búsqueda binaria es lo más eficiente, pues a cada paso se van eliminando la mitad de los elementos por  analizar. Por ejemplo, para el caso de un diccionario con 50 millones de palabras, hay que hacer solamente 26 búsquedas. El orden del algoritmo de la búsqueda binaria es logarítmico, es decir, el numero máximo de elementos que consultas es 2 elevado a la n, donde n es el numero de elementos en total.

En una búsqueda elemento por elemento, el orden es N, porque en el peor de los casos, hay que recorrer todo el arreglo para encontrar el elemento (o para verificar que el elemento no existe). En cambio en la busqueda binaria, si se tienen N elementos, en la primera consulta se selecciona N/(2^1) elementos, en la segunda N/(2^2) elementos (queda entonces un cuarto del arreglo por buscar), en la tercera N/(2^3)... así hasta que N/(2^x) sea cero. En otras palabras 2^x > N. donde x es el numero de búsquedas que se realizaron, y vale aproximadamente log2(N+1), que es de orden logaritmico.

Para ilustrar el asunto, muchas veces le pregunto a mis alumnos ¿cuántas búsquedas tienen que hacer si el diccionario tiene 1000 palabras? Alguno responde bien: unas 10. ¿Y si tienen 2000 palabras? Ya algunos se confunden, pero la respuesta correcta son 11 búsquedas. ¿Y si tengo 4000 palabras? 12 búsquedas serán suficientes. Cada vez que duplico la cifra, tengo que aumentar una búsqueda. No creo que exista en este rubro algoritmo más eficiente, amén que encaja perfectamente para el problema de la corrección ortográfica.

Funciones de Hash

Otra alternativa son las funciones de hash. En este caso hablamos d eun  algoritmo o subrutina que mapea un conjunto grande de datos a uno más pequeño, llamado llaves. En el caso de un diccionario, podríamos tomar cada palabra y aplicarle una función que nos regresara un número entero. Así, podríamos usar ese número como un índice en un arreglo para ver si la palabra que está ahí es la que buscamos.

Veamos cómo funciona esto. Asumamos que nuestra función de hash es la suma de los caracteres de la palabra. Para hacerlo más fácil, asumamos que la A es 1, la B es 2, la C es 3, y así sucesivamente. Tomemos por ejemplo, la palabra ROMA. Aplicando la función de hash obtendremos:

R(18) + O(15) + M(13) + A(1) = 47

Ponemos entonces la palabra ROMA en el casillero 47. Así, si busco esa palabra, le aplico la función de hash y me voy al casillero 47 y listo, solamente hice un acceso al diccionario. 

El problema es cuando tenemos otra palabra como AMOR, anagrama de ROMA. En este caso, la función de hash de AMOR será:

A(1) + M(13)+ O(15) + R(18) = 47

 

de nuevo 47. Aquí tenemos lo que se llama una colisión (dos palabras quieren ocupar el mismo casillero). Cuando esto pasa con demasiada frecuencia, es decir, cuando hay muchas colisiones, es momento de buscar una mejor función de hash, aunque hasta donde entiendo, no hay una función que no tenga colisiones. El asunto es minimizar esto y manipular el problema de las colisiones con una lista ligada, por ejemplo. Modos de tratar las colisiones hay muchos, algunos más eficientes que otros, pero finalmente para resolver esto requerimos de tiempo de procesamiento.

Por ejemplo, para evitar las colisiones con nuestra función de hash original, podríamos agregarle peso a la posición de las letras, así multiplicamos por 1 al valor de la primera letra, 2 al valor de la segunda letra, etc. Y con ello resolveríamos el problema de los anagramas, que siempre dan la misma función de hash. En el caso de ROMA y AMOR tendríamos:

Para ROMA:

R(18)(1)+ O(15)(2) + M(13)(3) + A(1)(4) = 

 

R(18) + O(30) + M(39) + A(4) = 91

para AMOR:

A(1)(1) + M(13)(2)+ O(15)(3) + R(18)(4) = 

 

A(1) + M(26)+ O(45) + R(72) = 144

Así evitamos la colisión de ambos anagramas, pero es probable que nuestra función sea muy elemental igualmente y conlleve colisiones con otras palabras. Por ello mismo me inclino a no usar funciones de hash en este problema y mejor aplicar la búsqueda binaria.

Lapsus: anatomía de un corrector ortográfico IV

 Una de las ideas ya bosquejadas aquí, para crear un corrector ortográfico que saque ventaja de todas las posibilidades que ofrece el español, es el usar un diccionario que contenga los verbos conjugados. Sabemos que cualquier diccionario contiene los verbos, pero en infinitivo. Así, si en un texto un verbo está conjugado (cosa que fácilmente suele suceder), entonces no podremos checarlo usando el diccionario principal de palabras. Por ende, hay que crear un diccionario con cada verbo conjugado.

El español, de acuerdo al pequeño manual Larousse de la conjugación, contiene unos 10,000 verbos, pero muchos no son regulares, es decir, tienen excepciones en sus maneras de conjugarse. El manualito en cuestión pone todas las posibles conjugaciones para cada verbo regular e irregular. En total -según recuerdo- hay unas 101 diferentes formas de conjugar verbos, lo cual implica que los verbos regulares terminados en ar, er e ir y además 98 otras conjugaciones para los verbos irregulares.

 Dar click en la imagen para ampliarla

Hacer un diccionario con todos los verbos implica por el momento un trabajo manual de mucho tiempo, el cual no tengo. Así que decidí entrar a Internet y ver si había una lista de verbos regulares al menos. Hallé en http://es.wiktionary.org/wiki/Categor%C3%ADa:ES:Verbos_regulares una buena lista de verbos regulares, cuya cuenta es de 2159. Si cada verbo puede generar unas 51 conjugaciones diferentes, tendremos 110,109 nuevas palabras que son simplemente los verbos conjugados. Podemos añadir esto a las diferentes técnicas de búsqueda. Evidentemente, en el caso de tener todos los verbos, regulares e irregulares, alimentados en el diccionario, estaríamos hablando de 510,000 palabras extras para buscar.

Escribí un programa que precisamente genera las palabras conjugadas y permite guardar el diccionario ya ordenado. Cabe señalar que antes de guardar la información al diccionario de verbos conjugados, éste se ordena alfabéticamente para después hacer una búsqueda binaria sobre éste. Hablaremos de eso en la siguiente entrega.

Lapsus: anatomía de un corrector ortográfico III

Escribir un corrector ortográfico es algo más que hacer una tabla de look up entre las palabras a analizar y un diccionario de las mismas. Los lenguajes humanos son muy sofisticados, con reglas, con excepciones, con un sinfín de recovecos que hacen de escribir un programa de esta naturaleza un interesante reto.

Consideremos a los usuarios que procesan textos con Windows. Suelen usar la mayoría la suite informática de Microsoft, Office, en muchas de sus versiones. Particularmente -desde luego- editan sus documentos usando Word para Windows.

Escribir un corrector ortográfico que contenga todo incluido, incluso un editor de textos no suena como la mejor idea, a menos de que funcionase y tuviese el mismo look & feel que Word para Windows. Escribir el procesador de palabras que funcione más o menos similar al de Microsoft puede ser una tarea muy ingrata. Mejor sacar ventaja de su uso incorporando el corrector ortográfico -Lapsus- como una aplicación que se liga a Word y que se comunica con éste, en donde Word manda las palabras a analizar a Lapsus y este último le responde precisamente con los mensajes de corrección ortográfica o bien, con una lista de palabras probables para la corrección.

Para que esto se pueda hacer, es necesario meterse en las entrañas de OLE, Object Linking and Embedded, que es el mecanismo de comunicación entre dos procesos que corren bajo Windows. Originalmente, cuado trabajé con la primera versión para Windows de Lapsus, usé la tecnología DDE (Data Dynamic Exchange), la cual tenía un manual de referencia por demás oscuro, nulos ejemplos, y que funcionaba una vez mal y otra también. Por ello, hasta que Microsoft no sacó OLE, el corrector Lapsus tenía muchísimas dificultades para correr ligado a Word y de hecho, se congelaba inesperadamente o bien, terminaba sin avisar, etc. Gracias a OLE, esos problemas desaparecieron.

Muchas herramientas de programación ya tienen incluido en sus bibliotecas de Windows, la que corresponde a OLE y Delphi no es la excepción. Como siempre pasa en estos casos, la referencia de Microsoft o es muy general o bien, muy específica a Visual BASIC o Visual C. Así, ejemplos de cómo echar a andar la biblioteca de funciones de OLE para Delphi parecía una labor complicada.

Hallé vía Google que en una revista que ya desapareció, Delphi Informant, tenía escritos un par de artículos de cómo ligar precisamente Delphi con otras aplicación a través de OLE. La única opción disponible era comprar el CD, con seis años de la revista en PDF (y una carpeta con todo el código fuente), por unos 40 dólares. El envío eran otros 20 dólares. Me animé pues el proyecto pensaba y sigo pensando, valía la pena. El susodicho CD no llegaba después de tres meses. Escribí a la revista y me dijeron que si no llegaba en esa semana me mandarían otro. Finalmente llegó, pero lo habían mandado por vía terrestre desde Sonora. ¿El costo del envío? Unos 3 pesos. Reclamé a la empresa que me vendió el disco indicándoles que el costo del envío era un robo, porque lo mandaban por vía terrestre y ya desde territorio mexicano. Me contestaron que ellos mandan los paquetes a su distribuidor en México y que se desentienden. Pedí el reembolso pero se negaron dármelo. Entonces les dije que repartiría el CD a todo aquel que lo quisiese (la oferta sigue en pie). Me dijeron que eso era ilegal. Les dije que el robo de lo que pagué por el envío era igual de ilegal. No me contestaron más. Así terminó esta fea historia, no sin antes aclarar que los artículos escritos en dicha revista sobre la conexión Delphi-OLE son magníficos y que valen la pena. Al término de estos artículos pondré disponible todo el material para quien se interese.

Pues bien, hallé que la comunicación de mi aplicación, Lapsus, con Word de Microsoft era muy simple usando OLE. A todo esto, muchos sitios en la red explican esto, pero en Delphi omiten partes por demás fundamentales que los artículos de Delphi Informant indican con precisión. Pienso que si se trabaja con Delphi, esta revista, lamentablemente ya desaparecida, tenía un buen caudal de información.

Con ello en mente, y ya habiendo probado que podía hacer "platicar"a Lapsus con Word, me di a la tarea de crear un primer menú con las opciones que el sistema debería tener. He aquí lo que esquematicé:

Dar click para ver en tamaño completo

En el siguiente artículo hablaremos de las opciones que el sistema tiene y ya nos adentraremos a analizar algunas partes del sistema que merecen más atención.

Lapsus: anatomía de un corrector ortográfico II

Las palabras con acento diacrítico

En el artículo anterior, hablamos de las características más importantes que un programa como Lapsus debe tener, que son -en principio- las diferentes estrategias para buscar palabras mal escritas. Sin embargo, hay que analizar otras cuestiones. Por ejemplo, las palabras que pueden tener un significado diferente y escribirse idénticamente, o bien, aquellas que de acuerdo al contexto tienen o no acento ortográfico.

Por ejemplo, "tú", como en la siguiente frase: "tú eres programador"; o bien "tu", como en "tu casa me gusta". Aquí, el acento ortográfico se pone si se habla del pronombre. Lo mismo pasa con "él" y "el". También tenemos el caso de "sólo" y "solo". Y aunque sé que la Real Academia de la Lengua Española ya parece haber relajado algunas reglas, el caso tradicional es que "sólo" lleva tilde en la primera "o" si se puede sustituir por el adverbio "solamente". En caso de hablar de "solo", como en la frase: "me siento solo", no se acentúa.

¿Cómo tratar con este problema. Para que el corrector ortográfico pueda corregir estos casos, requeriría de entender contextos y esto no parece ser algo que pueda hacerse fácilmente. Hay técnicas, que incluyen "tokenizar", es decir, poner cada palabra como un token, como una partícula y ver la siguiente partícula a ver si se da que es un token conocido. Por ejemplo, si escribimos: "¿Por qué la vida tiene que ser así de injusta?", habría que considerar el token que represente al signo de interrogación que abre, seguido de dos tokenes, valga la palabreja, que serían únicos: por y qué. En este caso podríamos decir que así está bien escrito, pero si ponemos: "¿Porqué la vida tiene que ser así de injusta?", ya en este caso tendríamos no tres tokenes, sino dos: el signo de interrogación que abre y el token porqué. Esto debería ser marcado como incorrecto.

Debido a que habría que definir estos tokenes y los casos de estas palabras en particular, el sistema tendría mucho más que analizar para poder decidir si está correcta o incorrectamente escrito. Una posible solución es simplificar el problema y mandar un mensaje de alerta cuando encontremos alguna palabra en este caso. Y sí, sé que ésta no es la solución perfecta, pero en muchos casos puede ser funcional en el sentido que la mayoría de las palabras en un documento no caen en esta situación.

En los siguientes artículos nos referiremos a algunas otras técnicas, como la de los bigramas, las búsquedas binarias, entre otras cosas.

Lapsus: anatomía de un corrector ortográfico I

Cuando me fui a hacer la maestría al Reino Unido, ya tenía un proyecto en mente, el cual era hacer un corrector ortográfico inteligente. La idea era usar reglas ortográficas, entre otras cuestiones, para discenir si las palabras de un texto estaban bien escritas. Supuse que tenía que prepararme en algún lenguaje ad hoc para esta tarea y es así como decidí entrarle a la maestría, cuyo pomposo nombre era el de "Inteligencia artificial y bases de datos inteligentes".

Pues bien, después de los correspondientes cursos, poco a poco fui adquiriendo experiencia en Prolog y realmente me fascinó el asunto de programar en este paradigma, particularmente cuando se trata de hablar de paradojas lógicas, de lo que ya escribí antes aquí.

Cuando regresé a México, decidí entonces desarrollar el proyecto que me había llevado a hacer la maestría, el cual le llamé "Lapsus, un corrector ortográfico inteligente". Lo escribí completo en Turbo Prolog 2.0, incluyendo un editor de textos. Sin embargo, me di cuenta que un programa de esta naturaleza debería corer como una aplicación dentro de los programas populares de procesdamiento de palabras, por ejemplo MS Word, y por ende, había que entender cómo hacer para que mi programa y Word actuaran concurrentemente. Así pues, la versión actual de Lapsus corre concurrentemente con MS Word a través de la interfaz OLE (Object Linking and Embedded), pero ya hablaremos de este tema.

Ahora bien, en las decisiones de diseño de Lapsus, tomé las siguientes decisiones:

1. Ser capaz de usar reglas ortográficas.
2. Ser capaz de usar un diccionario con unos 500,000 términos (cortesía de una de las aplicaciones en Linux).
3. Ser capaz de usar diccionarios personalizados.
4. Ser capaz de usar otras tecnologías para buscar errores, como patrones equivocados de letras.
5. Ser capaz de usar de un diccionario de verbos ya conjugados.

Estoy de hecho convencido que un corrector ortográfico poderoso debe incluir una serie diferente de técnicas para hallar las palabras mal escritas. Un sistema híbrido sin duda es mejor que un sistema que sólo sigue una técnica en particular.

Pasemos a describir y justificar este diseño:

1. Reglas ortográficas

El español, como todo lenguaje humano es cambiante. Palabras, expresiones y reglas que se usaban en el pasado son obsoletas ahora y en vista de esta situación, se decidió mantener las reglas ortográficas en un archivo especial, el cual es consultado cada vez que el sistema se ejecuta.

Este archivo se denomina Reglas.DB, y contiene alrededor de 260 reglas ortográficas de uso común en el castellano. Las reglas pueden ser editadas con cualquier procesador de palabras (o editor de textos) que utilice el formato ASCII sin caracteres de control o símbolos especiales. Por ejemplo, el block de notas..

Cada una de las reglas ocupa un renglón en el archivo Reglas.Db. Así entonces, escribir una regla nueva significa finalmente, agregar una línea más al archivo ya mencionado. Las reglas ortográficas, para que puedan ser entendidas por el programa, requieren de estar en un formato específico para poder ser leídas por el sistema. Así entonces, puede ser que en un principio, el archivo Reglas.DB le parezca al usuario final difícil de entender. No obstante la aparente complejidad del mismo, sus elementos esenciales son muy fáciles de comprender y usar.

Por ejemplo, he aquí una parte del conjunto de reglas ortográficas (sacadas del pequeño Larousse de la gramática española):

• v enb p
• v mob sb mobiliario
• v prib sb
• v ebo s sebo cebo efebo mancebo

Hay unas 260 reglas en total. Como éstas residen en un archivo en particular, pueden añadirse más reglas en caso de que se me haya pasado alguna.

A continuación se describe el formato completo de las reglas, indicando la sintaxis que las reglas necesitan y que -en rigor- deben ser escritas correctamente para que Lapsus pueda trabajar con las mismas:

Las reglas ortográficas tienen tres posibles alternativas, las cuales pueden aplicar a:

• prefijo (p) de la palabra analizada (parte inicial de la palabra en cuestión)
• sufijo (s) de la palabra analizada (parte final de la palabra en cuestión)
• subcadena (sb) de la palabra analizada (en cualquier subparte de la palabra en cuestión)

Las letras "p", "s", y "sb" corresponden respectivamente a prefijo, sufijo y subcadena, y estas letras serán usadas para informarle a Lapsus en qué parte de la palabra se aplica la regla ortográfica.

La regla entonces sigue el siguiente formato:

letra palabra clave lista

Pasemos al análisis de esta estructura. En primer término aparece la palabra seguido de paréntesis que abre. Esto debe aparecer en minúscula estrictamente. Acto seguido, pueden verse cuatro parámetros, a saber:

•  letra    Indica la letra a la cual se aplica la regla. Por ejemplo, si la regla ortográfica es sobre el uso de la v, éste es el parámetro que se utiliza. (Véanse los ejemplos más adelante).
•  palabra    Indica la palabra que no cumple precisamente con la regla que está siendo definida, es decir, muestra el ejemplo de la contraposición a la regla ortográfica misma.  
• clave    es exactamente lo que indica el alcance de aplicación de la regla (prefijo, sufijo o subcadena). Utilícese solamente las siguientes palabras claves (entre doble comillas: p, s, sb).
• lista        Se refiere a la lista de palabras que son la excepción a la regla en cuestión. Tales palabras deben aparecer separadas por espacios entre sí.

Algunos ejemplos pueden ser realmente ilustrativos. Considérese la siguiente regla:

Las palabras que empiezan con env se escriben siempre con v.

La regla en el archivo Reglas.DB se escribirá entonces así:

v enb p

Lapsus reconoce la regla de la siguiente manera: Las excepciones a las palabras que empiezan con env nada más pueden ser aquellas que comienzan con enb, que en este caso no hay tales excepciones a la regla y el rango de aplicación de la misma es con todos los prefijos de las palabras.

La regla descrita se refiere a palabras en donde el rango de aplicación corresponde al prefijo de las misma. Ahora considérese la siguiente regla:

Todas las palabras que terminan con ave se escriben con v.

Esta regla puede expresarse en el lenguaje descrito de la siguiente forma:

v abe s árabe jarabe

La cual puede ser descrita de la siguiente manera: Las excepciones a las palabras que terminan en ave nada más pueden ser aquellas que terminan con abe, las cuales son, árabe y jarabe (y nada más), y el rango de aplicación de la regla son los sufijos de las palabras.

Por último, un ejemplo de una regla que se refiera a subcadenas puede ser la siguiente:

Las palabras que tienen dentro de ellas (en cualquier parte de la misma) las letras ilv se escriben siempre con v.

La cual se traduce en el archivo de reglas de la siguiente forma:

v ilb sb bilbao

Y se interpreta de la siguiente manera: Las excepciones a las palabras que tienen como subpalabra ilv se escriben siempre con v, excepto la palabra bilbao.

Lapsus contiene un editor de reglas para hacer la vida más fácil al usuario (ver siguiente imagen).

 

2. Diccionario principal

Todo programa de corrección ortográfica requiere de un diccionario, que mientras más grande sea, mejor. Actualmente el diccionario de Lapsus contiene unos 500,000 términos. Originalmente tenía un diccionario de unos 250,000 términos, pero el Gemelo, Jesús Ortega, campeón de Scrabble, me dio el diccionario que hoy uso.

Obviamente para poder buscar en un diccionario con tantos términos, se necesita alguna técnica que sea eficiente. Cuando se trata de datos ordenados alfabéticamente, no hay mejor técnica que la búsqueda binaria. Por ejemplo, para ver si una palabra se encuentra en el diccionario necesitamos solamente 19 búsquedas. ¡Eso es eficiencia! Por supuesto que hay otras técnicas, como las funciones de hash, las cuales podrían hallar el término en una sola búsqueda, pero aquí hay que lidiar con hallar una función de hash adecuada (cosa nada fácil) y además, pelearse con las inevitables colisiones (cuando dos palabras ocupan el mismo sitio). Por ello, la decisión fue usar una búsqueda binaria, la cual es extremadamente rápida, más si se toma en cuenta la velocidad actual de las computadoras.


3. Diccionarios especializados

Los diccionarios tradicionales traen las palabras que normalmente se usan en un lenguaje. Sin embargo, puede pasar que no contemple palabras de algún nicho particular. Por ejemplo, pensemos en el lenguaje específico que usan los doctores. Probablemente algunos términos no aparezcan en el diccionario principal, por lo que aquí se pueden alimentar esos términos muy específicos.

Otro caso: cuando una empresa usa, por ejemplo, un nombre mal escrito. Hay en México una compañía que hace bolsas de polietileno, cuya razón social es "Volzas S.A.". Obviamente si dicha empresa escribe cartas a sus clientes y escribe la palabra "volzas", el corrector brincará anunciándonos que esa palabra está mal escrita (y tendrá razón normalmente, pero no en el contexto mencionado). Así, se pueden poner estos términos, incluso mal escritos, para evitar que Lapsus se dedique a señalarlos cuando no queremos. Un caso similar es el de la palabra "clabe", que significa en el mundo de los bancos "clave bancaria estandarizada", o algo así. Algún ingenioso le puso "clabe", lo cual es mala idea, porque nos acordamos de cómo se escriben las palabras, normalmente, porque las leemos de una manera. Por ello, cuando tenemos dudas sobre cómo se escribe un término, muchas veces la escribimos en un papel a ver cuál es la que vemos como escrita correctamente.

4. Patrones equivocados de letras

Las palabras en español no admiten ciertas combinaciones de letras. Por ejemplo, hasta donde me acuerdo, la combinación TH no existe en español. Así, si leemos un texto y partimos en bigramas ("palabras" de dos letras), podemos ver si una palabra está mal escrita sin siquiera revisar con reglas o diccionarios. Ya una implementación de esta técnica la escribí antes y se puede ver esto aquí.

5. Verbos


El español tiene alrededor de 10,000 verbos. Cada verbo tiene unas 50 conjugaciones. Por ende, esto da unos 500,000 términos que podrían ser añadidos a un diccionario de verbos conjugados. Cabe decir que se puede escribir un programa que haga esto automáticamente, pero solamente será útil para la mayoría de verbos que resulten ser regulares. En cualquier caso, la idea de un diccionario de verbos conjugados (cosa que no se verá normalmente en los diccionarios normales), puede ayudar a que la corrección sea más poderosa.

Seguiremos hablando de esto próximamente.

Murió uno de los creadores de C y Unix

Dennis MacAlistair Ritchie (que usaba en algunos foros de discusión el sobrenombre ‘dmr‘), nació en 9 de septiembre de 1941 y murió ayer 12 de octubre del 2011. Fue uno de los científicos más notables en la ciencia de la computación. Desarrolló C y tuvo una gran influencia en otros lenguajes de programación, así como en la parte de sistemas operativos, tales como Multics y Unix.

Recibió el premio Turing en 1983 (algo así como el Nobel de la computación), y también fue galardonado con la Medalla Nacional de Tecnología en 1998. Ritchie se retiró en el 2007 siendo la cabeza del departamento de investigación de software y sistemas de Lucent Technologies. Ritchie era físico de profesión además de tener un grado en matemáticas aplicadas. En 1967 comenzó a trabajar en los Laboratorios Bell (hoy AT&T). En 1968 recibió el título de doctor por la Universidad de Harvard,  bajo la supervisión de Patrick C. Fischer.

A Dennis Ritchie se le conoce más por se el creador del lenguaje de programación C y un desarrollador clave del sistema operativo Unix. El libro más popular es el que precisamente escribiera Ritchie con Brian Kernigham: “The C Programming Language“. La invención de C y su rol en el desarrollo de Unix conjuntamente con Ken Thompson, lo colocan como el pionero más importante de la computación moderna. El lenguaje C está en uso ampliamente y sin duda su filosofía ha influenciado decenas de otros lenguajes de programación. En lo que se refiere a Unix, estableció conceptos de sistemas operativos que hoy en día son usados contínuamente en todo el mundo. El 90% de los servidores de Internet usan alguna versión de Unix, Mac OS X es una versión de Unix. Vamos, la influencia del trabajo de Ritchie es enorme y vasta.

Dennis Ritchie recibió en vida muchísimos premios. Se le hizo miembro de la Academia Nacional de Ingeniería, en 1988, por el desarrollo del lenguaje de programación C y por su co-desarrollo del sistema operativo Unix. en 1983 Ritchie y Thomspon recibieron conjuntamente el premio Turing por su desarrollo en la teoría de los sistemas operativos genéricos y específicamente por la implementación del sistena operativo Unix. El discurso de Ritchie al recibir el premio se llamó: “Reflexiones sobre la investigación en software“, que puede leerse aquí.

En 1990, ambos, Ritchie y Thompson, recibieron la medalla Richard W. Hamming, por parte de la IEEE, por haber originado el sistema operativo Unix y el lenguaje de programación C. También ambos recibieron de mano del entonces Presidente Clinton, la Medalla Nacional de Tecnología por Unix y C, que ha llevado a enormes avances en hardware, software, sistemas de redes, además de estimular el crecimiento de la industria, logrando el liderazgo norteamericano en estos rubros de la ciencia de la computación.

Este año, 2011, Ritchie y su gran amigo Ken Thompson, recibieron el premio japonés para la comunicación e información, por sus trabajos en sistemas operativos, en particular el desarrollo de Unix. Parecen demasiados premios por lo mismo, pero eso simplemente habla de la importancia de lo que estos personajes han hecho en el mundo del cómputo y su relevancia internacional. Ritchie escribió dos libros muy conocidos:  The C Programming Language (1978, con Brian Kernighan; conocido tambien como el K&R) y  el Unix Programmer’s Manual (1971)

Dennis Ritchie era un hombre de carácter privado y a pesar de sus contribuciones, no ha tenido ni probablemente tendrá la cobertura mediática que recibió Steve Jobs al morir. Yo me pregunto qué calificativos se le pueden asignar a alguien que hizo tanto por el cómputo como Ritchie, cuando a Jobs no ha faltado quien (equivocadamente) le califica de genio y visionario. Así parece ser injusto el mundo. Descanse en paz.

Un programa por demás peculiar

Hace unos días, mientras dormía, soñaba que escribía un programa de computadora. Estaba frente al monitor y la meta a resolver era llevar cuenta de cuantos metros, ¿kilómetros? recorre el ratón cuando una persona está frente a la computadora en una sesión de -digamos- un par de horas. Porque uno apunta con el ratón, da click, abre alguna aplicación, aprieta botones en la misma, cierra las ventanas, va al menú de inicio, etc. Vaya, que en mi sueño estaba empeñado por medir la distancia que el ratón recorre por la pantalla una y otra vez.

Cuando desperté, bañado en sudor, y eso porque está haciendo mucho calor en la ciudad de México, me di a la tarea de ver cómo se podía hacer semejante labor. Es un hecho que escribir una aplicación que mida lo que quiero medir no es un programa tradicional, porque desde luego, puede escribirse un programa que lleve cuenta de dónde está el ratón, sus coordenadas, etc, pero solamente funcionará para el programa que se ejecuta. Es decir, si el "foco" del programa ya no está en la ventana del mismo, el software no podrá llevar cuenta de esos valores del ratón en ningún momento.

La solución es un "hook", enganchar un programa que haga esta labor de correr digamos "tras bambalinas", a nivel sistema, y que nos diga entonces las coordenadas del ratón en todo momento. Engancharse con el API de Windows es en realidad un proceso complicado y aunque hay diversas técnicas para lograrlo, Microsoft recomienda que la llamada (callback), del procedimiento del hook resida en una biblioteca de enlace dinámico (DDL).

Revisando en Internet, hallé diferentes programas que hacían hook para atrapar los eventos del ratón. Sin embargo, hallé una biblioteca de funciones para este propósito, escritas en Delphi (compatibles con las versiones 4/5/6/7/8/9), que hacen la tarea encomendada. Las bibliotecas se llaman: TCPMouseHook® System Wide Mouse Hook and DLL for Borland Delphi. El desarrollador es BitLogic Software Solutions, una empresa que está en el Reino Unido. Las rutinas son accesibles gratuitamente pero tienen una pantalla al inicio del programa que las use, indicando que no se ha pagado ninguna licencia por ellas. Si se desea pagar, entonces el autor del software manda una clave que deshabilita la pantalla inicial (llamada en el ambiente de cómputo "nag screen") y entonces el software funciona igual que antes, pero sin la pantalla comercial al inicio del mismo.

 

Pues bien, una vez que entendí cómo usar las rutinas, me di a la tarea de programar lo que yo quería. De entrada, descubrí que llevar el trazo constante del ratón no es una buena idea, porque si el usuario decide moverlo en círculos, por ejemplo, asunto por demás poco probable, entonces el sistema tiene que hacer montones de llamadas al evento de mover el ratón y llevar la cuenta de las coordenadas por donde pasó. Un esquema más racional es ubicar el ratón originalmente en alguna parte, y cuando lo muevo y doy click, entonces calcular la distancia entre esos dos puntos. Una vez calculada la distancia, se guarda en alguna variable y las coordenadas finales se vuelven ahora las iniciales. Si vuelvo a mover el ratón y doy click, entonces las coordenadas finales es dónde se encuentra el ratón ahora y se vuelve a calcular la distancia, la cual se suma a la anterior.

Aparte de esto, decidí también medir cuantos clicks se dan al botón izquierdo del ratón y algo más... debido a que hay muchas resoluciones de pantalla, la idea para medir la distancia en cms, por ejemplo, fue la de medir qué resolución tengo en la pantalla. Por ejemplo, en mi caso, 1200x800 (creo). Pues bien, en mi monitor, medí la distancia horizontal de la pantalla y hallé que hay unos 40 cms de largo, lo cual equivale a unos 34 pixeles por cm. De esta manera, podía ya entonces saber la distancia final que hubiese recorrido el ratón en cms.

¿Para qué puede servir este programa? Ni idea. Quizás no tenga mayor utilidad. Las rutinas que enganchan los procedimientos y eventos del ratón vía las bibliotecas mencionadas pueden, sin duda, tener mejor aplicación que la que a mí se me ocurrió, pero el asunto era ver cómo se podía hacer algo de esta naturaleza.

A quien le interese este maravilloso programa puede pedírme a morsa@la-morsa.com, y a vuelta de correo tendrá el sistema. Cabe decir que los programas antivirus, como el AVG FREE, por ejemplo, brincan cuando se correo este programa y de hecho, no deja que se ejecute, porque claramente la biblioteca de funciones para hacer el hook del ratón le parece sospechoso y eso no lo hacen los programas normales. Así entonces, si el software no corre, es porque el antivirus no les está dejando. De hecho, eso me pasó cuando quise correrlo y veía que no se instalaba el hook. Ésa fue la razón.

De la eficiencia en cómputo

A mí me gusta Prolog, el lenguaje de programación, que a decir de la propaganda que Borland hacía de su compiladort (turbo Prolog), era "el lenguaje natural de la inteligencia artificial". Bonita frase publicitaria, nada más.

Y lo que me gusta de Prolog es su paradigma, que es totalmente diferente al que tienen los lenguajes de programación de cuarta generación como Pascal y C. En prolog actuamos en otra forma: definimos el problema y el lenguaje se encarga de darnos la solución. Suena a magia, pero no lo es.

Prolog es un lenguaje de programación declarativo y por ende, lo que tenemos que hacer es precisamente declarar las condiciones iniciales y de frontera. Por ejemplo, puedo decir:

ama(juan, ana).

Lo cual quiere decir, por ejemplo, que "juan ama a ana". Ojo, aquí es importante el orden de los términos. En prolog no es esto equivalente a lo que sigue:

ama(ana, juan).

Lo cual querría decir que "ana ama a juan", lo cual evidentemente no es equivalente.

Pero lo interesante aquí es el que declaramos, casi en el idioma que hablamos normalmente, un hecho que dentro de Prolog tiene sentido. No hablamos pues de hacer cálculos sofisticados por ejemplo, sino de declarar estas relaciones, que en los lenguajes de cuarta generación se dificulta hacerlo.

Pero pensando en esto y en los problemas que Prolog puede resolver, vía el mecanismo de la recursividad, hallé que en realidad habría que preguntarse si Prolog es un lenguaje víable para aplicaciones reales y no para meramente problemas académicos como los que ya he tratado aquí (crear crucigramas, pasear por un laberinto, resovlver sudokus, etc.). Y la realidad es que pienso que Prolog bien puede ser una herramienta víable, pero solamente para unos pocos casos en donde las simbologías son muy importantes.

Por ejemplo, pienso en un diccionario que tengo que consultar. Si mi diccionario cuenta con digamos medio  millón de palabras, y necesito saber si una palabra determinada existe en mi archivo (y considerando que las palabras están debidamente ordenadas), requiero de hacer unas 19 búsquedas, pues 2^N = 500,000 es aproximadamente 19.

Escribir un programa en Prolog que haga una búsqueda binaria no es difícil. La idea es colocarse en la palabra 250,000 inicialmente y e si la palabra que busco es la que está en esa posición. Si no es, entonces debo ver si "me pasé", es decir, la palabra está antes de la que hallé o "me quedé corto", es decir, la palabra está después de la que leí. Así, divido esa región del archivo 0 a 249,000; o 250,001 a 500,000 entre dos y vuelvo a hacer la búsqueda. En Prolog, naturalmente esto se hace de forma recursiva, lo cual implica guardar el estado del sistema, vía el stack, que es una estructura de datos LIFO (Last In, First Out), cada vez que se hace la llamada recursiva. Obviamente necesito una condición terminal o de salida para no ciclar al programa y que éste termine por quedarse sin memoria.

Si intento hacer, en cambio, una búsqueda binaria en un lenguaje de cuarta generación, hallaré que no necesito usar ninguna función recursiva y con un ciclo WHILE puedo resolver mis dificultades. Aquí no hay que llevar cuenta del stack y resulta muy eficiente en términos de memoria.

Aún así, 19, 20 búsquedas usando un stack en un algoritmo recursivo no sólo no es terriblemente ineficiente, sino que es además muy elegante. Niklaus Wirth decía: "Iteratum humanum est, recursivitum divinum est" (la iteración es humana, la recursion es divina)

Pero pensando en esto, me pregunté si quisiese hacer una búsqueda linea, es decir, buscar de la primera a la última palabra en mi diccionario. Si hago esto, en el mejor de los casos haré una búsqueda: la palabra que busco está en la primera posición. En el peor de los casos la palabra que busco estará en la última línea de mi archivo, por lo cual haré medio millón de consultas.

Si quiero hacer esto en Prolog, y además lo quiero hacer recursivo, debo prepararme para guardar en el stack medio millón de estados. Por lo menos eso en un principio. Mi esquema en Prolog sería algo así:


Si la variable I es mayor que medio millón termina.

Define la variable I como 1
busca en la iésima palabra si es la que busco
si no lo es, crea una nueva variable I1 que sea igual a I+1
ve al principio del procedimiento y vuelve a buscar con estos valores
Si es el valor, imprime el resultado y asigna a la variable el valor de medio millón + 1 y ve al procedimiento recursivo


Obviamente estoy asumiendo que quienes me leen ya han tenido contacto con Prolog, pero aquí el asunto que quiero ilustrar es la dificultad que voy a enfrentar, que es la de guardar el estado del sistema en el stack a cada llamada recursiva. Dudo que el programa soporte medio millón de llamadas guardadas en el stack. ¿Qué hacer entonces? La solución es usar la instrucción corte (cut), la cual se identifica con un signo de admiración "!" y entonces le decimos al sistema en prolog que no guarde todos estos estados temporales de la recursión, porque en el fondo no me interesa saber qué pasa cuando regreso de la recursión en sí.

Si se me ocurre hacer esto en algún lenguaje de cuarta generación como Pascal, lo que haría es:

repite
  asigna a I el valor de 1
  asigna termina = falso
  lee el registro cuyo valor es I
  Si es la palabra que busco, entonces
      asigna a la varianble termina = verdadero
      escribe resultado
  Si la palabra no es la que busco, incremento la variable I
hasta que termina = verdadero



Aquí no llevo control del stack y no tengo que preocuparme por nada de eso. Por ende, parece ser más fácil usar para este asunto en particular, un lenguaje de cuarta generación.

Pero un momento, hasta los lenguajes declarativos, que usan simbologías, no se salvan de tener que hacer procedimientos repetitivos como en los lenguajes tradicionales. Aquí la cuestión es que el programador necesita definir las cosas de manera que el sistema sea eficiente y no se quede sin memoria.

En suma, pienso que Prolog es un lenguaje comercialmente víable, pero en este caso, el programador requiere de ser más cuidadoso, mucho más, de los recursos de memoria con los que cuenta. No tener esto presente puede hacer de prolog un lenguaje por demás ineficiente y poco usable.

Microcomputadoras en un chip

Hace ya tiempo hablé de los microcontroladores Pic, cuyo fabricante es la empresa Microchip. Estos circuitos electrónicos son computadoras completas en un chip. Tienen  puertos de entrada/salida, unidad lógica aritmética, convertidores analógico digitales, etc. Tiene memoria para programar y aparte de tener una arquitectura RISC (Reduced Instructions Set Computing), hay compiladores de Pascal, C y Basic, para no tener que lidiar con el lenguaje de máquina o con el ensamblador de estas simpáticas microcomputadoras.

Los Pics vienen en diversas presentaciones y dependiendo del tipo de aplicación que se quiera, hay una familia de microcontroladores que pueden hacer la tarea encomendada. La versatilidad de estos circuitos es tal que muchos dispositivos que hay en las casas podrían estar controlados port estos chips, con programas específicos que hacen las tareas encomendadas. Es lo que se ha dado en llamar también embedded computing. 

Pues bien, con el tiempo he seguido aprendiendo del tema y hoy en día se me han ocurrido dos proyectos en donde un microcontrolador pic, con una serie de botones y pantallas de LCD para desplegar resultados, pueden convertirse en dispositivos útiles. Ya hablaré en otra ocasión de estos proyectos. Lo que aquí quiero hacer es mostrarles la última tarjeta de desarrollo que adquirí, la cual es francamente una maravilla.

Se trata del MPLAB Starter Kit for Pic18 MCUs, hecha por Microchip, que se consigue por menos de 1000 pesos y que contiene botones capacitivos (es decir, de uso táctil, con sólo tocar la placa del circuito se simula el presionar un botón), acelerómetro, lo cual permite saber si hay movimiento en los tres ejes, X, Y y Z. Un displasy OLED de color, de 1/4 de una tarjeta VGA. Un chip Pic de 44 pines (Pic18F46J50) con 64Kbytes de memoria Flash, con tecnología para ser usado con muy poca corriente. Tiene también una microtarjeta SD de 2 gigabytes para guardar datos y programas. El paquete viene con una versión reducida (lite) del compilador de C y el medio ambiente de desarrollo MPLAB IDE. Contiene tutoriales, código de demostración, debugger (depurador) integrado y cable USB. Por lo que trae me parece una ganga.

He aquí un video que explica lo que puede hacerse con este kit de desarrollo:

En algún otro mensaje hablaré de los desarrollos que tengo pensados con este kit. Por lo pronto, es un sistema que sin duda podrá ser muy útil en términos de aprendizaje. Seguiremos informando.

Lenguajes de programación y obsolescencia

Cuando uno entra al mundo de la computación, tarde o temprano a algunos se nos despierta la curiosidad de saber cómo es que se hacen estos programas que funcionan en nuestras máquinas. Y así, de pronto, ya estamos leyendo manuales de diversos lenguajes de programación, empezamos a ver y a imprimir el código fuente de otros para ver cómo hacen los demás las cosas, y en todo este proceso vamos aprendiendo y nos vamos convirtiendo, bien que mal, en programadores.

En mi caso, aprendí a programar primero en Applesoft Basic, una versión del lenguaje BASIC tradicional, diseñado para la Apple ][. De ahí hice algunos pininos en ensamblador del 6502 y más adelante, ya en la facultad de ciencias, incluso tomé un curso de máquinas digitales con laboratorio, con el estimable físico Javier Sierra, en donde programé en el ensamblador del microprocesador 6809, amén de cursos de programación de sistemas, bases de datos, estructuras de datos, cursos varios de programación, etc.

En este largo camino por el tiempo aprendí Turbo Pascal y encontré a grandes amigos, como Víctor Delgado, apasionado de este producto de Borland, con quienes compartimos código, ideas y compiladores por muchos años. Luego llegó Delphi, que vino a ser el equivalente a Turbo Pascal para Windows y nos enfrascamos en aprender cómo programar bajo la interfaz gráfica. Pude ver Delphi 1.0 en 1994, en la 5a Conferencia Anual de Borland para Desarrolladores y quedé francamente sorprendido por las posibilidades del sistema. Usé la versión 2, 3, 4, 5, 6, 7 y las rebautizadas como Delphi 2008 y 2009 (se puso de moda poner el año de creación como número de versión. Así vimos Windows 95, 98, Windows Millenium, etc). Para mí, la versión 7 fue la más estable, la mejor, comparada quizás solamente con la versión 5. Las versiones 4 y 6 por alguna razón nunca me terminaron de gustar y siempre me parecieron inestables.

Pero he aquí que hemos llegado al 2011 y el año pasado, si la memoria no me falla, Codegear, una empresa subsidiaria de Borland, vendió sus herramientas de desarrollo y programación a la empresa Embarcadero, quien es ahora la compañía que distribuye y sigue soportando el desarrollo de las nuevas versiones de Delphi. Desafortunadamente, veo con cierta tristeza que mi lenguaje de programación favorito ya no tiene el volumen de personas que se ocupan de él. Digamos que el interés por Delphi, con estos cambios de empresas una y otra vez, ha desilusionado a muchos y es claro que cada vez parece haber menos apoyo. Y es una lástima, porque Delphi ha demostrado ser una gran herramienta, basada en el original Pascal de Niklaus Wirth y supercargado con toda la programación orientada a objetos.

Un síntoma de que algo anda mal con Delphi es que las editoriales norteamericanas que se dedican a publicar libros de programación, hacen años que no sacan un nuevo libro sobre Delphi. Y eso suena parecido a lo que pasó con una de las mejores revistas de computación que hubo en el mercado, la revista Byte, que de ser un volumen de cientos y cientos de páginas, de pronto empezó a adelgazar espantosamente y terminó muriendo de inanición. Esto está pasándole a Delphi, me parece.

Me pasó algo parecido en Prolog, aunque aquí la historia es en realidad diferente. En los años ochenta salió Turbo Prolog, y considerando la potencia de las herramientas "turbo" de Borland, me hice de este compilador. Me fui a hacer una maestría a la Universidad de Essex para aprender a usar Prolog entre otras cosas y a mi regreso escribí mi primera aplicación completa en turbo Prolog, un corrector ortográfico híbrido (usa reglas ortográficas, diccionarios, bigramas, etc.), al que llamé Lapsus. Pero he aquí que Borland regresó a los creadores de Turbo Prolog su herramienta y la empresa danesa desarrolladora, sacó más adelante una versión para windows llamada Visual Prolog. De nuevo, aunque el lenguaje sigue siendo el mismo, el soporte a Prolog es discreto y quizás en muchos sentidos no es el mejor lenguaje de programación por muchas razones, aunque sus puntos fuertes son inimitables en cualquier otro lenguaje.


El punto es que uno toma decisiones en el pasado, por ejemplo, la que yo tomé, de programar en Turbo Pascal, aunque pude haber elegido otra plataforma de desarrollo, quizás C, quizás Java, quizás ¿Visual Basic? y creo que por muchos años disfruté de una de las herramientas mejor escritas en este mundillo de la programación. Pero creo que me estoy quedando obsoleto.

Y sí, aprendí un poquito de Java, de PHP, de C++, pero no los he usado ni con la frecuencia que debería y tampoco creo tener las últimas versiones de estos compiladores/intérpretes.

Así pues, si hay alguna moraleja en esta historia sería la de tomar el estudio de diversos lenguajes de programación al mismo tiempo, por ejemplo Java y C. De hecho, su sintaxis es parecida y eso haría la curva de aprendizaje mucho más rápida, amén de que con la experiencia de lenguajes anteriores, muchos conceptos se entienden mucho más rápido. No obstante esto, es claro que los lenguajes de programación parecen tener un ciclo como las personas: nacen, crecen y mueren (no se reproducen)...

En cualquiera de los casos, pienso que a pesar de todo, esto da oportunidad  a aprender nuevas herramientas, nuevos paradigmas y seguir aprendiendo, cosa que finalmente siempre me ha parecido uno de los más extraordinarios goces en el ser humano: el del descubrir cómo funcionan las cosas y cómo hacerlas mejor, así como entender conceptos que quizás hemos pasado por alto por mucho tiempo. Quizás entonces, no todo está perdido.

Maestros de la Facultad de Ciencias, UNAM

La doctora Elisa Viso Gurovich es una profesora de la Facultad de Ciencias de la UNAM. Licenciatura en matemáticas en 1977 por la propia UNAM, Maestría en Ciencias de la informática, en el 2005, por parte del Politécnico Nacional y Doctorado en Ciencias (computación), por la UNAM también, en el año 2007. La conozco desde que empecé mi carrera de física y como esto de la vocación toma muchas veces forma mientras se estudia, entendí que me agradaba mucho todo lo referente a la computación y por años mantuvimos muchas pláticas amén de cursos que ella daba. Igualmente su esposo, Mario Magidin, que desafortunadamente ya no das clases en la facultad, quizás por falta absoluta de tiempo, nos mostró esa fascinación que da el cómputo. Se decía que Mario podía "compilar" un programa en ALGOL en el pizarrón, es decir, el código que escribía en el pizarrón sin duda correría si lo tecléabamos en una terminal de alguna computadora con un compilador de ese lenguaje (muy parecido a Pascal a todo esto). Amén de ser grandes profesores Elisa y Mario, creo que siempre se portaron también como grandes amigos.

Hoy estando en mi escuela encontré un cartel en donde se anunciaba un libro de Elisa. Minutos después me encontré a la autora y me dijo que me daría un ejemplar, que ahora tengo en mi poder. De hecho son dos ejemplares, el libro de texto, publicado por "las prensas de ciencias", que hasta donde entiendo es una organización editorial de la propia facultad de ciencias de la UNAM, cuyo título es "Introducción a las Ciencias de la Computación con Java", y un segundo volumen, menos grueso, que es el "manual de prácticas", del primer volumen.

Aunque Elisa ha escrito otros libros, lo cual fue sorpresa para mí, éste que reseño aquí está escrito con el licenciado en ciencias de la computación Canek Peláez (2004).

El temario de la obra es este:

1. Introducción.
2. El proceso del software.
3. Clases y objetos.
4. Manejo de cadenas y expresiones.
5. Datos estructurados.
6. Herencia.
7. Administración de la memoria durante ejecución.
8. Ordenamientos usando estructuras de datos.
9. Manejo de errores en ejecución.
10. Entrada y salida.
11. Hilos de ejecución. 

Esto es sin duda una introducción por demás completa y extensa al lenguaje Java de programación. Desde hace unos años el paradigma de los objetos hizo su aparición y su poder es tal que los autores de la obra enmarcan todo su texto bajo el fuerte influjo de la programación orientada a objetos (POO).

Viso y Peláez han decidido tocar muchos temas que quizás se salgan de cualquier curso introductorio a la programación en Java, empezando por las excepciones, el manejo de archivos y eventos. A diferencia de otros textos de esta naturaleza, el volumen gira siempre alrededor de un tema central: el manejo de una base de datos, en donde se ejemplifican conceptos importantes como extensibilidad, modularidad y reuso de los objetos.

El texto también contiene otros ejemplos que complementan la enseñanza de los tópicos más importantes, aunque estos no necesariamente sean de la POO.

Por su parte, el Manual de Prácticas, contiene un buen número de ejercicios para que el lector pueda aprender Java "ensuciándose las manos", es decir, practicando. Su índice va así:

1. Ant y el compilador de Java
2. Usar y modificar clases
3. Variables, tipos y operadores
4. Interfaces y clases por dentro
5. Estructuras de control y listas
6. Herencia
7. Entrada/salida y arreglos
8. Recursión
9. Manejo de excepciones
10. Interfaces gráficas
11. Ant y archivos Jar
12. *Hilos de ejecución y enchufes

Apéndice A: El resto de las leyes



He empezado a hojear la obra y francamente es un trabajo notable, bien escrito, cuidado, profundo, como caracteriza a Elisa (y supongo que a Canek también, que no lo conozco personalmente).  Estoy seguro que si se quiere aprender Java, es una buena idea hacerse de este libro. Enhorabuena y felicidades a los autores.

De la eficiencia en cómputo

Han pasado ya algunos años, por no decir muchos, desde que empecé a usar computadoras. Mi primera máquina fue una Apple ][ y ahí hice mis pininos, primero en el Applesoft Basic y más adelante en el UCSD Pascal. Cabe recordar que una computadora de los años ochenta tenía unos 128K de memoria RAM y unidades de discos flexibles. Ni pensar en discos duros. De hecho, me tocó ver uno, para un sistema de precios unitarios, que era cvomo de 5 megabytes y que, para usarse con la Apple ][, el disco estaba dividido en un sistema de discos flexibles virtuales, que el sistema operativo DOS 3.3, podía entender entonces.


Cuando se tenían estos sistemas, estábamos limitados a unos 70K por lado del disco. Si voltéabamos el disco flexible (floppy) y le hacíamos una muesca en un borde, podíamos duplicar la cantidad de información a guardar, aunque el fabricante de los diskettes no recomendaba esta práctica. Igualmente, al tener solamente 128K de RAM, teníamos espacio reducido para nuestros programas. Si usábamos el intérprete de Applesoft Basic entonces estaríamos hablando de unos 48K para programas, porque los 128K no podían usarse más que en dos mapas alternativos de memoria por la forma en que el procesador accedía a la memoria. Por ello, en Applesoft Basic se seguía un esquema que se usó mucho en los primeros sistemas con lenguaje BASIC, el cual lo que hacía era "tokenizar" cada palabra reservada del lenguaje, para así ahorrar bytes, que estaban tan escasos en ese tiempo. Así, la instrucción PRINT, por ejemplo, se traducía a un sólo número hexadecimal. Si queríamos ver el listado del programa en memoria, éste se desplegaba destokenizando, valga la expresión, cada token y el programador veía su código fuente.

En términos de hardware y software, por ejemplo, la Apple ][ tenía su sistema operativo en un diskette de 70K. Increíble pensar que se podía tener un sistema operativo en tan poca memoria. Pues bien, como desde luego esta pieza de software era la más importante de la Apple ][, me hice de un libro que explicaba lo que pasaba dentro del sistema: Beneath Apple DOS. Hallé, cosa notable, que los ingenieros de software de Apple habían decidido poner el sistema a la mitad del disco. Si éste tenía 36 tracks, se cargaba éste en el track 18. Sonaba extraño. ¿Para qué? la respuesta es notable: si el cargador se pone a la mitad del disco, la cabeza lectora tiene que caminar máximo la mitad de la distancia para hallar el track deseado.  Obsérvese pues cómo se buscaba optimizar hasta en estos detalles.

Con el tiempo y los megas, gigas y teras, que ya están con nosotros, las cosas cambiaron radicalmente. Cualquier computadora casera tiene al menos dos gigabytes de memoria, y ello hace que la optimización y la eficiencia pierda sentido.

Ahora nadie piensa realmente en este tema. Los compiladores ya no son tan cuidadosos para ahorrar memoria. Los procesadores de texto han hecho crecer los documentos porque ahora se les añadetodo género de tags y marcas para identificar tipos de letra, tamaños, formato, etc. Simplemente un archivo que contenga la frase "Hello world!", ocupa  24064 bytes, cosa que vendría ser la tercera parte de un diskette de Apple ][.

Ahora la eficiencia, creo yo, se considera desde otro enfoque. Ahora se trata de ser muy rápido en todo, aunque para ello necesitemos usar mucha memoria. Los programadores sabemos que no se puede tener un programa muy rápido que use poca memoria, a mayor rapidez de una cosa, más recursos para que esto ocurra. En ese sentido la computación es muy ética. No hay una relación de ganar ganar entre velocidad de proceso y uso de poca memoria.

Desde luego que a pesar de que los sistemas modernos no hacen énfasis en lo que se refiere a optimización, las herramientas de programación insisten en usar esquemas dinámicos de memoria. Apartar usando un arreglo demasiada memoria ya no es una práctica adecuada. Ahora lo que se hace es que el sistema operatiuvo otorga memoria a los procesos que la están pidiendo. Da bloques de memoria, no toda, a alguna aplicación. Si ésta requiere más, buscará darle más. De esta manera se optimizan ahora las cosas, como previniendo de antemano, por software, de hacer las cosas bien, de usar de la mejor manera losa recursos.

Como sea, creo que no estaría de más que se pensara de pronto en optimización. Aunque sobre memoria, ¿por qué no hacer las cosas un poco mejor dentro de la computadora?

Bosquejo de un lector de archivos PGN

PGN son las siglas de Portable Game Notation, un sistema para anotar partidas de ajedrez, usando el esquema de la notación algebraica, que es el único sistema de escritura oficial de la Federación Internacional de Ajedrez (FIDE). Gracias a este mecanismo, cualquiera puede leer una partida de ajedrez sin prácticamente importar en qué parte del mundo se encuentre. La notación de una partida de ajedrez contempla los siguientes rubros: Evento (en qué torneo se jugó el torneo), lugar del evento, fecha completa, ronda, nombre del conductor de las blancas, nombre del conductor de las negras, resultado, ECO (código de la apertura de acuerdo a la Encyclopedia of Chess Openings - ECO), el rating de las blancas, el rating de las negras, entre otros apartados (estos son los más generalizados). Inmediatamente después de esto, viene la partida, codificada de la siguiente manera: número de jugada, jugada del blanco,  jugada del negro, número de jugada, etc. hasta llegar va 1-0, 0-1 o 1/2 (ganan blancas, ganan negras, empate).

Por ejemplo, esta es la partida entre Leko e Ivanchuk, del torneo alemán de Dortmund, del 2008:


[Event "Sparkassen"]
[Site "Dortmund GER"]
[Date "2008.06.29"]
[Round "2"]
[White "Leko, P."]
[Black "Ivanchuk, V."]
[Result "1-0"]
[ECO "B46"]
[WhiteElo "2741"]
[BlackElo "2740"]

1. e4 c5 2. Nf3 e6 3. d4 cxd4 4. Nxd4 Nc6 5. Nc3 a6 6. Nxc6 bxc6 7. Bd3 d5 8. O-O Nf6 9. Qf3 Be7 10. Qg3 Nh5 11. Qf3 Nf6 12. e5 Nd7 13. Qg3 g6 14. Bh6 c5 15. Na4 c4 16. Be2 Bb7 17. b3 Bc6 18. Nb2 Rb8 19. Nd1 Nc5 20. Ne3 Ne4 21. Qh3 Ng5 22. Qg4 c3 23. a3 Bb5 24. Bxb5+ axb5 25. f3 Qb6 26. Rae1 d4 27. Nd1 d3+ 28. Kh1 dxc2 29. Nf2 Bc5 30. Nd3 Be3 31. Bxg5 Bd2 32. Re2 O-O 33. Nc1 b4 34. Bxd2 cxd2 35. Rxd2 bxa3 36. Rxc2 Rfc8 37. Qe4 Rxc2 38. Qxc2 Qd4 39. Na2 Qxe5 40. b4 Rd8 41. h3 h5 42. Rb1 Qe3 43. Rd1 Rd5 44. Qb1 Qe2 45. Re1 Qd2 46. Rc1 Rd8 47. b5 Rb8 48. Rc3 h4 49. b6 Qd6 50. Rb3 Rb7 51. Nc3 Qc6 52. Rxa3 Qxb6 53. Qxb6 Rxb6 54. Ra4 g5 55. f4 Rb3 56. Ne2 Re3 57. Ng1 1-0

Aquí las piezas se denominan por sus siglas en inglés: K-king (rey), Q-queen (dama), B-bishop (alfil), N-knight (caballo), R-rook (torre). No se pone la "P" de peón porque como hay dieciseís, se tomó la decisión que sería redundante. Si no hay pieza que se mueve, se asume que es un peón. Cabe hacer notar además, que aquí hemos puesto la partida en notación larga, es decir, indicando de qué casilla se mueve la pieza o peón y a qué casilla llega. En general se usa la notación corta, que es simplemente la pieza que se mueve y hacia qué casilla se mueve. Si dos piezas iguales pueden acceder a la casilla a la que se mueve la pieza, hay entonces que indicar cuál es la que se mueve, poniendo las coordenadas de donde nace la jugada. Por ejemplo, una partida en notación larga se ve así:

[Event ""]
[Site "Breslau"]
[Date "1912"]
[Round ""]
[White "Levitzky"]
[Black "Marshall"]
[Result "0-1"]

1.e2-e4 e7-e6 2.d2-d4 d7-d5 3.Nb1-c3 c7-c5 4.Ng1-f3 Nb8-c6 5.e4xd5 e6xd5 6.Bf1-e2 Ng8-f6 7.O-O Bf8-e7 8.Bc1-g5 O-O 9.d4xc5 Bc8-e6 10.Nf3-d4 Be7xc5 11.Nd4xe6 f7xe6 12.Be2-g4 Qd8-d6 13.Bg4-h3 Ra8-e8 14.Qd1-d2 Bc5-b4 15.Bg5xf6 Rf8xf6 16.Ra1-d1 Qd6-c5 17.Qd2-e2 Bb4xc3 18.b2xc3 Qc5xc3 19.Rd1xd5 Nc6-d4 20.Qe2-h5 Re8-f8 21.Rd5-e5 Rf6-h6 22.Qh5-g5 Rh6xh3 23.Re5-c5 Qc3-g3 0-1

Todo esto viene a cuento porque la cuestión es que se me había ocurrido hacer en prolog, sí, en prolog, un programa que leyera archivos de esta naturaleza y desplegara la partida en formato PGN en un tablerito electrónico. Para simplificar las cosas, decidí primero usar la notación larga, porque así resulta más fácil ya que la propia notación me dice qué movimiento hay que hacer, considerando la casilla inicial y la casilla de llegada de la pieza que hace la jugada.

Un problema inicial que observé es que en prolog no hay arreglos como en muchos lenguajes como Pascal o C. No incluyo Basic porque esto es de la "Tierra Primitiva". Pero en prolog lo equivalente son las listas. Así, puedo definir una lista con ocho casilleros: [tb,cb,ab,db,ab,cb,tb], lo cual representaría la primera fila del tablero. Quizás haya que ser más precisos y poner: fila(1,[tb,cb,ab,db,ab,cb,tb]).

Si quisiéramos usar esta representación para el tablero completo, podríamos poner:

fila(8,[tn,cn,an,dn,an,cn,tn]).
fila(7,[pn,pn,pn,pn,pn,pn,pn,pn]).
fila(6,[b,b,b,b,b,b,b,b]).
fila(5,[b,b,b,b,b,b,b,b]).
fila(4,[b,b,b,b,b,b,b,b]).
fila(3,[b,b,b,b,b,b,b,b]).
fila(2,[pb,pb,pb,pb,pb,pb,pb]).
fila(1,[tb,cb,ab,db,ab,cb,tb]).

donde tb, cb, ab, db, pb y rb son torre blanca, caballo blanco, alfil blanco, dama blanca, peon blanco y rey blanco, respectivamente (y con sus equivalentes para torre negra, caballo negro,alfil negro, etc.) La "b" representa una casilla vacía.

Muy bien, aquí ya tenemos parte del asunto zanjado. ya podemos representar en claúsulas de prolog el tablero de ajedrez. Ahora sólo resta poder manipular las jugadas y hacer que éstas se representen en el tablero.

En prolog, podemos encontrar el enésimo elemento de una lista de manera muy fácil:

% Hallar el enésimo elemento de una lista.
% El primer elemento de la lista es el 1.

element_at(X,[X|_],1).
element_at(X,[_|L],K) :- K > 1, K1 is K - 1, 
                         element_at(X,L,K1).

Esto significa que hallar, digamos, el quinto elemento de una lista es equivalente a hallar el cuarto elemento de una lista menos su primer elemento, o el tercer elemento de una lista sin considerar los dos primeros elementos, etc. Así se hace fácilmente en prolog.

Ahora basta ver la partida y describir cada jugada como una acción en prolog. Por ejemplo, si tengo la jugada "e2-e4", basta con poner lo que hay en la casilla 52 y pasarlo a la casilla 54. Para ello, ponemos una "b" (de blanco) en la casilla 52 (e2) y lo que había en esa casilla, lo escribimos en la casilla 54. (ver el tablero en la siguiente imagen - correspondence-chess.jpg).

Para hacer la traducción de las coordenadas de cada columna a, b, c, d, e, f, g, h, podemos hacer el siguiente predicado de equivalencias:

equivalencia(a,1).
equivalencia(b,2).
equivalencia(c,3).
equivalencia(d,4).
equivalencia(e,5).
equivalencia(f,6).
equivalencia(g,7).
equivalencia(h,8).

Así, basta ir de jugada en jugada y hacer una rutina que lea las coordenadas, inicial y final, así como la pieza que debe ir ahí y listo, el tablero cambiará su posición. Si la jugada la tenemos como una lista, por ejemplo: [e,2,e,4], el pseudocódigo podría ser algo así:

haz_jugada([X1,Y1,X2,Y2], Pieza) :- 
    /*saca las coordenadas de la posición inicial y final de la pieza que se mueve*/
    /*revisa qué pieza hay en la lista (fila) correspondiente a la posición de la coordenada inicial*/
    /*sustituye el valor que haya ahí por un blanco*/
    /*ve a la posición final y pon la pieza en la coordenada de la fila correspondiente*/

Es claro que este algoritmo no valida si las jugadas son legales o no, pero la idea es que las partidas dadas en formato PGN son correctas y no contienen errores. En caso de contenerlos caemos en "garbage in -> garbage out" (si le das basura al programa regresará basura).

Con esto en mente, podemos hacer un programa que lea el archivo PGN y pase jugada por jugada una partida. Sin embargo, esto sólo puede hacerse de ida, es decir, en una dirección, porque cuando se captura una pieza, por ejemplo, la pieza capturada desaparece y no llevamos registro de esto. Así, si queremos ir, por decir algo, una jugada hacia atrás, pues no podemos hacerlo porque no tenemos información de qué pieza fue eliminada del tablero.

La solución a esto es en realidad crear tantos tableros de ajedrez completos en donde cada jugada esté en uno de ellos. Así, si quiero ir a la jugada 27, entonces pinto inmediatamente el tablero 27. No me tengo que acordar si ahí hubo captura o no de alguna pieza. Si hago así las cosas, entonces mi definición del tablero de ajedrez debo modificarlo para que contemple en qué jugada está el programa en ese momento desplegando el tablero:

             
/*ejemplo de la estructura del tablero para el primer movimiento*/
fila(8,[tn,cn,an,dn,an,cn,tn],1).
fila(7,[pn,pn,pn,pn,pn,pn,pn,pn],1).
fila(6,[b,b,b,b,b,b,b,b],1).
fila(5,[b,b,b,b,b,b,b,b],1).
fila(4,[b,b,b,b,b,b,b,b]1,).
fila(3,[b,b,b,b,b,b,b,b],1).
fila(2,[pb,pb,pb,pb,pb,pb,pb],1).
fila(1,[tb,cb,ab,db,ab,cb,tb],1).
                    

Una partida promedio, digamos de 40 jugadas tendría entences 80 tableros (8 claúsulas por tablero), que se generarían en tiempo de ejecución como claúsulas de prolog. esto significa 640 claúsulas para guardar en memoria, cosa que actualmente cualquier computadora puede hacer sin mayores dificultades.

De hecho, los programas comerciales como Chessbase hacen precisamente esto, aunque como no lo hacen en prolog, usan otras técnicas. No sé en qué lenguaje está escrito Chessbase, pero pienso que es C. Si este es el caso, y si se sigue lo que aquí hemos comentado, entonces un programa que lea una partida PGN creará en tiempo de ejecución un diagrama por cada movimiento. Como en C se pueden crear arreglos bidimensionales, probablemente el tablero esté definido de esta manera y entonces, cuando se hace una jugada, se crea un tablero nuevo, en una estructura dinámica, que solamente pide la memoria necesaria cuando el sistema lo necesita.

Cuando se termina de ver esa partida, se libera toda esa memoria (es mandar los apuntadores a nil, por ejemplo), y entonces tenemos un sistema por demás eficiente.

El sistema de lectura de partidas PGN en Prolog no es el más eficiente, pero es un problema que puede ser atacado por Prolog de manera razonable y además, sin necesidad de pensar en estructuras dinámicas como en otros lenguajes, cosa que en general se aprende hasta un segundo curso de programación.