Saturday, March 7, 2009

Writing blog entries is hard. I'm trying to remember how it was that I ended up being a Lisp hacker when I started out disliking the language and somewhat uninterested in computers. I'm also trying to understand why many, if not most of my classmates found '001 difficult, and Lisp to be confusing, annoying, and exasperating. And I'm trying to spin this into a somewhat coherent story.

I think I'm going to relax the coherence, though. I'm ending up with a pile of blog fragments that I can't seem to organize, but I don't want to lose them, either. Fortunately, this is a blog and no one expects particularly high editorial standards, so I'll just post some of these.

There were several great lectures in 6.001, but that first one was the most memorable because it showed me that real computer hackers weren't writing accounts receivable and inventory reporting programs but were having an awful lot of fun making machines do amazing things. I figured out that the more I learned, the more fun it would be. Each lecture re-confirmed that. I was hooked. I couldn't wait for the homework assignments because then I could get the computer to do amazing things, too. This had the added benefit that the lab was generally empty so there would be no wait for machines and I could spend extra time experimenting after finishing the problem sets.

(The recitations and tutorials, however, were a different story. Recitations were smaller classes of about 30 or so people where a graduate student would go over the material covered in the lectures and in the homework in much more detail. The tutorials were small sessions where a graduate student would give 4 or 5 students very detailed instruction and help on homework. The recitations were uninteresting, but it gave me a chance to make sure I understood the lectures and didn't miss any important points. The tutorials were deathly dull and I stopped going to those.)

One thing I enjoyed about the lectures was that I'd often find myself reconsidering math and physics from a very different viewpoint. The lectures and the text would frequently start with a very naive and unsophisticated model of a problem and then spend time refining it. On more than one occasion I'd get new insights into things I thought I already knew.

A couple of examples come from the second lecture. We were going to teach the computer how to take square roots. I had learned two ways to (manually) take square roots in high school. The first was a horribly complex process that was somewhat like long division, but was quite a bit harder. The second was to use a table of square roots and interpolate. I assumed that the table was laboriously generated the long way and that we were going to implement the long way on the computer. Instead we used Newton's method.

I remembered Newton's method from calculus, but it didn't occur to me that it would be a practical technique. Part of it was that Newton's method didn't give you the answer to the problem, but rather an approximation to the answer. I didn't think approximations would be acceptable. But the main point wasn't that we were using a particular method to solve a particular problem, but that we if we didn't know a good way to get the answer to a problem, we could try taking a random guess at an answer and get the computer to keep refining this approximation until we got an answer that was good enough.

The second example came from a demonstration of procedural abstraction. The lecturer (it was Hal or Bill Siebert, I can't remember) pointed out that many of the programs we had written had similar structure. I was expecting to be told about the ‘Symmetry Principle: Programs should be symmetric and uniform when performing similar functions, unless there is good reason to the contrary.’ Instead, the lecturer wrote an abstract version of the program where the varying parts were replaced by names. Then the several programs from before were easily changed into simple calls to the abstract version. The ‘symmetry principle’, which was so important to the previous computer course, was suddenly irrelevant. You'd never have programs performing similar functions if you simply abstracted out the similarity.

The lecturer went on to show how the Sigma notation from mathematics was just a way to abstract out repeated addition (no great revelation there, but a nice concise explanation). He then went on to show that once you had an abstraction like this, you could use it as a building block for other abstractions. He wrote an approximation of the definite integral using the summation procedure he just defined. I was impressed. I wasn't as blown away as I was on that first day, but still, in two days we covered the main points of an entire semester of calculus.

But it also helped me understand something that I didn't understand when I took calculus. My calculus teacher made a point of always constructing a Riemann sum before writing the integral equation. I didn't understand the point of this extra step because you aren't doing anything much more than just replacing the sigma with the big curly S --- what's the difference? In the code example, however, it was clear that we were computing a sum and the value of the sum depended upon how finely we divided up the elements. The more pieces, the smaller each piece, the more accurate the answer, and the longer it took to get the answer. Going from a Riemann sum to a definite integral involved taking the limit as dx goes to zero. This is an abstract process in mathematics, but a concrete one given our computer program. It was hard to see what could go wrong when replacing the letter sigma with the big curly S, but it is pretty easy to see that the program might not converge if the function being integrated is suitably perverse. What seemed like a pointless rewrite in the calculus course became a condition that had to be satisfied in order to run the program.

1 comment:

grant rettke said...

Your approach works well.

It is better to get your story out then worry about a its presentation. If it really bothers you; you can always make a revised post in the future.