How Studying SICP Made Me a Better Programmer

While working through the problems of SICP section 2-2 this week, I had a flash of insight. Things that had frustrated and stymied me for years were suddenly becoming trivial. One data structures problem that had particularly bugged me had become pretty easy, too– though I had to apply everything I’d learned in SICP about recursion, first class functions, and the closure property to do it. Here’s a quick tour of my proof of concept from the REPL prompt:

CL-USER> (setf c (make-hash-table))
#S(HASH-TABLE EQL)
CL-USER> (create-widget c ‘division-a ‘mega-corp ‘(factory-1 factory-2 factory-3))
(DIVISION-A MEGA-CORP (FACTORY-3 FACTORY-2 FACTORY-1) #S(HASH-TABLE EQL))
T
CL-USER> (create-widget c ‘division-b ‘mega-corp ‘(dist-1 dist-2 dist-3 main-office))
(DIVISION-B MEGA-CORP (MAIN-OFFICE DIST-3 DIST-2 DIST-1) #S(HASH-TABLE EQL))
T

We’re starting out by defining a hash-table to store all of our work in. I guess I could have stored everything in a global variable so that I wouldn’t have to keep referencing the store all of the time, but I figured it was worth it not to have all of my functions hard coded to a particular variable. With the above code we assigned division-a and division-b to a company we like to call Mega-Corp. We created some factories, distribution centers, and a main office while we were at it.

CL-USER> (gethash ‘mega-corp c)
(MEGA-CORP NIL (DIVISION-B DIVISION-A) #S(HASH-TABLE EQL))
T
CL-USER> (gethash ‘division-a c)
(DIVISION-A MEGA-CORP (FACTORY-3 FACTORY-2 FACTORY-1) #S(HASH-TABLE EQL))
T
CL-USER> (gethash ‘factory-1 c)
(FACTORY-1 DIVISION-A NIL #S(HASH-TABLE EQL))
T

Here we take a look at what we’re actually storing in our hash table. Each item in the hash is a list in the format of (WidgetName Parent-Widget Children-Widgets-List Properties-Hash-Table). You can see above that Mega-Corp has children, but no parent. Division-a has both a parent and children. And Factory-1 has a parent but no children.

CL-USER> (create-widget c ‘office-staff-f1 ‘factory-1 ‘(bob fred joe))
(OFFICE-STAFF-F1 FACTORY-1 (JOE FRED BOB) #S(HASH-TABLE EQL))
T
CL-USER> (create-widget c ‘office-staff-d1 ‘dist-1 ‘(james mike sally bert))
(OFFICE-STAFF-D1 DIST-1 (BERT SALLY MIKE JAMES) #S(HASH-TABLE EQL))
T
CL-USER> (gethash ‘office-staff-f1 c)
(OFFICE-STAFF-F1 FACTORY-1 (JOE FRED BOB) #S(HASH-TABLE EQL))
T
CL-USER> (gethash ‘bert c)
(BERT OFFICE-STAFF-D1 NIL #S(HASH-TABLE EQL))
T

Here we extend our data structure even further by adding some office staff groups. We can extend the structure as much we want– and in principle, there’s nothing preventing us from writing procedures to copy and combine such data structures however we choose. That wide-open combinatorial possibility is what the closure property is all about.

CL-USER> (setprops c ‘(bob fred joe james mike sally bert) ‘salary ‘(40100 55050 50010 35025 33099 75042 20010))
(40100 55050 50010 35025 33099 75042 20010)
CL-USER> (setprops c ‘(factory-1 factory-2 factory-3 dist-1 dist-2 dist-3 main-office) ‘assets ‘(800000 950000 725000 225000 235000 230000 125000))
(800000 950000 725000 225000 235000 230000 125000)
CL-USER> (getprop c ‘factory-2 ‘assets)
950000
T
CL-USER> (getprop c ‘sally ‘salary)
75042
T

These functions use mapcar to set a slew of property values all at once– without having lots of repetitive code. The getprop procedure allows us to read those settings back out again.

CL-USER> (getval #’+ 0 c ‘sally ‘salary)
75042
CL-USER> (getval #’+ 0 c ‘office-staff-d1 ‘salary)
163176
CL-USER> (getval #’+ 0 c ‘office-staff-f1 ‘salary)
145160
CL-USER> (getval #’+ 0 c ‘mega-corp ‘salary)
308336
CL-USER> (getval #’+ 0 c ‘mega-corp ‘assets)
3290000
CL-USER> (getval #’+ 0 c ‘division-a ‘assets)
2475000
CL-USER> (getval #’+ 0 c ‘division-b ‘assets)
815000

Here we’re using a recursive procedure to apply the plus function to all of the property values from a certain point in the hierarchy down. The zero in the s-expressions there is an identity value– just like the ones we coded in SICP section 1-3. I had to implement that just in case there were all NIL’s in my hash table for a certain property. With a careful use of property names, you can get some benefits of stratified design (covered in SICP section 2-2) in this kind of data structure. We can code in all kinds of information about the separate divisions at one level… and way down the hierarchy we can have all kinds of other information stored about the employees. While working at either end, we can effectively ignore all of the other levels. At the same time we can “roll up” related values however we like at any level we care to focus on.

(There’s probably a few other things I could have done to make this better, faster, or slicker. If you’re working through SICP, too, please check out this complete code file and let me know if you have any tips or suggestions.  I used Common Lisp instead of Scheme, though. I really needed to stop a while and apply what I was learning in SICP to problems that I’d developed a personal stake in. Most people tend to abandon the book by section 2-2, so I better get back to work if I want to finish it!)

Back in the day, I would have avoided a recursive data structure like this if I was working on a similar task. I would have (horrors!) hard-coded the hierarchy at maybe 3 or 4 levels deep, coded all my tables as separate entities, and more than likely built in some work-arounds for the places where such choices were inadequate. (Thinking that OOP was the “right way,” I would have coded a class file for companies, divisions, offices, and employees– and then been stuck storing and retrieving data in as many separate RDBMS tables and figuring out how to map them back and forth somehow.  Writing nested hash tables to a file, on the other hand, is trivial in Common Lisp.) The end result would have been a maintenance nightmare…. It’s a good thing I was too lazy to finish any of those pet projects back then! Funny, I could see clearly the problems of coding 50 slightly different forms when one generic form could be rigged up to do the same thing, but I couldn’t break through my mental limitations to think three-dimensionally about data structures. Thanks to many painful hours spent working through SICP, I can now synthesize recursion, first class functions, and the closure property to make more elegant solutions to things that used to be next-to-impossible for me.

Update 10/26/07: I did manage to follow this post up here.

Advertisement