How Complex is "Personal Computing"? – by the Fine Folks from VPRI

Alan Kay, of Smalltalk fame, and a few of his colleagues from Viewpoints Research Institute gave two wonderful talks at the Computer Science department at UIUC today. It's been a while since I have heard such interesting and inspiring talks so I'd summarize them for you :-)

How Complex is "Personal Computing"?

The video is now available from here.

This was a joint talk by four people:

Alan Kay

Alan started the talk by asking a simple question: how large a t-shirt would we need to contain the essence of Computer Science?

It's a serious question. The foundations of electromagnetism is contained in Maxwell's equations which can easily fit onto a t-shirt. What about Computer Science? Imagine trying to fit the source code for Microsoft Windows onto a t-shirt. How many t-shirts would we need?

With that in mind, the folks at VPRI are trying to find those fundamental equations for computer science as well. Three of his colleagues present their attempts at three different domains.

Dan Amelang

If you have seen the algorithms and code for doing antialised rendering, you'd know that it's a very complex component. However, it's also a very important component for computer graphics. Almost everything that we see on our screens now is antialised.

How would we describe the fundamentals of antialised rendering in simpler terms? Dan has come up with a set of basic equations to do that. And he even created a domain-specific language called Nile to make it easier to describe those operations. For a glimpse of Nile (and I don't claim to even understand most of it), you can peek at Dan's code on GitHub.

Nile is still work in-progress; to compile it into executable code builds upon the work done by ...

Alex Warth

Alex is the creator of OMeta – an object-oriented language for pattern matching. In short, it's a language for rapid prototyping of languages. OMeta allows you to easily model existing programming languages and also create new ones easily to enable you to experiment with new features instead of messing around with different lexers, parser, code generators, etc.

By applying Occam's razor to computer languages, Alex hopes to enable everyone to easily grasp the fundamentals of one of the most important components of Computer Science: expressing your ideas in ways that the computer can understand. OMeta is succint, you can express a good portion of javascript in less than 200 lines. And like all good metalanguages, OMeta can be used to describe and bootstrap itself.

You can try out the Javascript version of OMeta here. I also strongly recommend reading Alex's thesis (very readable and very interesting as far as Ph.D theses go) where he talks about OMeta and some of his other work.

Hesam Samini

Hesam is tackling the problem of program correctness using executable program specifications. What I really like about his work is the idea of using program specifications to fix program behavior whenever possible.

Most unit testing today try to test what can go wrong with your program and how your program would handle those aberrant behavior. However, it's very hard to specify everything that can go wrong. It's much easier to say what's the intended behavior of a program. And once you have that, if you ever violate what is means to behave correctly, you can use that correctness specification to guide your program back to correctness.

There are many ways to try to correct your program. Here's my example on this: take the case of a malformed string; perhaps the user accidentally puts a space i the string. A naive way would be to randomly just permute the string until you get a version that is right and fits the constraint of correct behavior. A smarter way might be to apply delta debugging to find the cause of the problem and then rectify it. Or you can try the techniques that Martin Rinard uses for rectifying bad input for email messages..

In either case, specifying the correct and intended behavior in your program allows people to understand it more easily. Compare this with the arduous task of having to read through lines and lines of if...else and exception handling and having a hard time understanding the crux of your program.

Normal Considered Harmful (Or, How Much Like Frogs Are We Computerists?)

This was the second talk by Alan which was intended for a more general audience. This talk was recorded and is available from here.

Anyway, here are the three main points that I liked from the talk:

Learning from History

According to Alan, if you show people the picture above, they would most likely know that it's a picture of Albert Einstein. Show them the picture below and many won't know that it's a picture of Doug Engelbart, the inventor of the computer mouse among other things. Why is it that Computer Scientists don't know the historical figures in their field?

And because we don't bother learning about our history, we miss a lot of grand ideas that came about in the 60s. Here, most of us are spending time reinventing the wheel and not even doing a very good job of it. The ideas from the 60s were revolutionary (pun intended); the ideas of today pale in comparison. We aren't daring enough to explore. And because of that ...

We Aren't Solving the Important Problems

Research today is very parochial. Look at the papers at most conferences. It's almost like they follow some cookie cutter template: problem(a cleverly invented one sometimes that no one really cares about), motivation, solution, case study, evaluation. Researches pat each other's back for solving related problems. However, look closer and you would see that the problems being solved are small and narrow. The big picture is missing.

People aren't exploring revolutionary ideas because the system (tenure, conference acceptance, funding, grants) doesn't welcome those ideas. Doing something revolutionary is risky. Of course it is. So people do the easy things and never explore beyond their fields. They become complacent. Instead they need to see that ...

All Understanding Begins With Our Not Accepting The World as it Appears – Susan Santog

We need to be bolder and explore more. We need to come up with ideas that border on the insane. Some insanity is required. After all, only 1% of the population comes up with such ideas; the other 99% like to keep things in order as they are now. So it's up to those 1% to come up with new ideas that the other 99% will eventually accept.