The Snowtide Blog

This week, I find myself lucky enough to be at the International Lisp Conference at MIT in Cambridge, MA.  I won’t get into why I’m here right now, for those of you who might be surprised.  The purpose of this post is simply to paraphrase what Gerald Jay Sussman, one of the original creators of Scheme, said yesterday in an a brief impromptu talk about why the computer science department at MIT had recently switched to using python in its undergraduate program.  This change is something that was widely panned when it was announced by many people all across the programming and computing world from various disciplines, so it seems worthwhile to try to document what Prof. Sussman said.

(The impromptu talk happened much after Monday’s formal talks and presentations, and I don’t think that anyone was recording Prof. Sussman’s remarks.  If anyone does have a recording, by all means, post it, and I’ll link to it here — and probably just drop my paraphrasing.)

This is all from memory, so I’ll just apologize ahead of time for any errors or misinterpretations I propagate. If anyone has any corrections, by all means, leave a comment (try to keep your debate reflex in check, though).  In a couple of places, I’ve added notes in italics.  Just to keep things simple and concise, the following is written in first-person perspective:

When we conceived of scheme in the 1970’s, programming was a very different exercise than it is now.  Then, what generaly happened was a programmer would think for a really long time, and then write just a little bit of code, and in practical terms, programming involved assembling many very small pieces into a larger whole that had aggregate (did he say ‘emergent’?) behaviour.  It was a much simpler time.

Critically, this is the world for which scheme was originally designed.  Building larger programs out of a group of very small, understandable pieces is what things like recursion and functional programming are built for.

The world isn’t like that anymore.  At some point along the way (he may have referred to the 1990’s specifically), the systems that were being built and the libraries and components that one had available to build systems were so large, that it was impossible for any one programmer to be aware of all of the individual pieces, never mind understand them.  For example, the engineer that designs a chip, which now have hundreds of pins generally doesn’t talk to the fellow who’s building a mobile phone user interface.

The fundamental difference is that programming today is all about doing science on the parts you have to work with.  That means looking at reams and reams of man pages and determining that POSIX does this thing, but Windows does this other thing, and patching together the disparate parts to make a usable whole.

Beyond that, the world is messier in general.  There’s massive amounts of data floating around, and the kinds of problems that we’re trying to solve are much sloppier, and the solutions a lot less discrete than they used to be.

Robotics is a primary example of the combination of these two factors.  Robots are magnificently complicated and messy, with physical parts in the physical world.  It doesn’t just move forward along the ground linearly and without interruption: the wheels will slip on the ground, the thing will get knocked over, etc.

This is a very different world, and we decided that we should adjust our curriculum to account for that.  So, a committee (here, Prof. Sussman peaked his hands over his head, which I interpreted to indicated pointy-headedness) got together and decided that python was the most appropriate choice for future undergraduate education.  Why did they choose python?  Who knows, it’s probably because python has a good standard library for interacting with the robot.

That is my best paraphrasing of Prof. Sussman’s remarks.  I spoke with him briefly earlier today, primarily to ask his permission for me to post this sort of first-person paraphrasing; he replied: “Sure, as long as you paraphrase me accurately.”  Hopefully I succeeded; I’ll mention again my solicitation for corrections in the comments.

As a short addendum, while I had Prof. Sussman’s ear, I asked him whether he thought that the shift in the nature of a typical programmer’s world minimizes the relevancy of the themes and principles embodied in scheme.  His response was an emphatic ‘no’; in the general case, those core ideas and principles that scheme and SICP have helped to spread for so many years are just as important as they ever were.  However, he did say that starting off with python makes an undergraduate’s initial experiences maximally productive in the current environment.  To that, I suggested that that dynamic makes it far easier to “hook” undergrads on “computer science” and programming, and retaining people’s interest and attracting people to the field(s) is a good thing in general; Prof. Sussman agreed with that tangential point.

I’m generally not one to be impressed by celebrity — you won’t catch me reading People or US Weekly, example.  However, this morning I noticed with a shimmer of glee that Peter Norvig used some code that I wrote years ago in one of his recent projects.  So, just for the record, if Dr. Norvig ever shows up in US Weekly, I’ll pick one up!

In case you don’t know, Peter Norvig is the Director of Research at Google.  That’s interesting, but the real reason Dr. Norvig holds sway with me is his classic book, Paradigms of Artificial Intelligence Programming.  If it weren’t for that book, I almost certainly would not be doing what I’m doing today.  Its pages are where I came to understand lisps, and began to imagine what was possible and what I might be able to accomplish in computer science (final results yet to be determined, of course).  For that, I am extraordinarily grateful to him (and others, of course, but I’ll wait to talk about them when they get around to using some of my code! ).

Back to the story.  This morning, I decided to hop onto Google Analytics for a bit to check up on the traffic stats for our various websites.  Lo and behold, in the “top referrals” listing, I saw ‘norvig.com’; “Well,” I thought to myself, “that’s interesting!”   A quick grep of the server logs (is there a screen in Google Analytics that actually provides you with the full referral URLs?) showed the referral URL to be Dr. Norvig’s “post” from last week, An Exercise in Species Barcoding.

A search of my name on that page shows that he needed a way to calculate the Levenshtein distance (also known as the edit distance) between two large strings — his quick implementation (like most) operated in O(n^2) space, which would have required weeks of processing time in his particular case.  So, he looked around for a more efficient implementation, and found one that I wrote in October of 2003 that operated in linear space bounds (and was, ironically enough, my first-ever contribution to an open source project).  With a couple of tweaks to suit his specific needs, the code I wrote worked out nicely for him.

This story is satisfying and funny (for me, anyway) in a couple of different ways:

First, there’s the fact that (what I would now consider) throwaway work of mine floating around the nets six years later.  Remember kids, the Internet never forgets!

Second, it reminded me of what I was doing when I wrote that particular code.  I was building what would later become PDFTextStream’s first ground-truthing system¹ (although I don’t think I knew of that term at the time). It’s a lot more sophisticated now, but back in 2003, I was simply trying to set up a “ground truthing” system where the full (vetted and known-good) extracted text from each PDF document in our nascent test repository would be saved off somewhere, and later builds of PDFTextStream would compare its extracted PDF text to those saved files.

Of course, it wouldn’t be practical to require that PDFTextStream produce identical output forever — some amount of slop had to be allowable, because (for example) if an extracted word was outputted with four spaces before it instead of two, that would generally be sufficient.  For that and other reasons, I wanted to test that current PDF text extracts were the same as the known-good extracts within a defined margin of error.  Unfortunately, I was ground-truthing full document extracts at that time, and most Levenstein functions with their quadratic performance characteristics would take a lot of memory to diff the multi-megabyte strings that were involved.

Solution: write my own Levenshtein function (loosely based off of a pedagogical implementation by Mike Gilleland that had been incorporated into the Apache commons-lang project) that operated in linear space bounds.  Thankfully, I opted to offer the improvement back to the Apache commons-lang project and to Dr. Gilleland — had I not, Dr. Norvig would never had found that code, and I wouldn’t be writing this right now.

Third and finally, this story is satisfying because, hell, Peter Norvig used some of my code.  A person I respect and admire has found it convenient to use some minor thing I created years ago, and was thoughtful enough to say so.  I hope I can follow that example as I go along in my travels.

See, Dr. Norvig, I’m still learning from you.

Footnotes:

¹ Ground truthing is a testing methodology often used in document processing systems where ideal or otherwise known-good output is cataloged, and then actual or current output is compared to it to determine relative accuracy.  PDFTextStream’s current ground-truthing system serves as a semi-rigorous smoke test of its aggregate text extraction accuracy while we’re doing active development, as well as an ironclad regression test for when we’re looking to cut a release.  Thankfully, it’s come a long, long way from the very naive approach I was pursuing in 2003.

I hadn’t tried TweetDeck yet, and thought I’d give it a run.  It requires Adobe AIR, and I thought I’d end up having to do the download/install dance.  But lo-and-behold, the TweetDeck “Install Now” Flash button bootstraps a local install of AIR for me!  No mess, no fuss, and the whole thing took less than two minutes and three clicks.

That’s cool and all, but we’re (mostly) JVM partisans here, so the inevitable question is: why doesn’t Sun use the same mechanism to drive deployment of the latest and greatest JRE/JavaFX?  Flash functionally has 100% penetration, so it makes tons of sense to use it to make it trivial to get the JRE out there, at which point Java’s “native” update functionality can take over.

I’m not a RIA guru by any stretch, so maybe there’s a good reason why this isn’t done?

I’ve been doing a lot of writing in our FogBugz wikis of late, and I eventually found it irritating that so much of my vertical screen real estate was being eaten up by the FogBugz controls and such that take up permanent residence at the top of the screen.  So, I put together this simple Greasemonkey script that installs a full-screen toggler link in the upper-right corner of FogBugz wiki editing pages.  It should work with any standard FogBugz 6.x install — if you’ve styled your wikis significantly, or if the wiki in question is open to the community, then all bets are off (mostly because I didn’t test the thing that much!).

Normal view:

“Full Screen” view:

It’s only about 100 pixels or so, but that can be a lot when you’re doing some technical writing and are regularly scrubbing up and down a document as you go along.

Download / install: fogbugz_expand_wiki_editor.user.js