A Concurrent Affair

Here is a raw transcript of my hand-written notes from the ACM Turing Centenary Celebration in San Francisco a couple of weeks ago.

Please note that these are my thoughts and impressions, not necessarily those of the speakers, and that it is quite possible that I misheard or misunderstood a few things, or that I incorrectly attributed the wrong person. If you think I made a mistake, please let me know.

Turing, the Man

• Turing was misunderstood and discriminated against. Who are the misfits now? Who should be supported?
• Turing’s mom thought the Turing Award maybe was an award given to long-distance runners. Turing was a runner.
• Apparently, none of the 32 Turing award laureates in the audience knew of Turing when they did their award-winning work? That is hard to believe. Knuth said he knew of Turing. Maybe I misunderstood the question.
• Knuth: Turing was the first person with the mind of a geek.
• Turing did things from first principles. That’s why Turing machines are more understandable than Church’s lambda calculus (says Dana Scott).

Human and Machine Intelligence

• Jim Gray: AI should speak like a native speaker, hear like a native speaker, and see like a person.
• Interesting definition: all humans can do that. But is this harder than playing chess or proving theorems? Interestingly, it is harder. The easy things are hard.
• Turing: We should build a “child machine” and educate it.
• Book: Human Problem Solving
• Emotions used to re-prioritize goals in multi-agent systems: agents behave better with emotions when there is a lot of uncertainty.
• Much human intelligence is stored, with fast recognition.
• Another reference to “Thinking Fast and Slow”.
• Raj Reddy: “When you have learned something, you store it so you can retrieve it instantly. You dedicate permanent memory to it.” Then why do we forget?
• Creativity: Brilliant move in Deep Blue vs. Kasparov, game 3. (look up)

What Computers Do: Model, Connect, and Engage

• Big data: physics, chemistry, biology, geology, social networks.
• But how much of the data is actually useful? “We only use 10% of our brains” myth, “We only use 10% of our bandwidth”.
• Connectivity, ubiquity, scaling, approximation, AI, reusable components, dependability, uncertainty: key concepts.
• Probability distributions, parameterized over the main, like lists, as standard data type?
• Catastrophe mode – few dependencies on a “catastrophe computing base”, similar to trusted computing base. Make tough choices, but keep your service going.
• Swap people between security and attackers is a good idea.
• Butler Lampson: “A new TCP connection for every mouse click? Madness!”

Systems Architecture, Design, Engineering, and Verification – The Practice in Research and Research in Practice

• Would Turing machines have had the same impact if it had many instructions as opposed to just a few, elegant ones?
• Biggest advances since Turing: operating systems, programming languages, networks.
• Future? Not so rosy, says Thompson.
• 50s: computers were accessible
• 60s: had become inaccessible because of economic concerns and batch computing
• Formal verification: Turing 49 paper, “Checking a Large Routine”
• What makes research practical?
  • Thompson: right people, right time
  • synergism, backing the right people, not just concrete goals
• “Nice theory symptom” – we often like a nice theory, ignore practical problems and needs
• Most software (e.g. incrementally written software) is difficult to verify.
• Airbus software is completely verifiable by design/

Extracting Energy from the Turing Tarpit

• 67% of fossil fuels are burned to create electricity.
• Think of our real goal. We don’t want to create electricity, we want to do something with it. Similarly: our goal is not to write millions of lines of code.
• Alan Kay: “The easiest way to predict the future is to prevent it.” – Lots of things that barely scaled when they were invented are still around and still do not scale.

The Turing Computational Model

• Widening gap between users and programmers. Users’ expectation and programmers accomplishments.
• 1960s customs are a source of bugs. We don’t see them as just customs, though, we see them more as “laws”.
• 
• 
• Big-oh does generally not take into account communication costs. What if communication costs become dominant, or if it can break down?
• Vivek Sarkar: “What about energy? It seems like the Turing model is good to account for energy, as it takes energy to move the tape.

Computer Architecture

• Sutherland: communication dominates logic in hardware; we must begin to use clock-free designs.
• Fred Brooks: Turing’s ACE Pilot architecture assumed hardware is expensive and dear, and programmers are abundant and cheap.
• Chuck Thacker: “Cutting it [knowledge about the way computers work] off at the C computer level seems limiting.”

Programming Languages – Past Achievements and Future Challenges

• Nicklaus Wirth: “We don’t teach programming anymore. Students come to university already knowing it.” Really? IT seems like he is talking about wasteful programming.
• Liskov:
  • programming methodology first; then maybe find some programming language features that help.
  • Software architects: “Settle on a simple memory model. If all we can do is put in fences because we can’t reason about it, we haven’t achieved much.”
  • We now teach with Python. We may create a generation of programmers who don’t understand the importance of modularity.
• Wirth: “Vicious cycle between language used in academia and industry; can only be broken at the university.”

An Algorithmic View of the Universe

• Valiant (?): Turing pointed out “cultural search”, how science progresses.
• CS undergrads not interested in natural science applications. Should there be an explicit unit that introduces them to science applications?
• Karp:
  • “In biology, form is function. Protein folding determines what the protein does.”
  • X-ray crystallography vs. computed folding:
  • Computed folding is computation; therefore, X-ray crystallography is too.
  • Figuring out folding is NP-complete ==> X-ray crystallography is NP-complete
  • How long will it take for a protein to fold? CS can tell biologists: exponential time!
• Adleman:
  • Learned a lot about being a computer scientist in another field. Biologists don’t talk our language. It’s easy to solve the wrong problem.
  • Biologists may want a sample of not-quite-optimal solutions, but faster.
  • CS can contribute a lot with its “algorithmic lens,” but we need to meet with our “customers.”
• Tarjan: learn with skepticism, challenge your instructors and the papers you read — that’s where you’ll find problems to solve.
• Union set: O(inverse Ackerman) – crazy but true
• Can another Turing come along? “Yes. It’s not so important to know everything, but to have the ability to understand everything.” And perhaps to know of everything.
• Favorite algorithms: Shrinking blossoms algorithm (look up)
• Hungarian algorithm for assignment problem
• Is the strong Turing thesis enough to preclude time travel?
• Least favorite algorithms: Adleman, genetic algorithms. “We don’t understand the problem, so we hope the computer will understand.” Genetic algorithm idea taken from biology; why assume that the problem space is the same? But if it works (well enough)? Who says genetics in biology (mutation, sexual reproduction) is the best way to evolve?

Information, Data, Security in a Networked Future

• Shamir: “Codebreakers at Blethley Park not a victory of human brilliance over machines, but a victory of machine power (exhaustive search) over human stupidity (Enigma operator mistakes).”
• Rivest: “Calling a string ‘secret key’ does not make it secret.”
• Maybe we need an attitude adjustment: secret keys are secret most of the time. Users don’t make errors most of the time. That helps recover.
• Many security problems are caused by human error. What can technology do to make humans more trustworthy and compliant?
• Privacy/trust in social networks: needs to be an open architecture.

Again, these are my notes. In particular, all mistakes are mine. Caveat lector.

I absolutely love my Kindle Touch. I’ve already read two books, which embarrassingly is as much as I read all last year. I was skeptical about how easy it is to read, but it’s just as good as reading on paper. Perhaps better. I also would have expected that I’d be more careful with an electronic device, but interestingly, it’s just the opposite: I put it in my pocket, because I’m not worried about bending or tearing pages.

I also bought Legend of Grimrock a couple of weeks ago. Tonight, I finally installed it, and it looks and plays great. I think it could turn into another addiction. You can’t imagine how big this is: It’s the first video game I’ve bought in probably 15 years.

On Wednesday night, I went to Chez Shea in Seattle for dinner. It was fantastic. The food was delicious, and our waitress was great: knowledgeable, polite, attentive, but not pushy.

As appetizers, we had new potatoes and braised fennel salad with tarragon creme fraiche, pickled mustard seed vinaigrette and frisee; as well as Gruyere, spring onion and mushroom tart with baby arugula and jicama salad. The new potatoes were simple, clean, and appealing, and the Gruyere tart was decadent and rich.

Because our next dishes were running a bit behind, we got to try English pea soup, which had a hint of mint in it.

As main course, we chose pan-seared sockeye salmon on green lentils, shiitake mushrooms with bacon, rapini and caper brown butter; and potato gnocchi
with parsley and arugula pesto, roasted tomatoes, parmigiano reggiano, and toasted pine nuts.

Desert chocolate mousse and vanilla creme brulee. As drinks, we had a glass of La Chablisienne, a 2010 French Sauvignon Blanc; a glass of Chateau d’Oupia, a 2010 French Carignan/Syrah/Grenache blend; as well as something called “French Connection”, which was an mandarine-orange flavored drink with green chartreuse in it (can’t find the recipe for that version).

It was a fabulous meal and a great evening. Chez Shea could easily be my favorite Seattle restaurant. Unfortunately, it is closing at the end of this month. So it goes.

Weather forecast for Seattle:

Showers likely. Cloudy with chance of rain in the evening. Then rain likely after midnight.

I’m not even kidding. Those are the first three sentences of the current weather forecast on my phone.

Something anyone writing a paper or doing a presentation needs to keep in mind: Communication.

Here’s the mouseOver text for the image: “Anyone who says that they’re great at communicating but ‘people are bad at listening’ is confused about how communication works.”

Thanks, xkcd.

The accident last week was the second time that I was involved in a car accident (it happened more often if you count cars hitting me on a bike).

The first time, a Houston rapper rear-ended my friend’s car, with my friend and me in it, and totaled it. He had an insurance card that he handed over, but what we didn’t know was that he had canceled the policy. He had had enough money to buy his new car in cash, but then he was too stingy to have the legally-required insurance.

You suck, man.

The accident last week wasn’t nearly as bad. Some people might not even care. There is some bent metal on the fender and a bunch of long scratches. The woman gave me her insurance card and her phone number. I talked to her insurance last week, but they didn’t get anywhere, because the phone number they had wasn’t working. I tried calling her, and it was the same number. She had given me a phone number that didn’t work.

That sucks too.

I tracked her down on Google and called her at work. I’m glad she honored my request to call her insurance as soon as possible. She acknowledged she was at fault, and now I can go get an estimate. She stunned me a little, though, when she grumpily said “I’m disappointed you got the insurance involved. I wish you had just gotten an estimate, and I would have paid for the repairs.” Tough luck, missy.

A co-worker of mine had the perfect response. He asked, “Did you say ‘I’m disappointed you hit my car’?” I wish I had.

At work, we deployed the latest version of our code on Wednesday night. It included a new query language. We used ANTLR to do the parsing.

We had never tested the new queries in a production setting, but the deployments to our Alpha, Gamma, and two regional clusters worked without problems. A few hours after deploying to the last clusters, a customer started using it, and that’s when all hell broke lose. I ended up rolling back to the previous version at 4 AM on Thursday.

A quick analysis by my coworkers yesterday showed that most of the time was spent doing the parsing.

The grammar that we used was essentially this one, which required backtracking by ANTLR:


E ::= ( E )
| C
C ::= ( E and E )
| ( E or E )


We never even let our test query finish, but it had been running for 45 minutes non-stop. I suggested a small change, which amounted to something like this:


E ::= ( E R
R ::= )
| and E )
| or E )


Sometimes it is helpful that I spent grad school in the programming languages group.

The parser that ANTLR generated now parsed our test query in under a second. Sure, we changed an LL(*) parser into an LL(1) parser, but I never would have thought that changing the grammar could result in an improvement by a factor of 2700.

via xkcd: Citogenesis.

Something similar actually happened with the Karl-Theodor zu Guttenberg, who used to be the German Minister for Economics and Technology and later the Minister of Defense, before it became clear that he had plagiarized his doctoral dissertation.