Historias de los “abuelos” de la informática o los orígenes de la programación orientada a objetos

Nuestro amigo JL me/nos recomienda una sugerente lectura para las frías tardes de otoño e invierno, relatos sobre la historia de la informática de mano de sus creadores en la página web del Instituto Charles Babbage (computer science oral histories). JL nos recomienda la entrevista a Don Knuth (70 años). Hablando de Algol y Algol 68 me viene a la memoria Simula y Simula 67. Es una pena que no aparezca una entrevista a Ole-Johan Dahl y/o Kristen Nygaard, ambos fallecidos en 2002 (29 de junio y 10 de agosto, respectivamente). ¿Eres informático y no sabes quiénes son? No me lo puedo creer. Me da pena que la historia de la informática en las Escuelas españolas se reduzca a hablar del ábaco, la pascalina, Babbage y el Eniac, cuando la historia de la informática son, básicamente, los últimos 10 lustros.

IEEE John Von Neumann Medal 2002.

IEEE John Von Neumann Medal 2002.

Dahl y Nygaard, en los 1950, mientras diseñaban un simulador de reactores nucleares observaron las grandes dificultades que requería dicha tarea con los lenguajes de la época. Necesitaban un nuevo lenguaje de programación que les facilitara la tarea. Crearon Simula I, un lenguaje para la simulación de eventos discretos mediante el método de Montecarlo programado en Algol 60, que incluía versiones primitivas del concepto de herencia, vinculación dinámica y concurrencia basada en tiempo compartido. Estos conceptos les llevaron a desarrollar una nueva metodología de programación y un nuevo lenguaje de propósito general, Simula 67. Este lenguaje influyó mucho en los creadores de SmallTalk, Eiffel (Simula 85), C++ o Ada (este último implementó un subconjunto de Simula). Dahl y Nygaard recibieron el Premio Turing de 2001 (el equivalente el Nobel de la Informática concedido por la ACM) por su labor como pioneros de la programación orientada a objetos. Dahl es coautor, con Dijskstra (entrevista) y Hoare (entrevista) del famosísimo y altamente recomendable a los jóvenes que estudian informática “Structured Programming,” Academic Press, 1972 .

Los interesados en la historia de Simula disfrutarán del artículo de Jan Rune Holmevik, “Compiling SIMULA: A Historical Study of Technological Genesis,” IEEE Annals of the History of Computing archive, 16: 25-37, 1994 . Los interesados en más detalles de la vida de Dhal y Nygaard pueden recurrir a su obituario en JOURNAL OF OBJECT TECHNOLOGY, dónde si no, “In memory of Ole-Johan Dahl and Kristen Nygaard,” escrito por Bertrand Meyer (padre de Eiffel).

Nota al margen: no todas las entrevistas en Oral History Database están disponibles electrónicamente “Transcript not available electronically. Please contact CBI.” En muchas me he encontrado con dicha sorpresa, espero que pronto la subsanen. ¡Quizás he buscado entrevistas a investigadores “poco” conocidos!

PS: “Structured Programming,” es un libro editado por Charles A. R. Hoare de sólo 3 capítulos. El primero “Notes on Structured Programming,” de Edsger W. Dijkstra, notas del autor para sí mismo sobre cómo escribir programas “estructurados” y cómo verificar su corrección; incluye demostraciones de la corrección de algoritmos tan interesantes como la resolución del problema de las ocho reinas. El segundo “Notes on Data Structuring,” de C. A. R. Hoare, introduce los conceptos modernos de la actual programación estructurada, como tipos, registros, punteros, programación recursiva, etc. Finalmente, el tercer y último capítulo “Hierarchical Program Structures,” Ole-Johan Dahl and C. A. R. Hoare, introduce la programación “estructurada” en Simula 67, con conceptos como clases de objetos, instancias de objetos, jerarquías (herencia) de clases, incluyendo varios ejemplos muy interesantes de esta programación “estructurada” a la hoy posiblemente llamarías programación orientada a objetos. 220 páginas que no tienen desperdicio. Sé de buena tinta que la mayoría de los estudiantes de informática no se atreverán a leerlo, quizás, por la misma razón por la que no se han atrevido a leer “Don Quijote de la Mancha,” de Miguel de Cervantes Saavedra.

La historia oculta detrás del algoritmo PageRank de Google (o Keller, Keener, Page, Brin y Kleinberg)

¿Quién inventó el algoritmo PageRank que utiliza Google? El algoritmo está patentado por los fundadores de Google, Larry Page y Sergey Brin, cuando eran alumnos de doctorado en la Universidad de Stanford. Page fue alumno de doctorado de Terry Winograd, quien parece que le animó en la idea de trabajar en el PageRank, y Brin fue alumno de doctorado de Jeffrey D. Ullman, el famoso autor del libro de compiladores con Aho, aunque pronto se unió a Page para trabajar en temas “más interesantes” que los que le ofrecía su director (que le llevaron a hacerse multimillonario). Todo el mundo “sabe” que Larry Page inventó el PageRank, por eso se llama “Page Rank”. Eso lo sabe todo el mundo, ¿o no?

Acaba de publicarse el artículo del gran matemático aplicado Joseph B. Keller de la Universidad de Stanford, “Evaluation of Authors and Journals,” ArXiv preprint, 5 October 2008 , documento fechado originalmente en octubre de 1985, en el que aparece “calcado” el algoritmo PageRank de Google. En dicho artículo, que recomiendo, Keller “afirma” que lo inventó para clasificar equipos de béisbol (yo siempre lo leo como los cubanos: “beisból”). Un amigo y lector de este blog, JL, me pregunta “¿Sabes algo de esta historia? ¿Es conocida por los que estáis en el mundillo?” Me ha picado la curiosidad, lo confieso. No sé si Page y/o Brin conocieron a Keller, probablemente no. ¿Qué más puedo decir?

Ante todo, empecemos por el principio. Joseph B. Keller es un matemático famosísimo como inventor de la teoría de trazado de rayos difractivos (yo lo conocí hace años por eso). Sí, los rayos de la óptica geométrica (sin difracción ni interferencia) se pueden usar (convenientemente adaptados) para modelar la difracción. Esto es lo que se debería usar cuando se usa trazado de rayos en acústica arquitectónica, aunque muchos que la usan no los conocen. Su artículo “Geometrical theory of Diffraction,” Journal of the Optical Society of America, 52:116-130, 1962, es todo un clásico (citado más de 1000 veces en el ISI Web of Science). Pero Keller ha hecho muchas otras cosas importantes y conocidas, como sus trabajos sobre condiciones de contorno absorbentes con Givoli o sus modelos de la propagación de pulsos eléctricos en los axones de las neuronas. Es uno de los grandes matemáticos de la segunda mitad del s.XX en propagación de ondas y en el uso de métodos asintóticos en dicho contexto.

¿Alguna mención al trabajo de Keller sobre el PageRank antes de que Larry Page lo inventara? He encontrado el artículo “Who’s really #1?,” publicado en Science News, Dec 18, 1993, por Ivars Peterson (famoso escritor de noticias matemáticas por su Math Trek). En él nos hablaba ya de este algoritmo de Keller para clasificar equipos de fútbol (americano). Peterson comenta en dicha noticia el artículo “The Perron-Frobenius Theorem and the Ranking of Football Teams,” SIAM Review, 35: 80-93, 1993, escrito por el matemático James P. Keener de la Universidad de Utah (autor del famosísimo y buenísimo “Mathematical Physiology“, dos volúmenes que hay leer si se quiere trabajar en matemática aplicada a la medicina). Por cierto, este artículo de Keener yo lo leí hace años, cuando leía todas las revistas de SIAM en papel (hace ya algunos años que no las leo con asiduidad porque online me quedo muchas veces sólo con los títulos y ¡¿selecciono más lo que leo?!). En dicho artículo, Keener estudia cuatro métodos para clasificar equipos que compiten dos a dos (como los de fútbol) y cómo estos métodos dependen del teorema de Perron-Frobenius. El artículo no cita a Keller en la bibliografía, pero sí en los Agradecimientos, literalmente “Thanks to Joe Keller for introducing me to this fascinating topic over ten years ago.”

Peterson nos lleva más allá. Volvamos a él. Un equipo es bueno si vence a equipos buenos, que vencen a equipos buenos, … Una pescadilla que se muerde la cola. O en sus palabras, el problema de “quién fue primero, el huevo o la gallina”. Según Peterson, Keener logra resolver este dilema utilizando un algoritmo previamente sugerido por el matemático aplicado Joseph B. Keller de la Universidad de Stanford cuando era “alto cargo” de la organización matemática Society for Industrial and Applied Mathematics (SIAM). Keller quería saber cómo de buenas eran las revistas de SIAM comparadas con el resto de revistas en Matemática Aplicada (ahora mismo, las revistas de SIAM están entre las mejores y de más índice de impacto del campo de la Matemática Aplicada, destacando, como no, SIAM Review con factor de impacto 2.455 en el JCR 2007, la #3 de 165 en Matemática Aplicada).

¿Cómo resolvió Keller el problema de “la pescadilla que se muerde de la cola”? Utilizando el teorema de Perron-Frobenius (idea que Keener nos recupera en su artículo). El algoritmo actualmente conocido como PageRank de Google. Queréis más información en castellano, seguid los enlaces que os ofrecí en una entrada anterior sobre el “granadino” SCImago Journal Rank.

¿Y quién es Jon Kleinberg? ¿Qué pinta en el título de esta entrada? ¡Y tú me lo preguntas! Es uno de los especialistas mundiales en los algoritmo tipo PageRank, inventó al llamado algoritmo HITS, y ganó por ello el Premio Nevannlinna que se le concedió en el Congreso Internacional de Matemáticos de Madrid 2006 (premio al mejor trabajo en informática realizado por un matemático, foto). Los trabajos de Kleinberg han permitido desarrollar algoritmos muy eficientes para poder calcular métricas como el pagerank.

That’s all folks!

Metropolis y los métodos de Montecarlo (o la manía de usar Maniac para algo útil)

Las programadoras del ENIAC primero utilizaban paneles de cables.

Nick (Nicholas Constantine) Metropolis (nacido el 11 de junio de 1915) trabajó con Edward Teller y con J. Robert Oppenheimer en el proyecto Manhattan en Los Alamos durante la Segunda Gran Guerra. Tras ella, en 1948 lideró el grupo de Los Alamos que desarrolló y construyó el Maniac, uno de los primeros ordenadores electrónicos digitales. Metropolis desarrolló, junto a Teller, John von Neumann, Stanislaw Ulam, y Robert Richtmyer, los llamados métodos de Montecarlo (in inglés Monte Carlo, como les llamó el propio Metropolis). Es sorprendente, pero mucha gente asocia a Metropolis con las técnicas de muestreo basadas en la importancia, el llamado algoritmo de Metropolis, muy utilizadas en simulación de Montecarlo, olvidando su importante papel en el desarrollo de uno de los algoritmos más importantes en toda la Historia de la Informática.

El origen de métodos tan importantes como el método de Montecarlo siempre se puede trazar en el pasado muy lejos y siempre hasta llegar a los más grandes genios. Por ejemplo, Enrico Fermi, quien siempre estaba calculando algo, usó técnicas de muestreo estadístico en problemas de difusión de neutrones al menos en 1934, tras el descubrimiento en 1933 por Frederic Joliot e Irene Curie (la hija, también Nobel) de la radioactividad inducida en elementos ligeros mediante el bombardeo con partículas alfa (núcleos de Helio). Recuerda que Chadwick descubrió el neutrón un año antes. La idea de Fermi fue utilizar neutrones en lugar de partículas alfa. Utilizó métodos de Montecarlo para realizar sus cálculos. Nunca lo publicó. Se conoce la historia porque se la contó a Emilio Segré.

Las programadoras del ENIAC más tarde utilizaban paneles control (idea de Nick).

En 1948, Nick visitó el ENIAC donde, gracias a una sugerencia de von Neumann, implementó por primera vez cálculos de Montecarlo computerizados. Contratado por la Universidad de Chicago, desarrolló el computador electrónico de Los Alamos llamado MANIAC (Mathematical and Numerical Integrator and Computer) que utilizaba la arquitectura de programa almacenado de von Neumann. Lo más maravilloso de tener uno de los primeros ordenadores a principios de los 1950s es que prácticamente cualquier que se hacía con él era pionera y muy importante. El computador abría un amplio abanico de posibilidades de investigación científica hasta ese momento inalcanzables. En el MANIAC se realizaron las primeras simulaciones de osciladores no lineales acoplados (problema de Fermi-Pasta-Ulam, programado por la señorita Tsingou), idea de Fermi en 1953 acabó como informe técnico sin publicar por su fallecimiento. Pero también se desarrollaron trabajos tan importantes como el análisis del código genético (Gamow, Metropolis; 1954), el muestreo basado en importancia (Metropolis, Teller; 1953), física computacional de fluidos en 2D (Metropolis, von Neumann; 1954), y muchos otros más. Casi cada artículo abría un nuevo campo de conocimiento.

MANIAC II sustituyó a MANIAC I en Los Alamos en 1956, que incluía un aritmética en punto flotante y era mucho más poderoso. MANIAC III, con circuitos de estado sólido, se desarrolló en la Universidad de Chicago. Los MANIAC funcionaron hasta 1977.