DE CERVEZAS y otras cosas

CSI XVIII: Los húngaros nombran con prefijos

2009-10-12T09:25:00.001+02:00

El reciente post acerca del nombre de nuestras futuras (o muy presentes) cerveceras dio paso, de forma natural, a pensar de qué modo llamaríamos a nuestros productos. Ya lo comenté en el blog de Chela: me gustan los nombres relacionados con la música y hay muchos donde elegir en las anotaciones de las partituras, en latín, italiano o nuestra lengua: Ad Libitum, para la cerveza tomada a la velocidad que uno quiera. Tornada (estribillo), si la cerveza es para ser tomada una y otra vez, Ritardando, para tomar despacio...

El nombre de las cosas es importante. Y, como la mayor parte de cosas importantes, suelen dar problemas. Y en informática, el nombrado de variables puede suponer todo un reto, especialmente porque cuando se hace sin cuidado puede llevar a errores de programación, cuando no a imposibilitar que cualquier otra persona entienda el código (código inmantenible).

Por cierto, una variable no es más que un espacio en memoria destinado a albergar, en algún momento durante la ejecución del programa, algún valor. Necesitamos darle nombres para hacer referencia a ese valor. Así que, ¿qué nombre les ponemos?

El caso es que no vale el primero que se nos ocurra. MaryPoppins, por ejemplo, no vale. Porque luego tienes que operar con estas variables y en el código te pueden aparecer cosas como:

PedidoOctubre = MaryPoppins[3] * OdioAMiJefe;

Eso es código inmantenible. Una risa, si no te fuera el trabajo en descifrarlo y entenderlo.

Por ello todos debemos estar de acuerdo en que el nombre de las variables debe dar pistas acerca de qué tipo de almacén estás gastando para esa variable, qué es lo que deseas guardar en ellas o qué intención tienes al emplearla. Como llamar AldolfoHitler a tu hijo: el nombre da pistas.

Las empresas serias definen una serie de reglas a la hora de escribir programas: son los coding standards (o guía de estilo). Son simples convenciones para que -entre otras cosas-, con independencia de las personas que hayan pasado por la empresa, el mismo estilo perdure. Las convenciones pueden ayudar en el problema de nombrer variables, imponiendo una serie de reglas. Algunas de ellas están muy extendidas y las emplean la mayor parte de programadores en diversos lenguajes. por ejemplo, llamar i, j, k a las variables dentro de un bucle.

Una de las Cosas que Sí se estudió en Informática es la notación húngara. La notación húngara fue creada por Charles Simonyi, uno de los grandes programadores y reciente turista espacial¹. La notación húngara se caracteriza por anteponer al nombre de la variable un prefijo que nos da pistas acerca del tipo de variable que estamos empleando. El tipo de variable es la forma del almacén que estamos gastando para guardar su valor.

No voy a a explicar demasiado, porque esto da para otro post: me contentaré con poner algunos ejemplos sencillos. Una variable de tipo carácter está pensada y tiene el espacio asignado para guardar un carácter. Una variable que fuera de tipo cadena tendría un almacén asignado para almacenar una cadena de caracteres.

Entonces, si queremos almacenar un carácter en nuestro programa para guardar la preferencia de un usuario (que lo introduce mediante el teclado), declaramos una variable llamada UserOption y si empleamos la notación húngara, lo hacemos así:

caracter cUserOption;

Mediante esta linea le decimos al compilador (que es típicamente quien traduce nuestro programa a la máquina) que en algún momento tendrá que reservar un hueco en memoria para almacenar una variable de tipo caracter y que se llamará cUserOption. La 'c' usada como prefijo nos recuerda, cuando realizamos operaciones con esta variable, que se encuentra almacenada como un carácter.

La notación húngara tiene cierto sentido cuando, al operar entre variables de distinto tipo, podemos obtener problemas o resultados indeseados. Y justamente, el hecho de que se produjeran tantos errores al operar entre variables de distintos tipos dio lugar a la creación de los lenguajes fuertemente tipados, en los cuales el compilador impide realizar esta clase de operaciones. Así que la notación húngara dejó de tener sentido para muchos programadores.

Otra versión de la notación húngara sugiere que el prefijo debe estar más relacionado con la función que la variable va a cumplir que con el tipo de almacenamiento. Esta versión del invento cuenta con más adeptos, ya que no ha perdido el sentido al reforzar los compiladores el análisis de tipos. Algunos ejemplos de este uso son:

numeroentero nSandias;

Que informa al compilador de que debe guardar un espacio para almacenar un número entero. En ese espacio guardaremos el número de sandías de nuestra aplicación. De ahí el prefijo 'n'. Pero como si no hay guía de estilo, nadie tiene por qué saber que 'n' es de 'número' en vez de 'nuevas', pues resulta que la notación húngara sigue sin ser ninguna panacea.

Esta notación, sin embargo, se sigue empleando... y mucho. Porque Charles Simonyi fue fichado por Bill Gates y la notación húngara pasó a formar parte intrínseca de las aplicaciones de Microsoft, incluyendo su Sistema Operativo más popular. En los últimos tiempos, sin embargo, hasta los de Redmond se desdicen y recomiendan no emplear este sistema de nombrado en el código.

Recordar la notación húngara de prefijos me ha recordado otras notaciones algebraicas, que también tienen que ver mucho con la informática. Me refiero a la notación polaca (o infija) y a la polaca inversa (o postfija). Rápidamente:

(3 + 2) * 5 - Ésta es una operación como a usted a y mi nos enseñaron en el cole.
* + 3 2 5 --- Es lo mismo que antes en notación polaca. Lo inventó un polaco.
3 2 + 5 * --- Es lo mismo, pero en polaca inversa.

De los tres, el más útil y divertido es el de polaca inversa. Útil para algunas calculadoras, claro. Polaca y polaca inversa no precisan de paréntesis, ni de conocer las reglas de precedencia (no hay expresiones ambiguas). Eso le viene muy bien al informático para realizar cálculos. En polaca inversa, cada vez que se encuentra un operador, se realiza el cálculo indicado: los operados habrán sido leídos anteriormente (o hay un error en la expresión).

La polaca inversa tiene desventajas. Los espacios en las expresiones son de vital importancia para no confundir la expresión. Y como no se enseña en las escuelas ni se aplica sobre el papel, su uso está muy limitado.

Pero sirve para entender el chiste de arriba (cortesía de xkcd, como no). Ante ustedes, ¡un sandwitch de salchicha polaca inversa!

¹ El más famoso turista espacial relacionado con la informática es Mark Shuttleworth, empresario instigador de Ubuntu.

Notación Húngara: por Charles Simoyi.
Notación Polaca (wikipedia inglesa)

Posts relacionados

CSI XVII: El álgebra de Boole

2009-08-22T11:12:00.002+02:00

Demasiado tiempo hacía que no escribía acerca de las Cosas que Sí se dan en Informática. Pero mi retiro veraniego me ha despertado del letargo y me ha traído, con el viento levantino, los recuerdos de una de las primeras asignaturas que estudié en la carrera y que constituye una base esencial de la propia informática. Me refiero al Diseño Lógico. Mi idea era ir más allá y hablar de lenguajes de descripción de sistemas electrónicos, que tan olvidados e inútiles les resultan a los informáticos que se decantaron por los lenguajes de alto nivel.

Pero para entender de qué trata éste es necesario disminuir un poco las pretensiones e introducir algo todavía más elemental, que se estudia en el primer curso de la carrera y que, a menos que la especialización te conduzca por áreas de informática industrial o electrónica, se pierde con facilidad. Se trata del Álgebra de Boole, que hoy, en este capítulo de Cosas que Sí se dan en Informática, presentaremos: tanto en su definición matemática, como en su utilidad electrónica.

El Álgebra de Boole toma su nombre de George Boole, matemático y filósofo inglés del s. XIX. Sus estudios acerca de la lógica le llevaron a desarrollar un modelo matemático con el fin de analizar el razonamiento humano y de realizar operaciones con sentencias. De su trabajo surgió la estructura matemática que asigna a cada sentencia el valor de VERDADERO (o 1) y FALSO (o 0) y define las operaciones matemáticas que pueden realizarse sobre estos elementos.

Porque es eso mismo lo que conforma una estructura algebraica: un conjunto de elementos y un conjunto de operaciones definidas sobre los elementos. El álgebra de Boole tiene forma de anillo: esto significa que las operaciones definidas satisfacen ciertas propiedades. En la wikipedia pueden continuar con este tema.

Los elementos del álgebra de Boole son pues dos, que llamaremos 0 y 1. Las operaciones básicas que se pueden realizar sobre estos elementos son 3: disyunción (OR, o suma), conjunción (AND, o multiplicación) y negación (NOT, o inversión). Los dos primeros son operadores binarios, esto es, requieren dos elementos como entrada. La negación se aplica sobre un sólo operando: es unario, pues. Bien, si hasta ahora ha sido sencillo, lo que viene ahora lo es más.

Las tablas de verdad básicas definen el comportamiento de los operadores para las entradas. O lo que es lo mismo: su resultado.

OR
A	B	A OR B
0	0	0
0	1	1
1	0	1
1	1	1

AND
A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

NOT
A	NOT A
0	1
1	0

Explicar una tabla de verdad es casi innecesario: la primera tabla describe la operación OR: 0 OR 0 da como resultado 0. En cambio, 0 OR 1, 1 OR 0 y 1 OR 1 dan como resultado 1.

Aunque no es adecuado, viene bien evaluar una sentencia disyuntiva a un valor de verdad para acabar de entender la correspondencia lógica. La frase Marta tiene un abrigo azul o tiene una chaqueta colorada es cierta (verdadera: 1) si alguna de las sentencias que la forman -tiene un abrigo azul, tiene una chaqueta colorada- es verdadera. Para que la conjunción sea cierta (Marta tiene un abrigo azul y tiene una chaqueta colorada) es necesario que las dos sentencias individuales -los operandos- sean verdaderos. De este modo se entiende la tabla de verdad de la AND.

XOR
A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

Mediante sencillas combinaciones de los tres operadores básicos podemos obtener los operadores derivados, que nos sirven para representar otras relaciones lógicas, entre las que se encuentran la o exclusiva, la implicación o la equivalencia. Es posible que a muchos de los lectores les suene esto, ya que las tablas de verdad son las herramientas empleadas en el estudio de la lógica proposicional, que se cursa típicamente en el instituto. Los operadores derivados más frecuentes tienen sus propios símbolos. En la tabla de al lado se muestra una o exclusiva o XOR. La función XOR puede ser construida a partir de operaciones básicas, aunque no de modo sencillo. Sin embargo, resulta muy útil a los informáticos y es ampliamente empleada, como veremos enseguida.

Las representaciones de estos operandos son muy diversas y los informáticos preferimos la que emplea puertas lógicas. Y sin embargo... ¡un momento! ¿qué pintamos los informáticos aquí?. ¿Quién nos ha dado vela en este entierro?.

Pues en realidad fue Claude Shannon, uno de los grandes, quien nos dio vela. Ya hablamos de Shannon cuando describíamos el mínimo de información necesaria para codificar una cadena de bits. Pero antes de ocuparse de la teoría de la información, Shannon demostró que el álgebra de Boole se podía utilizar en el análisis y la síntesis de la conmutación y de los circuitos digitales.

Un circuito digital es un circuito electrónico que emplea señales eléctricas que representan (mediante la tensión) dos valores: 0 y 1. El circuito, visto como una caja negra consta de una serie de entradas y unas salidas. Lo que Shannon demostró es que cualquier salida puede ser producida a partir de las entradas mediante una combinación de operadores booleanos, esto es, mediante un conjunto de puertas lógicas, interconectadas de cierto modo. De este modo podemos ver cualquier transformación de entradas en salidas como la aplicación de cierta función (operación) lógica¹. A esto se le llama circuito, o sistema, combinacional.

SUMADOR
A	B	Suma	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Así, por ejemplo, un circuito básico podría ser el el que suma dos bits. Recordemos que la suma de dos bits era sencilla: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 y me llevo 1 (acarreo). Un sumador simple (half-adder) de un bit tiene dos entradas y dos salidas (la suma y el acarreo). Lo llamamos simple para diferenciarlo del completo, que añadiría como nueva entrada el acarreo del anterior. De este modo podríamos construir sumadores de cualquier número de bits sin más que encadenar la salida del acarreo de uno a la entrada del otro. Pero nosotros nos quedaremos con el simple, para no complicar el circuito.

El sumador que vemos emplea una puerta AND (la de abajo de la imagen) y una puerta XOR, la superior, que ya presentamos anteriormente. Con las tablas de verdad de ambas puertas, es muy sencillo jugar a poner unos y ceros en las entradas y ver cómo los resultados coinciden con los de la suma.

Puede parecer que un sumador de un bit sólo sirve para jugar, pero de hecho, es la base del cálculo de todas las operaciones que realizan los computadores. Sin embargo es cierto que los ingenieros que construyen circuitos lógicos tienen herramientas para no tener que estar trabajando con miles de puertas lógicas cada vez que pretenden diseñar una nueva unidad aritmética para un computador, por poner ejemplo. Qué pinta tiene alguno de los lenguajes para expresar circuitos lógicos de manera sencilla y potente será explicado en posteriores entregas.

¡Un saludo y hasta la próxima!

¹ ¿De qué manera se produce "físicamente" la transformación de dos niveles de tensión a las entradas de una puerta en un nivel de tensión a la salida que corresponda al resultado de la puerta?. Bien eso depende la tecnología empleada y sería necesario entender física de semiconductores para explicarlo. Queda fuera del alcance de este blog.

Infinidad de circuitos digitales construidos de forma incremental.
Álgebra de Boole en la wikipedia en español: se incide en la representación como como conmutación de circuitos.
La imagen del half adder es de dominio público

Posts relacionados

CSI XVI: los números de los computadores (II)

2009-05-24T13:03:00.002+02:00

Si recuerdan el ya lejano último post acerca de la informática, recordarán que había motivos para estar mosqueado. Muy mosqueado, de hecho, porque vimos que los bancos nos podían chulear con facilidad la parte fraccionaria de los ahorros. Pero eso es porque todavía no les he enseñado cómo representar números reales en los computadores. Y tranquilos, que eso es precisamente lo que voy a comentar hoy.

Ustedes los humanos emplean un punto (o una coma) o notación científica para representar un número con decimales. Pero la cosa es un poco más compleja si no se pueden valer de esos artificios. Para expresar números reales en un ordenador, la solución más sencilla es convenir que una parte de la ristra de unos y ceros represente la parte entera y el restos de unos y ceros representen la parte decimal. Se dedican n bits para la parte entera y p para la fraccionaria. Por supuesto, n y p son fijos para un computador, para no hacerse un lío. Por eso este sistema se denomina de coma fija.

La coma fija mola, porque no tenemos que aprender nada nuevo (aparte de lo que aprendieron en el anterior post). Con 8 bits podemos dedicar 5 a la parte entera y otros 3 a la parte decimal, por ejemplo. De manera que si usamos Complemento a 2 para representar la primera (para la decimal no empleamos ninguna codificación especial) entonces podemos representar un rango de números que va desde -16.0 hasta +15.875. La precisión la marca la cantidad de bits en la parte fraccionaria, claro, que en este caso es de 0.125 (1/(2^3)).

La coma fija no mola, porque operaciones entre números dentro del rango de representación exceden con facilidad el propio rango. Un ejemplo decimal: 0.345 * 0,001 = 0.000345. Si gastamos 3 dígitos para la parte entera y tres para la parte decimal, es evidente que el resultado de la multiplicación con este sistema sería 0. Y nos volvemos a quedar sin céntimos en los bancos.

Para hacer esto más flexible se inventó la coma flotante. La coma flotante es un lío, pero que es muy útil. Un número real se representa como:

R = M * B^E donde:
M es número fraccionario, donde se utiliza un bit para representar el signo (como en Signo y magnitud).
B es la base. 2, en casi todos los casos.
E es el exponente, que se representa en exceso Z (esto no lo he explicado).

Si lo pensamos un poco, esto no es más que una aproximación a la notación científica. Por ejemplo, -0.000456 = -456 * 10^-6, donde el signo es negativo, la mantisa 456, la base 10 y el exponente -6. La complejidad de la coma flotante es ajustar cada campo a un número limitado de bits. Y para eso vamos a aprovechar hasta el máximo.

El formato IEEE754 de simple precisión (el más conocido de representación de reales) emplea un total de 32 bits: 1 para el sigo, 8 para el exponente y 24 para la mantisa.

¿Cómo?. ¿Que no le salen las cuentas?. Claro, amigo, lo que usted no sabe es que los ingenieros aprovechamos todo el espacio que podemos. Y le ganamos un bit a la mantisa de forma sencilla. Porque, si usted quiere utilizar el formato IEEE754 es porque tiene algo que representar, aunque sea muy pequeño. Un ejemplo:

0,0000101 (binario). ¿Por qué tengo que almacenar en la mantisa los cuatro ceros? Al fin y al cabo, 0,0000101 = 1,01 * 2^-5. Sólo tengo que ajustar el exponente (restándole 5). Lo bueno es que esto lo puedo hacer para todos los números, de forma que, sea cual sea el número a representar, el primer bit de la mantisa será 1. Y como el primer bit de la mantisa es siempre 1, me puedo ahorrar el representarlo (¡siempre que luego me acuerde de él a la hora de interpretar el número!). De este modo tenemos 24 bits para representar la mantisa, aunque sólo empleemos 23.

A la operación de dejar un único bit significativo (1) a la izquierda de la coma se le llama normalizar la mantisa.

Hemos dicho que tras normalizar la mantisa conviene ajustar el exponente. Pero no hemos hablado de cómo se representa este mismo, ni qué significa exceso Z. Es una cosa tan tonta que da risa. En exceso Z se escoge cualquier número (Z) para representar el cero. Cualquier número entero A se expresa como el natural A+Z. Por ejemplo, en exceso 127, el -7 se expresa como 120 (-7 + 127). El 3 se expresa como 130 (3 + 127).

Precisamente 127 es el Z escogido para representar el exponente en el formato IEEE754. Por tanto, ya disponemos de todos los elementos para ponernos a calcular números reales. Buenos, nos falta dar el orden de los campos: Signo - Exponente - Mantisa. Ya está.

Representar -209.5625 en coma flotante IEEE754 (simple precisión)
S = 1 (signo negativo)
Parte entera: 209 = 11010001
Parte fraccionaria: .5625 = 0.1001 (2^-1 + 2^-4)
Mantisa: (parte entera.parte fraccionaria) 11010001.1001 = 1.10100011001 * 2⁺⁷
Exponente Z = 127 + 7 = 134, que en binario es 10000110

S E M
De lo cual: -209.5625 = 1 10000110 10100011001000000000000

Y ya hemos aprendido a representar números reales. Por supuesto, al ser un rango de representación finito, con este formato también tenemos cierto límite en la precisión (determinado por los 24 bits de mantisa). Para los más avezados dejo su cálculo.

Yo quiero incidir en otra cosa, que no sé si habrán notado. A pesar de que hemos detallado la representación de números en distintos formatos, al final, en su computador, todos los formatos no son sino ristras de unos y ceros, de modo que la misma longaniza puede ser un número entero negativo, real, o positivo. O no ser un número. Por eso a la hora de escribir un programa es fundamental dar a conocer al computador cómo debe interpretar un valor. Esto se consigue con los tipos de datos.

Cuando queremos gastar un valor, empleamos variables para almacenarlas. Y en gran parte de lenguajes es necesario declarar el tipo de dato de una variable antes de gastarla, para que el computador sepa cómo debe operar con ella.

En C, el lenguaje más extendido, si declaramos una variable como int (entero) lo más posible es que le digamos al computador que esa variable debe representarse en Complemento a 2¹. Si declaramos un float es muy posible que para representar esa variable se gasten 32 bits (simple precisión) en IEEE754. Y si declaramos un unsigned char, entonces estamos gastando 8 bits en una representación binaria sin signo (positivo).

Y ahora el chiste:

Si los androides algún día sueñan con ovejas eléctricas no olvides declarar el contador de ovejas como long int.

¿Que ha pasado?. Que el contador de ovejas estaba declarado como int (16 bits). Y el rango de representación es (Ca2) -32768 (1000000 00000000) - 32767 (01111111 1111111). Al sumar uno a 32767 el número de ovejas se convierte en negativo. De haber declarado el contador como long int, posiblemente habría tenido 32 bits para representar la cuenta. Eso significa que un androide insomne habría contado hasta 2147483647 (2³¹-1) antes de que sucediera lo mismo. Y si declarara la variable como unsigned long (sin signo), podría contar hasta 4294967295. La siguiente cuenta sería 0, ya que el computador jamás interpretaría este número como negativo.

Ojalá me disculpen. Tan sólo quería compartir humor friqui con ustedes.

¹ El número de bits con los que se representa y el formato de representación dependen de la arquitectura del procesador. Por eso es un error asumir que un int tiene siempre, por ejemplo, 32 bits.

Apuntes clase. Pero en la wikipedia también viene bien explicado
Pinar me pasó el link a la tira: más humor en su web.

Posts relacionados

CSI XV: Los números de los computadores

2009-02-10T22:32:00.003+01:00

Con la crisis, amigos míos, todos echamos números. Los hay que no, pero es lo que tiene vivir con dinero de los demás: atrofia el ingenio para buscarse alternativas, libres y gratuitas. Echar números es sólo necesario si vas algo apurado, como el 90% de población española.

Para echar números se inventaron las calculadoras, hace ya muchos años. Y de de la evolución las calculadoras nació el microprocesador, hace ya 38 años. Tiene huevos, por otro lado, que como respuesta a la crisis la vicepresidenta diga que nos vamos a montar en el chip para abandonar el crecimiento basado en el ladrillo. Porque para eso han tenido tiempo, y de sobra, dos administraciones socialistas, otras dos peperas, unas tres y media socialistas de nuevo y un trozo de la de la UCD. A buenas horas, (vice)presidenta.

Retomemos que me enciendo. Lo que les voy a contar hoy en Cosas que Sí se dan en Informática es cómo cuentan los computadores. O, dicho de otro modo, cómo representan los números los ordenadores.

A estas horas es vox populi (excepto quizá para nuestros representantes públicos) que los computadores utilizan ceros y unos para representar la información. Antiguamente eran campos magnéticos en núcleos de ferrita, hoy pueden ser en forma de surcos en discos ópticos y mañana quizá sea en cuantos de energía en átomos. Dejando la lógica difusa al margen la cosa sigue teniendo la misma base: haber o no haber. 1 o 0. Y ahora veamos qué es eso del binario.

Utilizar dos caracteres para representar números tiene la misma dificultad que emplear 10. Que es lo que hacemos los humanos continuamente. El llamado sistema decimal no es más que un sistema posicional de representación con diez símbolos (0, 1, 2, 3, ..., 9). Es posicional porque la posición importa en el valor de un símbolo, como sabrán todos aquellos que han sido llamados "ceros a la izquierda". Así, el número 459 significa, exactamente:

4*10² + 5*10¹ + 9(*10⁰)

El carácter más significativo -el 4- lo colocamos más a la izquierda y se multiplica por la base -10- elevado a su posición -la tercera-. Análogamente para el resto.

Con el binario, la representación es idéntica. Sólo tenemos que tomar la base 2.

1*2⁸ + 1*2⁷ + 1*2⁶ + 0*2⁵ + 0*2⁴ + 1*2³ + 0*2² + 1*2¹ + 1*2⁰

Nos da exactamente 459, si le apetece hacer la suma. O nos da exactamente 111001011. Utilizar un sistema decimal en lugar de cualquier otro es completamente arbitrario o fortuito. De hecho, no está del todo claro por qué gastamos un sistema decimal, aunque muy posiblemente sea por tener diez dedos. Desde luego, es un argumento de peso.

Como escribir 111001011 es un rollo, incluso para una cantidad pequeña como 459, los informáticos nos apañamos para representar grandes números empleando otras bases más cómodas, como la octal o hexadecimal. En la primera empleamos los símbolos 0, 1, 2, 3, 4, 5, 6 y 7. En la segunda, todos los anteriores y además 8, 9, A, B, C, D, E y F. Es inmediato pasar de binario a ocal y hexadecimal (y a la inversa). Tan sólo tenemos que agrupar los símbolos binarios de 3 en tres y representar el correspondiente caracter octal, o de cuatro en cuatro y sustituir por el correspondiente símbolo hexadecimal:

111 001 011 = 713 (7*8² + 1*8¹ + 3*8⁰)
1 1100 1011 = 1CB (1*16² + 12*16¹ + 11*16⁰)

¡Maravilloso!. Ya tenemos hasta cuatro maneras de representar lo mismo. Cualquier número que se nos ocurra puede ser representado de cualquiera de ellas, aunque no dentro de un computador. porque la aritmética de un computador es finita, lo que no es sino un modo de decir que tiene límites: números mayores de cierto rango (o menores) no nos cabrán. Pero no nos preocuparemos por ellos todavía.

¿Y nos sirve de algo lo visto en tiempos de crisis?. Pues no, porque aún no podemos representar la realidad, mucho más dramática que lo visto hasta ahora. La cruda realidad cuenta con números rojos.

Los números rojos son negativos y usted lo tiene muy fácil para representarlos porque hace trampa: pone un - delante de ellos y ya. ¡Es hacer trampa porque añade un símbolo que no estaba en el conjunto inicial de diez!. ¿Cómo se las apañaría para representar números negativos sin ningún símbolo añadido?. A esa pregunta respondieron los informáticos hace mucho tiempo.

La solución fácil: reservamos una posición, la más significativa, para indicar si un número es positivo o negativo. El resto del número nos da su magnitud. A ésta forma de representación se le llama signo y magnitud, por razones que explicaré otro día. Si el primer símbolo es un cero, el número es positivo. Si es un 1, negativo.

0 000 -> +0   |   1 000 -> -0
0 001 -> +1   |   1 001 -> -1
0 010 -> +2   |   1 010 -> -2
...

Ésta forma de representación, además de contar con la curiosidad de disponer de dos ceros, es un peñazo, porque requiere analizar el signo antes de ponerse a operar con los números y hacer sumas y restas y aritmética en general. Hay métodos más cómodos.

La forma que efectivamente se gasta un montón es el llamado Complemento a 2. El Ca2 representa los números positivos como los naturales que vimos al principio. Los negativos, en cambio, los representa invirtiendo todos lo bits y sumando uno al resultado (lo que se llama hacer el complemento a dos¹). Sumar, por cierto, es tan fácil como en base decimal: cero mas cero es cero; cero mas uno, uno; y uno más uno, cero y me llevo uno.
Veamos un ejemplo de representación en Ca2:

0000 -> +0   |   1111 -> -1 ( invertimos1(0001) = 1110 + 1 = 1111 )
0001 -> +1   |   1110 -> -2 ( invertimos2(0010) = 1101 + 1 = 1110 )
0010 -> +2   |   1101 -> -3 ( invertimos3(0011) = 1100 + 1 = 1101 )

¿Por qué es tan interesante esto que a primera vista parece un lío?. Bueno, podemos ver a la primera si un número es positivo o negativo. Y ya no tenemos dos ceros. Y sobretodo nos permite sumar a la primera cantidades negativas y positivas. Un ejemplo:

-20 + 10 = -10

-20 -> invertimos20(010100) = 101011 + 1 = 101100
+10 -> 001010
110110 -> Ca2(110110) = 001001 + 1 => 001010 = 8 + 2 = 10

La suma nos ha dado -10 directamente, sin tener que hacer ajustes posteriores. Y no los habrá que hacer, a menos que que el resultado no sea representable (no nos quepa) en la longitud de bits máxima que tenemos. Así que nosotros nos quedaremos con éste formato para representar los enteros.

De todos modos, este formato tampoco representa la realidad. Porque si usted va al banco, transfiere unos 120 euros y le cobran un 4% de comisión (5 euros) se quedará de piedra. Primero: porque hay que ser joputas para cobrar un 4% de comisión por una mierda de operación bancaria que se realiza a través de Internet. Y segundo, porque el 4% de 120 no son 5 euros, sino 4.80. ¿Quién se ha quedado sus 20 céntimos en tiempos de crisis?

El banco, evidentemente. Porque sus ordenadores no pueden representar cantidades decimales, no al menos hasta que yo les explique cómo. Y redondean (que no truncan) para fastidiarle a usted. Pero les contaré cómo representar cantidades fraccionales sin hacer de nuevo trampa e introducir más símbolos como el '.'.

¡Eso será más adelante, en Cosas que Sí de dan en Informática!

¹ ver la referencia para una explicación más convincente.

Apuntes de clase. ¡Esto se estudia en primero!
Sistema binario. Wikipedia.
Complemento a dos. Wikipedia.

Posts relacionados

Cómo escribir código inmantenible

2009-01-10T19:59:00.000+01:00

Últimamente algo ando espeso, lo siento. Tengo la cabeza tan llena de cosas del trabajo que no me da tiempo a escribir nada bueno para el blog, ni a pensar en nuevos temas ni nada. Disculpen si esto baja un poco el ritmo de actualización. Y de originalidad.

Como saben ustedes (y si no lo saben se lo cuento), yo soy programador. Programador de C, para ser más exacto. Ahórrense las condolencias: me gusta mi trabajo. Programo sistemas empotrados, que es como ordenadores, pero más pequeños y desnudos. Todo una delicia, si no atendemos al componente sexual del asunto.

La cuestión es que hace unos meses encontré este vetusto texto de Internet: How to write unmanteinable code, y me pegué una jartá a reír. Comento, para quien no lo sepa, que el código con el que funcionan los programas difícilmente es escrito por una sola persona y, en cualquier caso, es muy fácil que otra tenga que leerlo y entenderlo para actualizarlo, añadir funcionalidades y quitar otras. A eso se le llama mantener una aplicación. El problema que tenemos es que, por lo general, cada uno tiene un estilo a la hora de programar y entender un programa que ha escrito otro puede ser tremendamente complicado.

Para conseguir código mantenible existen centenares de guías. Y normas. Pero sólo existe una para escribir código inmantenible. Les traduzco algunas de las recomendaciones más graciosas que he encontrado en ella¹.

[Advertencia]: si usted no es informático, el concepto que tenemos usted y yo de lo que es gracioso y lo que no lo es puede variar mucho.

Nombrado de variables

Si llamas a tus variables a, b, c, entonces será imposible encontrarlas usando un buscador común. Además, nadie tendrá ni idea de para qué sirven. Anima a los lectores de tu programa a encontrar cada ocurrencia leyendo todas la lineas de todos los ficheros: así entenderán mejor el programa.

A.C.R.O.N.Y.M.S.: utiliza acrónimos para mantener el código carente de emoción. Los hombres de verdad jamás explican los acrónimos: los entienden por genética.

Reusa nombres: nunca está de más ser ecológicos. Siempre que el lenguaje lo permita, llama a funciones, variables y parámetros con los mismo nombres. El objetivo es obligar al mantenedor a que conozca perfectamente las reglas de ámbito del lenguaje.

Elige nombres con connotaciones emocionales irrelevantes y opera con ellos, p.ej.

marypoppins = (superman + starship) / god;

Esto confundirá al lector, que suele asociar nombres de variable de algún modo con el valor que contiene.

Asegúrate de que cada función realiza un poco más (o menos) de lo que su nombre indica. Como simple ejemplo, un método llamado isValid(x) puede tener como efecto colateral convertir x a binario y almacenarlo en una base de datos.

Emplea referencias ocultas a películas. Usa nombres constantes como LancelotsFavouriteColour en vez de azul y asígnalo al valor hexadecimal de 0x0204FB. El color es idéntico al azul de la pantalla y el programador mantenedor tendrá que buscar alguna herramienta gráfica para asaber qué color es. Sólo alguien muy familiar con los Monty Python (y los caballeros de la mesa cuadrada) sabrá que el color favorito de Lancelot era el azul. Si el programador mantenedor no puede citar de memoria las películas enteras de los Monty Python, entonces no tiene futuro como programador.

Camuflaje

Incluye secciones de código que están comentadas pero que a primera vista no lo estén. Por ejemplo:

for(j=0; j < array_len; j+ =8)
{
  total += array[j+0 ];
  total += array[j+1 ];
  total += array[j+2 ]; /* Main body of
  total += array[j+3]; * loop is unrolled
  total += array[j+4]; * for greater speed.
  total += array[j+5]; */
  total += array[j+6 ];
  total += array[j+7 ];
}

Recuerda al mantenedor las reglas de asociación añadiendo instrucciones que resultan ser comentarios.

Importantvalue = a/*p /* divide by the value pointed */;

Si tienes suerte y el compilador permite comentarios anidados, puedes reservar muchas sorpresas hasta que se descubra que no existe división alguna.

Esconde las definiciones de las macros, entre comentarios inútiles. Así el programador se aburrirá y no llegará a descubrirla. Asegúrate de que la macro reemplaza una asignación perfectamente normal por cualquier operación rara, por ejemplo:

#define a=b a=0-b

Aunque ya tengas una variable llamada xy_z, no hay ninguna razón para que no puedas emplear también otras con nombres similares, como xy_Z, xy__z, _xy_z, _xyz, XY_Z, xY_z, and Xy_z. Sé creativo: variables que se distinguen tan sólo por las mayúsculas y barras bajas tienen la ventaja de confundir a quienes recuerdan los nombres por cómo suenan, en vez de por su representación exacta.

Elige el mejor operador de sobrecarga: En C++, sobrecarga los operadores +,-,*,/ para hacer cosas totalmente diferentes de suma, resta... Después de todo, si Stroustroup puede usar el operador de desplazamiento para entrada/salida, ¿por qué no ser igual de creativo?. Si sobrecargas +, asegúrate de que i = i + 5 tiene un significado completamente distinto a i += 5.

Documentación

Miente en los comentarios. Es muy sencillo: no actualices los comentarios al actualizar el código.

Documenta cómo y no el porqué. Documenta sólo los detalles de lo que el programa hace (incluyendo los autoincrementos), no lo que pretende conseguir. Así, si hay algún error, el que lo tenga que arreglar no tendrá pistas para sabe qué es lo que el código debería estar haciendo.

Nunca documentes errores en el código. Si sospechas que hay un bug, mantenlo en secreto. Si crees que el código puede ser mejorado o reorganizado, por el amor de Dios, no lo digas. Recuerda las palabras en la película Bambi: Si no puede decir nada bonito, mejor no digas nada. Qué sucederá si el que lo escribió ve tu comentario?. ¿Y un cliente?. ¡Podrías estar despedido!. En cambio, un comentario del tipo: /* This needs to be fixed! */ puede hacer maravillas, sobretodo si no se sabe a qué se refiere. De este modo nadie podrá ser criticado.

Diseño

Gasta arrays de tres dimensiones: montones de ellos. Mueve datos entre ellos de originales maneras, llenando las columnas de uno con las filas de otro. Si el desplazamiento es de uno, sin razón aparente, bien hecho. Hace que el mantenedor se ponga nervioso.

Utiliza todas la variables globales que puedas. Si Dios no hubiera querido que usáramos variables globales, no las habría inventado. Cada función debe usar y dar valor a un par de variables globales al menos, incluso aunque no exista ninguna buena razón para ello. Al fin y al cabo, el mantenedor se figurará que es una especie de detective y estará contento de cumplir una tarea que separa a los verdaderos programadores de los aficionadillos.

Testing

Que tu proyecto sólo funcione en modo debug. Si tienes distintas configuraciones de proyecto, asegúrate de que tan sólo funciona con una de ellas. Es muy sencillo de realizar con directivas de preproceso: #define TESTING te da la oportunidad de tener dos secciones del código independientes. Dentro de #ifdef TESTING asigna los valores necesarios para que funcione el programa. Si alguien elimina el define, o mejor aún, no compila con la directiva adecuada, el programa no funcionará.

Testear es de cobardes. Un programador valiente se saltará este paso. Demasiados programadores temen perder su empleo y tienen miedo del jefe y del cliente. Este miedo les paraliza y reduce su productividad. Estudios han demostrado que eliminando las fases de test se puede adelantar las fechas de entrega, algo positivo para el proceso. Sin el miedo, las innovación y experimentación pueden florecer. El trabajo del programador es producir código, y mantenerlo es tarea de otros.

(...)

En fin, la lista tiene años y tiene multitud de ideas gloriosas para escribir código inmantenible. Si tiene tiempo y es usted programador de Java, C o C++ échele un vistazo. Si quiere escribir bien, en cambio, lo tiene más complicado.

¹ La traducción es muy libre, aviso. Yo he escogido ejemplos que se aplican a C porque es el lenguaje con el que trabajo. Y se pueden hacer muchas muchas guarradas en C...

How to write unmmaintainable code
C traps and Pitfalls, de Andrew Koenig pone el ejemplo del puntero-comentario.

Posts relacionados

CSI XIV: Lenguajes y gramáticas (i II)

2008-11-22T09:40:00.003+01:00

Es obligatorio leer el post anterior...

Nos habíamos quedado en una pregunta: ¿Cómo se relaciona las gramáticas formales con los lenguajes de programación de alto nivel? Pues verán, los lenguajes de programación están especificados mediante una gramática que determina la secuencia de palabras aceptable en un programa. Y nosotros, los humanos, hacemos algo parecido cuando queremos entendernos. Si yo les digo "rosa un pasea perro tranquilamente" no estoy hablando español, por más que las palabras que gaste existan en la lengua española. Existe una gramática que debo cumplir.

Es importante notar una diferencia respecto al ejemplo anterior de las aes y las bes. Lo que antes eran letras que conformaban el alfabeto ahora se corresponden con palabras que integran el vocabulario. Las reglas de la gramática castellana se aplican a las palabras, las cuales reciben categorías gramaticales, como sustantivo, adjetivo, verbo, etc. En informática en vez de palabras hablamos de tokens. Tokens típicos son identificador, declaración, expresión...

Vamos a crear una sencilla gramática, que será una burda imitación de nuestro lenguaje. Los símbolos no terminales serán: ORACIÓN, SUJETO, PREDICADO, DETERMINANTE, SUSTANTIVO, VERBO, ADJETIVO y ADVERBIO. Los no terminales serán el conjunto {un, el, este, aquel, perro, gato, pastel, azul, pequeño, pasea, camina, garbosamente, rápidamente}.

En primer lugar estableceremos la relación entre los terminales y las categorías gramaticales representadas por símbolos no terminales. En nuestro caso esto es evidente y la representación se entenderá fácilmente:

DETERMINANTE = {"un", "el", "este"}
SUSTANTIVO = {"perro", "gato", "pastel"}
VERBO = {"pasea", "camina"}
ADJETIVO = {"azul", "pequeño"}
ADVERBIO = {"garbosamente", "rápidamente"}

Si la secuencia de letras corresponde a una palabra con un no-terminal asociado viene determinado por el análisis léxico. Garvosamente no es un adverbio, por mucho que lo parezca: es una burrada. Decimos entonces que se trata de un error léxico.

Nuestra gramática relaciona los símbolos no terminales y tiene esta pinta, que seguro les sonará del cole:

ORACIÓN := SUJETO PREDICADO
SUJETO := DETERMINANTE SUSTANTIVO | DETERMINANTE SUSTANTIVO ADJETIVO
PREDICADO := VERBO | VERBO ADVERBIO

¹

Tomando el no-terminal ORACIÓN como símbolo inicial, ya pueden dedicarse a averiguar si los siguientes secuencias de palabras caen dentro de nuestro pequeño lenguaje. Por ejemplo, son parte de nuestro lenguaje: este perro azul camina rápidamente, un gato pasea o Este pastel azul camina garbosamente. En el último caso la oración no tiene ningún sentido, pero es sintácticamente impecable. El último paso para dotar de sentido una oración en un lenguaje es realizar un análisis semántico. En las lenguas naturales éste depende del contexto y es posible que en cierto ámbito pudiera tener sentido que un pastel caminara y, además, lo hiciera con cierto estilo.

Nuestra especificación de un lenguaje deja mucho que desear, por supuesto y sólo recuerda vagamente a los idiomas que hablamos. Los lenguajes que usamos los humanos son lenguajes naturales y la mayoría de las gramáticas que emplean son ambiguas, esto es, para una secuencia de entrada admiten distintas interpretaciones. Los lenguajes informáticos tratan de eliminar toda posible ambigüedad mediante reglas expresas en el tratamiento de la entrada, reglas de precedencia... sin embargo hay ocasiones en los que el comportamiento del compilador, que es quien debe leerse el programa y determinar su validez, se deja sin determinar.

Y en este punto ha aparecido un concepto nuevo: el compilador. El compilador es un programa que, tomando un conjunto de archivos con un lenguaje que podemos entender, genera un archivo ejecutable: una imagen en memoria que se puede ejecutar. Un programa, vamos. Y para entender lo que pone en el fichero, el compilador tiene que realizar las mismas acciones que acabamos de describir.

Es decir, que el compilador primero lee letra a letra el archivo y crea una secuencia de tokens. En nuestra analogía, si el compilador tomara como entrada una frase como Un pastel pasea azul, la salida del análisis léxico sería la secuencia: DETERMINANTE SUSTANTIVO VERBO ADJETIVO. El compilador a veces duda: si lee una p tras un espacio no sabe si corresponde a un SUSTANTIVO (pastel, perro) a un VERBO (pasea) o a un ADJETIVO (pequeño). Y a veces el programador piensa que el compilador va a entender una cosa y entiende otra. (Estoy en condiciones de poner ejemplos a petición de los informáticos).

Con la secuencia de tokens formada, el compilador toma el símbolo inicial de la gramática y juega a validar esa secuencia con las reglas de la misma (análisis sintáctico). De este modo decide si un programa es correcto. Que un programa sea sintácticamente correcto no significa que funcione como el programador espera, del mismo modo que nuestro ejemplo del pastel paseante funcionaba sintácticamente sin tener sentido. A veces las frases sin sentido nos hacen gracia, pero un programa sin sentido no hace ni puta gracia.

En serio.

Precisamente leí hace poco que el primer compilador fue desarrollado por una mujer, Grace Hopper, una de las pioneras de la informática. Programó los computadores más importantes de la época (años 50 y 60) y partici´po en el desarrollo de los lenguajes COBOL y FORTRAN, dos de los lenguajes con más arraigo entre los matemáticos y físicos y que son tan buenos que hoy en día, más de 40 años después, se siguen empleando

En resumen, quizá hayan visto ustedes el código de algún programa y les haya parecido complicadísimo (sin contar que hay gente que escribe código fatal). Desengáñense. Ese lenguaje hay un conjunto relativamente reducido de tokens y su gramática es tremendamente más sencilla y restrictiva que todo aquello que les enseñaron en el cole, con sus excepciones y dialectismos.

¡Los programadores estamos, definitivamente, sobrevalorados!

¹ Los informáticos me podrán decir que esta gramática no se ajusta a la forma normal de Chomsky y mogollón de cosas más. Es cierto que no he querido complicar demasiado la explicación: no pretendo que nadie apruebe una asignatura de teoría de autómatas o lenguajes formales gracias mis posts. Como dije, pretendo tan sólo mostrar que Informática es algo más que páginas web y bases de datos.

Apuntes de clase.
En la wikipedia podemos ver un diagrama sencillo de cómo actúa un compilador.

Posts relacionados

CSI XIV: Lenguajes y gramáticas (I)

2008-11-22T09:38:00.002+01:00

Éste post pretende ser, no exactamente una continuación, sino un complemento a éste post acerca del lenguaje de las máquinas. Recordando un poco de qué iba, vimos cómo en principio las instrucciones recibidas por máquinas y computadores eran de tipo mecánico. Con el tiempo se pudo almacenar estas instrucciones en forma de memorias magnéticas donde series de niveles de tensión determinaban el comportamiento de los componentes del procesador.

Se desarrollaron luego distintos niveles de abstracción sobre el lenguaje en el que se expresaban estas instrucciones (programas). El lenguaje ensamblador consistía en una serie secuencial de códigos que representaban directamente las instrucciones que podía ejecutar un procesador. Era completamente dependiente del mismo. Sin embargo, por encima del ensamblador surgieron lenguajes con un nivel mayor de abstracción, independientes de la máquina en el lenguaje que emplean. Se les llama lenguajes de alto nivel. Los lenguajes más empleados hoy en día son de este tipo, aunque hay muchas diferencias entre ellos.

En el post de hoy generalizaremos la representación de un lenguaje de alto nivel y veremos en qué medida sus conceptos son tomados de la lingüística y se basan en la teoría de grupos.

Empezaremos desde abajo: llamamos alfabeto a un conjunto finito de símbolos (que llamaremos letras). Una palabra es una secuencia de finita de letras de un alfabeto. Hasta ahí todo normal, ¿no?. Venga un ejemplo: Δ es un alfabeto compuesto por las letras a y b. No nos liemos con más. Algunas palabras posibles sobre ese alfabeto son aaaab o baaba. Al conjunto de todas las palabras que se pueden formar con este alfabeto se le denomina el lenguaje universal sobre el alfabeto Δ, siempre que incluyamos en el mismo la palabra vacía λ (lambda). La palabra vacía tiene longitud 0.

Dado que el lenguaje es un conjunto, se pueden realizar operaciones sobre el mismo y, dependiendo de las propiedades que cumpla, le daremos un nombre u otro. Eso se lo dejaremos a los matemáticos.

Los lenguajes universales, pese a ser fascinantes por sus propiedades (digo yo) de poco nos sirven en la práctica. Volviendo a un plano más cercano a la vida real, los seres humanos no sólo empleamos un conjunto finito de palabras, sino que además empleamos un orden determinado entre ellas. A este orden se le denomina sintaxis. Y la gramática determina las reglas en las que se deben combinar las palabras.

En informática (y matemáticas) una gramática tiene una definición formal: consta de un conjunto de terminales, un conjunto de no-terminales (o símbolos auxiliares), un símbolo no-terminal inicial y un conjunto de las reglas de producción. Las reglas de producción determinan la generación de las palabras del lenguaje. Con un ejemplo esto queda clarísimo.

Nuestro alfabeto Δ = {a,b,&lambda} podría ser el conjunto de terminales. S será el símbolo no terminal inicial y A es el otro no terminal. Las reglas de producción podrían ser estas (enseguida las explico):

S := bS | aA | λ
A := aS | bA

Posibles derivaciones:
S -> bS -> bλ: b forma parte del lenguaje.
S -> bS -> baA -> babA -> babaS -> babaλ : baba forma parte del lenguaje.

Ésta gramática genera el lenguaje de las palabras con un número par de aes. ¿No me creen?. Pues vean. El juego consiste en, empezando en el símbolo inicial, quedarse sin no-terminales. Cuando queden sólo terminales se termina y obtenemos una palabra. El símbolo inicial es S y decimos que S deriva directamente bS ó aA ó la palabra vacía (| significa 'o'). Podemos escoger cualquiera de las tres derivaciones. Si escogemos la palabra vacía ya hemos acabado, porque nos hemos quedado sin no-terminales: la palabra vacía tiene 0 aes y forma parte del alfabeto. Si escogemos bS tenemos que quitar la S, y derivamos de nuevo. Posibles secuencias de derivaciones a partir de ésta podría ser las que hemos visto en el ejemplo de arriba o la que se ve en la figura. (en la figura he empleado sigma para referirme al alfabeto, lo cual suele ser una convención).

¿Por qué no prueban a jugar siguiendo las reglas? Verán que todas las palabras tienen 0 o un número par de aes.

Y ahora es el momento de cambiar de post, porque si no, esto queda muy largo. Vayamos al siguiente para ver qué tiene esto que ver con los lenguajes de programación...

¹ Esta entrada no se ve bien con IE6, en parte porque yo no he escrito bien HTML (que Firefox se traga), en parte porque Internet Explorer no muestra casi nada bien. Pero bueno, no me enseñaron HTML en la carrera, me enseñaron cosas como ésta que les he contado. Por eso esta sección se llama Cosas que Si se dan en Informática,

Apuntes de clase. Anda que no hace tiempo que estudié esto...

Posts relacionados

Crear subetiquetas en Blogger

2008-09-09T18:34:00.008+02:00

Que Blogger no es especialmente flexible a la hora de personalizar el blog es bien conocido. Lo sabrá cualquiera que haya intentado juguetear un poco con el template. Wordpress ofrece muchas más características, además de plugins de terceros que se pueden integrar fácilmente (supongo) para personalizar el blog. Yo ya me he peleado unas cuantas veces con mi plantilla cuando he querido hacer algunas cosas un poco especiales: ensanchar el blog, introducir el Seguir leyendo, definir entradillas personalizadas, y más recientemente pasar del tamaño fijo y ajustar la anchura del blog al tamaño de la pantalla.

Una cosa que siempre he deseado hacer era utilizar subetiquetas. Es decir: refinar un conjunto de posts (los de la etiqueta Cerveza en este caso) con otras etiquetas. Esto es bastante útil para clasificar los post en la barra lateral, al menos en un blog como el mío. Los gestores de blogs no entienden de subetiquetas y todas las etiquetas tienen la misma jerarquía. Así que el tema consiste en conseguir que en la barra lateral aparezcan, alineadas en forma de árbol, las etiquetas y subetiquetas que yo desee. Encontré un método muy cómodo y personalizable, pero que incluía bastante Javascript (además de tener otros inconvenientes). Yo lo quería sin librerías de funciones ni muchas imágenes ni nada de eso. Finalmente se me ocurrieron dos soluciones de aficionado (que funcionan).

La solución con falsas etiquetas

El problema con Blogger es que no soporta las consultas del tipo: muéstrame todos los posts con la etiqueta 'Cerveza' AND 'Historia'. No le da la gana¹. Porque Wordpress sí que lo hace y para muestra, http://curiosoperoinutil.com/category/ciencia/fisica/. Podéis ver que el blog Curioso pero Inútil tiene en la barra, bajo la categoría Ciencia muchas subetiquetas, como por ejemplo Física.

Por otro lado Blogger sí que soporta la búsqueda de cadenas de texto. Así que mi primera solución fue de pillo: emplearía falsas etiquetas con palabras clave, ocultas en cada post que quisiera clasificar bajo la etiqueta de 'Cerveza'. Por ejemplo, en cada post que fuera de Historia de la Cerveza gastaría la palabra oculta cervhistoria. Para ocultarla, basta cambiar la propiedad de estilo display.

Es decir, escribo, al final de cada post de Cerveza con la 'subetiqueta' Historia <span style="display:none;>cervhistoria</span>.

Una vez hecho esto podemos consultar todos los posts con la palabra cervhistoria con la consulta http://civada.blogspot.com/search?q=cervhistoria².

Y ahora sólo tengo que editar el template del blog para cambiar la barra lateral. A los elementos especiales del blog que están en la barra lateral se les llama widgets. Hay un widget específico para las etiquetas. En él se recorren todos los nombres de etiquetas de tu blog que Blogger almacena (alfabéticamente) y se muestran como una lista html. Sólo tenemos que 'buscar' la etiqueta deseada (Cerveza) y entonces iniciar una sublista html. En ella añadiremos los enlaces a las búsquedas de palabras ocultas. (el añadido está en rojo)

Buscamos el widget en el template y hacemos esto (alguien que haya hecho algo de informática lo entenderá enseguida):

<b:widget id='Label1' locked='false' title='Etiquetas' type='Label'>
<b:includable id='main'>
<b:if cond='data:title'>
<H2><data:title/></H2> 
</b:if>
<DIV class='widget-content'>
<UL> 
  <b:loop values='data:labels' var='label'>
  <LI>
   <b:if cond='data:blog.url == data:label.url'>
   <SPAN expr:dir='data:blog.languageDirection'>
    <data:label.name/>
   </SPAN>
   </b:if>
   <b:else/>
    <A expr:dir='data:blog.languageDirection' expr:href='data:label.url'><data:label.name/></A>
   </b:if>
   <SPAN dir='ltr'>(<data:label.count/>)</SPAN> 
   <b:if cond='data:label.name == "Cerveza"'> 
    <UL style='margin-top:5px;'>
    <LI><A href='http://nombredelblog.blogspot.com/search?q=cervhistoria'>Historia</A></LI>
    <LI><A href='http://nombredelblog.blogspot.com/search?q=cervestilos'>Estilos</A></LI>
    </UL> 
   </b:if>
  </LI> 
  </b:loop> 
</UL> 
<b:include name='quickedit'/>
</DIV>
</b:includable>
</b:widget>

Y funciona. Veamos las ventajas de este método.

Es relativamente sencillo.
No hay que trastear mucho el template. Aunque por cada nueva 'subetiqueta' virtual tendremos que añadir una linea nueva, claro.
Es una idea cojonuda

Pero veamos las desventajas

No son etiquetas de verdad. Nadie se podrá suscribir a los posts de Historia de la Cerveza. Lástima por los historiadores maltasianos. Tampoco tenemos cuenta de posts subetiquetados. Lástima por los amantes de las estadísticas
'Etiquetar' muchos posts antiguos con las nuevas palabras ocultas es un rollo.
El día que a Blogger le de por añadir esta característica tendremos que etiquetar de nuevo y desmontar la paraeta.

Así que mirando el template di con una solución más bestia y menos elegante, pero con etiquetas de verdad.

La solución a lo bruto

Es muy sencilla: consiste en NO añadir a la lista principal las subetiquetas Y AÑADIRLAS expresamente bajo la etiqueta principal. Para eso gastaremos dos millones de expresiones condicionales. ¿Por qué?. Porque, que yo sepa, Blogger no entiende expresiones condicionales compuestas. Supongamos que tenemos tres subcategorías bajo Cerveza que son Historia, Estilos y Ronda.

La cosa es (atentos, amantes del pseudo-código)

PARA todas_las_etiquetas HACER
SI nombre_de_etiqueta NO_ES Historia NI Estilos NI Ronda ENTONCES
(abrimos lista)
...Código del widget...
SI nombre_de_etiqueta ES Cerveza ENTONCES
   PARA todas_las_etiquetas HACER
   (empezamos sublista)
   SI nombre_de_etiqueta ES Historia O Estilos O Ronda
     Añadimos enlace a la etiqueta como el resto.
   (cerramos sublista)
(cerramos lista)
PUES_YASTA

El único problema es que en Blogger (QUE YO SEPA) no se puede poner ni NI ni O. Lo cual es triste para la programación. Porque hay que añadir un mogollón de código. Algo así:

Y no queda nada elegante, pero funciona, y funciona bien, como pueden ver en la barra de al lado. Pasemos pues a la enumeración de pros y contras (esta vez en orden inverso).

Contras de esta solución:

Es un peñazo para el template, sobretodo si un desea emplear muchas subetiquetas. Hay que tocar mucho código.
Algún día Blogger le dará soporte directamente y todo esto se irá al garete

Ventajas:

Es muy fácil añadir las subetiquetas a los posts ya creados.
Tenemos etiquetas de verdad, a las que uno se puede suscribir. Los maltasianos estarán contentos. Y los amantes de las estadísticas.

Hay que hacer notar que, aunque pongamos mogollón de código condicional en el template, éste no se transmite y por tanto no hace que la página 'pese' más. Sí que puteamos un poco a los servidores de blogger, que son los que procesan el template junto con los datos del blog y crean el código html que es efectivamente transferido (el tiempo de proceso del servidor suele ser nimio en comparación con el de transmisión). Pero que se jodan. Haber dado soporte directamente, leñe.

Y ya está. ¿A que mola?. Yo no lo había visto en ningún blog de Blogger. Sólo hace falta que lo diga para que me salgan 15 ejemplos. Si alguien conoce una manera mejor de hacer lo mismo, que me lo diga, por favor.

Actualización

Rô ha realizado en su blog una explicación detallada del segundo método. La pueden consultar aquí: Parte I, Parte II y Parte III. Si después de leerlos les queda alguna duda... ¡léanlo otra vez, porque está muy bien explicado!. Bueno, no, pregunten si quieren...

¹ Si sí que lo hace y yo no lo he conseguido, dejen de leer, por favor. Y díganmelo, porque me he vuelto loco probando hasta decidir (yo solo) que no se puede.
² Evidentemente, hay que emplear alguna palabra que no vayamos a usar en posts que no sean de esa subcategoría.

Blogger Data API. Consultas.
Blogger Layout Help.

Posts relacionados

El fallo en BGP, algo nuevo pero no tanto

2008-08-28T12:08:00.003+02:00

Han saltado las alertas. La comunidad informática mundial se enfrenta a la mayor amenaza a la privacidad en Internet. Se ha desvelado un fallo de seguridad que pone en peligro las comunicaciones de todo el tráfico en la red de redes. De hecho esta página que usted está leyendo podría ser falsa y estas palabras no haberlas escrito yo. Es incluso más posible que alguien esté tan sólo fisgoneando todas las páginas que usted pide. Y este es el segundo super fallo desvelado en apenas unos meses.

Supongo que eso es lo que pensará usted si ha leído las informaciones (la I y la II) aparecidas en El País acerca del fallo en el protocolo BGP. No seré demasiado duro juzgando a los articulistas y diré simplemente que no lo han explicado o entendido muy bien. O traducido, porque la cosa viene bastante bien explicada en Wired y la información de El País copia sólo la mitad y traduce mal la parte que copia.

Lo que les cuento en el primer párrafo es totalmente cierto. Pero es que es totalmente cierto incluso sin existir el fallo de seguridad descubierto ahora. En este post, yo, que tengo más espacio que la gente de El País (en eso se les disculpa) les cuento de qué va el fallo BGP y qué supone de nuevo.

En una frase tiene mucha razón el segundo artículo de El País y es que Internet no se diseñó para ser segura. La información que usted solicita y que le llega a su ordenador fluye por los cables visible para todos: como si usted envía una carta en un sobre abierto. En Internet sería un poco complicado leer la carta, porque la información se trocea en pequeños paquetes, pero la idea es la misma: sólo tienes que estar en el lugar adecuado para recoger la información y husmear.

Ese tipo de ataques se llaman de hombre en el medio -man in the middle- y lo han hecho todos los estudiantes de informática en alguna práctica cuando, con un sniffer de paquetes, se ponen a mirar qué es lo que pasa por la red local a la que están conectados todos los ordenadores del laboratorio. Evidentemente, el hombre en medio puede leer toda la información entre origen y destino siempre que no vaya cifrada. Así que la amenaza no es nada nueva: el fallo BGP consiste en un buen modo de situarse en el lugar adecuado y recibir tráfico para fisgonearlo o incluso modificarlo.

Ya conté cómo funcionaba Internet, aunque me hicieron falta dos posts y puede que la cosa no quedara muy clara. La idea es que, para llegar de una red de computadores directamente conectados a otra se utilizan dispositivos llamados routers. Entre dos redes pueden existir varios caminos distintos que pasan por distintos routers. Es necesario que un mensaje que va de una red a otra no permanezca dando saltos sin llegar nunca a su destino. Para ello, los routers seleccionan el mejor camino entre dos redes de entre los muchos que pueden existir. ¿Cómo se ponen de acuerdo?. Pues usando un protocolo (un lenguaje común) que se llama BGP.

BGP significa Border Gateway Protocol. Tiene sentido si pensamos en los routers como puertas que están en las fronteras de las redes, decidiendo cuál es el siguiente salto que un mensaje tiene que dar para llegar a su destino. Sin entrar en detalles, los routers deciden a qué siguiente puerta tienen que encaminarlos en base a la información que le proporciona el resto de routers mediante BGP. Pero ¿qué sucede si un router miente?.

Pues eso es lo que se les ha ocurrido a los chicos investigadores. Que no hay manera de detectar esa situación porque cuando se diseñó el protocolo a nadie se le ocurrió que un router podía mentir. La gracia es que de forma muy sencilla puede mentir para situarse como la mejor puerta por donde pasar para ir a... y así espiar el tráfico que va a... Podría también eliminar todo el tráfico que por allí pasara (blackhole), pero entonces se detectaría fácilmente¹. Es más peligroso si modifica ligeramente la información, engañando de este modo a los receptores. Wired comenta que posiblemente este método podría ser usado para espionaje corporativo o militar. Aquí el artículo de El País la caga bien y traduce conceivably (posiblemente) por fue concebido y nos sale con que 'el fallo' fue concebido para ser aprovechado por el espionaje militar. Confunde ademas posibilidad (could) con pasado. Toma ya².

Por supuesto, la solución no pasa por gastar firewalls, como indica el segundo artículo de El País. Ni por tener cuidado por donde se navega, ni tener antivirus ni saber algo del SO³. Posiblemente la solución consistirá en modificar el protocolo BGP de una forma complicada. En realidad, la auténtica solución pasaría por cifrar todas las comunicaciones que realizamos a través Internet. Las técnicas de cifrado en Internet son conocidas, están bien estudiadas y garantizan la confidencialidad y seguridad durante largo tiempo. Con la implicación de los ISPs (proveedores de servicios, como Telefónica) no debería ser muy difícil conseguir esto.

El auténtico problema de la privacidad y seguridad en Internet es que no le interesa a nadie excepto a los usuarios. Y a los que menos interesa es a los Gobiernos, quienes, siempre invocando nuestra propia seguridad, desean tener la oportunidad de fisgonear e interceptar todo tipo de comunicaciones. Y claro, siendo así, difícil es que se implante, ¿no?.

¹ De hecho, eso fue lo que pasó cuando el proveedor de servicios de Internet (quienes suelen mantener los routers) de Pakistan decidió bloquear el tráfico a Youtube de ese modo. El problema fue que routers de países adyacentes fueron así confundidos y el tráfico dirigido a Youtube nunca llegaba a su destino: caía en el agujero de Pakistan.
² ¡ALT1040 no solo se lo cree sino que añade literatura!
³ Todas ellas prácticas muy recomendadas. Yo añado dos: evite Internet Explorer y bloquee los scripts de las páginas (en Firefox se puede hacer con No-Script).

El agujero de seguridad más grande de Internet. Wired
IP hijacking (Wikipedia inglesa).
Kriptopolis lo cuenta con más detalle y muy bien.

Posts relacionados

El problema de los generales bizantinos

2008-07-09T17:29:00.002+02:00

Sitúese.

Está usted en el campo de batalla arrasado, y el viento ondea sus banderas blasonadas, que amenazan la ciudad rebelde, por fin sitiada. Sin embargo, las torturas a las que ha sometido a los infieles no han minado el espíritu enemigo y ningún prisionero ha revelado la cantidad de hombres que guarda la ciudad amurallada. Usted tiene un ejército numeroso, sí, pero las lineas de comunicación y aprovisionamiento han sido destruidas: no podrá mantener demasiado el sitio sobre la ciudad. Urge tomar una decisión sobre el curso de la batalla y, como general que es, deberá consultar con el resto de mandos. La opciones son pocas: atacar todos a la vez o retirarse.

Pero hay un gran problema: sospecha usted que el enemigo se ha infiltrado en sus filas hasta tal punto que es posible que algunos de sus compañeros generales se encuentren, secretamente, sirviendo al enemigo. ¡Hay traidores entre los generales!. Usted sospecha de un par de ellos pero sólo si es capaz de ponerse de acuerdo con otros generales leales en su acusación podrá desenmascarar a los traidores. No puede usted pensar mucho, sus hombres son bravos pero la lealtad se resiente con el estómago vacío. Sólo podrá derrotar al enemigo si ataca con todas las fuerzas de los generales leales así que... ¿podrá usted descubrir a los traidores?. ¿Será capaz usted de poner de acuerdo a los generales bizantinos?.

El problema de los generales bizantinos fue formulado de esta forma (con menos literatura) por Leslie Lamport ^1,2, uno de los grandes de la informática, en 1982. Desde entonces es uno de los clásicos en la teoría de sistemas distribuidos. ¿Y por qué?. Pues veamos.

Piense que en vez de tener usted un conjunto de generales bizantinos tiene usted un conjunto de computadores distribuidos, llevando a cabo una tarea común. Por ejemplo, una transacción bancaria o la monitorización de la ruta de un avión. Eso suena más informático.

Supongamos que uno de los computadores del sistema deja de funcionar. Hace plof y ya está. No responde a los mensajes del resto, ni ofrece resultados: nada. ¿Como podemos saber que ha fallado? Pues muy fácil, como no hace nada ni envía los mensajes que tiene que enviar ni responde a las llamadas, deducimos que ha fallado. Lo más sencillo entonces es reemplazarlo: que otro haga la misma tarea que realizaba. Si un componente 'se muere' de este modo, decimos que ha fallado en modo crash.

Ahora el mismo componente falla, pero en vez de no hacer nada siempre realiza su tarea más tarde de lo que debería. ¿Cómo nos damos cuenta de este fallo?. Pues tan sólo nos es necesario poner en marcha un reloj cuando debería iniciarse. Si, transcurrido el tiempo determinado, el computador o componente no ha ofrecido un resultado, sabemos que está fallando. Y podemos reemplazarlo por otro, como antes. En este caso decimos que el componente falla en modo performance.

Un pasito más. Supongamos que un elemento ofrece resultados dentro del tiempo establecido pero... estos resultados son siempre incorrectos. Aquí se complica la cosa. ¿Cómo sabemos si falla?. Podemos, por ejemplo, poner dos procesadores a hacer la misma tarea y comparar los resultados pero aún así si estos no concuerdan, ¿cómo saber cuáles son los buenos y cuales no?. En este caso necesitamos tres componentes para tolerar el fallo de uno. Y, en general, 2n+1 para tolerar n fallos. Estos fallos se llaman response. Y los sistemas con tres componentes y un comparador se llaman TMR (triple modular redundancy).

¿Se han fijado cómo cada vez necesitamos más cosas para detectar el fallo?

Y ahora vamos a lo bueno. Supongamos que un componente tiene un comportamiento errático y que, a veces ofrece una respuesta correcta y a veces no. Supongamos que, en las votaciones para detectar la respuesta correcta, este computador acusa a otros de ser los erróneos: a uno le dice una cosa, a otro otra distinta. Actúa como un traidor. Como un traidor bizantino.

Está usted de nuevo en el campo de batalla. Y ya tiene su decisión, atacar o retirarse, que debe transmitir al resto de generales. Los generales leales no se equivocarán, y si creen que atacar es la mejor opción, arrasarán al enemigo. Sin embargo puede que los traidores consigan que decidamos retirarnos. Por otro lado, aunque una mayoría de generales leales haya decidido no atacar, es posible que con el voto de los traidores se fuerce el asalto, cayendo en una trampa mortal.

Usted razona: si sólo hubiera tres generales y uno fuera el traidor... ¿podríamos ponernos de acuerdo la mayoría? Supongamos que yo -Apocapes- envío a ambos la orden de atacar. Los generales Belisarius y Comentiolus reciben mi orden, bien. Y sin embargo, el traidor Belisarius informa a Comentiolus de que mi orden ha sido la de retirada. ¿Que pensará Comentiolus? Pues que, o bien Belisarius es el traidor, como de hecho sucede... ¡o bien que el traidor soy yo, el insigne general Apocapes!. Las dos situaciones serían indistinguibles a los ojos de Comentiolus.

Así que, a pesar de ser mayoría los generales leales (de 2 a 1), no podremos llegar nunca a un acuerdo, pues no sabremos de quien fiarnos. Si dispusiéramos de cartas firmadas... podría enviar cada una de ellas al resto de generales y luego estos intercambiar las mismas. Sin embargo cada general sólo puede controlar lo que transmite, no lo que intercambia el resto.

Entonces ¿y si somos cuatro y uno infiel?. Entonces sí que será posible, puesto que Droctulf, el cuarto general, podrá confirmar que yo di la orden de atacar. ¿Será posible que con más del triple de generales leales podamos acordar una solución?

Por supuesto, la suposición a usted no le vale. Necesita la prueba matemática de cuántos generales son necesarios para llegar a un acuerdo con t generales traidores infiltrados. Pero eso aquí no aparecerá: digamos que simplemente imagina grupos de 3t o menos generales generales (albaneses) que alcanzan el acuerdo: consigue reducir el problema al de los tres generales encontrando por tanto una contradicción. Se requieren 3t + 1 generales leales para acordar una solución.

Las banderas se hinchen con renovada fuerza en el campamento. Los generales que rodean la ciudad son 8 y, si el Imperio Bizantino aún conserva parte de su gloria, los traidores serán dos de ellos. Ahora sabe usted que sin duda podrán alcanzar la mejor decisión.

¿Y qué tiene que ver esto con la informática?. Pues mucho. Si usted no es capaz de evitar los fallos bizantinos en sus programas o componentes que actúan de manera distribuida, sepa que cualquier sistema de decisión requerirá de al menos MAS DEL TRIPLE de componentes que actúen correctamente que los que no³.

Y eso es vital en Tolerancia a Fallos: los sistemas están diseñados para que cualquier tipo de fallo pueda convertirse en uno tipo crash. Aunque se necesite aumentar la circuitería o software de detección, los fallos crash (u omission) -semántica débil de fallo- son por lo general más fáciles de tratar.

Y por eso se le suele dar muerte a los traidores. Es la solución mas ingenieril.

¹ El problema de los generales es más antiguo, pero la generalización de Lamport es la más conocida.
² ¿Sabían que Leslie Lamport también creó LaTeX (Lamport TeX)?
³ Siempre que las comunicaciones sean como las descritas, esto es, que un miembro no puede garantizar que e estado que de él transmiten los otros es cierto.

LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEASE. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, pp 382-401. (enlace)
Lista de Generales Bizantinos

Posts relacionados

CSI XIII: El lenguaje de las máquinas

2008-05-30T19:58:00.001+02:00

Muchas personas han oído hablar alguna vez de lenguajes de programación. Se intuye que los lenguajes de programación sirven para decir a un computador qué instrucciones debe ejecutar para llevar a cabo determinada tarea. Claro, que eso es bastante complicado de realizar. Si nosotros pudiésemos hablar al ordenador le diríamos: "conéctate a Internet" o "Inserta al nuevo cliente en la base de datos". Bueno, eso podemos, podemos hablar al computador todo lo que queramos. El problema es que dudo mucho que entienda nuestro lenguaje.

¿Qué lenguaje entiende un computador?. Según el párrafo anterior la respuesta sería: lenguajes de programación. Otro, quizá, más versado, diga: "el de unos y ceros". En realidad es una pregunta trampa, porque el concepto de lenguaje es una abstracción humana. Si llamamos lenguaje al conjunto de señales que emitimos y recibimos para comunicar algo, entonces el lenguaje de las máquina sería el de las señales eléctricas de tensión que según sus niveles, llamamos 0 lógico o 1 lógico. Si en cambio llamamos lenguaje a una construcción de símbolos (o palabras) gobernadas por una gramática, entonces la respuesta está más cerca de la primera.

No sólo los computadores como su PC entienden lenguajes: muchas máquinas, robots de procesos industriales o ascensores entienden algún tipo de lenguaje que los hace funcionar: qué características tiene ese lenguaje es lo que voy a intentar explicar en los siguientes posts.

[Antes de continuar aviso que me estoy metiendo en camisa de once varas, porque éste no es, ni mucho menos, mi campo natural. Avisado queda el lector avanzado]

Nos ayudará a entender qué lenguajes entienden las máquinas una pequeña revisión histórica. La programación más antigua de una máquina conocida es la de los telares de de Jacqard (1801), donde una tarjeta perforada controlaba el movimiento de las agujas. Aquí, por supuesto, no había computación alguna sino que los agujeros en las tarjetas permitían ciertos movimientos. Otras máquinas utilizaron este sistema y cuando nacieron los primeros computadores, basados en dispositivos electromecánicos, la tarjeta perforada se empleó para asignarles instrucciones y entrada de datos.

Durante la IIGM, por ejemplo, los grandes computadores se utilizaban para los complicados cálculos de trayectorias. Richard Feynman, en los laboratorios de Los Álamos estaba encargado de la sección informática. En el libro ¿Está usted de broma, sr. Feynman? narra cómo los ingenieros debían escribir los programas en tarjetas y, secuencialmente, introducirlas en la máquina para que ésta realizara su trabajo. Si te equivocas en el orden las has fastidiado¹. Aquí hay que entender que un computador es un procesador de instrucciones, nada más. Y las instrucciones que puede ejecutar son específicas de cada chip o circuito impreso.

Las tarjetas representaban en ocasiones códigos binarios (ceros y unos). Cada código identifica una instrucción o operación que puede hacer la máquina. Las operaciones que puede hacer un procesador son terriblemente sencillas: lee una instrucción de la tarjeta, multiplica un dato por otro, escribe sobre una posición de memoria... muy poco más, no se crean. Al lenguaje de unos y ceros se le llama código máquina.

Se pueden imaginar lo complicado que era programar de este modo un computador. Pero pronto, en la década de 1950 aparecieron una serie de códigos mnemónicos para identificar cada instrucción. Estos códigos consistían en unas pocas letras, que representaban el nombre de la instrucción seguidas de los operandos propios de cada una de ellas. Por ejemplo:

ADD A, #03h

significa, una vez traducida al código máquina:

00100100 00000011

Y representa la instrucción que dice que hay que sumar un número (3) al registro acumulador, que guarda los resultados de la unidad sumadora. Como ven, se trata de un avance significativo, porque programar se convierte en algo mucho más sencillo. Es muy fácil recordar los códigos de un procesador y más difícil equivocarnos. Por ejemplo, si escribo AFD A, #03h, el programa que traduce estos códigos a lenguaje máquina se quejará, porque no existe ningún código llamado AFD.

El programa que traduce estos códigos al lenguaje máquina se llama ensamblador¹. Y también se llama así al lenguaje generado por estos códigos. El paso de lenguaje máquina a lenguaje ensamblador produjo la llamada segunda generación de lenguajes.

Pero el ensamblador tiene algunas pegas: la operación que hemos visto, por ejemplo, pertenece al juego de instrucciones del procesador 8051 y, por tanto, no sirve para ningún otro procesador que no sea compatible con éste. Esto significa que un mismo programa no nos sirve para distintas máquinas y que cada vez que una compañía de chips cambie el juego de instrucciones del procesador, necesitaremos reescribir todos los programas que tenemos (por eso se intenta cambiar pocas veces el juego de instrucciones y cuando se hace es para ampliar, pocas veces para quitar).

Efectivamente, el lenguaje ensamblador está demasiado pegado a la máquina: para programar bien tienes que conocer detalles de la arquitectura del procesador. Por ejemplo, si no sabes cómo funciona ni donde está el registro acumulador del procesador, difícilmente sabrás cómo hacer una suma, por más que exista una instrucción llamada 'ADD'.

Era necesario "independizar" de alguna manera el código que escribíamos en cierto lenguaje del modo en que el procesador actúa. Y por cierto, estamos hablando de 'lenguaje', pero está claro que una secuencia de estos códigos se parece a todo menos a un lenguaje tal y como lo hablamos o leemos.

Sin embargo, imaginen poder decir a cualquier procesador algo así como:

si nuevo_nombre es_igual_a Ramon
entonces dime "Hola Ramon"
y_si_no dime "No te conozco"

Pues bien hay maneras de crear lenguajes de esta manera: a la nueva generación de lenguajes que pudo hacer eso: abstraerse de la máquina donde son ejecutados se les llamó lenguajes de tercera generación y los primeros surgieron hacia los años 60. Los lenguajes de tercera generación se separan tanto del computador que están más cerca del ser humano que de la máquina: por su nivel de abstracción se llaman lenguajes de alto nivel.

Y en el siguiente capítulo veremos cómo se puede conseguir hacer eso.

¹ Como le pasó al pobre Apu, el creador del primer programa para jugar al tres en raya. Bart desordenó sus tarjetas perforadas.
² Quizá se pregunten cómo se ha escrito el propio programa ensamblador. Pues los primeros de ellos, claro está, se escribieron en lenguaje máquina.

Por si les interesa: aquí el juego de instrucciones del 8051

Posts relacionados

El Nilo, Internet, y los fractales

2008-04-30T19:14:00.001+02:00

Y el precio del algodón, claro, aunque no me cabía en el título. Pero vayamos por partes.

Harold Edwin Hurst nació en 1880, cerca de Leicester. De origen humilde, muy pronto destacó en sus estudios, obteniendo una beca que le permitió estudiar en Oxford. Allí se graduó con méritos en Física, sin apenas formación matemática previa. En 1906 le surgió la oportunidad de viajar al aún británico Egipto y Hurst aceptó. En ese país se dedicaría a la investigación durante más de 60 años, por encima de los cambios políticos que sucedieron a la descolonización.

Aunque se ocupó de diversas tareas en sus primeros años (relacionadas con la astronomía o geología), pronto perseveró en el estudio de la meteorología e hidrología. En 1915 Hurst se convirtió en el director del Departamento Físico de Obras Públicas. Y a este departamento le correspondió el problema de domesticar el poderoso río Nilo a los intereses de las industrias y campos a sus orillas. El sistema utilizado para ello, era, claro está, a través de embalses.

Analicemos el problema (simplificado): supongamos que lo que queremos es determinar cuál debe ser la altura mínima de una presa o paredes de los embalses (Figura 1). Para ello, idealmente, sólo necesitamos conocer cuál es la capacidad y forma del embalse, la tasa a la que se puede desalojar el agua del mismo y el caudal máximo que llega a aportar el río a su entrada. Y claro, de las tres cosas, lo único impredecible es esto último. ¿O no?. Determinar ese nivel fue la tarea a la que se enfrentó Hurst.

Por suerte el Nilo es un río histórico, y sus niveles han sido estudiados a lo largo de los siglos por diferentes civilizaciones. Hurst no solo se aplicó en obtener detalladas mediciones del volumen del Nilo en distintos instantes de su época (correlacionados con muchas otras variables), sino que recopiló con tesón los registros históricos que le darían una visión de conjunto.

Hurst se dio cuenta, que, a pesar de la apariencia irregular de las mediciones, seguían cierto patrón agrupado en épocas de sequía e inundaciones. Y lo que es aún más raro, ese patrón irregular se repetía a distintos niveles. Dicho de otra manera: la serie de datos observada a corta distancia -intervalos de días- "se parece" a la serie observada a lo largo de años.

El problema es que entonces no existía ningún modelo matemático que expresase esta idea, así que Hurst creó el suyo. Sin entrar en detalles (ya no tengo mucha soltura matemática), descubrió que la relación entre las medidas podía ajustarse mediante un parámetro de una ecuación, que relaciona la varianza de las muestras agrupada. Si el valor de este coeficiente -coeficiente de Hurst- es 0.5, se considera que el proceso es completamente aleatorio. Si en cambio el valor de éste se encuentra entre 0.5 y 1, se dice que que el proceso sigue el mismo patrón a distintas escalas: se convierte en un proceso autosimilar. En concreto, para el Nilo, este valor era de 0.72.

Los científicos acogieron con escepticismo esta idea. Más que nada porque Hurst había dado con un ajuste, pero no había ofrecido lo más interesante: el por qué sucede de este modo y no de otro cualquiera. Pero tras divulgarse en los años 50 sus resultados, muchos científicos (y de muchos otros campos) midieron valores de 0.7 para fenómenos completamente distintos de los hidrológicos.

Uno de estos científicos era matemático y se llama Benoît Mandelbrot. Estudiaba la economía. Tras publicar un estudio sobre las fluctuaciones del precio del algodón, un amigo le advirtió de las similaridades con los resultados de Hurst. Mandelbrot estudió entonces en profundidad el trabajo de Hurst y concluyó que podía aplicarse a las finanzas, donde las fluctuaciones a largo plazo podían ser previstas gracias al análisis de Hurst. Mandelbrot, de origen judío, acuño dos términos para describir las variaciones en un proceso a larga escala:

El efecto José nos dice que las fluctuaciones de los valores de un proceso a lo largo del tiempo tienden a ser parte de un patrón más amplio. Se denomina de este modo a causa de la predicción que José lanzó sobre Egipto a través de los sueños del Faraón: que a siete años de abundancia seguirían siete de hambruna.

Aconteció que pasados dos años tuvo Faraón un sueño. Le parecía que estaba junto al río; y que del río subían siete vacas, hermosas a la vista, y muy gordas, y pacían en el prado. Y que tras ellas subían del río otras siete vacas de feo aspecto y enjutas de carne, y se pararon cerca de las vacas hermosas a la orilla del río; y que las vacas de feo aspecto y enjutas de carne devoraban a las siete vacas hermosas y muy gordas. Y despertó Faraón.

Genesis 41.1-4

El efecto Noé nos dice que, además, cuando se producen los cambios o fluctuaciones, éstas tienden a ser abruptas. Vamos, que de normal llueve poco y con regularidad, pero, de vez en cuando, cae la de Dios.

Los procesos autosimilares se han estudiado con tesón desde entonces. El propio Mandelbrot se convirtió años más tarde en el famoso padre de los fractales, donde la relación entre estos y los primeros es evidente. Hurst siguió estudiando el Nilo hasta sus últimos días y murió en 1978. Pero, ¿qué tiene que ver Internet con todo esto?.

Supongamos que un dispositivo de red debe encaminar flujos de información de muchos orígenes a través de una linea (Figura 2). Este dispositivo debe poseer los suficientes recursos para que no se pierda información, esto es, no se desborde. Claro, que siendo ingenieros nos interesa poner lo mínimo posible para que funcione bien. Por tanto, tenemos que calcular con precisión el tamaño de la memoria (llamada buffer) a a la entrada del dispositivo... ¿Les suena este problema?.

Hasta la década de los 90 se creía que las llegadas a un sistema o dispositivo en Internet (tales como un servidor o un router) seguían una distribución de Poisson. Pero entonces varios artículos y estudios empíricos (Leland et al) demostraron que el tráfico de red seguía un patrón autosimilar (o fractal). Por tanto, se podían aplicar todos los análisis realizados en otros campos al diseño de bufferes y asignación de recursos en la red.

La imagen muestra la carga real soportada por un servidor web de tamaño mediano y varios detalles de la misma. El parámetro Hurst estimado para ella es de...

Pero, y pasemos ahora de ingenieros a científicos, ¿por qué el tráfico de la red sigue un patrón autosimilar?. Bien, para eso también hay explicaciones propuestas. Se ha demostrado que la agregación de tráficos ON/OFF genera un patrón autosimilar. Tráfico ON/OFF significa, por ejemplo, que pido una página y me paro un poco. Al poco pido otra página y paro. Agregado significa que si mi hermano está navegando, y mi vecino y sus primos y todas esas peticiones van al mismo servidor, ese tráfico ON/OFF se suma en el destinatario. Pues bien, si el tráfico ON/OFF sigue cierta distribución (secuencia de paradas y peticiones), entonces el agregado resulta autosimilar.

La gracia es que el tamaño de los objetos que residen en la web (paginas, imágenes, archivos...) actúa sobre el tráfico de un modo parecido al descrito. En la web hay una gran cantidad de objetos muy pequeños que actúan como zonas OFF (poco tráfico) cuando los solicitamos. Pero también hay unos pocos objetos muy pesados que generan mucho tráfico (zonas ON) al transferirse. Si sumamos el tráfico de 10 personas con patrones de tráfico ON/OFF obtenemos un patrón de tráfico autosimilar, esto es: su coeficiente Hurst es sensiblemente mayor a 0.5.

No me dirán que no es interesante, ¿no?

Apuntes de clase
Safe Heaven Sobre el estudo de Hurst y Mandelbrot.
Hurst obituary. Vida de Hurst.
El análisis de carga se ha realizado a través del análisis de logs de un servidor mediano. El cálculo estimado del coeficiente de Hurst se ha realizado mediante el programa Selfis.

Posts relacionados

CSI XII: Criptografía y cifrado de datos

2008-03-29T13:07:00.000+01:00

Bueno, en los últimos posts de Cosas que Sí se dan en Informática hemos tratado (y bastante) el tema de la codificación, que no es más que utilizar otra representación de los datos con algún motivo. Hoy me voy a plantar y os presento el último post dedicado a este tema: luego pasaremos a otra cosa completamente diferente. Pero es que hablando de codificación de la información no quería dejar sin tratar uno de los temas más interesantes y actuales: la encriptación de datos.

Efectivamente, encriptar información consiste en transformarla siguiendo unas reglas o algoritmo. Cuando hacemos esto es, por lo general, porque no nos interesa que todo el mundo pueda entender nuestro mensaje. La primera aproximación para conseguir esto es la que nos parece más evidente: sólo el receptor del mensaje sabrá cuales son las reglas o algoritmo para descifrar la información que yo envío. A esto se le conoce como cifrado de algoritmo secreto y la verdad es que hoy en día está un poco caduco. Veamos por qué.

Probablemente, todo aquel que de pequeño haya formado parte de un club secreto sabrá a lo que me refiero. Lo más sencillo es establecer unas reglas para codificar la información que sólo conozcamos en el club. De ese modo será casi imposible, si las reglas son complicadas, que cualquier persona ajena pueda descifrar el mensaje. Pongamos un ejemplo, en cambio, de reglas sencillas.

El cifrado más antiguo que se conoce se denomina cifrado César y consiste en sumar a cada letra una cantidad para convertirla en otra del mismo abecedario. Si queremos codificar una 'a' y la clave es 5, sumamos 5 caracteres a la 'a' (b,c,d,e,f) y la cambiamos por una 'f'. Cuando llegamos a las letras del final, por supuesto, reemplazamos por las primeras. Así, un mensaje 'abcdez' se codificaría como 'fghije'. Sencillo.

Demasiado sencillo, claro. Pero aquí ha aparecido un concepto importante, que es el de clave. Nuestra clave era 5 y, en principio, sin conocerla, no podíamos descifrar el mensaje... aún conociendo las reglas de codificación. Bueno, en este caso sí, porque el algoritmo es muy sencillo: sabiendo que la regla consiste en sumar cierto número, para romper la clave sólo tendría que probar a ir sumando a cada carácter 1, luego 2, luego 3... hasta encontrar que la clave es 5 al leer un mensaje con sentido: a esto se le conoce como ataque de fuerza bruta

Pero a medida que el algoritmo se hace más complicado y las claves son largas y complejas, se puede asegurar con cierto rigor que un ataque de fuerza bruta encontrará la clave, en el peor de los casos, cuando la información enviada ya no tenga relevancia. Por eso hoy en día la tendencia es utilizar algoritmos públicos -reglas- para codificar la información. Además, con Internet surgió un problema muy importante para los algoritmos secretos: en nuestro club infantil podemos acordar las reglas secretas en una reunión secreta en la casa del árbol (secreta). ¡Pero en Internet no existe esa posibilidad!: necesitas una canal seguro para difundir las reglas secretas y es justamente eso lo que no tenemos¹.

El primer 'estándar de facto' de los algoritmos públicos fue DES (Data Encryption Standard). DES fue aprobado en 1976 y en 1998 se consiguió romper la clave mediante un ataque de fuerza bruta que duró 56 horas². Si consideramos que la potencia de los computadores ha crecido exponencialmente todos esos años podemos otorgar más que un notable a este algoritmo. De todos modos para entonces DES ya había sido sustituido por una variante más compleja Triple DES que en 2001 fue 'reemplazado' por otro algoritmo, AES (Advanced Encryption Standard). Se han especulado algunas debilidades de AES, pero por el momento no se conoce ningún ataque de fuerza bruta que pudiera dar resultado. Tanto es así que el Gobierno de los EE.UU., acostumbrado a los algoritmos secretos, anunció que podía emplear este método público para cifrar sus documentos TOP-SECRET. Así que es MUY, MUY DIFÍCIL romper una clave. Es MUCHO, MUCHO más sencillo robarla.

Se llama criptografía de clave simétrica a la que usa la misma clave para cifrar y para descifrar. Esto es lo más evidente y en lo que todos hemos estado pensando hasta ahora. Pero he aquí un problema: ¿cómo obtener una clave secreta?. Si emisor y receptor comparten ciudad, o país, la cosa es sencilla: quedan un día y, si tienen la seguridad de que la persona que tienen enfrente no es una impostora, acuerdan una clave segura. Pero si dos personas quieren intercambiar información a través de Internet y no pueden conocerse ¿cómo acuerdan la clave con seguridad?.

Otro problema: si yo quiero comunicarme con Juan, gasto una clave secreta. Y con María otra clave (no sea que Juan se entere) y con Antonio otra, Juan gasta otra distinta para comunicarse con Antonia... en fin, que para comunicarme con n personas necesito n claves distintas y esas son muchas: mejor las apunto en un POST-IT, ¿no?.

Para solucionar estos problemas surgió la criptografía de clave asimétrica que, básicamente, gasta una clave para cifrar y una pareja para descifrar. Y esto da mucho juego. Supongamos que yo en mi casa genero una pareja de claves y me quedo una para descifrar: esa es mi clave secreta. Pero la otra clave la publico en un servidor: es mi clave pública. Entonces, si Juan quiere enviarme algo cifrado, coge mi clave pública, encripta la información con ella y me la envía. La gracia está en que sólo con mi clave privada se puede descifrar este mensaje y esa clave yo la tengo escondida: cualquier otro que lea el mensaje sólo encontrará un galimatías. Y lo mismo puede hacer María, Antonio...

Pero, fatalidad, aquí el problema es otro: cuando me llega un mensaje cifrado con mi clave pública y firmado por Juan... ¿cómo sé yo que es Juan el que me lo envía?. No puedo: Juan debe autenticarse. Pero... ¿y si lo hacemos al revés?: Juan publica una clave suya para descifrar. Cifra el mensaje con mi clave pública para cifrar y cifra el resultado con su clave privada para cifrar. Entonces yo (y cualquiera) podré leer el mensaje cifrado por Juan sin más que coger la clave pública de Juan. El texto contendrá un galimatías: sólo yo puedo entenderlo gastando mi clave privada. Al mensaje cifrado con una clave privada para autenticarse se le llama firma digital. La firma digital autentica, impide la alteración (añadiendo contenido al mensaje) y no es repudiable: Juan no puede alegar que ese mensaje no era suyo.

¿Ya está?. No, nunca. Supongamos que Antonio quiere suplantar a Juan y cifra el mensaje: "Hola soy Juan" con una clave privada suya (la de Juan no la conoce). Y en el momento en que yo accedía a un servidor de claves para conocer la clave pública de Juan (y descifrar el mensaje), Antonio intercepta la comunicación y me envía SU clave pareja: entonces yo pensaré que el mensaje ha sido firmado por Juan. Es necesario que existan Autoridades Certificadoras (AC). Estas sirven para garantizar que cierta clave pública corresponde a la de una entidad o persona. Para ello, tras comprobar la identidad del solicitante (y en los casos más serios se requiere la presencia física), la autoridad certificadora asocia en un documento la identidad de la persona con la clave pública y firma digitalmente con su clave -la de la AC- esa asociación.

Yo puedo exigir a Juan su firma digital obtenida de alguna AC de renombre. Por ejemplo, si quiero hacer la declaración de la renta por Internet se me exigirá una firma digital expedida por la administración. Cuando "Juan" contacte conmigo descifraré la firma digital con la clave pública de la AC (que se supone conocida) y obtendré la clave pública de Juan junto con sus datos personales. Y si alguien ha suplantado la clave pública de Juan de algún modo maligno la culpa es de la AC. Fácil, ¿no?.

La verdad es que me he extendido mucho en este post y me he dejado muchas cosas en el tintero. Es un tema muy interesante que se presta al pensamiento conspiranoico. Y es que cualquier comunicación mediante Internet, en algún punto de la misma, será insegura. Pero es lo que tiene la conspiranoia: nunca se puede acabar con ella: siempre puede dar un paso más e incluir a alguien más en la trama. Normal que algunas de estas teorías tengan tanto éxito, ¿no?

¹ Eso no significa que los algoritmos secretos de codificación no se sigan utilizando. Los ejércitos (en especial el de EE.UU.) los emplean. Es lo que se llama seguridad por ocultación.
² La empresa RSA patrocinaba el concurso de rotura, otorgando un premio de 10000 dólares. El primer equipo que lo consiguió tardó 4 meses en encontrar la clave. En 1988 Distributed.Net ganó el segundo desafío en 41 días. Este equipo volvería a ganar en 1999 en un tiempo de 22 horas y 15 minutos, habiendo probado 245000 millones de claves por segundo.

Redes de Computadores (James F. Kurose, Keith W. Ross). Ed. Adison-Wesley
Wikipedia: Criptografia, DES (criptografía simétrica), RSA (criptografía asimétrica).

Posts relacionados

CSI XI: Códigos que corrigen errores

2008-03-12T19:39:00.001+01:00

En este blog hemos hablado bastante de codificación de datos. Lo hicimos para hablar de cómo se transmitía la información para que las características del medio de transmisión no afectasen demasiado a la señal. Y más tarde os conté de qué manera se podía codificar la información para que ocupase mucho menos espacio. En este último caso nos parecía estupendo que la misma información pudiese ocupar menos espacio del que ocupaba. Hoy en cambio codificaremos para que la información ocupe más.

Siendo un poco ingenieriles: si ocupa más, tendrá mayor coste almacenar estos datos, así que, ¿qué ganamos al codificar la misma información con más bits?. Bien, pues en este caso en concreto, los bits añadidos nos servirán para saber si se produjo un error durante la transmisión de esta información. Y no sólo eso, sino que además nos permitirá recuperar la información original, esto es, reparar el fallo.

Hoy hablaremos de códigos detectores y correctores de errores.

Para ello necesitamos cierta base. Este tema se presta a una modelización matemática mediante operaciones con matrices y cosas de esas, pero nosotros no llegaremos tan lejos. Nos bastará con entender un concepto muy sencillo: el de distancia de Hamming ¹.

Empecemos: llamamos código a una representación de datos que sigue ciertas reglas para su construcción. Por ejemplo, cuando hablé de la codificación Huffman os conté el proceso o reglas para obtener el código asignado a cada símbolo. Obteníamos para cada uno una palabra codificada. Ésta, por supuesto, satisfacía las reglas de la codificación.

Aquí lo importante es ver que no todas la palabras posibles obedecen las reglas de la codificación. Dicho de otro modo: el conjunto de palabras codificadas es un subconjunto de todas las palabras posibles. Imaginemos que hemos diseñado nuestra codificación de modo que un error de un bit en la palabra provoque que la palabra resultante no pertenezca al conjunto de palabras codificadas. En ese caso, el receptor se dará cuenta de ello y asumirá que ha habido un error. Acabamos de detectar un fallo.

Pongamos el ejemplo más típico: códigos de paridad par. Contamos el número de unos de cada palabra y añadimos un bit a la misma: un 1 si el total de unos es par y un 0 en caso contrario. El receptor realizará el mismo proceso: si ha habido un error de un bit en la transmisión, entonces el bit de paridad no coincidirá con el recibido. Por supuesto, el invento se nos va al traste si hay dos errores en la transmisión. Pero, ¿a que es maravilloso poder detectar, añadiendo un simple bit, todos las inversiones (fallos) posibles de un bit?.

Vamos a poner una medida del número de fallos que puede detectar y corregir un código. Se define como distancia de Hamming el número de bits en que se diferencian dos palabras. Tan sencilo como eso: la distancia de Hamming entre 100110 y 101100 es 2, porque cambian dos bits de una a la otra. La distancia de Hamming de un código es la distancia de Hamming mínima entre dos palabras válidas del código distintas. El código de paridad par que hemos visto antes tiene una distancia de Hamming igual a 2. Porque la mínima distancia entre dos palabras distintas cualesquiera es 1 bit. Pero si hay un error que cambia un bit, entonces también el bit de paridad ha de ser distinto.

Bien, pues aquí no se demostrará, pero el tema (temazo) es que para que un código detecte errores de n bits, su distancia de Hamming debe ser mayor o igual a n+1. Y para que un código corrija errores de n bits, su distancia de Hamming debe ser mayor o igual a 2n+1. Y ya lo más: un código corrige hasta n_c errores y detecta n_a errores si cumple que su distancia de Hamming es mayor igual a 2n_c+n_a+1.

En el dibujo de al lado podemos ver el más simple de los ejemplos. En el primer dibujo vemos un código de paridad par. De las 8 palabras posibles, sólo 4 son válidas. Cada arista representa una distancia de Hamming entre palabras igual a 1. En el primer caso, la distancia de Hamming del código es 2. Si transmitimos un 000 y se produce un error de un bit, entonces alcanzaremos una palabra no válida en el código (puntos negros). En cambio los errores de dos bits (011, 110, 101) serán tomados como palabras válidas.

En el segundo caso las únicas palabras válidas del código son 000 y 111. La distancia de Hamming es entonces 3. Vemos como ahora se detectan errores de hasta dos bits (si damos dos saltos desde cualquier palabra válida llegamos a una no válida). Pero además, errores de 1 bit se 'corrigen' sustituyendo la palabra por la más cercana válida en el código. En cambio, errores de dos bits se corregirían incorrectamente.

Evidentemente, la expresión de Hamming nos indica que, cuanto mayor sea el código que añadamos a la información (1 bit en el primer ejemplo, 2 en el segundo), mayor cantidad de errores podremos detectar y corregir. Pero claro, esa información añadida consume ancho de banda y espacio: supone más dinero. El ingeniero debe alcanzar un compromiso entre el coste de añadir esa información y los beneficios que genera. Como siempre.

La generalización de estos códigos se emplea altamente, por ejemplo para detectar errores en memorias. Los códigos SEC de Hamming (Single Error Correcting) se utilizan para corregir un único error en la transmisión de datos. El que Hamming propuso era capaz de corregir el fallo de 1 bit en 4 bits de datos, empleando códigos de 3 bits. Para corregir un fallo en 8 bits de datos empleando SEC, necesitamos 4 bits añadidos. Para 16 bits, 5 de código...

Los códigos SEC de Hamming son muy sencillos de generar y muy eficientes. Por desgracia, tienen el problema de que cuando se producen más fallos de los tolerados, la corrección genera una palabra inválida y, en principio, no podemos saber si durante la transmisión se produce sólo uno o más fallos. Pero bueno... ¡ni siquiera Hamming era perfecto!

¹ Pongo el enlace a la Wikipedia en inglés, porque en castellano está bastante pobre e incluso mal. Veré si lo puedo cambiar.

Material de clase.
Wikipedia: Error detection and correction

Posts relacionados

Cuando el informático la pifia

2008-02-29T19:05:00.000+01:00

A veces los informáticos hacen mal las cosas. Bueno, todo el mundo, pero los fallos informáticos tiene un nosequé que los hace misteriosos. Un fallo informático siempre parece inexplicable, algo que no debería suceder. Pero ya sabemos que los fallos suceden. Un buen informático tiene que diseñar su aplicación de modo que esta sea lo más confiable posible. Esto incluye evitar que los fallos y errores se conviertan en averías: hace mucho tiempo ya hablamos de esto: se llama tolerancia a fallos.

Otras veces sencillamente, los errores son tan tontos que claman al cielo y merecen ser ocultados para salvar la vergüenza de sus responsable. O públicamente expuestos para su escarnio. Pues bien, en Risk han optado por esto último. A modo de foro se exponen casos de lo que se conoce como "cagadas". Algunos tontos, otros graves, pero siempre evidentes. No todos son informáticos. No todos son bugs. Pero todos son, al menos, curiosos.

La alarma de mi portátil funciona acorde con el tiempo local de Estados Unidos en vez de con el tiempo del Reino Unido (donde he viajado) sin que pueda cambiarlo. Esto sucede aunque cambie el tiempo local de mi portátil al del Reino Unido.

Una compañía de teléfonos de Taiwan ocultaba parte de los teléfonos en la correspondencia con los clientes. Por privacidad, en las misivas sólo se muestran los números pares del número de teléfono al que se da servicio 2*8*4*8*. Para mayor seguridad, también se ocultan los dígitos impares del número de contacto *5*5*7*0. Pero si resulta que éste coincide con el anterior, ¡entonces se está revelando todo el número!.

Un "0" se les cayó del precio de un PC vendido por Marubeni, una gran compañía de venta web. Antes de que se dieran cuenta del error, alrededor de 1000 personas compraron 1500 unidades. En vez de 198000 yenes (unas 198000 pesetas) se vendieron a 19800 yenes. Tras percatarse del error, la compañía trató de oponer resistencia al cumplimiento del acuerdo. Sin embargo, finalmente decidieron ceder para mantener la fidelidad de sus compradores.

Después de que junto la cartera me robaran la tarjeta de crédito (American Express), cancelé la misma y obtuve una nueva. Un mes después, habían sido cargados a mi cuenta dos gastos de American-On-Line que yo no había realizado.

Según AOL, dos cuentas se habían abierto a mi nombre y, cuando se intentó realizar algún gasto con ellas, AOL encontró que la tarjeta había sido cancelada. Sin embargo, ante estas situaciones, se consulta (automáticamente, claro) a American Express, cuya política es la de... ¡proporcionar el número de la nueva tarjeta!. Por cierto, las cuentas abiertas en AOL estaban a nombre de mi hija y de mi mujer. (Esto no es un bug: esto es una cabronada de AmEx)

Adam Abrams no podía crear una cuenta en un servidor. Recibía un mensaje de notificación "La razón por la que no puedes crear una cuenta es debido a que su dirección de correo ha sido marcada por nuestra tabla de palabras inadecuadas". Tras mucho investigar descubrió que no era "bra" (sujetador), el problema era "dam" (maldición).

Envié una carta de referencia a la Fundación Hertz recomendando a un estudiante. La Fundación requiere una firma electrónica en la recomendación. La firma constaba de una página web con un formulario donde se podía leer algo así como: "Certifico que soy la persona de abajo:" y un cuadro donde escribir el nombre.

En Nueva York murió una persona porque los servicios de emergencia no pudieron localizar su apartamento. El problema fue que vivía en en un edificio con una dirección de 5 dígitos, mientras que el sistema para enviar a los profesionales de los servicios de emergencia sólo admitía 4 dígitos.

El Ariane 5, cohete estrella de la Agencia Espacial Europea voló por los aires el 4 de Junio de 1996 a los pocos segundos de su despegue. Al parecer una conversión de un número de 64 bits en un entero de 16 resultó en un desbordamiento. Este entero controlaba la estabilidad del aparato, de modo que el cohete trató de rectificar su posición (correcta), inclinándose un poco. Cuando, error tras error, el cohete superó la inclinación de seguridad permitida, se autodestruyó. El error se había producido por una incorrecta adaptación del código (en Ada) que regía el Ariane 4.

A veces, por más que se hagan bien las cosas, la fatalidad está asegurada.

En el desarrollo de un avión bombardero se diseñaron tres esquemas de prueba independientes para evitar cierto efecto causado por la vibración de la cola del aparato (NOTA AL MARGEN: los aviones son tan seguros que llevan un retraso tecnológico de unos 15 años. Por seguridad, protocolos, planificadores, redes, tecnologías demasiado nuevas no se aplican a causa del temor a que fallen).

1. Un túnel de viento fue construido expresamente para investigar el efecto de estas vibraciones. El túnel se probó sobre un modelo a escala del avión.
2. Se hicieron test de resonancia sobre el primer prototipo, con los que se ajustaron ecuaciones aerodinámicas.
3. Se hicieron test en vuelo a baja velocidad, cuyos resultados se extrapolaron para analizar las vibraciones a alta velocidad.

Los tres tests condujeron a similares resultados y se concluyó que no había problema con el diseño de la cola para ninguna velocidad. Poco después, mientras el primer prototipo estaba realizando maniobras a alta velocidad y baja altura, la cola se rompió, estrellándose el avión y muriendo su tripulación. Acto seguido se inició una investigación, que concluyó con los siguientes resultados:

1. La rigidez de una parte del túnel de viento construido no era la adecuada.
2. Un término en las ecuaciones aerodinámicas era incorrecto.
3. Los ingenieros se equivocaron al interpretar los resultados de los tests a baja velocidad.

Y, debido a la mala fortuna, todos los resultados conducían a la misma errónea solución.

Y, a veces, las cosas se hacen demasiado bien.

El sistema de teléfono de emergencia 911 de las mayores ciudades de Minnesota fue convertido a digital. De este modo se introducían menores interferencias en la lineas. La gente, que estaba acostumbrada a escuchar el ruido de la linea al descolgar el teléfono¹ quedaba extrañada al no escuchar nada y pensaba que había un problema con su conexión.

¹ No en todos los lugares del mundo hay tonos

The RISK Digest. Forum On Risks To The Public In Computers And Related Systems

Posts relacionados

CSI X: cuando la cosas ocupan menos

2008-02-16T17:25:00.003+01:00

Recuerdo perfectamente una de las primeras clases de informática, allá en primero. Bueno, no, eso sería casi un milagro habida cuenta que no recuerdo qué comí ayer... Pero sí que recuerdo una frase pronunciada por un profesor, a modo de jocosa obviedad. "Dicen que 'el saber no ocupa lugar'... ¡No pollas!".

Y es que el saber, cualquier tipo de información, SÍ ocupa lugar. Y sea del tipo que sea, ese lugar tiene un coste o precio. El cerebro también tiene un coste, por más que algunos se empeñen en destrozarlo a base de etanol o mítines. Por ello siempre que podamos comprimir los datos, información o saber (y el coste de la compresión no supere al de sus beneficios, claro está) nos interesará hacerlo. De este modo saldremos ganando espacio. Pero... ¿pueden ocupar las cosas menos lugar de lo que ocupan?. ¿Cómo se realiza este milagro?

Pues eso, en Cosas que Sí se dan en Informática, hablaremos de compresión.

Utilizaremos a modo de ejemplo las letras. Supongamos que queremos comprimir un fichero de texto que tan sólo contiene caracteres de nuestro alfabeto (unos 25 caracteres), por simplificar. Sabido es que en Informática los computadores sólo entienden de unos y ceros (bits). Bien, normalmente se emplean 8 bits para codificar caracteres (codificación ASCII extendida). Con 8 unos y ceros podemos codificar 256 (2⁸) 'letras' distintas... pero si ya sabemos que nuestro fichero tiene tan sólo 25 letras distintas... ¿para qué queremos tantas?. Quitemos bits.

Para codificar 25 caracteres distintos necesitamos al menos 5 bits, ya que 2⁵ es 32. Por tanto, un fichero con 10 caracteres ocuparía 50 bits. Pero imaginemos que, de estos 10 caracteres, 4 son 'a's. ¿Ya que hay más 'a's, no ganaríamos espacio si codificamos las 'a's con unos pocos menos bits que el resto?.

Esa es la idea base de la codificación Huffman, desarrollada por el señor del mismo nombre en 1951. Aunque variantes de la misma codificación son más eficientes en determinadas circunstancias, Huffman encontró la forma óptima de mapear cualquier símbolo de una alfabeto con una secuencia de bits de longitud óptima. La idea es tan sencilla y elegante que bien merece la pena explicarla.

Partimos de una alfabeto y una cadena de letras. Supongamos que nuestra cadena es 'aavnvavfja'. Conociendo la cadena, podemos asociar a cada símbolo de nuestro alfabeto una cuenta de apariciones. Esto se llama histograma. Por tanto, tenemos que a --> 4, v --> 3, n --> 1, f --> 1, j --> 1. El resto de símbolos son ceros. Bien, pues ahora vamos a construir un arbol binario. Árbol porque es un árbol al revés. Binario, porque cada rama se separa en 2 ramas. Cogeremos los dos símbolos con menor número de apariciones y los agruparemos, sumando sus apariciones: 'fj' --> 2. Y volvemos a operar del mismo modo... y otra vez y otra... ¡hasta que la raíz del árbol agrupa todos los símbolos! (ver imagen).

Y ya está. Porque si asignamos un bit a cada rama del árbol, '0' para la izquierda '1' para la derecha, podemos obtener el código para cada símbolo sin más que andarnos por las ramas encadenando estos bits hasta llegar al carácter que deseamos codificar. Codifiquemos, pues, nuestra cadena 'aavnvavfja'.
001011010010111011110
Hemos utilizado 21 bits. De codificar cada símbolo con 8 bits habríamos gastado 80. 50 si sólo codificáramos con 5 (alfabeto de 25 letras). Y 30 si codificáramos cada símbolo de este alfabeto en particular {a, v, n, f, j} con 3 bits.

¿Está ya nuestra cadena comprimida?. Pues no. Porque además de comprimirla, queremos enviarla por correo, que le llegue a un amigo y que éste, sin tener ni idea de cual era la cadena original, poder descomprimirla y leerla. Para eso es necesario que nuestro amigo conozca, bien la tabla de códigos que hemos creado, bien el histograma de apariciones de la cadena original. Aunque el histograma puede ser muy grande si el alfabeto lo es, su tamaño será despreciable cuando consideremos cadenas de miles y miles de bits.
Con el histograma nuestro amigo (o el descompresor de nuestro amigo) puede construir el mismo árbol que hemos creado y decodificar la cadena. Para ello sólo tiene que 'andarse por las ramas' con los símbolos que le han llegado.

El primero es un 0. Se anda por la rama izquierda y llega a la 'a'. Ya tiene un símbolo. Otro 0: se anda por las ramas y consigue otra 'a'. Ahora un 1: rama derecha. 0, rama izquierda: ha encontrado una 'v'... y así hasta completar la cadena entera.

Y ya está: una cadena que tendría 8 bits por símbolo de codificarse ASCII se comprimiría hasta 2.1 bits por símbolo (21 bits, 10 símbolos). Bueno, no está, porque este tema tiene mucha tela por cortar. ¿Sabéis que se puede calcular el mínimo de bits por símbolo necesarios para representar una cadena?. Lo hizo Claude Shannon, padre de la teoría de a información, antes de que Huffman inventara este método. El mínimo número de bits con el que se puede codificar una cadena viene definido por la entropía de primer orden.

En nuestro caso, H = 2.046439. Así que nuestra codificación Huffman no está nada mal. Hay mejores codificadores que los de Huffman, ojo. Por ejemplo los codificadores aritméticos. Sin embargo, Huffman se sigue gastando mucho... más que nada porque estos últimos (que tampoco son tan complicados de entender) están sujetos a patentes por parte de compañías poderosas. Lo de las patentes de software también tiene tela. Porque en muchos casos es algo tan absurdo como patentar la forma de darle la vuelta a una tortilla. Y nadie que quiera dar la vuelta a una tortilla lo podrá hacer de ese modo (aunque se le ocurra a él sólo) sin arriesgarse a ser demandado.

Con Huffman, la secuencia que obtenemos tras la descompresión es idéntica a la original. Se llama compresión sin pérdidas. Pero en muchos casos podemos tolerar cierto grado de pérdidas, esto es, de calidad. Por ejemplo, el oído humano enmascara ciertas frecuencias por debajo de otras, de manera que al ir seguidas, no percibimos algunas de ellas. ¿Por qué almacenar esa información, pues?. Con esa idea funciona MP3. O, en dos fotogramas seguidos el fondo de la imagen apenas cambia, ya que el protagonista sólo mueve el pie... ¿por qué almacenar dos veces el mismo fondo estático?... con esa (y otras muchas) idea funcionan los compresores de vídeo.

A la compresión que se aprovecha de cómo percibimos nosotros la información se le llama compresión basada en la fuente. Suele tener pérdidas, pero son aceptables, y obtenemos cotas altísimas de compresión. Pero de ellas ya hablaremos otro día...

Apuntes de clase: ¡esto es básico!

Posts relacionados

CSI IX: Codificación de datos

2008-01-12T12:30:00.001+01:00

Una vez introdujimos qué era la codificación, en este post veremos algunas técnicas para codificar datos y señales digitales. Recordemos que una señal digital es una secuencia de niveles de tensión discretos: cada uno de ellos es un elemento de la señal. Las técnicas de codificación convierten cada bit de datos 0 o 1 en elementos de señal, buscando ciertas ventajas o características de la misma.

¿Qué es lo que buscamos cuando queremos transmitir?. Pues, de normal, que la velocidad de transmisión sea elevada y que el número de errores pequeño. Pero también que el medio que utilicemos sea barato. Por desgracia, todo a la vez es imposible: canales con mayor ancho de banda aumentarán la velocidad de transmisión y, si están bien apantallados podrán transmitir a grandes distancias sin apenas ruido... ¡pero eso es muy caro!. ¿De qué manera puede ayudar la forma de la señal?

(Un poco más de vocabulario). Una señal es unipolar si todos sus elementos tienen el mismo signo (tensión sólo positiva o solo negativa). Polar cuando no. A veces transmitimos los datos sobre dos lineas, de forma que el elemento se transmite como diferencia en la tensión de ambas. Así, un pico de tensión afectará al valor de las dos lineas, pero no a su resta: eso se llama transmisión diferencial. ¡Pero pasemos ya a ver de qué maneras codificamos!

No retorno cero - NRZ. Es la forma más sencilla de codificar: usamos un nivel de tensión para representar el 0 y otro distinto para el 1. Lo más normal es que se codifique de forma polar: un nivel negativo para el 1 y uno positivo para el 0 (NRZ-Level). Se llama no retorno cero porque la señal se mantiene constante al transmitir dos datos seguidos idénticos. Es decir: no retorna al cero.
Una variación de NRZ es NRZInvertida, que es una codificación diferencial: la señal se codifica atendiendo los elementos de señal adyacentes. NRZI, concretamente, codifica los 1s como cambios en el nivel de tensión de la señal. Los ceros se transmiten manteniendo la señal invariable. Una ventaja de NRZI respecto a NRZ es que, con NRZ, el receptor debe comparar la tensión recibida con un umbral para determinar cuáles son los 0s y 1s. Con NRZI, sólo debe monitorizar las transiciones, algo, en principio, más sencillo¹.

AMI-bipolar. AMI-bipolar es una técnica de codificación multinivel: utiliza más de dos niveles de tensión. Tres. AMIb codifica los 0 como ausencia de tensión y los 1 como niveles positivos y negativos, alternando en cada aparición de éste. Por eso AMI significa Alternate Mark Inversion. Esta codificación tiene una ventaja importante sobre las dos primeras y es que elimina la componente continua dc de la señal: la suma de los niveles de tensión da cero. Similar a AMI es MLT-3, que transmite los 1s como ciclos de -1, 0, +1, 0, transmitiendo los 0s manteniendo el nivel.

Por otro lado tiene un problema: la inserción de más niveles de tensión incrementan la necesidad de ancho de banda. El receptor tiene que distinguir entre tres niveles, y no dos, por tanto la señal tiene que tener "más espacio" si no queremos aumentar el número de confusiones. Es como si pongo un lápiz encima de una libreta y te pregunto si está a la derecha o a la izquierda. Es fácil responder sin equivocarte. Pero si te pregunto si está a la derecha, izquierda o en el medio, te lo estoy poniendo más difícil: cuanto más grande sea la libreta, más sencillo te resultará responder sin confundirte.

Todas las técnicas anteriores tienen otro problema muy importante que ya apunté. Es imposible tener el mismo reloj para decidir cuánto dura cada elemento de señal. A la larga, uno de los dos se atrasará lo suficiente como para que emisor y receptor no estén de acuerdo en el número de bits enviados, sobretodo si el nivel no cambia. La solución consiste en codificar un flanco como medida de sincronización. Y eso es lo que hacen...

Manchester. Lo que hace es, a mitad de un intervalo de bit, insertar una transición: un cambio de alto a bajo es un 0 y un 1 se codifica como flanco de subida². Manchester diferencial también hace siempre una transición a mitad del intervalo, pero no representa el dato: un 0 se transmite como una transición al inicio del bit y el 1 como ausencia de transición.

Lo bueno de estas codificaciones es que proporcionan sincronización: el transmisor está diciendo en la propia señal cuando cree él que toca la transición de mitad del intervalo. El receptor puede que piense que el primero está equivocado, pero si quiere entenderle, más le vale hacer caso de lo que dice el emisor y muestrear el valor del bit cuando toque. Además no tienen componente continua y proporciona cierta detección de errores si no se recibe la transición esperada. Por otro lado estamos gastando hasta 2 transiciones para enviar cada bit: es decir incrementamos la velocidad de modulación (numero de transiciones por segundo). La señal, por tanto, requiere un ancho de banda mayor... o transmitirse a menor velocidad.

Y eso es un problema si queremos redes de alta velocidad que sean baratas. Por eso se emplean más trucos ingeniosos. La tecnología es cara y los ingenieros baratos. Decíamos que AMI y NRZ daban problemas de sincronización con secuencias largas invariables. Pues lo que se hace es 'pasar' de los datos y transmitir lo que nos de la gana. Más o menos. B8ZS y HDB3 están basados en AMI y funcionan con tablas: cada secuencia de 8 y 4 bits (respectivamente) se reemplaza (consultando una tabla y teniendo en cuenta la última secuencia) por otra secuencia que contiene violaciones de código: códigos no permitidos por la codificación AMI, como dos niveles de tensión positiva seguidos. De esta manera introducimos transiciones que ayudan en la sincronización. Hay otros esquemas basados en tablas de sustitución, como 4B5B o 8B10B.

Hay maneras más sencillas de violar código. En NRZI podemos acordar que no permitiremos más de cinco ceros seguidos, por ejemplo. Y si encontramos una cadena con 5 ceros, cogemos y le endosamos un 1. El receptor, siempre que encuentre 5 ceros seguidos, sabe que el 1 siguiente lo he puesto yo, y entonces lo quita. Son lo que se llama bits de relleno.

Y con esto ya he puesto bastantes ejemplos. Si piensas que esto no vale para nada y tiene puesto un cable Ethernet en tu red local, te equivocas. Porque Ethernet a 100MB-TX utiliza un esquema 4B5B: sustituye secuencias de 4 bits por secuencias de 5, impidiendo cadenas de 1s o o 0s demasiado largas y luego lo codifica con MLT-3. Y si gastas USB, has de saber que utiliza transmisión diferencial a 1'5V y codifica utilizando NRZI con bits de relleno.

Bueno no, no has de saberlo. ¡Para eso están otros!.

¹ Hay otra ventaja y es que, gastando transmisión diferencial, las lineas pueden intercambiarse por error sin alterar el significado de la señal.
² En realidad, hay discusión acerca si debería ser al revés, tal y como sostiene Tanenbaum. Yo he seguido el criterio de Stallings, adoptado en Ethernet.

Apuntes de clase (¡tienen ya unos años!)
Wiquipedia (inglés): NRZ, AMI, MLT-3, Manchester, 4B5B.
USB in a Nutshell. Hardware

Posts relacionados

CSI VIII: Transmisión de datos

2007-12-24T12:50:00.000+01:00

Bien, con este post regresamos al fascinante mundo de la Cosas que Sí se dan en Informática. En capítulos anteriores vimos cómo podíamos transmitir datos sobre redes distintas (Internet). Y entonces comenté que los datos (0s y 1s) no son siempre lo que parecen, sino que se codifican de cierta forma buscando algunas propiedades.

En el post de hoy vamos a meternos un poco más en harina para dejar claro conceptos que a menudo se confunden. Con esa base teórica explicaremos algunas técnicas de codificación. Empezamos con términos. Dato es cualquier entidad capaz de transmitir información. Señal es la representación eléctrica o electromagnética de los datos. La señalización es el hecho de la propagación física de las señales a través del medio. Y lo que queremos es comunicar datos mediante su propagación y procesamiento de señales.
Bienvenidos al universo de la transmisión de datos.

Con ejemplos se ve más claro. La voz es el típico caso de dato analógico: toma valores continuos en el tiempo. Los datos digitales toman en cambio valores discretos (prefijados) en el tiempo. Un ejemplo claro son las cadenas de caracteres. Las señales analógicas son ondas electromagnéticas que varían continuamente y que pueden propagarse por medios guiados (un cable de teléfono) o no (el aire). Las señales digitales son secuencias de pulsos de tensión, transmitidos por un medio conductor, como el cable USB.

Entonces ¿los datos analógicos se transmiten mediante señales analógicas y viceversa?. Sí, pero no sólo. En un teléfono típico, la voz (que se mueven en una frecuencia entre 100Hz y 7kHz) se transmite mediante una señal analógica entre 300Hz y 3400Hz. Esto es más que suficiente, pues la mayor parte de la energía de la voz se concentra entre los 700Hz y menos de 2kHz. En el otro extremo el teléfono realiza el proceso inverso y la voz resultante es muy parecida... pero no igual.

¿Qué pasa cuando queremos enviar un fichero (datos digitales) a través de una linea de teléfono (transmisión analógica)?. Que necesitamos un modem: un aparato que modula los datos en una señal de cierta frecuencia portadora. ¿Y cuando necesitamos ciertos codecs para ver una peli en el ordenador? Pues que necesitamos algo que transforme señales digitales en datos analógicos y viceversa. Si no, no va.

Y falta lo más fácil: representar datos digitales mediante señales digitales. Eso es muy sencillo. Si tenemos un dato, por ejemplo un uno, lo representamos con un nivel alto de tensión. Y si tenemos un cero, con un nivel bajo o ausencia de tensión. Y listo. Bueno, sí, pero no se hace de este modo, sobretodo cuando queremos transmitir grandes cantidades de datos y a largas distancias. Es entonces cuando codificamos la señal.

En general, desde ya hace unos años, la transmisión digital se ha impuesto a la analógica. La razón primordial es que es más barato y sencillo lidiar con señales digitales. Las nuevas tecnologías (como fibra óptica) se abaratan y resulta factible tender dorsales a lo largo del océano para comunicar continentes. Se trabaja más fácilmente con señales digitales en la eliminación de ruido, mientras que es necesario aplicar filtros de frecuencias en amplificadores analógicos para evitar la transmisión de señales molestas. Asimismo, es más seguro aplicar técnicas de cifrado sobre datos originalmente digitales que analógicos.

Pero la transmisión digital tiene sus inconvenientes. Especialmente molesta es la atenuación de la señal. Ésta, a largas distancias, se deforma. La calidad del medio transmisor es un factor clave en este caso. Por otro lado existe lo que llamamos ruido, que no es más que la intromisión de señales no deseadas en la nuestra. En ocasiones un pico de intensidad de corriente puede provocar un salto en la señal. En transmisión de voz podríamos oírlo como un chasquido sin la menor importancia. En la señal digital puede provocar que un bit a cero en el origen se vea como un uno en el destino, provocando un error en el mensaje.

¿En qué cosas puede ayudar la codificación empleada?. Pues nos puede ayudar a bajar la frecuencia de señal. Las señales con ausencia de componentes de alta frecuencia se pueden transmitir por canales con menor ancho de banda¹. Además, es deseable que la señal no tenga componente de continua, esto es, que que la suma de sus tensiones (señales) se acerque a cero, ya que así se reducen las interferencias.

Pensemos en otro problema menos "físico". ¿Cómo sabemos lo que dura un elemento de la señal (por ejemplo un 1)?. Supongamos que somos el receptor y recibimos, durante un milisegundo, un nivel alto de tensión. ¿Cuántos unos hay ahí?. Vale que podemos ponernos de acuerdo con el receptor para decidir cuando dura... ¡pero el problema es que jamás tendremos el mismo reloj!. Imaginemos que cada uno dura 100ns. Si su reloj se adelanta medio ns respecto al mío, al cabo del microsegundo yo me creeré que he recibido 10 unos... ¡pero él me habrá enviado 15!. Bueno, pues la codificación también puede ayudar en este problema de sincronización.

La codificación también puede ayudar a detectar errores. ¿Qué cómo?. Pues imaginemos que, al codificar, añadamos un bit 0 si el número de 1s transmitidos es par y 1 si es impar. En ese caso el receptor cuenta los unos y, si la paridad no concuerda, sabe que ha existido un fallo². Claro, que si ha habido un número par de fallos, la cosa ya no funciona. Pero algo tan simple detecta gran número de fallos a bajo nivel, antes de que el software, más lento, se dé cuenta.

La codificación también sirve para minimizar el ruido. Ya veremos cómo. Y por último... hasta ahora hemos estado pensando en codificar UN bit de datos en UN elemento de tensión, pero, ¿y si decido tener no dos sino cuatro niveles de tensión?. Entonces podré codificar DOS bits en UN elemento. Con esta operación tan sencilla acabo de duplicar la capacidad de mi canal... y le he puesto mucho más difícil al receptor enterarse de lo que digo.

Y ya paro. Y en el siguiente post veremos algunas de estas técnicas maravillosas.

¹ No hay que confundir ancho de banda con la velocidad de transmisión, ojo, aunque estén relacionados (lo dijo Nyquist). Ancho de banda de un canal hace referencia a las frecuencias que "caben" en él. La velocidad de transmisión son los bits por segundo que se transmiten.
² Ver: bit de paridad

Mis apuntes de Redes. Tomados del famoso Stallings

Posts relacionados

Identificar personas: tarea de informático

2007-11-15T19:20:00.000+01:00

Los informáticos... ¿de qué trabajan?. O mejor aún, ¿para qué sirve un informático?. Más concretamente: ¿y un informático que ha estudiado Inteligencia Artificial?. ¿Cyborgs en España?. No me hagan reír, hombre. El caso es que el amigo Pinar, trabajar aún no, pero acaba de terminar la carrera (especialidad IA) con un interesante proyecto que demuestra cómo la informática se puede aplicar a muchos problemas sencillos en otros campos. Aquí, con su permiso, les cuento de qué va.

Los artículos son la base de la producción científica. Escritos normalmente por más de un investigador¹ suelen publicarse en revistas especializadas y congresos. En revistas importantes incluso se paga por publicar. A cambio, los autores ganan en prestigio o méritos académicos (consiguen un doctorado, por ejemplo). Los artículos se almacenan en bases de datos especializadas -algunas de pago- a través de las cuales se pueden consultar total o parcialmente. Podemos consultar el nombre de un autor, por ejemplo, pero... ¿¿¿quién es, en realidad, ese nombre???

Veamos otro problema parecido. Supongamos que tenemos dos artículos. Uno de ellos asociado a la Polytech Univ Valencia, Valencia y otro a Valencia Univ Technol, Valencia 46022. Vale es evidente que corresponden a la misma institución, evidente para un humano. Tenemos que tener a una persona encargada de revisar y comprobar que las distintas versiones de una institución se corresponden (o no) a una única institución. Este es un (aburrido) trabajo que se realiza de forma manual.

Pero más pesado y difícil es identificar el/los autores de un artículo. Porque los nombres no se presentan de forma estándar. Porque hay países (en general de habla hispana) en los que muchas personas tienen dos nombres y dos apellidos. Porque los nombres se transcriben a menudo con errores. Así que, por ejemplo, si tenemos dos artículos, uno firmado por J. Morno Pérez y otro firmado por Juan Moreno P. puede pasar:

Que ambos artículos sean escritos por el mismo investigador, llamado Juan Moreno Pérez. O que el primero haya sido escrito por el tal José Moreno Pérez y el segundo por otro señor, Juan Moreno Piqueras. O más difícil: pongamos que existe un tercer investigador llamado Javier Morno Pérez. En ese caso, ¿a quién corresponde el primer artículo, a José o a Javier?.

Los problemas, en general, son dos: la homonimia (personas con nombres parecidos) y la polisemia (variantes de un mismo nombre). Y es que el lenguaje natural es ambiguo. Si a eso le sumamos errores de transcripción, el problema de la desambigüación puede ser muy complejo. Estos dos problemas también se dan en el tratamiento del lenguaje natural y los nombres provienen de ahí.

Actualmente, aunque éste es un problema conocido, no existen soluciones universales. Podemos poner a un experto que se encargue, atendiendo al resto de información de la que dispone, de relacionar correctamente autores e investigadores para su clasificación. El problema es que cuando la cantidad de artículos es muy grande esta tarea conlleva una perdida de tiempo demasiado grande. El proyecto de Pinar tratará de automatizar un sistema para ofrecer una clasificación y (algo muy importante) una medida de la confianza que podemos tener en ella. De este modo al menos facilitaremos la tarea del experto.

El trabajo de Pinar parte de que ya tenemos cierta información acerca de investigadores, independiente de la de los artículos. En concreto disponemos de información institucional acerca de investigadores que solicitaron la realización de un proyecto y en qué lugar (institución). Atendiendo a esos datos, el trabajo consistiría en clasificar la producción científica -artículos- referida a ese área de estudio durante un periodo de unos 15 años y determinar qué autores de estos artículos se corresponden con los investigadores que aparecen en la base de datos que tenemos. Concretamente se recopilaron más de 20.000 artículos, escritos por más de 75.000 autores.

A obtener nueva información a partir de relaciones no explícitas entre diversas bases de datos se le llama minería de datos y supone añadir una capa de inteligencia a partir de simples datos.

La idea básica es que si un artículo ha sido escrito por un investigador, entonces la información que tenemos del autor y artículo se parece más a la información que tenemos sobre ese investigador que no a la otro. Ahora hay que pasar esta idea a términos matemáticos para poder aplicar un algoritmo. Esa es la parte difícil que en este blog no aparecerá.

A grosso modo: se compara la similitud entre los nombres de los investigadores y los nombres de los autores del artículo. Para ello existen algoritmos muy conocidos para comparar cadenas, que nos dan una distancia o medida de lo que se parecen (ej: distancia de Levenshtein). Lo siguiente que podemos comparar es el título del artículo con el título del proyecto que figura en nuestra base de datos original. También podemos medir cuánto se parece el lugar de trabajo del investigador con el lugar de trabajo de los autores del artículo. Y mucho más: distancia en tiempo de la fecha de aprobación del proyecto con la fecha de publicación del artículo, o similitud con artículos ya asignados: si ya sabemos que tal investigador escribió un artículo, es probable que sea el autor de un segundo artículo parecido.

Una vez decidimos qué parecidos son importantes (y cuánto, asignándoles un coeficiente), sólo nos queda seleccionar un algoritmo de clasificación: estos sirven para clasificar un conjunto de datos en clases. Es como poner una etiqueta a cada dato. En nuestro caso, pondremos una etiqueta a cada artículo con el nombre del investigador. Algunos algoritmos requieren que un subconjunto de datos estén ya correctamente clasificados (se llaman aprendizaje supervisado) y otros no. Nos quedaremos con el algoritmo que mejor clasifique. El tiempo que tarde en hacerlo nos da relativamente igual.

Pues eso ha estado estudiando Pinar. Y lo debe haber hecho bien, porque está escribiendo algún artículo sobre el tema. Esperemos que su nombre se publique sin errores y todos sepamos que lo ha escrito él mismo.

Pinar dice: "seguro que ponen 'Piñar', como en mi título de inglés".

¹ En realidad lo escribe uno sólo y todos los doctores por encima del mismo ponen su firma. ;-)

Artículo revisado y con el visto bueno del Rincón de Pinar!

CSI VII: Cómo funciona Internet (II)

2007-10-12T08:49:00.001+02:00

No tenía pensado escribir una segunda parte de este tema. Me parecía que ya había quedado más o menos claro el funcionamiento de Internet en el anterior post. Craso error. No queda nada claro, excepto para mí, que ya lo entiendo. A alguien que lo está leyendo le parecerá que ni siquiera tiene nada que ver con Internet. Por eso en este segundo post me propongo explicar qué es lo que quería decir con un sencillo ejemplo, tomado de la vida misma. Es decir, nada de metáforas.

En el anterior post lo que quería explicar es que, para comunicarnos entre distintas redes (como Internet) necesitamos información de nuestra red. En especial dónde hay un dispositivo encaminador que conozca otras redes (router), información acerca de la dirección destino (dirección IP), unas reglas sobre cómo se producirá la comunicación (que llamamos transporte) y un lenguaje común a ambos para entender qué deseamos del otro: a esto se le llama protocolo de aplicación. Estructuramos esta información en capas, de manera que, si cambiamos una de ellas, no tenemos porqué cambiar las que están por debajo o por encima. Veamos cómo queda.

Uno de los protocolos de aplicación más útiles, usados y conocidos es DNS (Domain Name System). Aunque DNS puede servir para más cosas, su función principal en Internet es proporcionar las direcciones IP de los nombres de equipo. Por ejemplo, tomemos el nombre de equipo google.es al que accedemos desde España. Pero ya sabemos que en Internet los equipos se identifican con números, direcciones IP. La traducción de este nombre, sencillo de recordar, a dirección IP la realizan los servidores DNS. En este caso, la dirección IP es 72.14.207.191 (aunque lo más seguro es que haya más de una IP para este nombre).

DNS da para muchos posts. Diremos sólo que el servicio funciona de forma jerárquica. Probablemente tendremos un servidor DNS cercano y a éste irán nuestras preguntas del tipo "¿qué dirección IP tiene www.talmaquina.com?". Si nuestro servidor cercano lo sabe, perfecto. Pero si no, él tiene un servidor DNS por encima y le pregunta a éste. "¿Oye, tú sabes qué dirección IP tiene www.talmaquina.com?". Si ese servidor no lo sabe, contestará algo así como: "No, ni idea, pero pregunta a 'Otro servidor' que sabe más'". ¡Lo típico cuando preguntamos direcciones!. Y así va preguntando hacia arriba. Y arriba de todo están los super-servidores DNS de primer nivel, de los cuales hay 13 distribuidos geográficamente de forma equitativa: 7 en EE.UU. y el resto desperdigados.

Volvamos a lo nuestro, supongamos que yo tecleo el nombre de una dirección web en mi navegador: www.dimequenoexiste.com. ¿Qué es lo que pasará? Que mi navegador tratará de averiguar cuál es la dirección de la máquina con ese dominio para contactar con ella y pedirle una página html, típicamente. Para eso, efectuará una petición DNS.

La petición que quiero mandar al servidor DNS es: "¿qué dirección IP tiene www.dimequenoexiste.com?". Esa pregunta la codifico según el protocolo DNS. DNS, por otro lado, funciona sobre el protocolo de transporte UDP. Recordemos que los protocolos de transporte servían para añadir cierta coherencia al lío de la fragmentación de paquetes que se producía al gastar IP, y al hecho de que podían llegar desordenados o perderse. UDP no ofrece tanta garantía como TCP, es más sencillo: apenas añade información del número de puerto para identificar el servicio (ahora DNS). Metemos la información DNS dentro del paquete UDP. Toda esa información la meteremos en un paquete IP, para que viaje por Internet. Como yo me conecto a Internet gracias a una red Ethernet, tendré que meter el paquete IP dentro de una trama Ethernet. El controlador de Ethernet (que está en la tarjeta de red) se encarga de codificar esos unos y ceros de la mejor manera para transmitirlos.

En total, 5. 5 niveles, que fueron los explicados en el anterior post. En la imagen vemos como se forma cada paquete y se mete en el del nivel inferior. Al navegador que gastamos, por ejemplo, la información acerca de las direcciones Ethernet utilizadas le importa un pimiento. De ahí que podamos hacer navegadores sin preocuparnos de esta cuestión.

Una vez hecha la pregunta, el servidor nos contestará gastando el mismo protocolo DNS. En la segunda imagen podemos ver la respuesta¹. Podemos identificar los distintos paquetes de información de la respuesta. Arriba Ethernet, luego IP, luego UDP y luego DNS. Abajo vemos todos los bits del mensaje, en forma hexadecimal.

Nos podemos fijar, por ejemplo, en que la parte Ethernet hay un identificador que nos dice que el mensaje que contiene es IP (Type 0x0800). Asimismo, en el mensaje IP vemos que hay un identificador que nos dice que el mensaje que transporta es de tipo UDP (Protocol UDP: 0x11). Y que en el mensaje UDP, el puerto de origen 53 identifica el servicio que lo envía: DNS. La respuesta proporcionada por DNS es clara: No such name: ese nombre solicitado, www.dimequenoexiste.com, no existe.

Si hubiese pedido una página html a un servidor HTTP, sería muy parecido. Pero gastaría TCP en vez de UDP, ya que hay que manejar mayor intercambio de información y es necesaria cierta coherencia en la comunicación. Y por encima de TCP gastaría HTTP. Pero el formato por debajo no cambiaría.

Pues más o menos así funciona Internet (o así nos dicen que funciona). En general, el servicio proporcionado por los protocolos de transporte TCP o UDP se queda demasiado corto para aplicaciones, cada vez más usadas, de vídeo bajo demanda, televisión por Internet, videoconferencias... y es necesario ingeniar otros protocolos.

Hasta IP se está quedando limitada. La nueva versión IPv6 permite no sólo más direcciones en el mundo (las actuales se habrían acabado de no ser por ciertos trucos que hemos inventado) sino también permiten un sistema de prioridades y hasta soporte para reserva de ancho de banda. Es decir, identificar la importancia de la comunicación y darle un canal dedicado para mejorar la calidad de servicio. Pero poco a poco. Si ni siquiera esto nos lo enseñan en la carrera de Informática a todos los alumnos (depende de las intensificaciones), ¡menos aún voy a empezar por ahí en este blog!

¹ He ocultado información acerca de las direcciones Ethernet e IP. No porque desconfíe de los lectores del blog. Es que hay mucha gente rara suelta en Internet.

Enlaces del texto
Captura realizada con Ethereal, un conocido analizador de paquetes.

Posts relacionados

CSI VI: Cómo funciona Internet

2007-09-27T19:42:00.000+02:00

Vale, venga: hagamos una pregunta inocente: ¿cómo funciona Internet?. Por suerte, esta sí es una de las cosas que se estudian en Informática. Pero la pregunta no es tan sencillita, no. Primero: ¿qué significa Internet?. Según la Wikipedia:

Internet es un método de interconexión descentralizada de redes de computadoras implementado en un conjunto de protocolos denominado TCP/IP y garantiza que redes físicas heterogéneas funcionen como una red lógica única, de alcance mundial.

Aquí hay jerga de esa que tanto nos gusta. Este párrafo quiere decir más o menos que Internet sirve para comunicar distintos dispositivos con otros ordenadores. Descentralizado hace referencia a que no existe un supercomputador gigantesco en Arizona haciéndolo funcionar. Implementado en un conjunto de protocolos nos dice simplemente que utilizamos ciertas formas de comunicarnos para entendernos unos a otros. Y garantiza que blablabla significa que los usuarios no tienen por qué conocer de qué manera se transmite la información. Eso para los Telecos.

Así que vayámonos haciendo a la idea. Internet no es la WWW. Internet no es el eMule. Internet no es Youtube. Internet no es la causa del bajo nivel del cine español, ni del cierre de los videoclubs, ni de que los niños no lean. Y por supuesto, no tiene nada que ver con el porno, por más que Tom Cruise quiera. Otra cosa es que se vea porno a través de Internet

Vale. Tenemos la vaga idea de que Internet es un canal para comunicar información a través de una o muchas redes, sean del tipo que sean. Pero ¿cómo funciona?. Pues a ver: hagamos una prueba y construyamos Internet. Supongamos que Aitor le quiere pedir a Bartolo una foto. Como le han dicho en PC City que los cables Ethernet sirven para transportar datos le tira una punta del cable a Bartolo (B). Pero no nos sirve gritarle al cable. De alguna manera hemos de codificar el "quiero una foto" para transportar la petición por el cable. Cuidado. No me refiero a transformar las palabras "quiero una foto" en secuencias de 0s y 1s. Eso también se hace y para ello hay tablas (ASCII es la mas conocida). Me refiero a que esos ceros y unos se codifican luego para enviarlos de cierta forma. Y con ciertos niveles de tensión. O transformándolos en ondas de cierta manera.

Maneras de codificar/transformar/modular la información hay muchas. Dependen, fundamentalmente del medio a través del cual vayamos a enviarla. Y de lo que queramos hacer con ella. Por eso se definen muchas maneras de hacerlo según el nivel físico por donde se va a enviar.

Vale. Ahora imaginemos que B se dedica a repartir fotos. Y que todos los Colegas de la oficina estamos conectados al mismo cable y pedimos fotos a B. A B le llegan mensajes del tipo "quiero una foto", pero... ¿Cómo sabe B quién le ha pedido una foto?. Pues añadimos información de quién somos y a quién pedimos algo. Porque al estar todos conectados al mismo cable, ¡los mensajes los recibimos todos!. Hace falta indicar no sólo qué queremos, sino quiénes somos y a quién se lo pedimos. De este modo sabremos cuándo las respuestas o peticiones son para nosotros. Esta información que se añade no tiene nada que ver con la información que se podía añadir en la codificación. Esto es importante notarlo porque...

Supongamos que en vez de un cable quiero transmitir la información de otra manera. A través de Wi-Fi, (para no gastar cables, por ejemplo). La información será de otro tipo (ondas electro-magnéticas)... y por tanto deberé codificar la información de la mejor manera para ese tipo de transmisión. Pero ¿por qué debería cambiar la manera que tenemos de identificarnos?. Mantendremos independientes esos dos niveles.

A esa idea tan buena y tan tonta se le llama estructurar en forma de pila. Internet funciona en forma de pila de protocolos: hay partes de la comunicación (niveles) que tienen unas tareas específicas. Puedo idear muchas maneras adecuadas de realizar esas tareas... pero no es necesario cambiar el resto de "niveles". Constituye así una arquitectura flexible.

Demos un paso más. Supongamos que queremos ofrecer ciertos servicios a otra oficina. Que ellos también quieren fotos. El problema es que ellos no tienen nombres como los nuestros (A, B, C): se llaman con números (1, 2, 3). Y... ¿le importa a B cómo se llamen ellos? Pues no. ¿Y si gastan telepatía para transmitirse entre ellos las imágenes? Tampoco nos importa. Lo único necesario es que existan unos nombres comunes a todos nosotros: de este modo alguien de la otra oficina puede hacer una petición a B incluyendo su supernombre y B sabrá a quién tiene que contestar.

Para encaminar bien los mensajes hacia otras oficinas existen unos elementos: se llaman routers. Un router debe encontrar al destinatario de un mensaje en la red donde opera. Y si no lo encuentra, redirigir ese mensaje a otro que quizá lo sepa. Un router opera en el nivel de red. Este nivel es el que es la clave de Internet. Las direcciones comunes a todos se llaman direcciones IP. IP significa Internet Protocol, en un dechado de imaginación.

Entonces hagamos un repaso: transformamos la información de cierta manera, añadimos información para encontrarnos dentro de una red, le sumamos información para transmitirlo a otras redes. Además, en cada nivel añadimos más cosas. Por ejemplo para controlar que no ha habido ningún error en el envío. O para dar pistas sobre lo que contiene el mensaje, o el tipo de red desde donde se envía... en fin: un montón de cosas. Pero resumiendo: llevamos tres niveles. Y se llaman nivel físico, nivel de enlace y nivel de red.

Pero hay más. Resulta que en Internet no se envían los datos todos juntitos. Se envían por paquetes. De este modo podemos aprovechar mucho más toda la amplitud de la red. Unos paquetes de un mensaje se intercalan con los de otro. Cada paquete se busca la vida para llegar a su destino. ¿Qué es lo que pasa con este modelo?. Pues que cuando nos salimos de nuestra red o cable podemos tener problemas. A veces se pueden perder fragmentos, o llegar desordenados, o que algunos lleguen corruptos...

Para controlar un poco todo este lío se añade un nivel o capa más: la capa contiene cierta información acerca de la comunicación que mantienen dos equipos. A esta capa se le llama de transporte. De este modo podemos proporcionar control de flujo, que no es más que cierta coherencia en la transmisión de la información. Podemos utilizar protocolos que garanticen mayor o menor control sobre la comunicación. En Internet se gasta un protocolo llamado TCP (Transmit Control Protocol). De ahí la definición anterior de la Wikipedia.

¡Pero aún no hemos terminado! Supongamos que B ofrece muchos servicios, además de enviar fotos. Supongamos que, encima, te dice la hora, repite lo que dices o cada día te cita una frase famosa¹. Pues le pondremos un identificador a cada uno. Los servicios más conocidos tienen un identificador / número de puerto bien conocido (por todos). Además, cada servicio o aplicación requiere de un protocolo de transporte u otro, según la necesidad de control sobre la transmisión que precise. Lo que se hace es añadir el identificador del servicio junto con la información de la capa de transporte. Y luego añadimos la información referida únicamente al servicio.

Esta última capa se llama de aplicación. En Internet, el protocolo más conocido en esta capa es HTTP. HTTP definía básicamente una manera de transmitir letras y la manera en que queremos que un programa navegante las muestre. El resultado son las páginas html. Como la que vemos.

Resumen, tenemos 5 niveles: físico, enlace, red, transporte y aplicación. Cada nivel añade información al siguiente, empezando desde el de aplicación. Añade la información que aquí he contado... y mucha más. Y la comunicación es muuuucho más compleja. Pero qué mas quieren. Si pudiese contar cómo funciona Internet en un post... debería preguntarme dónde fue a parar el dinero que invertí en la carrera.

¹ Todos estos servicios existen y son bien-conocidos

Para saber de verdad cómo va esto: Wikipedia

Posts relacionados

Seguir leyendo (2º bobo-tutorial)

2007-09-02T12:10:00.001+02:00

Como verán, he estado trasteando los últimos días con el template del blog. Para tener una sección con las referencias, pies de página, con su propio estilo. Y luego para conseguir un cuadro desplegable en el que ubicar los posts relacionados a cada artículo. Como salió, me sentí fuerte, poderoso e informático y decidí conseguir que la página principal del blog mostrase sólo el inicio de los posts, junto con una enlace "Seguir leyendo" al post completo.

Lo he conseguido. Pero el mérito no es mío, ya que al final copié. De Hackosphere, para ser más exactos, que es un blog de donde puedo aprender bastante para ir jugando. Como no tiene mucho sentido que yo vuelva a explicar el procedimiento que ya explica el autor del "truco" (aunque luego veremos que algo de sentido sí tiene), casi mejor explico por qué funciona y qué es lo que intenté hacer yo. Así de paso comento un poco lo que he aprendido.

Vale. Lo primero que hice fue bajar la página principal de mi blog y el template. Quería comparar la estructura de la página con el template. Sabiendo qué tendría que cambiar en la página .html para conseguir mis objetivos podría identificar en qué lugar del template debía realizar los cambios. Fácil y sencillo si cuentas con un editor de HTML (Dreamweaver, por ejemplo).

Encontré que todos los posts de la página principal se ubicaban en unas "divisiones" del texto, llamadas post-body. Los contenedores básicos de HTML se marcan con la etiqueta <div>. Al buscar post-body en el template encontré una única linea: la que buscaba.

Esto ya es el pie, donde pone el autor, hora...

Entendía poco, pero lo suficiente para saber que data:post.body es información que guarda Blogger y hace referencia al contenido completo de post. Bueno, lo primero que hice fue añadir una sección bajo el post (que incluiría la referencia al post entero), aunque ésta sólo debía aparecer en la página principal y no en el resto. ¿Cómo se hace eso?. Pues de la misma manera que se hace con los comentarios. Tiene que haber una condición antes de los comentarios que indique si estamos o no en la página principal. La encontré, y, añadiendo la información de la referencia a la entrada (que aparece en todo título de Blogger Beta), la cosa quedó así:

<b:if cond='data:blog.pageType != "item"'>
<A expr:href='data:post.url'>Ver el resto de la entrada</A>
</b:if>

Lo siguiente era conseguir: a) limitar la información que Blogger enviaba a la página o b) limitar el tamaño del párrafo y ocultar la información de sobra. Como de la a) no tenía ni repajolera idea, intenté la b. Lo único que se me ocurrió fue "tapar" esa información con las siguientes secciones, poniéndolas "encima" (para eso está el atributo z-index de las hojas de estilo). De todos modos parte de los post tenían que ser tapados por los siguientes post con partes visibles... y otras ocultas, así que la cosa no tenía solución. No encontré nada en HTML ni en las hojas de estilo que me ayudara.

Y es que la solución venía a través de funciones Javascript, según me enteré al leer el post de Hackosphere, que invitaba a copiar al template esto. Las funciones Javascript son funciones en un sencillo lenguaje de programación desde las que se puede hacer referencia a elementos del documento HTML. Como programación "normal" pero gastando los identificadores de los elementos HTML para utilizarlos como variables.

Para nuestro caso, lo que queremos es que una parte del documento quede visible en ciertas circunstancias. Para ello deberemos dividir los posts en dos "partes". Esta era la clave, en la que no había pensado (pese haber hecho algo parecido para mostrar y ocultar los posts relacionados). Las partes en que dividiremos el post serán estas:

Aquí va la entradilla
<span id="fullpost" >A partir de aquí va el resto del código<span>

Como se ve, hemos gastado el elemento <span> y hemos identificado el resto del código, llamándolo fulltext (aunque sería más apropiado llamarle restoftext). Lo que haremos ahora es ocultar esta parte en la página principal. Eso se hace modificando, desde el template el propio código de la página, cosa que yo tampoco sabía que se podía hacer. Pongo el código y explico qué es cada cosa:

/*aquí añadimos un identificador del post a la sección*/
<div class='post-body' expr:id='"post-" + data:post.id'>
/*Si no se trata de la página principal...*/
<b:if cond='data:blog.pageType == "item"'>
/*la sección fullpost del documento se mostrará inline*/
<style>#fullpost{display:inline;}</style>
/*Este es el artículo*/
<p><data:post.body/></p>
/*Si estamos en la página principal...*/
<b:else/>
/*la sección fullpost no se mostrará...*/
<style>#fullpost{display:none;}</style>
/*...pero el post sigue estando ahí, enterito!*/
<p><data:post.body/></p>
/*Este es el link al artículo completo*/
<span id='showlink' style='font-size:80%;'>
<a expr:href='data:post.url'>Seguir leyendo </a>
</span>
/*Y esta es la función que no muestra el enlace si el post no tiene fulltext*/
<script type='text/javascript'>
checkFull("post-" + "<data:post.id/>");
</script>
</b:if>

Y ya está. Y si alguien, por casualidad, se ha molestado en leer el post de donde sale el truco, se preguntará (con toda la razón del mundo): ¿y para qué leches valen las funciones Javascript hideFull y showFull?. Pues para nada, al menos en mi blog. En realidad sirven para mostrar y ocultar el texto entero del post en la página principal. Y como eso no era lo que quería, no he copiado estas funciones a mi template. Me juego un pie que más de uno las tiene en su blog, cargándolas cada vez que visita la página principal sin gastarlas. Hay un errorcillo, y es que al visitar las entradas anteriores en la página principal (que no tienen entradilla y fulltext) sigue apareciendo el enlace a la entrada completa, pero tampoco me preocupa demasiado.

De todos modos, aunque me habría gustado hacer todo este proceso yo sólo, también es importante haber aprendido más cosas. Ahora que entiendo cómo funciona un poco todo este tema podré trastear un poco más con Blogger, al cual le estoy cogiendo cariño.

CSS Reference. Lista de atributos CSS.
XHTML Reference. Para saber qué es lo que compone las páginas.
Guía breve de XHTML. En castellano.

Posts relacionados

CSI V: Evolución de los SO (II)

2007-08-25T10:07:00.000+02:00

En el capítulo anterior... la II Guerra Mundial impulsó toda una serie de nuevas tecnologías y dio un notable empujón a la ciencia de la computación. A finales de los años 70 ya existían sistemas capaces de compartir los recursos físicos de las máquinas de cómputo a varios procesos en ejecución, para los cuales se empezaban a crear cada vez más sofisticados lenguajes de programación. Cada proceso actuaba como si fuese el único que se estaba ejecutando y el intercambio de procesos era tan rápido que permitía al usuario interaccionar con el sistema.

Y no sólo eso, el tiempo compartido abrió la posibilidad a que varios usuarios pudiesen ejecutar sus programas sobre la misma máquina. Hasta entonces sólo un usuario podía interactuar con ella, sentado frente a un terminal. Con la opción de multiusuario se extendían las posibilidades.

Todo esto conllevaba grandes retos: como los programas se almacenaban en disco, es necesario una gestión de memoria de modo que se puedan traer procesos de dondequiera que estén almacenados a la memoria principal que gasta el procesador. La solución consistió en crear jerarquías de memoria, donde las más pequeñas son las más rápidas y están más cerca del procesador. Las técnicas que se emplearon crearon el concepto de memoria virtual. La memoria virtual permite, en esencia, que el programa sea más grande que la memoria física.

Como los programas escribían sus resultados en disco en vez de directamente en impresora o cinta, era necesario inventar alguna gestión de archivos. Los sistemas de archivos se encargaron de organizar e indexar todos los distintos archivos que estaban en en los discos. Y, si hay varios discos, ¡también tiene que encargarse de mantener y ofrecer una visión coherente por encima de estos!.

Y como hay muchos trabajos o tareas que se ejecutan "a la vez" entonces tenemos que incluir un sistema de gestión de tareas. Porque aunque cada una piense que ella es la única, muchas veces requiere de los resultados de otra. De quién le da igual; de eso se tienen que ocupar los esquemas de planificación de la CPU. Ordenar la ejecución de muchas tareas estableciendo un orden y una asignación de recursos tal que no se produzcan interbloqueos es otra de las muchas tareas del sistema operativo moderno. Todas estas funciones son complejas de realizar, pero muy fáciles de explicar y algún día las veremos.

Pero volvamos a la historia, que aún no ha terminado. Porque hasta ahora no hemos hablado del trasto que tenemos junto a nosotros, al cual llamamos PC¹ (o pasokon si por casualidad hablamos japonés).

Aquí hay dos caminos distintos. Por una lado la evolución de lo que es la propia máquina. En ese sentido podemos decir que los computadores personales descienden de las calculadoras. La historia de la creación de los PC es muy entretenida por ese camino: hay bancarrotas, ladrones de ideas, oportunistas, genios de las computadoras y genios de las promociones. Algún día la contaré, aunque no se estudia directamente en la carrera.

Por otro lado está la evolución del sistema operativo. Los sistemas operativos de los PC no eran multiusuario ni multitarea cuando nacieron. El bajo coste del hardware no urgía de un aprovechamiento exhaustivo de éste y su reducido tamaño justificaba el uso de un sólo usuario. Algunas de las características de sistemas grandes no se aplicaron a los computadores personales. Por ejemplo, en principio se pensó que no era necesario un sistema de protección de archivos en computadores personales. Los virus chungos (que los informáticos llamamos programas maliciosos) demostraron lo contrario.

Pero otras muchas características de los macrocomputadores sí fueron utilizadas para gestionar PCs. El ejemplo más claro de esto es el sistema operativo MULTICS, desarrollado entre 1965 y 1970 en el MIT, que se ejecutaba en un monstruo (GE 645). Muchas de las ideas fueron tomadas de MULTICS cuando Dennis Ritchie y Ken Thompson desarrollaron UNIX para un "mini" computador PDP. A lo largo de los años 80 UNIX incorporó mecanismos de seguridad, multitarea y multiusuario que han sido tomados por muchos sistemas posteriores. Hay más de 100 sistemas operativos basados en UNIX en los últimos 20 años.

Por otro lado, IBM modernizó su primer sistema operativo para PCs, MS-DOS, y creó OS/2, lo que terminó en una crónica de un fracaso en la lucha contra Microsoft. OS/2 incorporaba ya multitarea. Microsoft, que mantuvo los derechos sobre su código para el primer PC de IBM, realizó su carrera en solitario en los 80. Tanto Windows 1.0 como 2.0 eran poco más que aplicaciones corriendo sobre MS-DOS, permitiendo, eso sí, la multitarea (MS-DOS no era multitarea ni multiusuario). Windows 3.0 ya incorporó gestión de memoria virtual. Hoy en día Windows acapara cerca del 90% de sistemas operativos del mundo.

Otro tipo de sistemas

Pero no nos perdamos. Los sistemas operativos están para más cosas que para bajarse música. Los hay que tienen que gestionar cálculos extremadamente grandes. Una solución consiste en utilizar muchos procesadores juntos. Un sistema con muchos procesadores incrementa sus prestaciones, pero requiere de una gestión mucho más compleja. A veces los sistemas paralelos comparten memoria u otros periféricos. A veces no. Hay que gestionar con cuidado las escrituras y lecturas de memoria cuando hay varios procesadores que las gastan porque, por ejemplo, podríamos leer una copia de un dato que actualmente está siendo modificado por otro procesador.

A veces hay muchos ordenadores distantes, cada uno con sus cosillas, ejecutando una tarea conjunta. A esto se le llama sistemas distribuidos. Los sistemas distribuidos suelen tener un sistema operativo "normal", pero por encima de él hay una capa de servicios relacionados con la gestión del sistema distribuido.

Otras veces es necesario imponer serias restricciones al tiempo en que deben ejecutarse ciertas tareas, como en entornos industriales. Para esto existen sistemas de tiempo real. A veces nos interesa que los errores que se puedan producir no detengan el sistema, sino que lo degraden de forma aceptable: buscamos sistemas tolerantes a fallos. En fin, las distintas necesidades determinan el tipo sistema que gastaremos.

Y yo no necesito más que Windows ~~pirateado~~. Y por eso gasto Windows. Queda pues, contestada la pregunta que me hacía yo mismo.

¹ Jamás entenderé por qué la RAE acepta cederrón y no pecé

Sistemas Operativos. Addison Wesley Longman. ISBN 0-201-59113-8

Posts relacionados

CSI IV: Evolución de los SO

2007-08-10T21:20:00.000+02:00

Yo gasto Windows. Uf, ¡que vergüenza para un informático!, ¿no?. Se supone que debería saber gastar alguno tipo UNIX, de código libre, haber añadido un par de llamadas al sistema y compilarlo... Pues no, no sé, por más que se haga en la carrera. Y gasto Windows porque... porque... porque aceptamos Windows como sistema operativo.

Y de eso va el tema de hoy en Cosas que SÍ se enseñan en Informática: qué es y para qué sirve un SO. Y lo haremos a través de su historia.

Un Sistema Operativo es aquello que da sentido al cacharro lleno de cables, tarjetas y discos que tenemos como ordenador. Sabemos que tenemos una CPU dentro, un monitor, un ratón, uno o varios discos duros, lector de DVDs... un montón de cosas que se llaman Hardware. Sabemos que tenemos la mula descargando Pitch Black (yo no), el reproductor sonando, la sesión del hermano abierta... un montón de cosas que llamamos Software. ¿Quién se encarga de repartir los recursos limitados de la maquinaria entre todos los programas que se están ejecutando?. No, no es Aitor Menta, aunque podría. Es el Sistema Operativo.
Pero esto no ha sido siempre así...

Buceemos un poquito en el pasado. La informática remotamente parecida a lo que conocemos nació en los años 40. Había una guerra y era necesario calcular las trayectorias de los misiles. Parece que hay pocas cosas como la guerra para agudizar el ingenio. Las grandes máquinas de calcular solían diseñarse para un único propósito. Para el resto estaban las calculadoras. Los datos de entrada de los computadores se proporcionaban mediante tarjetas perforadas y el resultado se escribía en cintas magnéticas o imprimía. Existía la sensación de que algo más podía hacerse con esos trastos tan grandes.

Pero entre las muchas personas trabajando en los EE.UU. había un luminaria: John von Neumann ¹. A él se le atribuye una idea magistral al colaborar en el diseño de una gran computadora, el EDVAC: cada máquina podrá entender una serie de operaciones y tomará como entrada una serie de instrucciones (programa) a ejecutar secuencialmente. Casi simultáneamente otro genio que condujo a su país a reventar la superioridad alemana en las transmisiones lleva un tiempo pensando en eso. Su nombre es Alan Turing ². A finales de los 40 en un congreso en Manchester afirmó: "Estamos intentando construir una máquina que haga todo tipo de cosas diferentes simplemente programándola, en vez de añadiendo aparatos extra".

Bien, a ello se le llamó programa residente: la máquina ejecuta un código proporcionado desde fuera en algún lenguaje. Si en la memoria de la máquina se encuentran tanto los datos que necesite el programa como el código a ejecutar, se llama Arquitectura von Neumann y hoy subsiste como la base de la informática moderna. Hay quien opina que von Neumann inventó el concepto de software, aunque esto quizá sea ir demasiado lejos.

Los programas de entonces solían ser cálculos matemáticos, junto con algunas instrucciones sencillas: ahora calcular, ahora detenerse, ahora escribir en una cinta el resultado, ahora leer más datos. El usuario introducía unas tarjetas perforadas que el computador leía. Cuando en los años 50 apareció el lenguaje FORTRAN (el padre de todos los lenguajes), esta técnica mejoró mucho, pero seguía siendo muy pesada y requería al dos personas: el programador y el técnico. En seguida se dieron cuenta que podían acelerar el proceso agrupando las tareas en lotes con necesidades similares. A estos sistemas se les conoce como sistemas por lotes sencillos. El sistema operativo -monitor residente- se limitaba a transferir el control de un proceso al siguiente.

Uno de sus problemas era que el tiempo en que tardaban en leerse las tarjetas y en escribir resultados era demasiado lento. Los dispositivos de E/S son infinitamente más lentos que los procesadores y más si los primeros son mecánicos. La cosa mejoró con la introducción de discos magnéticos. Así, las tarjetas se escribían en discos y el sistema operativo creaba una "tabla" para cada proceso en disco. Lo mismo se hizo con la salida: en vez de escribir a la cinta o impresora se escribía en disco. Luego, al finalizar el trabajo, se escribía todo el resultado. A esto se le llamó spooling.

El spooling dio origen a algo mucho más interesante: la reserva y planificación de trabajos. En disco podían mantenerse varias tareas esperando a ser ejecutadas. Es decir, pueden ejecutarse en un orden distinto y variable. Algo así permite que mientras un proceso realiza una larga operación de entrada o salida, otro esté ejecutándose. Por tanto el "SO" ya tiene más curro: escoger una tarea para ejecutar. Esto incluye escoger las tareas para copiar a memoria si hay muchas y escoger de entre las tareas listas en memoria cual ejecutar. Como podemos tener potencialmente muchas tareas es necesario también gestionar la memoria. De nombre le pusieron sistemas por lotes multiprogramados.

Tomemos nota que en este punto el usuario tenía un papel pasivo: ¡no podía hacer nada nada mientras los programas se ejecutaban!. El tiempo de respuesta de los sistemas por lotes multiprogramados solía ser largo, pero ¿y si se deseaba realizar muchas acciones cortas? ¿Y si el usuario necesitara interactuar, proporcionar datos al programa mientras se ejecutaba?. Bien, esto sólo se pudo hacer cuando la conmutación entre trabajos se hizo mucho más frecuente, tanto, que daba la imagen de que todas las tareas se ejecutaban "al mismo tiempo". A esto se le conoce como sistemas multitarea o de tiempo compartido.

De este modo se genera la ilusión de que un programa puede estar esperando al usuario, cuando en realidad pasan otras muchas cosas por la CPU en ese instante. La idea de tiempo compartido ya había surgido en los años 60, pero no fue hasta principios de la década de los 70 cuando pudo ponerse en marcha. El OS/360 de IBM de 1964 (IBM fue pionera en el desarrollo de grandes computadores) era originalmente un sistema por lotes, el cual se modificó para añadir la opción de tiempo compartido.

Y aquí lo dejamos por el momento. Por supuesto: continuará...

¹ Aunque me gustaría hablar de lo extraordinario que era John von Neumann, ya lo han hecho otros, y seguro que mejor que yo. Aquí lo hace Omalaled. Y aquí. Y aquí.
² Lo mismo que antes. Sin embargo aquí se ha quedado un poco corto en la importancia que tuvo y su triste muerte. A ver si algún día hablo de Alan Turing y cuento más cosas.

1er bobo-tutorial: ensanchecer Blogger

2007-08-05T13:54:00.001+02:00

Como diría Jedebiah Springfield, he ensanchecido el blog. Y es que una de las cosas que menos me gustaba del diseño por defecto es el espacio de escritura en una estrecha columna central, dejando amplios márgenes a los lados inservibles. ¿A qué se debe esto? No lo sé. Sea cual sea la respuesta, otros diseños (blogs de Wordpress, por ejemplo) no parecen considerarla. El diseño tradicional de Blogger está bien si lo que se pretende es publicar un vídeo y decir: "¿Qué os parece?", pero cuando los escritos sobrepasan las 1000 palabras los posts quedan demasiado largos y para evitarlo hay que a) ponerlo a letra muy pequeña o b) aprender a cambiar el diseño.

Yo he venido optado por la opción a). Pero como me daba un poco de vergüenza ser informático y no intentar al menos aprender cómo funcionaba esto, me he puesto manos a la obra. Y bien, ya he entendido como funcionan los diseños o templates de Blogger. Bueno, he entendido cómo funciona el diseño de MI página, que puede no ser el mismo para otros diseños que Blogger ofrece. De todos modos un buen diseño debe poder permitir cambiar el aspecto general realizando pocos cambios, así que no debe ser muy difícil ensanchecer otros blogs.

Para ponerme a prueba, he decidido ensanchar los márgenes de un blog amigo (El Rincón de Pinar). Con un poco de idea, Dreamweaver 8 (vale cualquier editor de texto) y Gimp2 (aceptamos Paintbrush) en menos de 10 minutos he ensanchecido el mismo. Y como me aburro, explico cómo. Quizá haya mejores tutoriales en la red para hacer lo mismo. Creo que no.

Empecemos por el sentido común y leemos el código del template¹. Vemos que hacia el principio pone algo como layout. Buscamos layout. Vemos que significa diseño o composición... pues por ahí tenemos que toquitear.

/* layout
----------------------------------------------- */
#outer-wrapper {
margin: 0 auto;
width: 760px;
text-align: left;
font: $bodyFont;
}

Width significa anchura. La anchura de outer-wrapper (envoltorio externo, es decir lo de más de fuera) es 760 loquesea (px significa pies xuntos para nuestros propósitos). Como queremos que sea más grande, ponemos 900 pies xuntos. Como se ve, no hace falta tener ni idea de informática. Por eso hay tantos tutoriales en linea de informática. Sigamos, empero, con el nuestro.

#content-wrapper {
position: relative;
width: 760px;
background: #f7f0e9 url(http://www.blogblog.com/thisaway/bg_main_wrapper.gif) repeat-y left top;
}

#main-wrapper {
display: inline; /* fixes a strange ie margin bug */
float: left;
margin: 0 0 0 3px;
padding: 0;
width: 483px;
word-wrap: break-word; /* fix for long text breaking sidebar float in IE */
overflow: hidden; /* fix for long non-text content breaking IE sidebar float */
}

Content es contenido. El envoltorio del contenido también medía 760px. Ya sabemos que ahora tiene que medir 900. El main-wrapper es el envoltorio principal. Ahí se enmarcan nuestros posts. Como queremos hacerlos más grandes, lo cambiamos a 600px. Para esto es necesario hacerse con una calculadora: 760 es a 483 como 900 a x. Yo he puesto 600px porque no gasto calculadora.

Ya hemos acabado. Si ahora salvamos y vemos qué pasa (las pruebas mejor hacerlas en una página en el disco duro), veremos que muy posiblemente, no hemos acabado. Los colores y lineas no cuadran con el texto. La gracia está en que las imágenes que dan color y ornamentan el blog están pensadas para unos tamaños determinados. Por eso no basta con cambiar el tamaño de los márgenes: debemos adecuar las imágenes a los nuevos tamaños. Generalmente estas imágenes corresponden a la cabecera y pie del blog y algún tipo de imagen que separe el texto (main) de la barra lateral (sidebar). En mi caso es una imagen como ésta, que se repite en el eje vertical (y). En caso de dudas, lo mejor es escribir la dirección de cada imagen en el navegador para ver de qué se trata. Así sabemos en qué parte del código debemos reemplazar.

#header-wrapper {
padding-bottom: 15px;
background: url(http://www.blogblog.com/thisaway/bg_header_bottom.gif) no-repeat left bottom;
}

#header {
background: #634320 url(http://www.blogblog.com/thisaway/bg_header.gif) repeat-x left bottom;
}

Estas son la imágenes que componen la cabecera. Ambas tienen 760px de longitud. Bueno, necesitaremos bajarlas, editarlas para que tengan 900px y buscar un servidor donde alojarlas. Si tenemos Blogger, entonces también tendremos ~~PicasaWeb~~². Luego reemplazaremos la url del template por la que nos ofrezca el servidor. url significa "una ristra de letras" para nuestros propósitos. Lo mismo haremos para la(s) imagen(es) que usamos como separador. Ejemplos:

Separador: antes y despues.
Separador(es) de Pinar: antes (I, II, III) y después (I, II, III).
Nuevo código de mi separador.

#content-wrapper {
position: relative;
width: 900px;
background: #f7f0e9 url(http://img382.imageshack.us/img382/8864/bgmainwrappercc0.gif) repeat-y left top;
}

Y ya hemos acabado. En mi caso, ha sido también necesario cambiar las imágenes del pie del blog (footer). Dificultad no tiene ninguna, como todo buen tutorial on-line. De hecho, poner la etiqueta informática a esto da un poco de grima, pero prefiero no inventar más etiquetas hasta tener nuevos posts del tema. Próximo tutorial: "cómo ofrecer la suscripción a etiquetas del blog con divertidos dibujos inclusive".
Tampoco lo he encontrado en Google.

ACTUALIZACIÓN

No copies y pegues el código de este post en el template de tu blog, aunque los colores de tu blog coincidan con los de el mío. Antes, preocúpate de subir las imágenes de fondo a tu propio servidor de almacenamiento de imágenes (como ImageShack). De lo contrario, estarás utilizando MIS imágenes, y el día menos pensado te puedes quedar sin ellas.

¹ Si no sabes dónde encontrar el template de tu blog, mejor saltarte todo el post.
² Picasa no es recomendable, puesto que sólo almacena ficheros JPEG. Yo gasto ImageShack, en el cual no sé si confiar, después de haberme hecho la jugada de impedir postear imágenes en el blog sin razón alguna. Cosa que, por supuesto, llenó de ranas el mismo. Tras enviar un correo solicitando una explicación encuentro que ya está todo de nuevo arreglado. Por si acaso, hay otros servidores de alojamiento como Hotlinkfiles y Filenanny.