El crecimiento de las plantas es una gramática

 

Wolfram, en su libro "A New Kind of Science", hace un trabajo exhaustivo sobre los autómatas celulares en una dimensión. Después de leer en diversas ocasiones algunos de los capítulos de dicho libro, empiezo a sospechar que Stephen Wolfram nos sabe llevar de la mano para poder presentar los resultados de sus investigaciones. Vamos, no llega a conclusiones de la nada, sino que va armando el tema hasta que llega donde él quiere.

Por ejemplo, se inventa unos autómatas, a los que llama "móviles", para así pasar eventualmente a la discusión de si los autómatas en una dimensión son máquinas de Turing, que cabe decir, es un concepto. Alan Turing afirmaba que podía plantearse una máquina capaz de realizar cualquier cálculo. A esto eventualmente se llamaría la máquina universal de Turing.

Pero el punto aquí es que Wolfram demuestra que los autómatas son máquinas de Turing y entonces pasa a un tema por demás curioso: los sistemas de substitución. Por ejemplo, veamos la siguiente imagen:

Lo que aparece en los círculos rojos representan el sistema de substitución de dos diferentes autómatas celulares. Lo que aparece en verde es el inicio de un autómata. Por ejemplo, en la imagen izquierda, el sistema de substitución dice que un punto negro se substituye en un punto negro y uno gris; mientras que un punto gris se substituye por un punto gris y un punto negro.  Si empezamos con el punto negro, al inicio del autómata, vemos que crece (si contamos los números de cuadros nuevos), en dos, cuatro, ocho, dieciseis, etcétera. Este autómata hace un cálculo, el duplicar el valor anterior. En la parte derecha de la gráfica, vems que el sistema de substitución pone un punto negro en un punto gris; un punto gris lo convuerte en un punto gris y un punto negro. Si procesamos el autómata con un solo cuadro gris como generación inicial, tenemos (en cuadros nuevos en total, por generación): 1, 2, 3, 5, 8, 13, etcétera, es decir, la serie de Fibonacci. La imagen anterior entonces muestra dos autómatas que, de acuerdo a las reglas de substitución, o calculan el doble de un número o calculan la serie de Fibonacci.

Si abstraemos un poco la idea, veremos entonces que lo que hemos encirculado en rojo son el software, el programa que se ejecuta en una máquina, en este caso, el autómata celular. Pero podemos ir más lejos, y es expresar ya no con dibujitos, sino simbólicamente estas reglas. Así, para el valor que duplica el autómata podríamos escribir estas reglas de substitución: A --> AB y B -->BA. Esto dará entonces:

A --> AB --> ABBA --> ABBABAAB ...

Lo que tenemos aquí es una gramática, cuyos elementos son A y B, con las reglas de dicha gramática (A --> AB y B -->BA), las cuales permiten generar "todas las oraciones válidas" de acuerdo a las reglas de substitución planteadas. Esto lleva a darnos cuenta que los programas de computadora son reglas de substitución, que generan una gramática y ésta a su vez, al procesarse, es lo que llamamos la ejecución de un programa. 

Pero vayamos más lejos: Si vemos la figura siguiente (ver más abajo), encontraremos el software (los esquemas de substitución), pero como dibujos de lo que asemejarían árboles. Por ejemplo, en la imagen de la izquierda, vemos que una barra oscura se convierte en una barra oscura,con una subrama a la izquierda, oscura también y una subrama derecha gris. Y la segunda regla de substitución nos dirá que una barra (rama) gris, se convertirá en una barra gris con subrama a la derecha gris y a la izquierda negra.

Y esto genera imágenes que sin duda se asemejan a los árboles. Desde luego aquí puede ser que hablemos de cierta simetría que no se llega a ver en los árboles reales, pero estamos ilustrando esto nada más. De hecho, la simetría en los árboles quizás no se da por el ambiente externo donde están, si tienen más acceso a agua y nutrientes, etcétera.

El otro día fui a los viveros de Coyoacán. Paseé por los diferentes negocios y me di cuenta de algo, lo cual es una conclusión que me parece asombrosa: el crecimiento de las plantas es una gramática.

Programación lúdica: escriba un intérprete de Pilot

Pilot (Programmed Instruction, Learning, or Teaching) es un lenguaje simple, muy simple, de programación, el cual fue desarrollado en los años 60s del siglo pasado. Su idea era automatizar algunos sistemas para enseñanza/aprendizaje. A este tipo de programas se les llamó en su momento CAI (computer-assisted instruction). Fue desarrollado por John Amsden Srtarkweather, un profesor de psicología de la Universidad de California (San Francisco), su intención era la creación de pruebas de aprendizaje automatizadas llamadas "Computest".

La sintaxis de Pilot es casi trivial. Una línea en Pilot contiene (de izquierda a derecha), los siguientes elementos sintácticos:

• Una etiqueta (opcional)
• La letra de un comando
• Una letra opcional Y (yes) o N (no)
• Una expresión condicional opcional entre paréntesis
• Dos puntos
• Un operando o múltiples operandos delimitados por comas

Una etiqueta puede estar sola en una línea, sin necesariamente tener más código. La sintaxis para la etiqueta es un asterisco seguido de un identificador (una cadena alfanumérica con una letra como símbolo inicial).

Los posibles comandos son:

R - Las líneas que comienzan con R: indican un comentario que explica en general el código.

A - Acepta la entrada de datos del teclado, por ejemplo:

 R:La siguiente línea de entrada reemplaza el contenido del búffer de datos aceptados
 A:
 R:La siguiente línea acepta una respuesta del teclado y queda en la variable 'FREE'
 A:$FREE
 R:Las siguientes tres líneas de entrada se asignan a las variables 'X', 'Y' y 'Z'
 A:$X,$Y,$Z
 R:Una entrada de datos numéricos se define así, que en este caso queda en la variable "Q"
 A:#Q

C - calcula y asigna valores numéricos. La implementación original de Pilot sólo tiene aritmética entera (y no hay arreglos). Por ejemplo:

 R:Sacar el promedio de #X y #Y en #AM
 C:#AM=(#X+#Y)/2

D - Permite dimensionar arreglos en algunas implementaciones. Para este ejercicio no hay que hacerlo.

E - End. Regreso de una subrutina, o si es fuera de una subrutina, es el fin del programa. No se usa con operandos.

J - Brinca a una etiqueta. Por ejemplo:

 J:*RESTART

M - Verifica la cadena aceptada en la entrada de datos contra una variable o una cadena de caracteres. Por ejemplo:

 M:TRUTH,$MEXICO,YOUTH

Se regresa 'yes' o 'no' dependiendo si las dos variables son iguales o no. Cualquier instrucción que tenga una Y seguido de una letra de comando es procesada si

N - Equivalente a TN

R - para comentarios

T - Operando Type como salida. Ejemplo:

 R:Manda una cadena a la salida
 T:Gracias por su apoyo.
 R:Manda una variable a la salida
 T:Gracias, $NAME.

U - Haz una llamada a una subrutina. Esta empieza con una etiqueta y termina con un comando E:. Por ejemplo:

 R:Llama a la subrutina empezando en la etiqueta *INITIALIZE
 U:*INITIALIZE

Y - Equivalente a TY (que se usa cuando el resultado de un condicional es Y(es))

Un programa ejemplo:

T: Hello, welcome to my program. Please enter a number
A: #num
C: #ans = #num + 7
T: You entered #num. #num + 7 = #ans

Como puede verse, la creación de un intérprete que ejecute programas escritos en Pilot no parece ser muy complicado. Una taza de la Morsa al que implemente mejor este pequeño lenguaje que, desde luego, parece verse superado ante otras muchísimas iniciativas. En cualquier caso es un ejercicio sencillo pero interesante, el cual plantea algunos elementos que deben contemplarse cuando se escriben intérpretes.



Referencias:

Wikipedia 
RPilot 
Byte Magazine (How To Write a Language in 256 Words or Less) 

Para quien quiera programar en Prolog

Prolog (PROgramming in LOGic) es un lenguaje funcional, declarativo, que a diferencia de los lenguajes de programación imperativos, en este caso lo que hace es describir el problema y Prolog, a través de su mecanismo de inferencia (implementado por Robinson en 1968), da los resultados a la problemática definida. Parece magia en algún sentido porque ¿cómo puede ser que un programa mecánico llegue a una conclusión en base a inferencias? Pues no lo es tanto. Prolog usa hechgos y reglas para llegar a conclusiones. Por ejemplo, podemos definir los siguientes hechos:

padre(juan,manuel).
padre(pedro,manuel).

En este caso leemos "manuel es el padre de juan" y "manuel es el padre de pedro".

¿Cómo podríamos hacer la inferencia evidente de que son hermanos? Muy fácil, creando la siguiente regla:

hermanos(X,Y) :- padre(X,Z), padre(Y,Z), X=\=Y.

Lo cual se lee: X y Y son hermanos SI el padre de X es Z, el padre de Y es también Z y X no es Y. 

Tenemos que aclarar esto último (X no es Y), pues sino, el programa reportaría que juan es hermano de sí mismo o que pedro es hermano de sí mismo, lo cual lógicamente no tiene sentido.

Y quizás estamos abreviando demasiado lo que puede hacer Prolog, pero la idea es ésa: poder hacer inferencias y llegar a resultados. Es interesante aclarar que en un lenguaje como estos, muchas veces caemos en el no determinismo, es decir, no podemos saber qué clase de respuestas entregará el programa y si éste entregará acaso alguna respuesta. Un ejemplo de esto puede verse en el problema que Bertrand Russell expresara: "en un pueblo existe un barbero, el cual rasura a todos aquellos que no se rasuran a sí mismos". Y la pregunta que hace Russell: "¿Quién es el que rasura al barbero?

Este tipo de problemas se puede expresar en Prolog, a pesar de que lógicamente no parece haber un resultado. Russell -de hecho- se inventa una teoría llamada "de tipos", en donde los conjuntos están perfectamente definidos. En esta teoría, el filósofo y matemático nos dice: "la pregunta no tiene sentido, es inválida".

Pues bien, el problema de Russell se puede expresar de la siguiente manera en Prolog:

rasura(X,Y) :- not(rasura(Y,Y)).

Esto se lee así: X rasura a Y SI Y no se rasura a sí mismo.

Como puede verse, es una regla recursiva, que se llama a sí misma. Si se ejecuta este programa en algún intérprete o compilador de Prolog, el resultado será simple: error por memoria insuficiente, overeflow, etcétera.

Quien tenga interés en desarrollar programas de esta naturaleza, o de entender mejor el paradigma funcional y declarativo, bien puede usar intérpretes y compiladores que son de código abierto y/o libres. Un ejemplo de ellos es SWI Prolog, el cual es una implementación muy cercana al Prolog estándar. que si mal no recuerdo, tiene ya más de 15 años de haberse propuesto.

SWI Prolog está documentado, hay ejemplos, tutoriales, comunidad de usuarios e incluso, se puede correr en el navegador. Todo esto la hace una herramienta estupenda por muchos motivos, aparte de gratuita, está muy bien cuidada. Échenle un ojo, de verdad me ha convencido.

¿Cuándo no usar Java?

Yo sé que Java prometía ser un lenguaje casi universal, pues parecía cumplir con la expectativa: escríbase una vez y córrase en cuanta plataforma halle. Todo esto es factible porque Java trabaja sobre una máquina virtual y entonces no hay que escribir un compilador para cada plataforma. Se cambia esta ingrata tarea por la de escribir una máquina virtual lo cual, parece ser, es mucho más fácil de hacer. De hecho los emuladores son una solución económica a muchísimos problemas de compatibilidad y el software actualmente tiene el suficiente nivel de abstracción para lograr este cometido.

Java, supuestamente, funciona en algo que se llama un "sandbox", un arenero, una analogía para indicar que lo que corre en el arenero no puede salir de ahí y por ende, los virus son imposibles. Sin embargo, hay reportes de posibles virus como el "Java.Trojan.Exploit.Bytverify.Q", el cual, se dice, aprovecha la vulnerabilidad de Java Runtime Environment para ejecutar código malicioso. El peligro, afirman, acecha en los 'applets' de Java que se integran en las páginas web. A mí no me queda estrictamente claro cómo es esto posible de acuerdo a la definición de seguridad de Java, pero evidentemente no faltará quien haya encontrado una manera de brincarse las trabas que originalmente pone el sistema.

Y la verdad es que Java suena como una muy buena idea y tiene montones de virtudes que no hay que despreciar, amén de que hoy en día hay muchísimas bibliotecas de funciones para todos los gustos y necesidades. Es increíble la cantidad de gente que ha escrito código y rutinas para Java. No es un asunto que deberíamos despreciar.

Sin embargo, el problema es el tipo de aplicaciones y programas que se pueden hacer con Java. En muchos casos, queda claro que Java es una buena opción, pero hay un caso interesante en donde me pone a dudar el usar Java. Se trata cuando las aplicaciones por escribir tienen que ver con sistemas que inherentemente buscan ser seguros. Hablamos de los bancos o bien del SAT, en donde los usuarios (con eso de la factura electrónica), están mucho más involucrados para hacer todo el asunto de sus impuestos vía una página web.

Y si vamos a la experiencia práctica, ocurren una serie de factores que me ha tocado ver de primera mano en el uso de Java y particularmente en el SAT (Servicio de Administración Tributaria). Por ejemplo, si como yo, no se recuerda la clave (contraseña) con la que se definió la FIEL (Firma Electrónica Avanzada), está perdido, porque no podrá facturar electrónicamente. La solución es relativamente simple pero implica ir a la oficina local del SAT para pedir una nueva firma electrónica avanzada. No hay que llevar más que una identificación y un USB o disco compacto para que le graben la información. Curiosamente para ello se puede bajar un programa del sitio del SAT para generar un archivo con extensión ".req" y con él, al ir a la oficina del SAT, le generarán los archivos ".key" y ".cer". Pero oh, uno descarga el archivo y cuando lo quiere ejecutar en el navegador, Java se niega a hacerlo.

Y esto es un solo de los detalles. Otro es el acceso a la información de cada usuario que factura electrónicamente. Por una parte, el manejo de bases de datos parece ser una cuestión crítica y resulta que al hacer una factura nueva, a veces el registro tarda hasta 72 horas en generarse. ¿Tantas horas? ¿Por qué? ¿No debería ser inmediato? ¿Dónde está el cuello de botella? ¿En el manejador de bases de datos usado? Misterio.

Y no quiero exagerar, pero el sistema simplificado de facturación electrónica es malísimo, mal explicado, lento, en donde muchas veces no funciona si uno usa Chrome, Firefox o el inútil pero favorito del SAT, el Internet Explorer. En ocasiones no se sabe qué está pasando porque aparece un símbolo como que el sistema está cargando algo pero no pasa nada en la pantalla en un buen rato. Sigo sin entender muy bien qué software es el responsable de todas estas dificultades.

Si a mí me hubiesen preguntado cómo hacer un sistema de esta naturaleza, hubiese elegido otra opción. Mi enfoque hubiese sido hacer programas clientes para las diferentes plataformas, los cuales pudiesen acceder a las bases de datos de los usuarios en particular. Por una parte, los sistemas tenderían a ser más ágiles, porque solamente se mandarían y se recibirían los datos, sin necesidad de mandar toda la parafernalia que significa por ejemplo, crear la factura electrónica en línea. De hecho, éste es el enfoque de algunos sitios web donde interactúan con el usuario. El sistema en donde se ven sus ventajas es por ejemplo el Internet Chess Club - ICC, un sitio web donde se puede jugar ajedrez en línea. A diferencia de Yahoo, por ejemplo, que su "club de ajedrez" funciona usando un programa que corre en Java en el navegador, el ICC corre un cliente en la plataforma de cada usuario y solamente manda la información relevante de las partidas. La diferencia en el desempeño de Yahoo contra el del ICC es evidente: el segundo supera en agilidad y precisión al sistema escrito en Java.

Mi opinión sobre todo este asunto de usar Java para estos sitios de -digamos- misión crítica [1] no es la mejor. Quizás lo que ocurre es que todo esto de la factura electrónica va evolucionando y por ende, hallamos las dificultades normales porque aún estamos aprendiendo a hacer estas cosas.  No obstante esta argumentación, me queda claro que en este país hay suficiente masa crítica de neuronas que pudo haber llevado a una solución mucho, pero mucho más eficiente en el SAT, y sin necesidad de Java.


___
[1] Podemos entender por sistemas de misión crítica a aquellos servidores que ejecutan aplicaciones esenciales que, si fallan, tienen un impacto significativo en el funcionamiento de cualquier empresa, organización o institución que dependa de su información. (http://www.datacenterdynamics.es/focus/archive/2011/12/%C2%BFqu%C3%A9-es-el-c%C3%B3mputo-de-misi%C3%B3n-cr%C3%ADtica)

Paradigmas en programación... ¿verdad o mentira?

Los lenguajes de programación se basan en diferentes paradigmas. Unos son imperativos. Otros usan la lógica de predicados para funcionar (como Prolog), otros más han definido la programación orientada a objetos, con los subsecuentes beneficios que esto tiene en general para los desarrolladores. Por ello, parece ser necesario saber de qué se trata esto para poder decidir -en algún momento- cuál es el lenguaje a usar.

Curiosamente, como veremos más adelante, hay algo perturbador en esta idea de los paradigmas en los lenguajes de programación y la conclusión a la que llegaremos resulta en alguna medida, inesperada. Entremos pues en materia:

Consideremos las redes semántica, las cuales se representan comúnmente como gráficas consistiendo de nodos que se conectan a través de líneas. Los nodos representan objetos y los enlaces entre nodos representan las relaciones entre esos objetos.

Una red semántica simple puede verse en la siguiente imagen:

Nótese que los enlaces son flechas, lo cual implica una dirección. Así, el perro persigue al gato pero éste no persigue al primero. Esto podría ocurrir pero la red semántica no lo plantea explícitamente.

Las redes semánticas plantean una manera muy intuitiva de representar conocimiento sobre objetos y las relaciones entre ellos. Los datos de una red así se basan en un dominio en particular. Esto hace que el esquema sea limitado. Por ejemplo, no podemos establecer la regla de que "el perro no es un gato".

Cabe decir que muchas de las relaciones son evidentes por sí mismas, pero hacen uso del conocimiento externo que tenemos del mundo. En principio, deberíamos definir dichas relaciones para evitar ambigüedades.

Herencia

Es una relación que puede ser particular útil. La idea de la herencia se entiende fácilmente de forma intuitiva. Por ejemplo, decimos que los mamíferos dan a luz bebes vivos y podemos decir también que todos los perros son mamíferos por lo que podemos concluir que un pero da a luz mamíferos vivos. Sin embargo, no estamos diciendo nada sobre el sexo del perro y por ello la relación no necesariamente sería cierta.

La herencia nos permite especificar propiedades de una superclase y así poder definir una subclase, la cual hereda las propiedades de la superclase. En nuestro ejemplo los mamíferos son una superclase y los perros una subclase.

Frames (marcos)

Los marcos son un desarrollo de las redes semánticas y permiten expresar la idea de herencia. Un sistema de marcos consiste en un conjunto de marcos (o nodos) quienes están conectados por una relación. Cada marco describe una instancia (un marco instancia) o clase (marco clase).

En este contexto, los objetos que se representan son objetos físicos pero no necesariamente tienen que serlo. Un objeto puede ser una propiedad (un color, una forma), un sentimiento, un lugar, una situación. La idea de los objetos en este sentido es idéntica a los que se ven en la Programación Orientada a Objetos (POO).

Cada marco tiene una o más ranuras, también podrían llamárseles "propiedades, a las que se le asignan valores. Esta es la manera en que una red de marcos se construye. En lugar de simplemente tener enlaces entre marcos, cada relación se expresa con un valor en una de las ranuras.

Por ejemplo, cuando decimos que "Fido es un perro" lo que queremos decir es que "Fido es una instancia de la clase perro"  o bien, que Fido es un miembro de la clase perro". Aquí la relación "es un" (is-a) es muy importante en una representación de marcos porque nos permite expresar que alguien es miembro de una clase. Esto se conoce como una generalización porque referirse a la clase de mamíferos es más general que referirse a la clase de perros y referirse a la clase de perros es más general que referirse a Fido.

Es también útil hablar de un objeto que es parte de otro objeto.  Por ejemplo Fido tiene cola, por lo que la cola es parte de Fido. Esto se llama agregación porque Fido puede ser un agregado de las partes de un perro.

Otra relación es la asociación. Un ejemplo es la relación de "perseguir" Esto explica cómo un perro y un gato están relacionados o asociados uno con el otro.

¿Por qué usar marcos?

La ventaja principal de usar sistemas de marcos es que la información de un objeto se encuentra toda en un solo lugar (esto es clásico en el paradigma de la POO). Además, la herencia puede extenderse de la siguiente manera. Por ejemplo:

Los perros persiguen a los gatos
Los gatos persiguen a los ratones

Para expresar este tipo de información, no necesitamos saber que el perro persigue al gato o que éste último persigue a los ratones. Podemos heredar la información porque un gato en particular podría ser una instancia de la clase gatos y en nuestro ejemplo, Fido es una instancia de la clase perro.

Podemos además añadir la siguiente información:

• Los mamíferos respiran
• Los perros son mamíferos
• Los gatos son mamíferos

Y tenemos una superclase, mamíferos, en donde los perros y gatos son subclases. Así, no necesitamos expresar explícitamente que los perros y gatos respiran porque se puede heredar esta información.

Herencia múltiple

Es posible en un marco heredar propiedades de otro marco. En otras palabras, una clase puede ser una subclase de dos superclases y el objeto puede tener una instancia de más de una clase. Por ejemplo, podemos decir que el hombre es un constructor de casas, y que además, es un mamífero. Esto es la herencia múltiple, pero en mi opinión, es absurda si se tiene un sistema con una jerarquía bien armada. A la fecha, de hecho, no he hallado un ejemplo de la necesidad de herencia múltiple para representar conocimiento.

Procedimientos

En la POO las clases (y de hecho los objetos), tienen métodos asociados a ellos. Esto también ocurre con los marcos. Estos tienen métodos asociados a ellos llamados procedimientos.

Un procedimiento es un conjunto de instrucciones asociados al marco que puede ser ejecutado a petición. Por ejemplo, un procedimiento lector de las propiedades puede regresar un valor particular dentro del marco. Otro procedimiento puede insertar un valor en una propiedad. Un procedimiento importante es el constructor de una instancia, el cual crea la instancia de una clase.

Y si pensamos en esto, una red semántica dirigida (los marcos, pues), son un equivalente a la programación orientada a objetos, en donde se definen las propiedades de los mismos, los métodos que pueden usar y la herencia. Solamente quedaría duda de cómo usar el polimorfismo, es decir, cuándo se debe usar un procedimiento de un objeto u otro. Evidentemente esto se puede hacer y entonces, cualquier lenguaje basado en el paradigma de la POO puede ser usado para escribir programas " inteligentes". Es más, hay una clara equivalencia entre los marcos y la programación basada en la lógica de predicados y por ende, si podemos expresar un marco en la POO o bien, en la lógica de predicados, entonces en el fondo no hay un cambio de paradigma. Lo que parece ser que realmente tenemos es un esquema ded representación de conocimiento que no distingue entre paradigmas, porque en el fondo todos los lenguajes que expresan y representan conocimiento, hacen lo mismo.

Este resultado me parece asombroso en cierta medida. Así pues, no hay necesidad de elegir un lenguaje de programación que use un paradigma u otro, cualquiera puede usarse para representar conocimiento de la misma manera.

Nuevo reto de programación lúdica: Óleo digital

Una característica de las imágenes en la computadora es que son digitales, es decir, hechas de dígitos, de números, pues. Cada dígito representa un punto en la pantalla, y normalmente el valor que vemos corresponde al color que ese punto tiene en la imagen. De esta manera, las fotografías digitales (ya sean escaneadas o tomadas con alguna cámara digital), son en realidad una matriz cuadrada de pixeles (puntos en la pantalla), que bien puede ser en color o en blanco y negro.

En la medida en que la tecnología ha progresado, hemos pasado de imágenes de 256 colores a las que nos pueden mostrar alrededor 16 millones de colores. Actualmente, cualquier tarjeta de video que se precie de serlo muestra los tres componentes de color R(ed – rojo), G(reen – verde) y B(lue – azul) en cada pixel (o punto), el cual puede ser un valor entre 0 y 255. De esta manera, 256 x 256 x 256 nos da 16,777,216 posibles colores. Cabe señalar que el ojo humano no puede ver semejante espectro de colores, pero es un hecho que la computadora puede desplegarlos.

Ahora bien, cada fotografía digital es en realidad una aproximación sobre lo que se fotografía tomando una cámara analógica, es decir, una que tenga filme. Por ello mismo, “el grano” de la cámara digital es la precisión con la cual puede distinguir los detalles. Por ello vemos que hay cámaras digitales de 4, 8, 10 o más megapixeles. De hecho, tampoco ya el ojo humano no distingue entre, digamos, 8 y 10 megapixeles. De esta manera, la resolución de las imágenes ha crecido y con ello la necesidad de usar cada vez más bytes en los archivos y memorias donde se guarda.

Con el advenimiento de la tecnología digital de imágenes y su gran aceptación en el mercado, estamos viendo desaparecer las cámaras analógicas y los filmes. Se acabó el revelado y los costos asociados a esto. Además, con la generación de imágenes digitales, también nació la posibilidad de post procesarlas para generar efectos en ellas. Photoshop, por ejemplo, es uno de los programas más populares para manipulación digital de imágenes.

Filtros Digitales

La manipulación de una imagen digital se denomina genéricamente como un “filtro”, el cual convierte una imagen en alguna otra cosa. Existen filtros que son reversibles, mientras que también los hay aquellos que no lo son. De acuerdo a las necesidades, se pueden tener diversos filtros o transformaciones que pueden aplicarse a una imagen incluso ya filtrada. Los resultados suelen ser sorprendentes.

Muchos filtros gráficos, sino es que todos, se consideran transformaciones gráficas basadas en una matriz llamada también “convolución” (no se asuste por la palabra, es sólo un término que da precisión a todo esto). Estas convoluciones es el procesar segmentos de la imagen a partir de una submatriz (que puede ser de 3×3, 4×4, 5×5, etc.) de pixeles, que va recorriendo la imagen completa. El resultado final convierte la imagen original en alguna otra cosa. Existen filtros para reconocer bordes, para quitar ruido, para meter ruido, para hacer más precisa una imagen, para hacerla más borrosa, para deformarla, etc. Las aplicaciones son infinitas.

El filtro Oleo Digital (en tonos de grises)

En el libro Beyond Photography (The Digital Darkroom), de Gerard J. Holzmann, que trabajó algunos años en los Laboratorios Bell, el autor nos habla de cómo alterar imágenes. Ahí presenta la fotografía de Dennis Ritchie (uno de los inventores del lenguaje C), y al procesarla la convierte en la misma imagen, pero como si fuese pintada al óleo. De acuerdo al autor, lo que hace es esto: “Para cada punto en la imagen, un programa calcula el histograma de los 36 bordes del derredor [del punto de interés], en la vecindad del punto de interés, y se asigna el valor [al propio punto que estamos procesando] el valor que contenga la mayor frecuencia. El resultado es casi una pintura al óleo”.

Cuando intenté escribir mi propio programa que hiciese este filtro “al óleo”, decidí, sin embargo, no usar 36 puntos, sino 49, para que así mi matriz (llamada: de convolución), mi cuadrícula, tenga un punto central en [4,4]. Con una convolución par no se puede tener un punto central. Igualmente, generé un arreglo de 256 números (de 0 a 255), para colocar la frecuencia de los 49 valores de la matriz de 7×7, que voy recorriendo en la imagen, pixel a pixel. Así, saco los primeros 49 valores y encuentro la frecuencia de los mismos. En el punto de interés pongo el que tenga la mayor frecuencia. ¿Qué pasa si hay más de uno valor con la mayor frecuencia? ¿Cuál pongo? Cualquiera de ellos. Da lo mismo.

La imagen de la izquierda es la de Dennis Ritchie (el creador del lenguaje C), como aparece en el libro de Holzmann. A la derecha aparece mi propia versión del algoritmo descrito. ¿Cuál le gusta más a usted? Este programa funcionaba originalmente sólo con imágenes en blanco y negro (tonos de grises), pues en imágenes de tonos de gris hay nada más 256 tonos y además, las componentes RGB de cada pixel tienen el mismo valor, es decir, R=B=G, lo cual hace sencillo el encontrar el histograma de frecuencias de color. La diferencia en resultados es que Holzmann usa una matriz par y yo uso matrices impares.

El filtro Oleo Digital (en color)

Para poder generar imágenes al mejor estilo óleo, en color, se necesita hacer una modificación que parece trivial, pero que no lo es. La dificultad es que al querer pasar a color, tenemos que las imágenes pueden contener poco más de 16 millones de colores. Esto, obviamente hace el problema un poco más difícil, pues no podemos generar un arreglo de 16 millones (para seguir con la técnica usada en la parte en tonos de gris), pues es totalmente ineficiente y absurdo. Así, aquí hay que contar y crear el histograma de frecuencias de manera más sencilla. Después de dos semanas de darle la vuelta al problema, finalmente hallé una solución simple. La implementé y de pronto ya tenía mi programa que generaba el óleo digital en color. (¿Cómo le hice?… es parte del reto)

Al poder hacer el histograma y hallar cuál es el valor de mayor frecuencia, simplemente lo pinto para cada punto en la pantalla. Es claro que el filtro hace una imagen que pierde precisión contra una fotografía real, pero se asemeja, sin duda, a un cuadro hecho al óleo.

El reto es pues el siguiente: hágase el filtro óleo en color siguiendo la técnica: “Para cada punto en la imagen, un programa calcula el histograma de los 36 bordes del derredor [del punto de interés] y se asigna el valor [al propio punto de interés] el valor que contenga la mayor frecuencia. El resultado es casi una pintura al óleo”.

He aquí las bases adicionales del reto:

• Ganará el programa que transforme la imagen de Lena (que aparece más abajo), en el menor tiempo posible. El segundo mejor tiempo obtendrá el segundo lugar.
• Habrá dos lugares: Ambos se llevarán una taza con el logotipo de La_Morsa. Mi intención es que al imprimir esas tazas aparezca una leyenda con el título de la misma y el lugar obtenido, para que quede constancia por el tiempo de vida de la taza.
• Los programas pueden hacerse en cualquier lenguaje de propósito general y no se vale usar en éste particularmente, bibliotecas que hagan filtros gráficos. Los programadores tienen que resolver el problema por sí mismo, sin ayuda de bibliotecas externas. (Desde luego, se vale usar alguna biblioteca para cargar/guardar la imagen de Lena para procesarla, la cual es un JPG, pero nada más). Así pues, C, C++, C#, Pascal (Delphi), Javascript, Python, Ruby, Visual BASIC, Visual C, Java, etcétera, son idóneos para esta labor.
• Los autores de los programas deberán mandar el código fuente y el archivo ejecutable en Windows 7.
• Un autor puede mandar versiones mejoradas de su propio software dentro del tiempo del concurso. No se tomarán en cuenta las que se salgan del tiempo establecido.
• En la medida de lo posible, el programa debe indicar el tiempo total del proceso realizado para crear la imagen al óleo de Lena.
• El autor debe enviar el código fuente y quienes ganen aceptan que su código quede accesible para quien lo quiera ver.
• Los programas deben poderse ejecutar en el sistema operativo Windows 7 de 64 bits. Se correrán en una máquina AMD con 6 núcleos y los resultados obtenidos son inapelables y definitivos. De nuevo aclaro: este es un reto de buena fe y no un concurso estrictamente. Los premios son meramente un estímulo extra para que se animen a entrarle al reto. Evidentemente asumo que el código de cada concursante es creación del mismo y que no andan copiando el código de otras partes, foros, sitios en Internet, etcétera. En caso de hallar que el código fue copiado, el programador queda descalificado.
• El reto dura una semana a partir del día de la publicación del artículo. Por ejemplo, si éste se publica un 10 de mayo a las 3 de la tarde, el reto se cierra el 17 de mayo a esa misma hora.
• Cuando reciba algún programa participante en el reto, le enviaré un acuse de recibo para asegurarnos que están todos los que son y son todos los que están.
• El concurso es para quienes viven en la República Mexicana. Si alguien de otro país quiere participar es bienvenido, pero no podrá acceder a los premios.
• Los programas deben ser enviados a morsa@la-morsa.com o en su defecto a lopem@hotmail.com, por si alguna de las direcciones no funciona.

Así que queridos y entusiastas programadores, a entrarle al reto. Afilen sus herramientas de programación y que gane el mejor.

Imagen a procesar (512 x 512 pixeles):

Mi caso contra Javascript

  

En los últimos meses, años quizás, se ha dicho que Javascript es algto así como el nuevo BASIC, aludiendo a que en las computadoras de 8 bits el lenguaje más barato, en términos de recursos de máquina, era el intérprete de BASIC. Ahora Javascript, habiendo pasado una buena cantidad de años -y considerando los aances que han habido en lenguajes de programación- bien podría convertirse en el lenguaje de programación que fuese el más usado para un sinfín de tareas sencillas.

De acuerdo a la siempre sabia Wikipedia:

JavaScript es un lenguaje de programación interpretado, dialecto del estándar ECMAScript. Se define como orientado a objetos, basado en prototipos, imperativo, débilmente tipado y dinámico.

Se utiliza principalmente en su forma del lado del cliente (client-side), implementado como parte de un navegador web permitiendo mejoras en la interfaz de usuario y páginas web dinámicas, en bases de datos locales al navegador... aunque existe una forma de JavaScript del lado del servidor (Server-side JavaScript o SSJS). Su uso en aplicaciones externas a la web, por ejemplo en documentos PDF, aplicaciones de escritorio (mayoritariamente widgets) es también significativo.

JavaScript se diseñó con una sintaxis similar al C, aunque adopta nombres y convenciones del lenguaje de programación Java. Sin embargo Java y JavaScript no están relacionados y tienen semánticas y propósitos diferentes. Todos los navegadores modernos interpretan el código JavaScript integrado en las páginas web. Para interactuar con una página web se provee al lenguaje JavaScript de una implementación del Document Object Model (DOM).

Tradicionalmente se venía utilizando en páginas web HTML para realizar operaciones y únicamente en el marco de la aplicación cliente, sin acceso a funciones del servidor. JavaScript se interpreta en el agente de usuario, al mismo tiempo que las sentencias van descargándose junto con el código HTML.

JavaScript fue desarrollado originalmente por Brendan Eich de Netscape con el nombre de Mocha, el cuál fue renombrado posteriormente a LiveScript, para finalmente quedar como JavaScript. El cambio de nombre coincidió aproximadamente con el momento en que Netscape agregó soporte para la tecnología Java en su navegador web Netscape Navigator en la versión 2003 en diciembre de 1995. La denominación produjo confusión, dando la impresión de que el lenguaje es una prolongación de Java, y se ha caracterizado por muchos como una estrategia de mercadotecnia de Netscape para obtener prestigio e innovar en lo que eran los nuevos lenguajes de programación web.


Pues bien, hace poco decidí echarle un vistazo más serio a Javascript y me hice de un par de libros que empezaran desde cero. Asumiendo que he programado por muchos años y que los lenguajes de programación finalmente comparten los mismos preceptos, no debería sr muy pronunciada la curva de aprendizaje.

Estoy leyendo el libro "Javascript programming for the Absolute Beginner", de Andy Harris, Ed. Prima Tech., y encuentro que francamente no es el mejor para hacer de la programación una disciplina. Veamos algunos ejemplos:

Este primer programa pide un nombre del usuario (del teclado) y pone una ventana saludándolo. Hasta aquí se ve simple y fácil. La expresión:

greeting  = "Hi, " + userName + "!!";

"pega" la cadena "Hi, "con el nombre escrito por el usuario y termina pegando la cadena "!!".

Pero veamos cuando trabajamos con números:

Si corremos este programa, hallaremos que al desplegar el programa el total de la cuenta, (asumiendo, por ejemplo, que la comida costó 100 pesos y la propina fue de 15 pesos), el resultado que dará es "10015", lo cual está mal, evidentemente. Resulta que cuando se pone:

var total = meal + tip;

Hallamos que pega ambas cantidades como si fuesen cadenas de caracteres. Pero fíjense que en el caso de la siguiente línea:

var tip = meal * .15;

el sistema entiende que el valor que está en la variable "comida" es un entero y hace el cálculo correctamente.

Dicho de otra manera, Javascript no es un lenguaje que preste atención a la tipificación de variables y esto es en mi opinión un diseño que no promueve una disciplina correcta en el arte de programar. Lo adecuado sería, e incluso el inventor de Pascal, Niklaus Wirth, estaría de acuerdo conmigo es que las variables se identifiquen como de cadenas de caracteres, reales, enteras, etc. Pero no, no pasa esto y entonces hay que adivinar el comportamiento del sistema.

El problema no es el ejemplo, que finalmente se soluciona agregando

//ponemos el valor de la variable 'meal' como un número y
//y no una cadena de caracteres
meal = eval(meal);

sino la cantidad potencial de errores que pueden darse por esta situación. Es francamente ridículo que a estas alturas de los lenguajes de programación tengamos que pasar por este tipo de lenguajes no tipificados. Y por cierto, PHP hace lo mismo.

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.