An Update

SICP will not be abandoned at Berkeley.

Although Python will be used to convey the material, I have been assured that much of the content from SICP will be preserved.

I recognize now that CS61A is a fusion of sorts: an exciting modern treatment of traditionally intellectual material. This change reflects concerns about the difficulty of SICP, the popularity of Python, and a general lack of interest on the part of students and teachers in Scheme. Fair enough. I think this is the best possible solution for an introductory course, but that’s just my opinion.

I want to reiterate that I mean Berkeley or its professors no disrespect, and that I only raised this issue because I was concerned about a potentially drastic shift in the curriculum.

I can’t begin to thank you all for your comments, criticism, emails, and interest. It’s made a world of difference.

(The original essay can be found below, but I am no longer worried about the intellectual rigor of the course at Berkeley.)

Original Essay

It’s official. UC Berkeley will soon join MIT and several other universities in abandoning Structure and Interpretation of Computer Programs, widely regarded as one of the best textbooks in computer science, in favor of alternative material covering Python.

This is a mistake.

SICP is revered for its wit, clarity, and brilliance. It expands the mind. It rewards creativity. There have even been reports of it inducing paroxysms of joy.

The best thing that can be said about SICP is that it will make you a better programmer. It discusses crucially important topics like problem decomposition and the performance implications of various types of procedures. It initiates profound changes in the way you plan and think about code. Although the text is based on Scheme, its teachings are timeless and essentially language agnostic.

This is where most of its competition fails.

Berkeley’s intended replacement for SICP, Dive Into Python, will make you a better Python programmer. Another candidate, Thinking In Java, will make you a better Java programmer. A third option, Thinking In C++, will no doubt make you a better C++ programmer. From an educational standpoint however, none of these alternatives are satisfactory. The sad truth is that SICP’s gradual removal from computer science curricula has left behind a gaping hole that few other texts can hope to fill.

To understand what makes SICP so special, you have to immerse yourself in it. So get ready.

To Slay a Dragon!

One of the earliest topics covered in SICP is linear recursion and iteration. At one point, you are asked to implement the function:

    f(n) = n, n < 3
    f(n) = f(n-1) + 2f(n-2) + 3f(n-3), n >= 3

It’s straightforward to translate this definition into Scheme:

But SICP challenges us to do better. Much better.

If you look carefully, you’ll find three recursive function calls in f that deal with what happens when n >= 3. The top-level call to f(n-1) spawns three calls, each of which spawn three more, and so on, until the recursion terminates with the case n < 3 in each chain of calls. This process is repeated for the calls to f(n-2) and f(n-3).

All of this is incredibly wasteful. After f(n-1), f(n-2), …, f(2) is evaluated, redundant work is performed to calculate f(n-2), f(n-3), …, f(2), and then again for every chain of calls starting with f(n > 3). The challenge, then, is to convert this resource-hungry recursive process into an efficient iterative one.

When I first encountered this problem, I thought it seemed trivial. I was quickly humbled. After a few messy attempts at a solution, I decided that the challenge was outright impossible. I had attacked the dragon with a dull butter knife and all the raging ferocity of a domesticated panda. It was not amused.

The issue I was having was that each term in f(n) has an enormous amount of dependencies. I couldn’t figure out how to represent these dependencies in a reasonable amount of state, or how to update that state without making the same class of huge, branching function calls that I needed to avoid. Sketching these dependencies out on paper didn’t help: it turns out that attempting this for any large n is a lot like playing by the rules in Duel Monsters (tm). It’s tedious, and the cool kids don’t bother with it anyway.

A Revelation

I pondered iterative processes for a solid hour before having a sudden rush of understanding. Everything became blindingly simple. Instead of trying to work my way down from f(n), f(n-1), …, f(n-k), what would happen if I started with the base case and worked my way up? What would happen if I isolated what I already knew into some basic state and then devised some logical mechanism to update it? Wouldn’t I eliminate the need to keep track of all of those dependencies?

It all fell into place. You would probably be safe in comparing that moment to a religious experience. Not having ever seriously tried religion, I can’t say for sure.

The epiphany involved the realization that f(n) can be decomposed into three distinct bits of state, or variables. Specifically:

    a = f(n-1)
    b = 2f(n-2)
    c = 3f(n-3)
    f(n) = a + b + c

The values of f(n < 3) are obvious. The first n that we have to make a real attempt to calculate is n = 3. That leads us to:

    f(3) = a + b + c
    f(3) = f(2) + 2f(1) + 3f(0)
    a, b, c = {2, 2, 0}

Before updating our state from f(n) to f(n+1), consider how things would change algebraically:

    a' = f(n+1-1) = f(n)
    b' = 2f(n+1-2) = 2f(n-1)
    c' = 3f(n+1-3) = 3f(n-2)
    f(n+1) = f(n) + 2f(n-1) + 3f(n-2) = a' + b' + c'

Then update the state using the first set of definitions:

    a' = f(n) = a + b + c
    b' = 2f(n-1) = 2a
    c' = 3f(n-2) = 3b/2

The value of f(n), of course, can be discerned at any time:

    f(n) = a'

Beautiful.

The dragon is slain.

Reflect on What Just Happened

Stop. Take a deep breath. Think about all that you have just discovered (or if you have already discovered it all, reflect on how awesome it is). By page 45 of SICP, you will have;

  • Translated recursive definitions into iterative processes
  • Examined the differences in the space requirements of various processes
  • Used tail-recursion to implement efficient iterative procedures
  • Seen that iteration can be thought of as a special case of recursion
  • Realized that iterative processes can be restarted easily by capturing and restoring their state variables
  • Given thought to complexity, optimization, and state transition theory
  • Been encouraged to explore creative solutions to challenging problems
  • Learned the basic syntax and semantics of Scheme
  • Observed a quasi-religious experience

What will you have accomplished by page 45 of Dive Into Python? Don’t hold your breath. I’ve looked into it. You’ll be learning how to use the and-or “trick” to make simple programs difficult to read. Soon afterwards you’ll be exposed to Python’s intentionally crippled lambda statement.

I find it hard to believe that any young, aspiring computer scientist would prefer that to what SICP has to offer. It’s just.. it’s just not the same. So why are we chucking SICP out of the classroom?

Burn the Wizard Books?

"Python is more practical than Scheme."

I more or less agree with you. I love Python. I’ve been using it for 5 years to build all kinds of things. I realize that you are far more likely to use Python than Scheme when working. None of this means that you have nothing to gain from SICP. I previously claimed that SICP is fairly language agnostic, and I stand by that. It instills something deeper and more important than knowledge about how to glue APIs together, or how to deal with the vagaries of string encoding, or how to abuse the syntax of a language. It’s so much more than that.

"Why shouldn’t students start with Python if it is the more practical language?"

Scheme is considerably less complicated and idiosyncratic than Python. It’s simplicity and consistency have immense pedagogical value. It might take you anywhere from a day to a month to pick up the basics of Python. Scheme, on the other hand, has virtually no syntax. It’s definitely possible to get a solid grasp of its fundamentals in less than an hour.

Python can be used to accomplish many of the same things as Scheme. Practically anything you can do in Scheme you can do in Python, and formally speaking, the two languages are equivalent.

However, until a Python textbook emerges that surpasses SICP in teaching the core elements of programming, we should stick with Scheme.

"But.. but everyone else is doing [LanguageFoo]! What about the job market!?"

Think about it this way. What if the language du jour happened to be BrainF—-? What if there were plenty of lucrative opportunities in this hypothetical mainstream BrainF—- programming scene? Would you switch introductory computer science courses over to BrainF—- because industry leaders complained about the low quality of your school’s BrainF—- programmers? Hopefully not.

"You are not qualified to comment on pedagogy."

You’re probably right. I’m just a student, but I do care about the state of computer science education. Given how much I’m paying for it, I feel like I’ve at least earned the right to criticize it.

A Plea

I respect the Berkeley CS department’s decision to try Python for its introductory course. I’m sure that the decision was well-meaning, and who knows, things may even turn out for the best this way.

That said, I really hate to see SICP on its deathbed at Berkeley. Dive Into Python, whatever its merits, is certainly not an adequate replacement. Not if you want students to walk away with a deep appreciation for the elegance and power of their field. I was looking forward to CS61A over the summer and received an unpleasant surprise when I heard rumors of change… A lot of students will be missing out on a great program this fall.

Please help me raise awareness about this issue. I don’t know if the department can be convinced to reverse their decision, but I hope that’s the case.

I’ll take the musings of Ben Bitdiddle over XML parsing 101 any day. Any day.

-vk

  1. mybestrestaurantforms reblogged this from vedantk
  2. freesamplesuk reblogged this from vedantk
  3. inktcartridges reblogged this from vedantk
  4. asternux reblogged this from vedantk
  5. jmvldz reblogged this from vedantk
  6. vedantk posted this