Archive for the ‘Informática’ Category

h1

Las gramáticas de Chomsky (ahora sí) :D

marzo 12, 2008

En el anterior artículo, que pretendía que versara precisamente sobre las aportaciones de Noam Chomsky a la ciencia computacional, hablamos finalmente de la relación entre lenguajes y ordenadores. Lo que pasa es que a veces enseguida empiezo a divagar y acabo hablando de sabe dios qué, pero intentaremos centrarnos ahora con este artículo 😉

Sin embargo, para hablar de gramáticas, primeramente tenemos que hablar de lenguajes, y antes de nada, por tanto, tenemos que definir un lenguaje…

Por lo general, las definiciones que más me gustan son las más simples. Aunque a veces sean incompletas o incluso inexactas de algún modo, prefiero siempre comenzar con un concepto lo más sencillo posible aunque después tengamos que ampliarlo o modificarlo. Siguiendo este concepto, un lenguaje no es más que un conjunto de palabras.

Pero evidentemente, se trata de un conjunto finito, por lo tanto tiene que haber algo que nos indique qué palabras pertenecen o no al lenguaje. Asimismo, resulta también obvio que estas palabras se forman combinando una determinada serie de símbolos (letras, por ejemplo). Así pues, aunque un lenguaje no sea más que un conjunto de palabras, necesitamos al menos dos cosas más: los símbolos con los que crear las palabras, y una regla o conjunto de reglas que nos permitan saber qué palabras pertenecen al lenguaje.

Todo lo dicho hasta ahora, vale tanto como para lenguajes naturales como para lenguajes computacionales (sí, estoy hablando de Java, C++, o cualquier otro que se os ocurra) No obstante, no hay ninguna regla establecida que nos permite saber que “know” pertenece al lenguaje inglés y no a otro salvo nuestro propio conocimiento del lenguaje, pero la idea es la misma.

Ahora viene uno de los puntos clave del asunto, si cambiamos ligeramente la definición de “regla(s) que permitan determinar si una palabra pertenece al lenguaje” obtendremos la definición de gramática desde el punto de vista de la informática. Sólo tenemos que decir que estas reglas no sólo valdrán para determinar la pertenencia, sino que serán estas propias reglas las que “fabriquen” únicamente las palabras válidas para el lenguaje. Dicho de otra manera; una gramática es una regla que nos permite crear únicamente palabras válidas para un lenguaje determinado.

Este es el punto donde los lenguajes naturales y los computacionales se separan más. Pero no del todo. A fin de cuentas, en los lenguajes naturales también hay ciertas reglas para crear palabras. Por ejemplo, si necesitamos una palabra para definir el concepto “ciencia de la vida” utilizaremos dos lexemas con significado predefinido: bio- (vida) y -logía (ciencia). Se podría haber llamado a la biología escataralofusia, por ejemplo, o cualquier otra cosa, pero, sería mucho más inútil, y carente en sí misma de significado.

La gran diferencia con los lenguajes de ordenador, es que esas reglas son totalmente explícitas y han de cumplirse estrictamente. Esto sería imposible de realizar con los lenguajes naturales, pues son totalmente irregulares y contienen etimologías de fuentes muy diversas. Son tan complejos, variados y ricos que es imposible clasificar y regularizar todas sus palabras al dedillo como si se hace con los lenguajes de ordenador. Y esto es, porque estos últimos son lenguajes regulares.

Continuaremos próximamente 😉 …

Anuncios
h1

Las gramáticas de Chomsky

marzo 6, 2008

En el artículo de ayer, nos introducíamos muy por encima en la vida y obra del filósofo y lingüísta Noam Chomsky. Hoy vamos a ahondar un poco más en su mayor aportación en el campo de las ciencias de la computación ( pomposo nombre para lo que los mortales conocemos como informática 😉 ); las gramáticas.

La informática y el lenguaje son disciplinas que intuitivamente nos pueden parecer separadas por un abismo. Ya desde el instituto nos adoctrinan en diferenciar claramente el estudio de los lenguajes (letras puras) con el de la ciencia o la tecnología (ciencias puras) al menos a mí, me resulta curioso ver como una de las ciencias más jóvenes de la historia, se apoya y fundamenta en gran medida en una de las más antiguas y más intrínsicamente ligadas al hombre. Ver como a veces todas las disciplinas del saber humano se interconectan de la manera más inesperada me resulta tan abrumador como alentador 🙂 .

Pero dejémonos de cursiladas y volvamos al tema ¿Hasta qué punto están relacionadas la informática y el lenguaje? Pensemos que el arte de crear programas de ordenador, no es si no comunicarse con el ordenador, decirle cómo tiene que comportarse en cada caso y qué respuestas tiene que dar. Si lo vemos así, está claro que necesitamos un lenguaje para hablarle al ordenador. ¿Pero cómo son estos lenguajes? ¿Se parecen a los lenguajes naturales como el inglés o el castellano? Pues sí y no.

Se parecen en el sentido de que tienen unas reglas gramaticales estrictas y una sintaxis muy concreta. Se parecen en el significado de muchas de sus palabras. Pero también se distinguen en muchas cosas. Un ordenador, al menos de momento, es incapaz de entender ambigüedades, ironías, dobles sentidos u obviedades. La máquina carece por completo de inteligencia; hay que explicárselo todo. Un ordenador no aprende. A pesar de las noticias que vemos muchos días acerca de superordenadores que parecen más inteligentes que el hombre, en realidad son extremadamente estúpidos, sólo que compensan su estupidez con una capacidad de cálculo extraordinaria. Veamos un ejemplo real muy claro.

kasparov_deep_blue.jpg

En 1997 el ajedrecista Garry Kasparov se enfrentó al ordenador Deep Blue de IBM en un duelo de seis partidas de ajedrez. Finalmente y como todos sabéis, la computadora se alzó con el triunfo, aunque necesitó de las seis partidas para ello, tras ganar el ruso el primer duelo, Deep Blue el segundo y saldarse con tablas las tres siguientes partidas. El megaordenador de IBM era una supercomputadora capaz de analizar millones de jugadas por segundo. Kasparov, en cambio, “sólo” era capaz de analizar tres o cuatro jugadas por segundo. Aún así fue capaz de derrotarle en una ocasión y resistir su envite de tal manera que la de Deep Blue se convirtió en una victoria pírrica. ¿Fue el triunfo de la inteligencia computacional sobre la humana? rotundamente no; Deep Blue necesita en cada turno analizar todas las posibles jugas, incluídas las más absurdas o las antirreglamentarias. Pero aún así, le daba tiempo. Kasparov, en cambio, ya sabía qué jugadas tenía que analizar. Su cerebro descartaba automáticamente las jugadas que no le aportaban ningún beneficio. Eso es inteligencia, lo de Deep Blue, sólo es capacidad de cálculo. Si enfrentásemos a Kasparov contra otro buen ajedrecista, y éste último tuviese todo el tiempo del mundo para pensar cada jugada, y el ruso tan sólo unos minutos, nadie diría que el otro jugador es más inteligente que el excampeón del mundo.

Bueno, después de este pedazo de rollo, no me quedan ganas de empezar a hablar de gramática ahora, mejor lo dejamos para mañana 😀

h1

Nombres propios de la informática

marzo 6, 2008

Hoy nos toca repasar brevemente la vida y obra de uno de los nombres más importantes, no sólo de la informática, sino de muchos otros campos como la filosofía, el lenguaje o incluso la política del siglo XX. Estoy hablando del lingüista norteamericano Noam Chomsky.

10.gif

Noam Chomsky nació en Filadelfia, Estados Unidos en 1928. Fue uno de los grandes precursores del estudio de los lenguajes desde una perspectiva científica, y en gran parte gracias a él, hoy manejamos conceptos como teoría del lenguaje. De hecho, sus aportaciones en el campo de la informática, como veremos más adelante, son sólo la punta del iceberg de todo el conocimiento que generó Chomsky.

En su tesis doctoral de 1957, Chomsky afirmaba que el lenguaje no se aprendía sólamente mediante aprendizaje y repetición, como cualquier otra disciplina, sino que existía una región del cerebro destinada a manejar el lenguaje, en una fase primigenia, de una manera innata. Esta idea chocaba frontalmente con lo que se pensaba hasta entonces, por lo que se generó una enorme controversia al respecto. Pero no sólo eso, el filósofo estadounidense aseguraba también la existencia de una gramática universal, con unos principios comunes a cualquier lenguaje habido y por haber y fácilmente interpretable por ese mecanismo lingüístico que poseía nuestro cerebro.

De esta forma y según Chomsky, podemos reducir el estudio de lenguajes al estudio de las gramáticas que los generan. El concepto de gramática tal y como lo estamos usando aquí, no es el mismo que intuitivamente tenemos todos de lo que es una gramática (pero es similar) pero todo ello lo explicaremos en un próximo post.

Volviendo a Chomsky, su concepción de gramática generativa (llamada así porque permite generar estructuras léxicas (o sea, frases) en base a unas reglas implícitas (las estructuras correctas de una frase de cualquier idioma.

Al margen de su aportación a la teoría del lenguaje, que revolucionó además todo lo que se pensaba del conocimiento humano influyendo en campos tan dispares como la economía o la psicología, Noam Chomsky fue, y sigue siendo, un concienzudo activista político. Desde su frontal oposición a la guerra de Vietnam en los años setenta, ha mantenido una postura de confrontación con la política exterior de su país, especialemente en lo referente a Palestina, pero también en lo tocante a las intervenciones nortemericanas en Sudamérica, Afganistán o mismamente Irak. Desde hace más de treinta años, Noam Chomsky es uno de los más firmes luchadores contra el imperialismo y militarismo norteamericano en todo el mundo.

Mañana, entraremos más en detalle en lo que las gramáticas de Chomsky representan en el lenguaje…

h1

La sentencia GO TO

diciembre 10, 2007

Como vimos en el anterior post, una de las grandes obsesiones de Dijkstra fue tratar de eliminar la sentencia GO TO de los lenguajes de programación de alto nivel. Para cualquiera que no tenga conocimientos de informática, esto le sonará probablemente a chino 😀 , así que tratemos de aclarar algunos conceptos…

Cualquier programa informático (desde un editor de texto como Microsoft Word, un sistema operativo como Windows o Linux o mismamente un videojuego) en su origen no es más que un conjunto de miles de líneas de texto detallando lo que el programa hace en cada momento. A esto lo llamamos código fuente. Pongamos un ejemplo básico y simplón para entendernos. Si quisiésemos programar el Super Mario Bros. , parte de su código fuente sería tal que así:

Comprobar que a Mario le queden vidas

Si a Mario le quedan vidas

entonces la partida continúa

Si se aprieta el botón A

entonces Mario salta

Si se aprieta el botón ABAJO encima de una tubería

entonces Mario se mete en ella

Mientras dure el efecto de la estrella, Mario es invencible

Evidentemente, ni Super Mario Bros. ni ningún otro juego están programados con un lenguaje como este 😀 (de hecho, los juegos de consola antiguos están programados en ensamblador, un tema que dará para algún que otro interesante post más adelante…) ni es tan sencillo ni intuitivo como puede parecer, pero supongo que sirve para introducirnos en lo que es el código fuente. Sin embargo, tampoco penséis que un lenguaje de programación de alto nivel sencillo (como puede ser Pascal) es tan, tan diferente de lo que he puesto ahí 😉 . En realidad, y adaptándolo un poco a las características propias del lenguaje y de la propia programación, podría ser bastante parecido.

Una vez el programador ha completado el código fuente del programa, utiliza un compilador sobre él. Un compilador, en su definición más general, no es más que un programa que traduce un texto de un lenguaje a otro. En este caso, traduce el código fuente ( que está escrito en un lenguaje de programación como pueden ser C++, Java, Pascal, Perl, PHP…) a código máquina, o lo que es lo mismo, únicamente ceros y unos, que es, a fin de cuentas, lo único que comprende un ordenador. De esta forma, hemos obtenido un ejecutable, también llamado binario por los de unos y ceros, que, como su propio nombre indica, ya podemos ejecutar en la máquina.

¿Qué papel juega la sentencia GO TO en todo esto? pues recurramos nuevamente al ejemplo de antes, sólo que ahora enumeremos las líneas…

0001: Comprobar que a Mario le queden vidas

0002: Si a Mario le quedan vidas

0003: La partida continúa

0353: Si se aprieta el botón A

0354: Entonces Mario salta

0455: Si se aprieta el botón ABAJO encima de una tubería

0456: Mario se mete en ella

0678: Mientras dure el efecto de la estrella

0679: Mario es invencible

Obviamente, el código fuente del Mario (de cualquier programa, vamos) sería muchísimo más grande, de ahí que numere de esa forma (se supone que entre la línea 0003 y la 0353 hay muchas otras). Si empleamos la sentencia GO TO, el código quedaría más o menos así:

0001: Comprobr que a Mario le quedan vidas

0002: Si a Mario le quedan vidas entonces GO TO 0003

0003: La partida continúa

0353: Si se aprieta el botón A entonces GO TO 0354

0354: Mario salta

0455: Si se aprieta el botón ABAJO encima de una tubería entonces GO TO 0456

0456: Mario se mete en la tubería

0658: Mientras dure el efecto de la estrella GO TO 0659

0659: Mario es invencible

GO TO, que, como sabéis, podríamos traducir como ir a, va al final de cada línea indicando a dónde se tiene que ir en caso de cumplirse la condición, o dicho de otra forma, dónde está la siguiente línea (o instrucción) que debe procesarse. De esta forma, el orden de las instrucciones pierde relevancia; la sentencia GO TO modifica el flujo del programa (en pocas palabras, qué instrucciones y en qué orden se ejecutan) a su antojo.

Vale, así contado la verdad es que la instrucción GO TO puede parecer útil y muy flexible, pero es precisamente esa flexibilidad donde radica su peligro y los motivos de su obsolescencia; pensemos que cualquier programa mínimamente complejo tendrá miles y miles de líneas de código fuente, con millones de flujos de programa posibles diferentes. Si alteramos dicho flujo con la sentencia GO TO de un modo incontrolado, el código se volverá totalmente caótico, y por tanto muy difícil de controlar, depurar, mejorar o entender, lo que nos llevará, inevitablemente, a ejecutables (programas) de escasa calidad.

Como mejor alternativa a la sentencia GO TO, que, no obstante, se sigue usando en algunos casos, surgieron las estructuras de control, sobre las que también me gustaría hablar, pero no se si me ha quedado un artículo demasiado aburrido, ininteligible o ambas cosas. Tenéis los comentarios para hacérmelo saber, y en función de eso, decido 🙂 .

h1

Nombres propios de la informática

diciembre 8, 2007

Esta vez le toca el turno al que quizá podríamos denominar padre de la programación moderna: Edsger Dijkstra.

dijkstra.jpg

Edsger W. Dijkstra nació en Rotterdam en 1930. Estudió física teoríca en la universidad de Leiden (Holanda) y después se trasladó a los Estados Unidos, dónde trabajó en el sector privado antes de incorporarse a la universidad. Se retiró en 2000 y murió en 2002 víctima de un cáncer.

Son muchas las aportaciones hechas por Dijkstra en materia de programación. Pero sin duda una de las más relevantes la conforma su famoso artículo A Case against a GO TO Statement, que representa el espaldarazo definitivo de las estructuras de control (como los bucles while o repeat) en detrimento de la mítica sentencia GO TO de los antiguos lenguajes de programación, en mi siguiente artículo, explicaré un poco todos estos términos…

Pero las aportaciones de Dijkstra no acaban ahí. Fue también uno de los padres de la moderna correción de programas, efectuando constantes pruebas de toda clase desde el inicio de la programación, y no sólo una vez terminado el programa como se hacía hasta entonces. Es también autor de una de las máximas de la programación moderna (Que por cierto, suena a Ley de Murphy total 😀 ):

Si un programa funciona, es que, probablemente, aún no hayamos encontrado el error

Antiguamente, cuando se probaba un programa y éste no daba errores, se consideraba que estaba bien programado. Pero después de Dijkstra, la filosofía fue otra y se pasó a considerar que si la prueba ejercida sobre un programa no mostraba errores, no era necesariamente porque el programa no contuviese fallos, sino porque la prueba no era la adecuada. Un pensamiento interesante ¿verdad? De esta forma y desde entonces, las pruebas para verificar los programas informáticos han avanzado muchísimo (otra cosa es que se utilicen en la práctica…)

Dijkstra fue también el autor de algunos conocidos algoritmos como el de la cena de los filósofos (destinado a ayudar a un sistema operativo a ejecutar varios programas en el orden correcto) o creador de los semáforos, que, como su nombre indica, indican a los programas de un ordenador en que momento pueden o no ejecutarse.

Por todas estas aportaciones y muchas más, Edsger Dijkstra está considerado uno de los grandes maestros de la programación moderna y uno de los grandes nombres de la informática 🙂 .

h1

Nombres propios de la informática

noviembre 19, 2007

Vamos a repasar durante algunos post, algunos de los nombres más relevantes en la historia de la informática (la cual para mí es, por paradójico que resulte, más interesante que la propia informática 😀 ) y nadie mejor para empezar que…

George Boole

boole2_lg.jpg

Matemático irlandés (1815-1864) considerado uno de los grandes padres de la informática. A él debemos el Álgebra de Boole, en la que se basa prácticamente cualquier sistema informático o electrónico de hoy día. En pocas palabras, es algo tan simple como definir ciertas operaciones (AND, OR, XOR…) en función de sus entradas y salidas tal que así:

1 AND 1 = 1 ||1 OR 1 = 1|| 1 XOR 1 = 0

1 AND 0 = 0 ||1 OR 0 = 1|| 1 XOR 0 = 1

0 AND 1 = 0 ||0 OR 1 = 1 || 0 XOR 1 = 1

0 AND 0 = 0|| 0 OR 0 = 0 ||0 XOR 0 = 0

Es decir, en la operación AND, bastará con tener un cero en la entrada (aquí los sumandos) para que la salida (el resultado) sea también un cero. De igual modo, en la operació OR, será suficiente un uno en la entrada para que la salida sea igualmente uno. En la operación XOR, la salida será 0 ó 1 dependiendo si las entradas son distintas o iguales entre sí.

Las entradas no tienen porqué ser sólo dos; también podemos por ejemplo, hacer la operación….

1 AND 1 AND 1 AND 0 … AND 1 = 0

del mismo modo. Y, por supuesto, también combinarlas:

[(1 AND 0) OR 1] XOR 0 = 1

con lo que podemos complicar la cosa casi tanto como queramos 😉 . Como veis, la idea es extremadamente simple. Pues con estas operaciones y considerando que 5v. de corriente es un uno y 0v. un cero podemos construír puertas lógicas (un minúsculo aparatito que se comporta como una de esas operaciones) y combinarlas para obtener circuitos lógicos que permitan a un ordenador realizar las operaciones de su juego de instrucciones (sumar números, restarlos, moverlos…) con las cuales y mediante un lenguaje de alto nivel (C++, Java…) podremos programar lo que queramos.

Obviamente, y habiendo transcurrido su vida enteramente en el siglo XIX, Boole jamás pensó en aplicar su álgebra en nada remotamente parecido a un ordenador. De hecho, su trabajo estuvo olvidado y considerado inútil durante mucho tiempo, hasta que algún otro chiflado 😉 se le ocurrió que se podía utilizar para crear una de las mayores revoluciones del siglo XX 😀

A pesar de lo compleja que puede ser a veces la informática, no debemos olvidar que, a fin de cuentas, todo está construído gracias a ceros y unos y a miles y miles de millones de operaciones elementales con ellos, y que todo esto se lo debemos muy especialmente a George Boole 🙂 , precisamente en su honor, se denomina variable booleana en un lenguaje de programación a algo que únicamente pueda adoptar dos valores: verdadero o falso, o lo que es lo mismo, uno o cero.