Traduciendo morse con Prolog

Ayer estaba tumbado en la cama pensando en nimiedades (qué nos depara el futuro, cuál es el sentido de la vida, a qué huele un Cloud Computing…) cuando pensé lo mucho que molaría aprender morse. Así que saqué una cheatsheet del lenguaje y me interrogué, ¿cuál puede ser la forma más fácil de aprender? Está claro que siguiendo el orden alfabético no. Una A es un punto y una raya, mientras que una E es solo un punto, y dos puntos hacen una I, y… No, no es la forma más fácil. En un primer momento pensé que representar el lenguaje en una especie de autómata que cambiase de estado con puntos, rayas y tiempos haría un buen mapa que poder aprender por secciones. Pero, por supuesto, hay una forma más fácil. Si únicamente tenemos en cuenta los puntos y los espacios para cambia el autómata de estado, ¿qué tenemos? Un árbol binario. Así que tras una breve búsqueda, resulta que sí, que morse se puede representar como un árbol binario bastante bien equilibrado.

Figura 1: la codificación morse como árbol binario

Figura 1: la codificación morse como árbol binario

¿Y en qué lenguaje de programación es muy sencillo representar árboles? Efectivamente, Prolog. Mediante el predicado transition(Origin, Character, Destination) representamos las transiciones dentro del árbol. Por ejemplo, transition(start, ‘.’, e) o transition(e, ‘-‘, a). Si introducimos una secuencia morse mal codificada, en algún momento se caerá en una transición que no esté entre los hechos y el predicado no unificará, por lo que la traducción sencillamente fallará sin tener que preocuparnos más del resto.

Ahora necesitamos una forma de introducir una secuencia de rayas y puntos, que el programa se vaya desplazando por el árbol, y que cuando se encuentre un espacio como siguiente caracter, se apile el nodo actual. Para ello tengo el predicado translate(Lista, Pila, Posicion, Resultado). Lista será la lista de puntos, rayas y espacios. Pila será otra lista donde iremos apilando los caracteres traducidos, y que ha de estar instanciada en el momento de la llamada. Posición se refiere al nodo actual del árbol, y Resultado será la lista de caracteres traducidos. Tengo los cuatro siguientes predicados translate.

translate([Ca|Co], T, A, R):-
    Ca /= ' ',
    transition(A, Ca, S),
    translate(Co, T, S, R).

Si la cabeza de la lista de puntos y rayas no es un espacio, se busca la transición que tenga como origen la posición actual, y como caracter de transición la cabeza de la lista. Una vez lo tengamos, desapilamos la cabeza y volvemos a llamar a translate con la nueva posición. Si la unificación con el predicado de arriba falla, es que hemos encontrado un espacio.

translate([Ca|Co], T, A, R):-
    translate(Co, [A|T], start, R).

Desapilamos el espacio, añadimos la posición actual a la cabeza de la lista de caracteres ya traducidos y llamamos de nuevo a translate desde el nodo inicial. ¿Qué pasa si a nuestra lista le queda un único elemento?

translate([Ca], T, A, R):-
    transition(A, Ca, S),
    translate([], [S|T], start, R).

Hacemos básicamente lo mismo que antes y llamamos a translate con una lista vacía. Lo que, por último, nos lleva al caso base.

translate([], T, start, R):-
    reverse(T, R),
    !.

Como en la lista auxiliar hemos ido apilando los resultados, para conservar el orden original hay que invertir la lista. Con esto ya podríamos traducir morse, pero introducir listas de puntos y recibir listas de caracteres es muy engorroso, así que para terminar, vamos a darle un poco de azúcar.

translate_morse(Text, Result):-
    atom_chars(Text, List),
    translate(List, [], start, Chars),
    atom_chars(Result, Chars).

El predicado atom_chars/2 unifica cuando el primer parámetro es la representación en string de la lista de caracteres del segundo parámetro. Así, es sencillo primero separar la entrada y luego volver a unir la salida.

¡… .- .-.. ..- -.. — …!

 

Deja un comentario