Too Cool for Internet Explorer

Beautiful Code 2

Hora y Fecha: Mayo 19, 2008 @ 9:24 pm Autor: Moisés Maciá
Categorías:
19 views

Esta es una respuesta para este comentario que al final ha quedado demasiado larga y la pongo aquí.

Veamos, para empezar hay que comprender lo que para los autores del libro es beautiful code: De la misma manera que no se pueden comparar dos poesías por lo melodiosas que suenan al recitarlas, no se puede comparar el código por lo lo estético que resulte.

La belleza a la que se refiere el libro está en los pequeños detalles de la resolución del problema; a veces la belleza reside en lo óptimo del código, la simplicidad, la estructura de la arquitectura, la elegancia del planteamiento, etc. Todos los capítulos hacen referencia a una o varias de estas cualidades.

Hay varios capítulos con implementaciones en el lenguaje C, me voy a quedar con el primero: “A Regular Expression Matcher”, donde el mismísimo Brian Kernighan hace un repaso a las implementaciones de expresiones regulares que se pueden ver hoy en día a lo largo y ancho de lenguajes, librerías, sistemas operativos, etc.

Brian tuvo la necesidad de incorporar expresiones regulares en UNIX pero examinando la implementación de grep le pareció demasiado compleja (~500 lineas), así que desafió a Robert Pike a encontrar la implementación mínima capaz manejar construcciones con:

Carácter Significado
c Coincide con el literal c
. Coincide con un carácter simple
^ Coincide con el inicio de la cadena
$ Coincide con el final de la cadena
* Coincide con cero o más ocurrencias del anterior carácter

Como he dicho, se trata de la funcionalidad básica de un autómata que reconoce expresiones regulares. Perl, grep, awk, etc. son capaces de manejar construcciones mucho más complejas que estas.

Cuenta la leyenda(tm) que Pike se encerró en su despacho, al cabo de un par de horas apareció con 30 líneas de código que implementaban el autómata propuesto por Kernighan y hasta la fecha es la solución óptima al problema.

A esto es a lo que Kernighan llama beautiful code y creo que la afirmación está fuera de toda duda después del show me the code!:

  1.  
  2. /* match: search for regexp anywhere in text */
  3. int match( char *regexp, char *text )
  4. {
  5.     if ( regexp[0] == ‘^’ )
  6.         return matchhere(regexp+1, text);
  7.     do { /* must look even if string is empty */
  8.         if ( matchhere(regexp, text) )
  9.             return 1;
  10.     } while ( *text++ != \0 );
  11.     return 0;
  12. }
  13.  
  14. /* matchhere: search for regexp at beginning of text */
  15. int matchhere( char *regexp, char *text )
  16. {
  17.     if ( regexp[0] == \0 )
  18.         return 1;
  19.     if ( regexp[1] == ‘*’ )
  20.         return matchstar(regexp[0], regexp+2, text);
  21.     if ( regexp[0] == ‘$’ && regexp[1] == \0 )
  22.         return *text == \0;
  23.     if ( *text != \0 && (regexp[0] == ‘.’ || regexp[0] == *text) )
  24.         return matchhere(regexp+1, text+1);
  25.     return 0;
  26. }
  27.  
  28. /* matchstar: search for c*regexp at beginning of text */
  29. int matchstar( int c, char *regexp, char *text )
  30. {
  31.     do { /* matches zero or more instances */
  32.         if ( matchhere( regexp, text ) )
  33.             return 1;
  34.     } while ( *text != \0 && (*text++ == c || c == ‘.’) );
  35.     return 0;
  36. }
  37.  

En el libro se discuten largo y tendido todas las decisiones, casos especiales y alternativas del algoritmo así como la explicación de porque es imposible batir a esta implementación con un lenguaje de alto nivel (básicamente por la manera en que C gestiona las cadenas y la memoria).

El capitulo en cuestión no esta disponible en la red, pero rebuscando he encontrado una explicación similar. Para más detalles podéis encargar el libro en Amazon (es una buena compra), o no.


Bad Behavior has blocked 1150 access attempts in the last 7 days.