Mastering Higher Order Programming Techniques with SICP Chapter 1

Section 1.1 was deceptively simple, but things rapidly got heavy in section 1.2. The process of tree recursion was exceedingly difficult to visualize. Exercise 1.13 asked us to “use induction” to prove something. Plugging through exercise 1.20 was exceedingly painful back when I was working on my own. The march of technology added some complications to the later problems that caused me to dread going on… and the Miller-Rabin problem was completely mystifying. (I hacked out a Common Lisp version of the algorithm described on Wikipedia, but even that exercise failed to give me the insight necessary to understand the question. I haven’t been that befuddled since that problem from PAIP chapter 2….) Collectively, these experiences might lead one to believe that working through SICP was a lost cause….

A couple of things can really improve your chances of getting through it, though. One thing is to definitely watch the videos— they really make things interesting and more accessible. Another thing is just to have a friend or two that you can bounce things off of. “I tried x on problem y… is that what you think they wanted there? Also, are you getting something like z on problem w?” A few encouragements from a peer can really help you focus.

Continuing on into section 1.3 things got much easier. The lecture was outstanding. It is probably the definitive sales pitch for higher order thinking. If you ever wondered what people mean when they talk about “higher order procedures,” this is the place to go. The problems for the most part were straight-forward or about medium level. A lot of them push you to alter or imitate clear examples, so they are pretty “fair” as exercises go. Others require a modicum of persistence and experimentation, but are still pretty straight forward. I got through most of them with only a couple of minor questions. (Simpson’s rule in 1.29 didn’t work for me as it was advertised. The instruction to “show that the Golden Mean is a fixed-point transformation” is perhaps beyond my math skills. I wasn’t sure how to test my answer in 1.44, and I’m not quite sure where to go with 1.46.) But if the goal here was to get me to understand when and how to implement functions that take functions as arguments and that return a function for their value… then I’m there. They push the level of abstraction… and then push it some more… and then push it until I want the merry-go-round to stop. I used to think that mapcar was pretty darn cool. Now I have an entire new mental apparatus that I can apply regardless of the language or platform.

So I’ve got the bulk of the problems from the first chapter completed and it’s all culminated into a deeper understanding of how to apply and implement functional style abstractions. I’m really pleased with how far they’ve brought me in the text, but I begin to get anxious: I want to go code something… and I’m afraid of how far into the stratosphere they’re going to push my mind. I wanted at first to learn more powerful methods of creating general solutions… but really, I only wanted to get maybe half an order of magnitude better as a programmer. I had no idea that they would push my mind so far beyond its comfort zone. I had no idea that I even had a mental comfort zone! The experience gives me a new respect for MIT… and I’m glad I have a chance to experience a bit of what they put their computer science students through. (I want to also give my thanks to the SICP study group for providing me the inspiration and the encouragement to continue working through this book!)

Two minor things stand out for me, as far as mental processes go. One is the “faith oriented programming” that Sussman advocates in the lecture: if you’re not sure how to code a complex routine, just assume the hard parts are already done. If you can put a name on what’s missing, you’ll be able to easily address it later. Thankfully, DrScheme doesn’t auto-highlight “syntax errors” in this case! This worked surprisingly well for me when I went back and reworked the Pascal’s Triangle problem from section 1.2. Also, in section 1.3 they formalize the “guess-fudge” method that helped me do well in so many math classes in the past. The iterative approaches in the section mirror my own problem solving techniques: if you’re not sure of the answer, guess… then make small improvements or adjustments until it’s good enough. Combining these techniques gives you the key to solving recursion problems: start with a rough outline the covers the trivial cases… then “guess-fudge” the missing piece into existence with a function or two. This works for many of the problems in the text.

Anyways, if you got overwhelmed in section 1.2, just hang tight… it gets easier. Or maybe you get smarter. Something. They keep the pressure on, but they are very steady in section 1.3. It’s a lot of work– almost like learning to program all over again– but everything they make you do is part of their perfect plan to transform the way you think about algorithms. I can’t for the life of me imagine why so many people have complained about Scheme: it’s an exceeding beautiful language that gets out of the way so that you can express raw thought in its most elegant form. It’s hard to believe how much can be accomplished with only a handful primitives and parentheses….

For those that want to compare notes, here’s my code for exercises 1.29 to 1.33, 1.35 to 1.39, and 1.40 to 1.46. Also, here’s my algorithm for the Miller-Rabin test based on the instrictions from this Wikipedia entry.


3 Responses to “Mastering Higher Order Programming Techniques with SICP Chapter 1”

  1. Eli Says:

    Worry not – you’ll get to write quite a lot of code in chapter 2

  2. Improved Means For Achieving Deteriorated Ends / SICP Section 1.3 Says:

    […] Blog, SICP Wiki, Ken Dyck’s Solutions, Theloserblog, Wfasim’s Solutions, Autodidact and Lispy for […]

  3. Improved Means For Achieving Deteriorated Ends / SICP Section 1.2 Says:

    […] Checked against: Eli Bendersky’s Blog, SICP Wiki, Ken Dyck’s Solutions, Autodidact and Lispy for […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: