sábado, 26 de noviembre de 2011

Descomentador De C/C++

Una de las primeras cosas que aprendemos cuando nos iniciamos en cualquier lenguaje de programación es que debemos comentar de manera correcta nuestro código, es más, muchos autores han dedicado una buena parte de sus libros con temas relacionados a los comentarios, cómo redactarlos y dónde ponerlos. Pero ¿Qué pasaría si no quisiéramos comentar nuestro código? Mejor aún ¿Qué pasaría si no quisiéramos comentarios de ninguna índole en nuestros ficheros fuente?; el mundo da vueltas (!).

El programa descomentador que presento en este artículo está basado en las especificaciones de esta página COS 217. Solo funciona con ficheros fuentes de C o C++. Si no se especifica ningún fichero en los argumentos, el programa lee de la entrada estándar e imprime por pantalla.

Recuerda que necesitarás una shell para ejecutar los siguientes mandatos, preferiblemente Bash.

Si no quieres leer todo este artículo y solo quieres quitar los comentarios de un fichero, puedes usar la siguiente orden, después de haber compilado el programa correctamente.
./decomment comentado.c 2>/dev/null > comentado.c
Compilar Programa
Para compilar con gcc ejecuta uno de los siguientes mandatos
#Compilar
$ gcc decomment.c -o decomment

# También puede permitir que gcc optimice el código para mayor rapidez 
$ gcc -O2 decomment.c -o decomment

# Optimizar un poco más (quizás)
$ gcc -O2 -fomit-frame-pointer decomment.c -o decomment
Modo de empleo
# Quita comentarios e imprime por pantalla
$ ./decomment comentado.c

# Guardar resultado en un fichero
$ ./decomment comentado.c > nocomentado.c

Si el descomentador llega al final del fichero fuente y no encuentra un cierre de comentario, imprimirá una línea como esta: Error: línea x: comentario no cerrado. Si estás consiente de que tu fichero fuente quizás esté mal formado, podrías obviar ese aviso y quitar los comentarios de todas maneras, así:

# Quita comentarios, imprime por pantalla y obvia errores
$ ./decomment comentado.c 2>/dev/null

# Si quiere redirigir la salida a un fichero solo debe hacer
$ ./decomment comentado 2>/dev/null > nocomentado.c

# también podría hacerlo así
$ ./decomment < comentado.c 2>/dev/null > nocomentado.c

Si tus intenciones son eliminar todos los comentarios de un árbol completo de ficheros fuentes, tan solo debes de poner el siguiente programa para Bash a trabajar dentro del directorio raíz:
#!/bin/bash
DEC=./decomment # ruta absoluta del programa decoment
OLD_IFS=$IFS
IFS=$'\n'
for line in `find -iname '*.c' -or -iname '*.h' -or -iname '*.cpp'`; do
   $DEC $line 2>/dev/null > tmpfile
   mv tmpfile "$line"
done 
IFS=$OLD_IFS
Si lo que deseas es no dejar rastros de comentarios por ninguna parte, entonces deberías ir a por las copias de seguridad que hacen algunos editores de texto. El siguiente script busca los ficheros C o C++ y sus copias de seguridad. Sin misericordia, por ejemplo, este script es capaz de encontrar  "la copia de seguridad de la copia de seguridad de la ...", así una copia de seguridad que tenga el nombre: programa.cpp.old.back.old.old~ será procesada. Ten mucho cuidado con este script, pues no hay vuelta atrás.
#!/bin/bash
DEC=./decomment # ruta absoluta del programa decoment
REGEX='.*\.([ch]|cpp)(\.?(~|old|back))+?$'
OLD_IFS=$IFS
IFS=$'\n'
for line in `find -regextype posix-extended -iregex $REGEX`; do
   $DEC $line 2>/dev/null > tmpfile
   mv tmpfile "$line"
done
IFS=$OLD_IFS
Portabilidad

Este programa se puede ejecutar (compilar) en cualquier sistema operativo que posea un compilador para lenguage C compatible con ANSI C. De todas maneras listaré los sistemas donde no habrá problemas para compilar y ejecutar el descomentador:
  • GNU/Linux
  • FreeBSD, OpenBSD, NetBSD
  • Mac OS X
  • Windows
AVISO

Recuerde que descomentar ficheros fuentes podría resultar en grandes consecuencias morales y económicas, se desaconseja su uso, úselo cuando sea realmente necesario y bajo su propia responsabilidad, no me hago responsable de lo que pueda pasar o de los archivos que se corrompan usándolo.

Despedida

Si  bien hice todo lo posible por seguir buenas maneras y estilo mientras programaba el descomentador, todo se fue a pique cuando tuve que reducirlo a un fichero para poder distribuirlo con Google Docs; mis más sinceras disculpas.

¿Tienes alguna funcionalidad nueva en mente? ¿Encontraste algún error o tienes alguna inquietud? No dude en hacérmela saber.

Descarga Código Fuente Del Programa

jueves, 18 de agosto de 2011

Las Funciones memcpy() Y memmove()

Cuando terminamos el ciclo básico y dominamos una buena parte de las funciones de entrada y salida, empezamos a sentirnos agobiados por la incapacidad de mover y copiar la información que obtenemos. Quisiéramos o no, nos vemos forzados a estudiar las funciones para la manipulación de caracteres.

La  función strcpy es la que primero hallamos y utilizamos hasta que vemos su peligro, luego es strncpy, mas prometedora que strcpy pero el peligro aun toca la puerta, y al igual que strcpy solo funciona con cadena de caracteres y corrompen los datos al agregar el carácter \0 al final (con strncpy no siempre es cierto).

Buscando hallamos a memcpy() y memmove() e inmediatamente caemos en una encrucijada ¿Cuándo debo usar memmove? De esto se trata este artículo, explicar cuando utilizarlas y porque.
/* Tomado del código fuente de linux */
void *memcpy(void *dest, const void *src, size_t count)
{
 char       *tmp = dest;
 const char *s   = src;

 while(count--)
  *tmp++ = *s++;
 return dest;
}
Debido a la gran cantidad de versiones y optimizaciones realizadas a esta función, copie esta implementación para la cual su comportamiento está definido en todas las arquitecturas (no intentes optimizarla con el compilador). Antes de entrar en lleno, examinemos que dicen las especificaciones de ambas funciones con el Traductor 9000:


Todo parece estar bien, a excepción de esa palabra; superposición. Para entender más un poco sobre la superposición entre dos áreas de memoria, veamos un ejemplo visual sin superposición, pero antes definamos (de manera vaga) lo que superposición significa (para nuestros fines).
Es cuando dos áreas de memorias están correlacionadas y una modificación en una de las partes se ve reflejada a lo largo de las modificaciones siguientes.

Como se puede apreciar en la animación, una modificación en una área de memoria no afecta las modificaciones sucesivas. Veamos ahora otra animación un ejemplo que muestra claramente la superposición.

En la animación anterior, el uso de la función memmove es necesario. A estas alturas te podrías estar empezando a preguntar si  utilizar memmove y nunca memcpy, la respuesta simple es: podría. Los tíos de FreeBSD (quizás otros) meditaron sobre esto y modificaron su API, de manera que cuanto intentes utilizar memcpy o memmove, sin darte cuenta estarás usando bcopy; función muy parecida a memmove.

Despedida

Luego de haber leído este artículo sería lógico si terminas preguntándote ¿Cuál es el propósito de la función memcpy? ¿Introducir posibles errores en nuestra aplicaciones o copiar áreas de memoria? La respuesta es que memcpy algunas veces posee optimizaciones específicas; es más rápida.

Ahora que conocemos la diferencia entre ambas funciones usarémos memmove solo cuando sea necesario; siempre tratemos de utilizar memcpy, la cual en muchos casos posee mayor rendimiento.

Comentarios y Cosas Raras
 ... os he atrapado con las manos en la falda ¡Qué problema! ¿Eh? Terroríficas, precisas y calculadoras (frías), no podemos escapar de ellas; nos tienen dominados ...
Enlaces
  1. Ejemplo sin superposición
  2. Ejemplo con superposición
  3. Ejemplo con memmove

lunes, 15 de agosto de 2011

Buenas maneras para programar y técnicas de legibilidad

Anteayer estaba observando una carpeta con ficheros fuentes de ANTAÑO. Viendo estos ficheros fuentes (míos todos) difíciles de leer, con estilos diferentes y buenas técnicas de ofuscación (!), decidí elaborar este artículo que contiene de manera resumida una listas de buenos modales para utilizar mientras se programa.

Aclaro que ninguna de estas normas son de carácter obligatorio, pero se sugiere su puesta en práctica. Muchas de estas recomendaciones no son mías, son solo una compilación de aquellas que considero se deben poner en práctica y tomar en consideración por todos los programadores, principalmente por aquellos que programan en C, que es a los que principalmente está dirigido el artículo.

Maneras
Fuera de código
  • Recicla unas cuantas hojas de papel e imprime una copia del documento «GNU Coding Standards» y no lo leas, solo quémalo; será un lindo y simbólico gesto. Linux
  • Lea el fichero Conding Style (Estilo del código) encontrado en la documentación del proyecto al que piensas contribuir, apega tu estilo de programar en lo posible a sus demandas, pues, muchos proyectos son muy inflexibles en este asunto. Newbie Shell
  • Cuando inicies un nuevo proyecto y redactes el fichero Coding Style, se flexible, de esta manera ganarás la voluntad de más personas para que te ayuden en tu proyecto. Newbie Shell
Sangrado
  • Si necesitas más de 3 niveles de sangría (identation) en tu código, vas mal y deberías reparar tu programa. Linux
  • Evita si puedes, sagrados menores de cinco espacios de longitud. Sangrados muy pequeños pueden causar problemas de visibilidad de bloques y ocasiona en el peor caso problemas de legibilidad y fluidez mientras se programa.  (Linux y FreBSD hablan de esto pero sugieren ocho espacios. Cinco espacios es la media y es una buena media)
  • Usa la tecla Tab para sangrar y no espacios; utiliza espacios y no la tecla Tab para alinear. De esta manera tus ficheros fuentes serán portátiles (portable) entre editores, podrás darles formato a gusto y tendrán menor tamaño. Si considera que este tipo de cosas son triviales, debería reconsiderarlo y leer este artículo Tabs vs Spaces An Eternal Holy War de J. Zawinski. Newbie Shell
  • No pongas un else justamente después de un return, es innecesario y aumenta el nivel de sangrado del código. Asterisk
if(algo) {
      esto();
      return aquello;
} else {
      lo_otro();
      /* muchas líneas de código */
      return CONSTANTE;
}

Mejor así

if(algo) {
      esto();
      return aquello;
}
lo_otro();
/* muchas líneas de código */
return CONSTANTE;



Generales
  • Divide los problemas en subproblemas mas simples tantas veces como sea necesario, hasta que la resolución de los subproblemas se torne obvia. Newbie Shell, Alg. Divide y Venceras
  • Puedes utilizar goto, con buenas practicas y cuidado, para saber cómo, observa el fichero /usr/src/linux/kernel/fork.c de tu distribución GNU/Linux favorita. Newbie Shell
  • Los nombres de las funciones y métodos deberán estar en minúsculas y las palabras separadas por un guion bajo. Gimp
  • Los nombres de las variables y los nombres de los campos de las estructuras, deberán estar todos en minúsculas. Asimismo se sugiere que trates en lo posible de que los nombres de las estructuras estén en minúsculas también.
  • Los nombres de las variables y las funciones deberán ser cortos pero significativos. Los nombres de variables de una sola letra deberán evitarse, a excepción de las variables temporales desechables. Para el caso anterior, utiliza los nombres i, j, k, m, n para enteros; c, d, e para caracteres; p, q para punteros; s y t para puteros a cadena de caracteres. (SunOS) OpenSolaris
  • Evita en lo posible variables con nombres largos y de varias palabras como en: pointer_to_a_list en su lugar piensa y reduce el tamaño así: list_ptr, quizás listptr o listp. Newbie Shell
  • No utilices números mágicos, en su lugar usa constantes. Newbie Shell
  • Los valores de las enumeraciones deberán estar en mayúsculas. FreeBSD
  • Evita en lo posible usar variables globales, piensa sobre la necesidad de usarlas y en el mejor caso, escribe una explicación breve sobre las claras ventajas y las pocas desventajas. Tome dicho texto y agréguelo como documentación. Newbie Shell
  • Los nombre de las constantes deberán estar en mayúsculas.
  • En lenguaje C, no hagas conversión de tipo (void *). Conversiones implícitas de/a (void *) son explícitamente aceptables por la especificación de C. Asterisk
  • El número de variables locales utilizadas no deberá ser mayor de 10, de lo contrario estas haciendo algo mal. Piensa la función una vez mas y divídela en pedazos más cortos. Un cerebro humano por lo general puede mantener fácilmente el rastro de siete cosas diferentes, una cosa mas, y se confunde. Linux
  • Los comentarios son buenos, pero existe el peligro de sobrecomentar el código. Nunca trates de comentar cómo funciona tu código en un comentario, es mejor programarlo de manera que su lectura y significado sean visibles. Linux
  • Al declarar variables, utiliza un línea por declaración, de esa manera podrás agregar pequeños comentarios a cada una de ellas sobre su uso.
  • Al hacer comparaciones, pon la parte literal en la parte izquierda de la comparación y la parte variable en la parte derecha. Con esta técnica podrías evitar errores de tipografía, muchas veces no detectado por el compilador y muy difíciles de encontrar cuando los buscas. Sucede cuando por error pones un = en vez de == . Peter Van Der Linden Ejem:
/* Utilice */
if(CONSTANTE==var)

/* en vez de */
if(var==CONSTANTE)
 
Despedida

Sin dudas existen más recomendaciones propuestas por los programadores de los proyectos exitosos de allá fuera, pero a mi entender las que listo aquí son las más significativas a la hora de programar.

Si eres programador, experimentado o no, deberías intentar cumplir cada una de estas normas para programar o al menos intentar desarrollar tus propias estrategias de escritura basadas en el mismo propósito que intentan cumplir estas técnicas; Estilo Y Legibilidad.

Comentarios y cosas raras
3:00 am

– escribiendo de forma muy rápida – tac tac tac tac [¡espeis!] tac tac tac next tac tac tac tac [¡espeis!] step continue tac tac tac [enter] [enter] ... ¡Segmentation Fault! ...  ¡AH! Funciona, JODER ... por favor.

Referencias
  1. Asterisk Coding Guidelines
  2. FreeBSD kernel source file style guide
  3. C Style and Coding Standards for SunOS
  4. Linux kernel coding style

domingo, 10 de abril de 2011

Ortografía

Hace poco discutía los detalles de un proyecto sobre: análisis sintáctico, recolección y clasificación de información. No fue sino hasta estar enfrente de twitter, que pude ver la calidad de la información que circula por la red ¡Mentiría! Si dijera haber encontrado un twit con buena ortografía y ni hablar de la gramática.

En parte esto se debe al limite de caracteres de algunas páginas web y que la mayoría de los usuarios publican desde sus dispositivos móviles mientras hacen otras cosas. Bueno entrando en materia; un corrector ortográfico podría resultar muy práctico. Buscando información al respecto me topé con el blog de un tío (el Google's Director of Research) quién implementó un corrector ortográfico en el avión camino a casa en tan solo 22 líneas de Python-2.5, con una precisión de ~89%

import re, collections

def words(text): return re.findall('[a-z]+', text.lower()) 

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model

NWORDS = train(words(file('big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(word):
   splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes    = [a + b[1:] for a, b in splits if b]
   transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
   replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
   inserts    = [a + c + b     for a, b in splits for c in alphabet]
   return set(deletes + transposes + replaces + inserts)

def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

def known(words): return set(w for w in words if w in NWORDS)

def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get)
Peter Norvig, el autor, para sus fines solo necesitó un fichero de texto (cuentos de Sherlock Homes) y el Teorema de Bayes. En vista de la aceptación que tuvo y lo divertido que se veía, decidí intentarlo con Ruby y hacer una entrada con mis resultados. Sin mas, les dejo mi versión. (en 23 líneas)

def words(text); text.downcase.scan(/[a-z]+/); end

def train(wds)
  model = Hash.new(1)
  wds.each {|w| model[w] += 1}
  model
end

$alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(wd)
  del=[]; tras=[]; alt=[]; ins=[]; len=wd.length; allen=$alphabet.length + 1
  len.times    {|i| del << wd.delete(wd[i]) }
  (len-1).times{|i| w=wd+''; w[i],w[i+1]=w[i+1],w[i]; tras << w }
  len.times    {|i| w=wd+''; allen.times{|j| w[i]=$alphabet[j].to_s; alt.push w+''}}
  (len+1).times{|i| allen.times{|j|  w=wd+''; w.insert(i,$alphabet[j].to_s); ins.push w+''}}
  ret = del+tras+alt+ins; ret.empty? ? nil : ret
end

File.open('./big.txt') {|fd| $nwords=train( words( fd.read ) )}

def known_edits2(wd, re=[])
  edits1(wd).each{|e1| edits1(e1).each{|e2| re << e2 if $nwords.has_key?(e2)}}; re.empty? ? nil : re
end

def known(wds, re=[]); wds.each{|w| re << w if $nwords.has_key?(w)}; re.empty? ? nil: re; end

def correct(wd)
  (known([wd])||known(edits1(wd))||known_edits2(wd)||[wd]).max{|a,b| $nwords[a] <=> $nwords[b]}
end
 Comparando ambos códigos

Python25
~ $ time python spell.py 'eviroment'
environment

real    0m1.015s
user    0m0.960s
sys     0m0.053s
Ruby19
~ $ time ruby spell.rb 'eviroment'
environment

real    0m2.128s
user    0m2.027s
sys     0m0.087s
Ruby19        (  Brian Edkins )
~ $ time ruby spell_edkins.rb 'eviroment'
environment

real    0m2.173s
user    0m2.080s
sys     0m0.077s
A simple vista se puede ver que la versión de Norving es más rápida. También tomé la versión de Edkins y la sometí, logrando un tiempo semejante al nuestro. Sin lugar a duda la versión de Norving es mejor, pero no quiere decir que nos quedaremos de brazos cruzados, lo que pasa es que el algoritmo que él utilizó es muy eficiente. Tratemos de reimplementar el método edits1 lo más semejante posible a la versión de Norving:

# Opción 1, este es un poco más limpio
def edits1(word, set=[])
  splits      = (0..word.length).map{|i| [ word[0...i],word[i..-1] ] }
  splits.each {|a,b| set << (a + b[1..-1]) if b!='' }
  splits.each {|a,b| set << (a + b[1] + b[0] + b[2..-1].to_s) if b.length>1 }
  splits.each {|a,b| $alphabet.each_char{|c| set << (a + c + b[1..-1].to_s)} if b!=''}
  splits.each {|a,b| $alphabet.each_char{|c| set << (a + c + b) } }
  set
end

# Opción 2
def edits1(word, del=[], tra=[], rep=[], ins=[])
  splits      = (0..word.length).map{|i| [ word[0...i],word[i..-1] ] }
  splits.each {|a,b| del << (a + b[1..-1]) if b!='' }
  (word.length-1).times{|i| w=word.dup; w[i],w[i+1]=w[i+1],w[i]; tra << w }
  splits.each {|a,b| j=-1;  rep << (a + $alphabet[j] + b[1..-1].to_s) while $alphabet[j+=1]  if b!=''}
  splits.each {|a,b| j=-1;  ins << (a + $alphabet[j] + b) while $alphabet[j+=1] }
  del+tra+rep+ins
end
Como ven imprudentemente utilicé el espacio de los argumentos de los métodos para poder declarar algunas variables y optimizar un poco de espacio, todo sigue igual,  veamos que tal van las cosas:
~ $ time ruby spell.rb 'envroment'
environment

real    0m1.527s
user    0m1.480s
sys     0m0.047s
Aunque hubo una mejora apreciable de 0.601s ó 39.36%, Python sigue siendo 0.512s o 33.36% mas rápido, acercándose mucho a los tiempo de la implementación en C de Toledo. Por más vuelta que le di al asunto, no pude optimizar más el método edits1, después de todo, sigo siendo un newbie. Si tienes alguna implementación que me ayude a batallar los Pythonistas hacédmela llegar.

Ideas
  • Utilizar este algoritmo y la librería Link-Grammar para obtener basados en el número de null-links, la palabra adecuada al contexto.

Despedida

Bueno, creo que eso es todo, solo me queda por decir, que este corrector funciona con otros idiomas también, solo debes alimentarlo con texto adecuado y modificar la variable alphabet (agregando la ñ y las respectivas vocales acentuadas en el caso del español). Si decides hacerlo con Ruby, sería buena idea utilizar el comentario mágico  encoding: <codificación> para evitar problemas de codificación.

Referencias  
«Peter Norvig»  How to Write a Spelling Corrector
                      ~  Archivo de prueba big.txt
«Brian Edkins» http://lojic.com/blog/2008/09/04/how-to-write-a-spelling-corrector-in-ruby/ 
«Marcelo Toledo» http://marcelotoledo.com/2007/08/10/how-to-write-a-spelling-corrector/