I meant to post this a while back, but you know how it is… work, family, oral surgery, and where does the time go? Anyway, here are some notes I took from week 4 of our SICP adventure about higher-order procedures, Abelson’s dismissal of the “mythology” of software engineering, and the pleasures of building up a language to solve problems.
Higher-order procedures and the joys of abstraction
I’ve been working a lot with JavaScript this year, and I’ve some to agree with people like Douglas Crockford who claim JS is possibly the most misunderstood and under-appreciated modern programming language. One thing I’ve enjoyed immensely about working with JS is taking advantage of lexical scoping to bind values into functions at the time of their definition and then storing those functions for use later. It’s also genuinely fun to bind functions to objects as runtime, too.
My fun with JavaScript has taught me how to use closures: how to bind information in functions and then use those functions as arguments or as objects receiving arguments. Without knowing it, I was using functions as first-class objects: higher-order procedures. This is a major feature (and subject of rightful boasting) in Scheme. Section 1.3 of SICP (courtesy MIT Press) starts out with an argument for the importance of higher-order procedures:
Often the same programming pattern will be used with a number of different procedures. To express such patterns as concepts, we will need to construct procedures that can accept procedures as arguments or return procedures as values. Procedures that manipulate procedures are called higher-order procedures. This section shows how higher-order procedures can serve as powerful abstraction mechanisms, vastly increasing the expressive power of our language.
Section 1.3 is a great read. It begins with a problem reminiscent of the math-heavy Section 1.2, exercise 1.29, in which we’re asked to apply a general summation procedure to model Simpson’s Rule for numerical integration. Hard, but rewarding. Before SICP, I would have approached a problem like this by focusing on defining variables and changing or maintaining their values, and summing up each term computed via Simpson’s method as an afterthought. It would have probably been ugly. What I gained from working through this exercise was a different perspective. Before you worry about actual variables and values, model the problem. Simpson’s method is fundamentally a mathematical summation. So use a summation procedure like the one developed in the section: that procedure takes as arguments the numerical lower and upper bounds of the summation, a procedure for computing a term to be added to the summation, and a procedure to determine the next value for the index variable:
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
Now you’re only focusing on the work done at each step of the summation: given a value for ‘a‘ — the current index (ie the value that tells you you’re working on term number ‘a’ in the summation), the the b variable that holds the upper bound the summation should be approaching, just use the term and next procedures to determine what the current term will be. Now where is all the work? In crafting term and next procedures that correctly produce each term and move the summation towards its conclusion. So instead of marching through the summation with mutable variables and lots of explicit loops and if-else blocks, you find yourself looking at Simpson’s Rule to find the pattern of change from one term to the next that you can abstract into term and next procedures.
I am continually surprised by how different it feels to approach composing a program functionally. It isn’t all that different, is it? In my old imperative approach, I would have been looking for patterns too, right? Except that what I learned would probably have to have been spread out over several parts of my code. Here, it’s tucked tightly and lucidly into two procedures.
And there’s more. Using the summation procedure has taken a lot of work off my hands. By applying it to the problem, I get to treat Simpson’s Rule as the mathematical summation it is. I get to forget about adding things and just focus on the patterns between the terms. What would have been error-prone to implement myself in an imperative approach is instead given to me. Semantic clarity plus time-saving reusable code, all thanks to higher-order procedures.
In the exercises that follow, we build on what we learned from the summation procedure by creating a similar product procedure, and then abstracting out of them an accumulate procedure, which can apply whatever “combiner” procedure we want to give it: + *, or anything else that returns a number. Then we are introduced to the idea of filters, which can further abstract our procedures. By exercise 1.33 we have a procedure that can “take off our hands” much of the work of repeated calculation in any number of possible problems. We’ve climbed up the abstraction ladder.
The myth of software engineering
An enjoyable lecture often offers a liberal peppering of the lecturer’s opinions, especially when they surprise and provoke. In video 3a of the SICP-style course taught for HP, Abelson makes this statement:
“There’s a mythology that’s charitably called software engineering.”
Huh? Isn’t software engineering what we’re doing here? No. Abelson follows up the first lecture’s claim that the SICP course isn’t about anything called “Computer Science” by critiquing the common method for decomposing a problem during the analysis stage of “software engineering”. In a perfect world, all problems can be broken down into a hierarchy of every smaller perfectly-isolated and abstract-able mini-problems. And once we code all the way down the hierarchy, we’re done.
That sounds familiar to me. That top-down approach is still the way things are done, from what I’ve seen, twenty years after this video was made. Witness Joel Spolsky arguing for the necessity of scheduling your project down to every subroutine your team has to write in the next six months: “demand fine-grained time estimates from the developers.” There’s a confidence in this approach that you can schedule three hours for subroutine 417 on day 63. I’ll give this to Joel: he ships a major piece of software, and I don’t. Maybe his team really can foresee months of the future in stark detail. But I’ve never seen scheduling like this work.
Abelson is critical of the top-down approach. His main objection, like mine, is that you’re never developing in the perfect case. Something important always changes midway, your subcomponents always turn out to be somehow coupled to each other, and your ability to anticipate every detail of the problem is never faultless. Instead, Abelson argues, you should build up layers of languages that address the problem you’re tackling at different levels of granularity.
In the video, Abelson is presenting his languages for implementing the Escher-Henderson drawings. First, he defines a language of primitive pictures. Then, a language of geometric positions: above, beside, right-push, etc. And, above that, a language of schemes of combination, generalizing. The objects being talked about at each level are built up by the layer below.
Instead of task decomposition, we have a range of linguistic power–not built to do a particular task, but to describe a whole set of applications. This is more robust and adaptable. You also have a vocabulary at each level for describing objects, describing changes.
Fast Forward
I wrote the notes form which I’ve written this post about a month ago now. Since then, I’ve been grappling with new topics, including lists, sets, and trees. There’s a lot more to say about those subjects, but here’s just one tidbit, a footnote from Section 2.3 about the book’s implementation of set trees:
We are representing sets in terms of trees, and trees in terms of lists — in effect, a data abstraction built upon a data abstraction.
And on and on it goes….