Language design

I’m too busy to pursue this blog further, but i just got one more reply to my big question from Paul Graham.

Sorry to be so long replying. It was largely because I wasn’t sure what to say. But one answer just occurred to me: inventing the concepts people make programs out of. Aka language design.

Long it was. I wrote him Aug 24, 2007 and he replied yesterday. Amazing that someone doesn’t just forget about an email after all this time.

If you don’t know him, the language design he talks about is Arc and i know him, because of his great essays. At least his older writings are good. The newer stuff doesn’t always reach the old quality.

Don Knuth on progress in computer science

This blog led me to a premiere: My first letter written with TeX. Guess whom I sent this letter? Don Knuth, inventor of TeX and author of The Art of Computer Programming. His answer looks like this:

He corrected my use of the quotes and then goes on to reply to my question “what are the most important problems in computer science?“, inspired by a talk of Richard Hamming.

I admire Dick Hamming enormously, but I disagree that his first question is “good”. Everybody knows famous, unsolved, “big” problems, which tend to be thought important because of their fame. And perhaps those problems are indeed important … although when they are finally resolved (like the question of deciding equivalence of deterministic languages) I find to my surprise that I don’t get very excited by the result, rather by the method used to get there

I firmly believe that computer science advances by thousands of people solving small problems, which go together and create a massive edifice. Every year that goes by, hardly anything is done that appears to be a milestone worthy of mass attention; yet after five or ten years pass, the whole field has changed significantly. So I’m no fan of “top ten” problem lists.

Let’s hear it for the people who work on and solve small problems based on their judgement of peer pressure. Like for example Hamming.

I agree that the progress in year seems insignificant, but I don’t want to agree that we can’t see where we’re heading with computer science. This blog is my try to get an overview, to get a form stand on the shoulders of the giants and see a littler further.

About the most important problem in computer science

This blog was founded to collect answers to one question. Richard Hamming asked it in his speech “You and your research”. His talk was more general, but it is a really good question and i applied it to my field.

What are most important problems in computer science?

I sent out lots of email to famous and not so famous people. You can read all replies on their own, but this is my try to summarize them all. I don’t think i’ll get much more responses to the emails, i sent for now.

The big problem is complexity. Computers are a bicycle for your mind, so we can tackle more complex problems. The tools to these problems naturally are complex, so users get easily confused. The results are buggy programs, distressed users and wierd interfaces. “In spite of great advances, programming is still too difficult and machines are still too hard to use“, Kernighan wrote.

Prof. Tichy maps out the goal like this:

When everybody doesn’t just use a PC, but commands it [...]. Only then computer science has fullfilled its potential, which is to free humanity from tiresome, boring, error-prone and dangerous work.

There are some really annoying problems on the way to simplicity. Prof. Adleman mentioned the famous P=NP problem. Joe Armstrong remarked that we don’t really know how to store and how to find things. For Prof. McCarthy the tangible path is “getting interactive provers for showing that programs meet their specifications and formalizing common sense knowledge and reasoning in mathematical logic“, thus improving our mind tools.

It’s not easy to discover how the computer can work for us. If we have figured this out, we need to “make everything as simple as possible, but not simpler” (Einstein), because “simplicity is the ultimate sophistication” (da Vinci).

We’re still working on operating systems, compilers, languages and algorithms, because haven’t got them right so far.

As a student of computer science i want to find my personal attack vector to the big problem, but how to find that? Philip Greenspun presented a nice thought experiment: The Fantasy Research Lab

Do you miss anyones reply? Tell me! I’ll try to contact them. Also write me your own answer!

Dealing with complexity

Mark Chu-Carroll has a really cool blog. If he doesn’t blog, he works for Google. Here is his answer to my Hamming question:

I’ll do my best to answer. By necessity, I’ve got to be a bit vague, because I don’t want to give away any google secrets.

First, I need to draw one important distinction. Computer science is too broad – there are lots of different areas, and I don’t think I can pick exactly one of them that’s clearly more important than the others. So I’ll arbitrarily pick the one that I know best: software engineering.

So – what are the most important problems in software engineering? I’d answer “dealing with complexity”. Software is frighteningly complex, and becoming moreso by the day. The editor that I use for programming has reached more than 2 million lines of code – I don’t think that there’s any person in the world who actually understands the whole thing. And that’s just a programming tool! Imagine the complexity of the things we build with it! Software is now built by groups of people, and no one person can understand all of the details. It’s built for hardware that people can barely program themselves (if they can do it at all!). It’s built to run scattered around huge numbers of machines around a network (the mail client where I’m writing this is running partly on my computer, partly on a web server at google, and partly in a mail database server.)

What do I do? I’m a toolbuilder. I make tools to help software engineers deal with complexity. Over the last few years, I’ve worked on SCM systems – which are tools that help groups of engineers deal with the complexity of working together. I’ve worked on programming environments – which are tools that help individual programmers deal with the complexity of understanding systems. And I’ve worked on build tools – which are tools that help deal with the complexity of assembling a large system from many small parts.

So what I do is a small part of trying to solve the biggest problems in software engineering. I don’t want to sound too egotistical – it is a *very* small part of a *very* big problem, but it’s the part that’s interested me from the first time I saw a computer, and I’m very proud to be contributing to it, even in a tiny way.

Working on the tools really isn’t a prominent job, but important none the less. Researchers may write prototypes and evaluate them for papers, but it needs more people to make real, useable programs out of that. When the programs are written we need even more people to maintain, adapt and debug those programs.

How to find and how to store?

For readers of programming.reddit at least, it’s clear that Erlang is gaining momentum. Erlang is a programming language + virtual machine environment for extremely concurrent and fault tolerant software. It was built for the telecommunication branche and the lead scientist is Joe Armstrong.

Nice to hear you quoting Hamming – I often ask students the same questions!

The most important things:

• how to store things
• how to find things

By store I mean store forever – things like backup and syncing systems should not exist and are a consequence of a broken storage paradigm.

Once we have stored things we need to find them.

We need to understand how to make systems that run forever and evolve with time.

Am I working with these? – Yes and no. I keep coming back to them, then get stuck and work on something else, then go back to them.

The A in RSA

The RSA algorithm for public-key encryption is used practically whenever a secure connection must be established. The A in RSA is Leonard Adleman. He recieved the Turing Award for this work. He is also doing lots of rather theoretical stuff with DNA.

His reply to the Hamming question is:

Your question is a good one and to give a complete answer would require more time than I currently have; so I will just provide a brief remark:

1. NP≟P (or some varient of it) is the most important open problem in CS. It is also on the short list of most important open problems in mathematic (see the Cole prize).
2. I don’t work on it for 2 reasons. First, I did work on it for a few years as a youth, I had a few ideas worth (I thought) writing down (see “Time Space and Randomness” by moi), but ultimately I came to the conclusion that the problem was not “ripe” – ready to be solved. A few more decades (at least) of research would be required. It is for this reason that I changed my research to work on Fermat’s Last Theorem instead. My intuition suggested that, after 3 centuries, the problem was ripe. When Andrew Wiles proved FLT a few years ago, my consolation prize was to know that at least my intuition was correct.

Adleman is the first to respond with the P=NP problem. Is the P≟NP problem more a prestige problem than a theoretical one? Whether the result is useful depends on the answer. So we don’t know how important it is.

Create your own Fantasy Research Lab

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

If you read about Lisp, it won’t take long until you come to this quote. It’s from Philip Greenspun, who worked with Lisp while it was popular. Later he was one of the first internet entrepeneurs and founded photo.net and built the ArsDigita Community System.

Today he spends his time teaching helicopter and computer science students, taking photos and traveling. He response came from Africa.

I wrote

http://philip.greenspun.com/research/fantasy/

back in 2003. I don’t think too much has changed since then.

I haven’t read this before. It’s a nice thought experiment.

New graduate students in computer science often have a difficult time choosing among research projects and may never develop a broad view of the field nor think about the relative significance of efforts in various directions. When new graduate students ask me for advice I tell them to start by pretending that they are the lab director for computer science at a brand-new research university and to come up with a plan for how they’d populate their lab with projects. This is sort of like the fantasy baseball leagues that are popular with kids, hence the page title. In preparing a fantasy research lab plan, a student will need to familiarize him or herself with a broad range of problems and the current state of the art in solutions. This ought to give the student more perspective in planning a career.

He goes on and develops some projects and what research is needed for them.

I would add making

http://philip.greenspun.com/business/mobile-phone-as-home-computer

a reality would be a very useful problem too, though not fundamental. Consumers shouldn’t have to use scaled-down mainframes such as Windows and Mac OS.

His second link leads to a lengthy description about a phone-centric distributed computing thing.

Personal Research Agenda

I found Brad Neuberg wrote a blog entry, where he ponders about the exact same question as i am doing here. He has a list of things, he considers important.

1. What does a true, next-generation Internet word processor look like, one that deeply embeds the browser and community?
2. Is it possible to continue creating radically new versions of the web and browsers that introduce fundamental new advances?
3. The flip side of the previous question is: How far can we push the present generation of web browsers from the inside through clever tricks?
4. How can we create communication technologies that provide ever greater levels of interpersonal connection, collapsing the geographical distance between loved ones and family?
5. How can we create email systems that almost completely eliminate email from your life, allowing you to focus on the emails that you need to with as little time invested as possible?
6. How can we create search systems that make answering our questions even more intuitive and integrated then they are now?
7. Can we create hypertext technologies that transform how we link and talk about information and documents? Further, how can we port these hypertext technologies to the contemporary web so they are actually adopted?
8. Handling events still sucks — how can we make scheduling and discovering events that are important and relevant to you and your groups suck much less than it does now?
9. How can we be more effective at creating ideas?
10. Can we create technologies that are as fundamental and important as writing has been?

That’s quite web centric, but we agree that it is important to think about this.

I’d love to see others create similar lists on their own blogs. One of the reasons for posting this list is I want to attract others who are interested in similar things, so we can brainstorm about them over a strong cup of coffee (or a strong Guinness).

Me too! I just have no list of my own, yet.

The spec and the knowledge

The Lisp programmers claim that nearly every programming technique in the universe was first invented by them. Lisp is one of the oldest programming languages still in use. It was invented by John McCarthy in 1958 for his AI research. In 1971 McCarthy recieved the Turing Award for his major contributions to the field of Artificial Intelligence. Since 2001 he is Professor Emeritus of Computer Science at Stanford University.

McCarthy emphasizes mathematical logic in his research and his answer to my Hamming Question mirrors that. His email reply:

Two of the most important problems in computer science are getting interactive provers for showing that programs meet their specifications and formalizing common sense knowledge and reasoning in mathematical logic. I work on the latter. Arguments for the importance of these problems are in the articles reprinted on my web site.

This conforms with his article AI Needs More Emphasis On Basic Research from 1983:

In my opinion, the key problem at present is the formalization of common sense knowledge and reasoning ability. It still looks to me that separating epistemology from heuristics will pay off.

AI research has changed in the last twenty years. Today it is mostly about heuristics (perceptrons, bayesian filters, …) and we still have no model for human knowledge. We can’t measure knowledge and experience. I don’t even know about any ideas how to attack this problem.

We also won’t reach human level intelligence by building larger and larger production systems involving more and more facts all on the same level.

You can build pretty impressive things this way, though. Google is the prime example for this.

No idea, but it’s interesting

Turns out i’m not the only one on this quest. Simon Peyton-Jones wrote back:

I wish I knew what the most important problems are. Then I could work on them.

What I do know is that functional programming is full of interesting problems. I hope they will turn out to be important too, but you only know for sure in retrospect.

Peyton-Jones is the principal designer of GHC and works at Microsoft Research. I recently read one of his papers on Software Transactional Memory and i think he does good work.