This is extremely exciting for me: Researchers at MIT have done some studies on the feasibility of using natural English for programming, and it turns out the feasibility seems to be surprisingly high. In fact, they already have a working prototype program called "Metafor" which can generate object-oriented Python code given natural English descriptions. You've got to see the video, especially if you're a programmer, and even more so if you know Python. It's simply amazing.

Now I can't say how much, if any, of that video was "faked", but based on the researcher's blog, it sounds like it's not being faked at all. In Hugio Liu's paper, Liu being the head of the research team, he gives two examples. An idealized "this is what I want my final program to be able to do" example in which a user programs a PacMan game using only natural English, and a concrete "my program can already do this" example in which a user writes a program which simulates a bartender at a bar serving drinks.

Previously, AI researchers believed that being able to "understand" natural English was AI-complete, which means that if you solve this problem, you've solved all of AI (or equivalently, it means that this is one of the hardest problem in AI). Liu points out though that while it may be difficult (as in AI-complete) to be able to understand any meaningful English utterance, from a practical standpoint, a computer is able to extract a lot of useful data from common, simple phrases. In fact, if a user knows that she is having a conversation with a computer, and avoids using complex metaphors for example, it seems feasible for a computer to understand everything the user says completely.

The dream is to create the ultimate user-friendly interface. Rather than having the user learn and memorize movements as representations for abstract metaphors, like "clicking means selecting something, double clicking means initating something, shift-clicking means exanding a selection in a rectangular region, etc.", you just tell, in natural English, what you want the computer to do. Rather than you learning how to use your computer, your computer will understand you.

In the bartender example, the user types in "There is a bar with a bartender who makes drinks.", Liu's Metafor program is able to determine: There is a bar; A bar has something called a bartender; There is a bartender (implied); a bartender can make drinks. Note that the pronoun "who" is resolved to refer to the bartender, and not the bar. This is because Metafor has a "common sense" database that lets it know that bars are inanimate objects, while bartenders are animated objects.

This "common sense" database is an web-based volunteer project based on ConceptNet which already has a million assertions on everyday life, things like "cooking typically happens in a kitchen". Metafor probably also has a English dictionary packed somewhere in there so that it can recognize which words are nouns, verbs, and so on, but I didn't notice any mention of this in Liu's papers.

The bartending example continues with the user entering text such as "The bar has a menu containing some drinks, which include: a sour apple martini, a margarita, and rum and coke. When a customer orders a drink, the bartender tries to make it. When the bartender is asked to make a drink, he makes it and gives it to the customer only if the drink is in the menu's drinks; otherwise, the bartender says "Sorry, I don't know how to make that drink" to the customer." and Metafor is able to produce the appropriate Python code.

In the PacMan example, Liu shows that his plan is to have the user and the computer have a conversation about the program. The user makes statements that describe what kind of program she wants, and the computer asks for clarifications, and shows code asking "Is this what you want?". This goes back and forth until the user is satisfied with the resulting program. This implies that the user needs to know how to read a programming language, even if she doesn't know how to write one herself. Liu's PacMan example follows:

User: We're going to program a game, Pac-Man.

System: OK. I know a few things about how to make games. We need to decide what the playing field looks like, design some characters for the game, how the users are going to control the characters, and how the scoring system is going to work. OK?

U: Sure. The yellow dots are set through a maze, and Pac-Man, the chomping yellow circle, has to collect them.

S: OK, let me see if I've got this straight. You want the playing field to be a grid of squares, each containing a yellow dot, right? (System displays a grid of squares with yellow dots). To make it a maze, we need to have some walls. Can you draw some walls for me?

U: (User draws in walls, selecting color, texture, etc.)

S: Pac-Man is the name of a character in the game, represented as a yellow circle, is that right? How's this? (System displays a yellow circle in one of the grid squares).

U: Oh, the dots should be red. (Things don't have to be done "in order". You can refer to something previously said.)

S: OK. What does it mean for Pac-Man to "collect" a dot?

U: Whenever Pac-Man is on a square with a dot, he eats it. That means that the dot is gone and the player gets another point. (The system introduces a variable to count the number of dots eaten by Pac-Man).

S: OK, now I don't understand what "eats" means. Can you explain it?

U: When you draw Pac-Man, you alternate between a picture of Pac-Man with his mouth open and a picture of Pac-Man with his mouth closed.

S: Can you draw me what Pac-Man looks like when he has his mouth open? Mouth closed?

U: (Draws.) There are blinking big yellow dots that allow you to eat the ghosts (draws picture of ghost).

S: (Continues dialogue about dots and ghosts...)

Currently, Metafor isn't sophisticated enough to form questions to ask for clarifications. However, it is capable of explaining what it's doing, so that the user can check if the computer understands what was said. In the bartending example, as the user describes the program, the computer responded with the following:

User: There is a bar with a bartender who makes drinks.

System: OK. I create a new thing called bar within __main__. I changed bar into a structure. I augmented bar with the part: with bartender. I created an object called bartender within __main__. OK. I added the ability for bartender to make. The bartender can make using drink.

While the system's responce is a bit jarring for an English speaker, if you actually examine the Python code the system produced, you can see that the system did indeed fully understand the specification. Here's the python code, for the curious.

Again, I must say that this is utterly spectacular. We computer scientist debated whether generating programs from natural English was even possible, and here Liu comes along, not only answering "yes, it's possible", but actually gives a working implementation! For what it's worth, an article in the TRN claims that Liu's research will be complete around 2010. If this progress rate continues, I'm optimistic about having StarTrek level conversations with my computer within my life time.