martes, 10 de enero de 2012

Identificando números primos con expresión regular en Perl

Lista de números primos

Como puede resultar raro que una expresión regular tenga algo que ver con los números primos quiero aclarar algo : este artículo no es una broma. Las  expresiones regulares provienen fundamentalmente de la rama de la teoría de compiladores y son el bloque fundamental de muchos lenguajes de programación. Esto se debe en primer lugar a que son utilizadas por el analizador sintáctico del lenguaje. Además hay librerías para trabajar con expresiones regulares en la gran mayoría de los lenguajes de programación (de alto nivel ;) . Estas expresiones están relacionadas con las  máquinas de estado y algunos  autómatas simples. Otra historia muy diferente son los  números primos, los archi-conocidos guardianes de gran parte de los secretos más celosamente guardados de la  teoría de números. A continuación trato un tema de esos que evidencian las extrañas conexiones entre la informática y las matemáticas y que me dejó sin palabras cuando supe del truco recientemente por primera vez. Antes ya he otras curiosidades similares . Recuerdo ahora por ejemplo el  artículo publicado anteriormente acerca de los  números de Fibonacci. La vida es bella ... y los números y la informática todavía son capaces de sorprendernos. En caso que Usted desee estar al tanto de curiosidades matemáticas semejantes, les invito a  suscribirse mediante RSS.

Los hechos

Para ir directo al grano, la expresión regular es la siguiente :

perl -lne '(1x$_) =~ /^1?$|^(11+?)\1+$/ || print "$_ is prime"'

¿Puede darse cuenta de cómo funciona? Más adelante ofrezco una explicación, pero trate de descifrarlo Usted mismo. A continuación les presento lo que ocurre cuando se ejecuta (es preciso teclear el número que se desea comprobar y pulsar la tecla Enter para que el comando facilite la respuesta ;)

$ perl -lne '(1x$_) =~ /^1?$|^(11+?)\1+$/ || print "$_ is prime"'
1
2
2 is prime
3
3 is prime
4
5
5 is prime
6
7
7 is prime
8
9
10
11
11 is prime
127
127 is prime
1009
1009 is prime
1234577
1234577 is prime

Con números grandes el comando puede tardar un poco en dar una respuesta. Sea paciente ;)

¿Cómo funciona?

En primer lugar el número es convertido a su representación unitaria mediante (1x$_) . Por ejemplo el número 7 es convertido en 1x7, que es 1111111 (o sea 1 repetido 7 veces ;). En términos generales la idea consiste en aplicar posteriormente la expresión regular que aparece en el miembro derecho a esta cadena. Si se encuentra una coincidencia el número es compuesto sino es primo.

Explicaré a continuación cómo funciona la expresión regular. La misma consta de dos partes ^1?$ y ^(11+?)\1+$. La primera reconoce el número 1 y la cadena vacía. Ambos casos se considera que no son números primos. La segunda determina si dos o más 1s repetidos llegan a conformar una parte del número. Si este es el caso entonces el número es compuesto sino es primo.

Dos ejemplos

Veamos cómo es que funciona todo con los números 5 y 4.

La representación del número 5 es 11111. La expresión (11+?) reconoce los dos primeros dígitos (i.e. 11). La referencia \1 se instancia al mismo valor (i.e. 11) y la expresión regular en sí se expande a ^11(11)+$. La misma no puede aceptar cinco números uno, por tanto falla. Sin embargo, como se utilizó +?, se inicia el mecanismo de backtracking y reconoce los tres primeros dígitos (i.e. 111) . La referencia \1 se instancia al mismo valor (i.e. 111) y la expresión regular en sí se expande a ^111(111)+$. Tampoco tiene éxito ese intento. El proceso se repite para 1111 y 11111, que tampoco aporta una coincidencia. Por tanto la expresión regular en el global no devuelve coincidencia y se concluye que el número es primo.

La representación del número 4 es 1111. La expresión (11+?) reconoce los dos primeros dígitos (i.e. 11). La referencia \1 se instancia al mismo valor (i.e. 11) y la expresión regular en sí se expande a ^11(11)+$. En este caso la representación original sí es aceptada por la expresión regular expandida. Por tanto la expresión regular en el global sí devuelve una coincidencia y se concluye que el número es compuesto.

Conclusiones

Debo dejar claro que no tomo el crédito por haber descubierto este truco. Al parecer fue inventado por  Abigail en 1998. Hay que aclarar que el ejemplo mencionado no es exactamente ni una expresión regular (atendiendo a su definición formal) ni tampoco es un método para verificar si un número es primo. Es simplemente algo raro que se puede hacer con Perl. Le invito a  suscribirse a este blog y así descubrir juntos los secretos de la matemática y la informática.

jueves, 5 de enero de 2012

El SPDY de Google no es tan malo como el Internet Explorer (IMO)

Windows Phone vs Android vs ...

Érase de una tarde de diciembre fría y nublada cuando debatía el archi-tema de Microsoft vs software libre en  una conversación con mis amigos  Román Fresneda,  Mauricio López y en especial  Leonardo Paneque , quien me preguntó

 Olemis Lang ¿qué opinión merece desde su punto de vista que  Google decidiese utilizar código propietario en su navegador y romper con la naturaleza abierta de la web? .

Esa conversación va a motivar que publique otros atículos próximamente así que, si está interesado en conocer otros temas polémicos sobre código abierto vs software privativo, le invito a  suscribirse mediante RSS.

El smartphone de la discordia en el Eden Virtual

De forma inmediata (ya que nadaba en un mar de ignorancia y desactualización acerca del tema) simplifiqué mi respuesta y empecé diciendo :

a ver  Paneque , sobre los navegadores ... si no quieres código propietario ahí : usa  Chromium (q es d hecho el q yo uso ;)

... y luego ...

 Paneque por si las moscas pásame la noticia esa del código propietario en  Chrome pq a lo mejor no estoy claro y puedo estar hablando d otra cosa ...

Después de leerme  el artículo de PC Mag en cuestión , siento que debo al menos abordar el tema. Para ello empiezo analizando el contenido del artículo. Luego reflexionaré acerca de algunos de los comentarios de las personas antes mencionadas.

Pues bien, con un título muy sugerente y acompañado de  unas diapositivas el artículo  Is Google Chrome the New IE6? trata de establecer un paralelo entre las prácticas que llevaron en su tiempo a Microsoft a establecerse como el líder absoluto e indiscutible en el sector de navegadores web; y las que recientemente aplica Google con el fin de fomentar el uso de los navegadores web bajo su influencia  Chromium Browser y  Google Chrome. Vale destacar que el primero es un producto basado en una comunidad de código abierto patrocinada por Google. Es allí donde surge la mayor parte de la innovación incorporada a este producto; que sirve de base para construir el segundo producto, que no es más que unaa versión personalizada, optimizada y absolutamante bajo el control de Google . De hecho en los metadatos del paquete de instalación para Ubuntu se puede constatar lo siguiente :

$ apt-cache show google-chrome-stable | grep Maintainer
Maintainer: Chrome Linux Team <chromium-dev@chromium.org>
$ apt-cache show chromium-browser | grep Maintainer
Maintainer: Fabien Tassin <fta@ubuntu.com>

... a buen entendedor con pocas palabras basta ;)

La hegemonía del gigante de Redmond antes mencionada se viene resquebrajando por varias razones entre las que se pueden mencionar el descuido de Microsoft, su estrategía de romper la web con el fin de imponer sus tecnologías, y el surgimiento de otros navegadores que apostaron por la innovación llegando al punto de revolucionar varios fundamentos de la red de redes.

Dos enfoques diametralmente distintos

En primer lugar , el artículo menciona características que introdujo el Internet Explorer 6 tan comunes hoy como pueden ser DHTML, CSS, y mecanismos de seguridad. Algunos de ellos se transformaron en estándares. Sin embargo no se menciona todas las otras tecnologías propietarias e incompatibilidades que perturbaban intencionalmente o no (pero sí sistemáticamente) la experiencia de navegación de los usuarios en la web con el fin de ratificar su dependencia y sacar a otros navegadores de la competencia . A continuación les menciono algunas ActiveX, Microsoft SharePoint, ... y ni me voy a desgastar en demostrar el gran número de incompatibiliades. Solo habra un libro de Javascript , CSS o HTML y muy pronto se dará cuenta de que la idea central de pronto se convierte en cómo lograr que funcione su sitio con Internet Explorer :$. Todo se fundamenta en que la compañía priorizaba sus ventas de software, y utiliza esta situación para obtener ventajas en la comercialización de sus productos, dígase Microsoft Windows, Microsoft Sharepoint, Microsoft Outlook , ... y otros ... Para redondear la idea, la estrategia consistía en que solo si se usa el Internet Explorer (en Windows) es posible acceder a las funcionalidades de sitios, intranets empresariales, y así sucesivamente.

Por otra parte la estrategia empresarial de Google se basa en servicios. Esto quiere decir que es de sumo interés en su caso que todo el mundo pueda acceder a dichos servicios de la forma más fácil que sea posible (si hay varias alternativas para llegar a un mismo fin , quizás mejor ;) y que la experiencia del usuario supere la de las ofertas de la competencia. Con el transcurso del tiempo esto ha redundado en su compromiso con las comunidades de código abierto que han construido un ecosistema orientado a facilitar el uso de sus servicios.

Supuestas ventajas

Pero todo no queda ahí . Google participa activamente en el esfuerzo de construir una web abierta para todos pero también tratando de innovar y transformar los pilares fundamentales para mejorar así su desempeño . Menciono algunos ejemplos para que esta idea no se quede en el aire : Jingle y Wave son las extensiones al protocolo XMPP que surgieron con los productos Google Talk y Google Wave; en el último caso se innovaron características significativas que pasaron a formar parte del conjunto de APIs que integran HTML 5, entre ellas el drag n' drop para subir y bajar ficheros ... en fin la lista sería extremadamente larga. Con el tiempo todo esto se fue estandarizando al punto en que la mayoría de los navegadores principales incorporan estos adelantos. Pero es oportuno destacar que en todos los casos antecedió un período en que Google , y en cierta medida la comunidad que les rodeaba, se encargó de hacer implementaciones y experimentar hasta llegar a un punto en que se estabilizaba el rendimiento de la solución. Al satisfacer los objetivos era propuesta como un estándar (en muchos casos un estándar de facto). Mientras esto ocurría muy frecuentemente sucedía que no era posible hacer las mismas cosas con otros navegadores que todavía no habían incorporado estas mejoras (... claro ... eran ¡ EXPERIMENTOS !) .

Con esta introducción llegamos al punto en que se empieza a hablar en el artículo de PCMag sobre el tema de la optimización de los servicios de Google mediante aplicaciones para Chrome, especialmente con el fin de permitir su uso offline. Bueno ... más de lo mismo hasta donde se puede ver. Todos los servicios de Google tienen una API y, si el navegador implementa partes de HTML 5 se pueden lograr resultados similares en otros navegadores. El hecho es simple : Google hizo una aplicación para Chrome como cualquier otra que Usted pueda hacer y que permite el uso offline de GMail . Vamos a hacerle la autopsia a este fenómeno (bisturí, por favor, pinzas ... :)


$ dpkg -L google-chrome-stable | grep crx$
/opt/google/chrome/default_apps/gmail.crx
/opt/google/chrome/default_apps/youtube.crx
/opt/google/chrome/default_apps/search.crx

$ apt-cache show google-chrome-stable | grep Version
Version: 16.0.912.63-r113337

Esto quiere decir que Google Chrome distribuye tres extensiones para GMail , Youtube y Google Search que, aparentemente, utilizan los mismos mecanismos de extensión que tienen a su disposición los desarrolladores. Por tanto el argumento de que en Chrome no hay aplicaciones para Yahoo! Mail, Hotmail , Blip.tv, Bing , ... se soluciona con la repuesta : Solo hay que hacerla. ¿Qué esperan? . El argumento de que les puede dar cierta ventaja a los productos de Google y que hay quienes pueda no gustarles y prefieran el sitio web tiene una respuesta simple ... son aplicaciones como otra cualquiera. Desinstale la que no le guste ... El argumento de que no hay aplicaciones similares para Firefox , Opera, Internet Explorer, Safari solo se explica por el hecho de que no hay una API , librería ... que permita el desarrollo de plugins para varios navegadores , y mucho menos un formato de paquetes único, ni siquiera hasta cierto punto compatible , para efectuar la instalación.

Ahora vamos a ver la otra cara de la moneda. Traté de corroborar el hecho de que las aplicaciones no dependieran de algun detalle que no estuviera presente en Chromium , la versión comunitaria del navegador. Al tratar de instalar los ficheros .crx de las aplicaciones antes mencionadas el proceso aborta reportando la necesidad de conectarse al Web Store ... y lo mismo sucede cuando efectivamente la instalación ocurre desde el Web Store ¡qué mala onda! :$

Por cierto se espera la integración de más servicios en versiones posteriores.

El caso SPDY

The SPDY Book

Ahora quizás llegamos a la cereza del pastel. Se ha formado un revuelo tremendo con el fenómeno  SPDY (se pronuncia en inglés como speedy). ¿Qué es SPDY? Segun el artículo es el monstruo de la laguna verde; comparable con el Internet Explorer 6 pero varios órdenes de magnitud peor. Sin embargo, segun Wikipedia :

SPDY (pronounced speedy) is an experimental networking protocol developed primarily at Google for transporting web content.

La traducción al español es, en pocas palabras, que  SPDY es el protocolo experimental hecho por Google que se piensa remplazará la infraestructura HTTP. Esto quiere decir que en los próximos años puede suceder que la infraestructura subyacente de toda la Internet haya cambiado para bien . Puede que esto sea gracias a Google . Actualmente segun tengo entendido la compañía ofrece 90% de las peticiones de sus servicios con SPDY y el otro 10% con el protocolo HTTP. La razón es que de esta forma pueden tener comparaciones del uso en sistemas en producción y evaluar las mejoras en la calidad del servicio . Si no lo ha entendido , se lo repito :

La Internet del futuro está ya aquí y, si Usted usa Google Chrome o Chromium, entonces ya es cómplice de semejante calamidad :). Si desea comprobarlo use su navegador y acceda a la dirección chrome://net-internals/#events&q=type:SPDY_SESSION%20is:active

La implementación de  WebSockets que ofrecen los navegadores de Google parte de SPDY , segun se cuenta . A diferencia de lo que se pudiera pensar, SPDY no es privativo debido a que se desarrolla por la comunidad alrededor de Chromium . Se encuentra disponible para  descarga el código fuente . Hay librerías para clientes y servidores en  Python,  Java (Tomcat),  un módulo para el servidor web Apache,  Ruby SPDY,  node.js,  Go  Erlang  C SPDY  libcurl. Además se está trabajando en una versión incorporada a Firefox 11. Se maneja la idea de que el protocolo está en vía de estandarización.

Conclusiones

Sinceramente, tengo que decirlo, sospecho que el hecho de que  Michael Muchmore diga ...

Thankfully, Microsoft has abandoned these IE-only features. Let's hope Google follows suit.

... sospecho que se debe a que nunca ha tenido que depurar un flujo de trabajo (o prácticamente cualquier cosa hecha) en Sharepoint , no usa sus galerías de imagenes, supongo que tampoco el Exchange, no consulta sitios hechos con Silverlight , ... en fin no puedo seguir. Me duele la cabeza ya. Establecer una comparación entre lo que hoy hace Google y lo que ha venido haciendo Microsoft durante tanto tiempo , realmente deja mucho que desear. Un punto coincidente es que ambas empresas quieren dominar este sector del mercado de los navegadores web. Todo parece indicar que Google tiene la iniciativa y la innovación a su favor.

Por otra parte , incluso en caso que SPDY sea un éxito , la migración hacia el uso masivo de esa arquitectura implicará una inercia apreciable . Por una parte  los proxies, y la  autentificación tienen particularidades diferentes. Eso implica una actualización paulatina a gran escala del software existente para estos fines. Algunos navegadores e.g.  Opera no parecen estar dispuestos a adoptarlos en un corto plazo. Sin embargo, el peso específico de Google en la web no se puede ignorar. Pronto esta tecnología estará incorporada en dispositivos móviles con el sistema operativo  Android.  Amazon parece incorporar SPDY en su navegador  Silk para  Kindle Fire.