Corrado Bohm

SUP_0236

I was very saddened to hear that Corrado Böhm died today at age 94.

Böhm was one of the founding fathers of Italian computer science. His dissertation, from 1951, was one of the first (maybe the first? I don’t know the history of these ideas very well) examples of a programming language with a compiler written in the language itself. In the 1950s and 1960s he worked at the CNR (an Italian national research institution with its own technical staff), in the IAC (Institute for the Applications of Computing) directed by mathematician Mauro Picone. IAC was the second place in Italy to acquire a computer. In 1970 he moved to the University of Turin, were he was the founding chairman of the computer science department. In 1972 he moved to the Sapienza University of Rome, in the Math department, and in 1989 he was one of the founders of the Computer Science department at Sapienza. He remained at Sapienza until his retirement.

Böhm became internationally known for a 1966 result, joint with Giuseppe Jacopini, in which he showed, roughly speaking, that programs written in a language that includes goto statements (formalized as flow-charts) could be mapped to equivalent programs that don’t. The point of the paper was that the translation was “structural” and the translated program retained much of the structure and the logic of the original program, meaning that programmers could give up goto statements without having to fundamentally change the way they think.

Dijkstra’s famous “Go To Statement Considered Harmful” 1968 letter to CACM had two references, one of which was the Jacopini-Böhm theorem.

Böhm was responsible for important foundational work on lambda calculus, typed functional languages, and the theory of programming languages at large.

He was a remarkable mentor, many of whose students and collaborators (including a notable number of women) became prominent in the Italian community of theory of programming languages, and Italian academia in general.

gruppetto

In the photo above is Böhm with Simona Ronchi, Betti Venneri and Mariangiola Dezani, who all became prominent Italian professors.

You may also recognize the man on the right as a recent recipient of the Turing Award. Silvio Micali went to Sapienza to study math as an undergrad, and he worked with Böhm, who encouraged Silvio to pursue his PhD abroad.

I studied Computer Science at Sapienza, starting the first year that the major was introduced in 1989. I remember that when I first met Böhm he reminded me of Doc Brown from Back to the Future: a tall man with crazy white hair, speaking of wild ideas with incomprehensible technical terms, but with unstoppable enthusiasm.

One year, I tried attending a small elective class that he was teaching. My, probably imprecise, recollection of the first lecture is as follows.

He said that one vertex is a binary tree, and that if you connect two binary trees to a new root you also get a binary tree, then he asked us, how would you prove statements on binary trees by induction? The class stopped until we would say something. After some consultation among us, one of the smart kids proposed “by induction on the number of vertices?” Yes, said Böhm, that would work, but isn’t there a better way? He wanted us to come up by ourselves with the insight that, since binary trees have a recursive definition, one can do induction on the structure of the definition.

In subsequent lectures, we looked (without being told) at how to construct purely functional data structures. I dropped the class after about a month.

(Photo credits: corradobohm.it)

Advertisements

Aldo Fabrizi

Today Aldo Fabrizi would turn 110. Outside of Italy, those who know him at all probably know him from Rome, Open City, one of the early movies of the Neorealismo genre. (It is available in the US in a Criterion edition.)

But, in Italy, Fabrizi is famous for being one of the giants of the first generation of Italian-style comedy, from the 1950s and 1960s. My favorite movies of his are those in which he acts as a straight man for Totò, and my absolute favorite is Guardie e Ladri, which never had an American release.

For those who understand Italian, it’s possible to find the whole movie on youtube. Here is one iconic scene.

Ora e sempre resistenza

Today it’s my favorite of Italy’s public holidays.

To keep a long story long, at the start of WW2, Italy, which was an ally of Germany, was initially neutral, in part because its armed forces were completely unprepared for war. At some point in the May of 1940, with German troops advancing into France, and British troops evacuating the continent, Italy decided to join what looked like a soon-to-end war, in order to claim some French territories and colonies.

But then, in 1941, Germany attacked Russia and Japan attacked the US, underestimating what they were getting into, and by the beginning of 1943 the tide was clearly turning against the “axis.” Italy’s king, who was definitely not the “fight until the last man” type, had Mussolini arrested, installed a general as prime minister, and started negotiating Italy’s surrender with the allies (even as Italian troops were fighting with the Germans in Russia and in Africa). Eventually, on September 8, 1943, the king announced a cease-fire. Because of the secrecy of the negotiations, nobody knew what was going in advance, and most of the Italian troops that were fighting with the Germans were taken prisoners, while the rest of the armed forces basically disbanded. German troops came into Italy from the North to occupy it, even as allied troops landed in Sicily and took control of most of Southern Italy. The king fled to the South, and the Germans freed Mussolini and installed him as head of a puppet government in the North.

With the Italian army disbanded, and with the allies neglecting the “Southern front” in Italy as they were plotting the landing in Normandy, guerilla groups were formed in Northern Italy to fight the Germans. Eventually, in April 1945 the German troops were retreating from the Eastern and Western fronts against the advancing American and Russian forces, and the allied made another push in Italy; concurrently, the resistance organizations planned an insurrection that, on April 25, liberated Torino and Milan. All the German forces in Italy surrendered on April 29.

The resistance was the training ground of some of the first generation of politicians of the new Italian Republic (a referendum to abolish the monarchy passed in 1946, and a new Republican constitution was approved in 1948), and it brought people who were willing to die for their ideals into politics. That spirit didn’t last very long, but it remains one of the few bright spots in recent Italian history.

On Berlusconi’s legacy

Here is the call for applications, from the official Italian web site of the Ministry for Education and Research, for a postdoctoral fellowship on a project titled “‘Dalla pecora al pecorino’ tracciabilità e rintracciabilità di filiera nel settore lattiero caseario toscano”, which roughly translates to “From sheep to pecorino, traceability in the Tuscan dairy industry.”

The announcement has an English translation, and something got lost in translation, having to do to the fact that in Italy we say “sheep style” instead of “doggy style” (don’t ask).

Update 2/16/2012: the page has been updated, below is a screenshot before the update (click to expand)

On Italy’s Embarrassments

If there is one thing that Italy excels at, it’s producing brilliant and handsome theoretical computer scientists, but if there are two things that Italy excels at, it’s producing brilliant and handsome theoretical computer scientists and embarrassing public figures.

When it comes to embarrassing public figures, one would think that a prime minister under trial for paying an underage girl for sex would be on top, but recently Roberto de Mattei has been working really hard and he deserves at least an honorable mention. Continue reading

Happy Sesquicentennial, Italy!

So your prime minister pays underage girls for sex, but you have given the word Enrico Fermi, Sophia Loren, Italo Calvino, Federico Fellini, Luigi Pirandello, early algebraic geometry, neorealismo and futurismo. I’ll call it a tie.

(Related memory: one night during STOC 1997 in El Paso, a group of theoreticians that included Daniele Micciancio and myself goes to Juarez, and walks into the one bar that didn’t seem to have prostitutes sitting outside. Daniele and I are talking, and the man sitting next to Daniele stares at us oddly. Finally, he asks what language we are talking in. “Ah, Italy,” he then says, “Paolo Rossi! Edwige Fenech!”)

What I miss: an incomplete list

I just returned from a trip to Rome. While there, I was asked by my friends what I miss most of Rome. Of course what one misses the most is the city itself. Anybody who has walked around, and gotten lost into, the side streets around via del Corso or Trastevere, especially in the late afternoon, when everything is bathed in an odd yellowish light, knows what I am talking about. One thing I don’t miss is Roman traditional food. Roman cuisine is one of the worst of Italy’s and a lot of its delicacies gross me out. One famous dish for example, la pajata, has been (and probably still is) illegal since the emergence of mad cow disease, because it’s made from veal intestines, including digestive juices. The matter of its legality has preoccupied Rome’s mayor to no end, and he has threatened “eat-ins” of pajata as acts of civil disobedience.

Back to the things I miss, in random order:
Continue reading

Graph Conductance and Gossip Spreading

Flavio Chierichetti, Silvio Lattanzi and Alessandro Panconesi, of the Sapienza University of Rome, have showed tight connections between the time it takes for a rumor to spread in a social network and the conductance of a network, in two recent papers in the past SODA and the next STOC. (The SODA paper is also notable for its “no thanks” section at the end.)

Flavio and Alessandro were recently invited on Italian national television to talk about gossip spreading in social networks, and the video (in Italian, no subtitles) is notable for Flavio writing, around 2:30, the formula for graph conductance on the “blackboard” provided by the producers.