SICP Exercise 1.11: “There is no spoon”

This is the first in what I hope will be many posts talking about Structure and Interpretation of Computer Programs, by Abelson and Sussman. This and future posts on this subject will be based on the online (second) edition that’s available for free. I started in on this book last year, but I haven’t been posting about it because I hadn’t gotten to any interesting parts. Now I finally have.

After I solved this problem, I really felt that this scene from The Matrix, “There is no spoon” (video), captured the experience of what it was like to finally realize the solution. First realize the truth, that “there is no spoon”–separate form from appearance (referring to Plato’s notion of “forms”). Once you do that, you can come to see, “It is not the spoon that bends. It is only yourself.” I know, I’m gettin’ “totally trippin’ deep, man,” but it was a real trip to do this problem!

This exercise is an interesting look at how programmers such as myself have viewed how we should practice our craft. It starts off innocuously:

A function f is defined by the rule that f(n) = n if n < 3 and f(n) = f(n – 1) + 2f(n – 2) + 3f(n – 3) if n >= 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by an iterative process.

(Update 5-22-2010: Don’t read too much into the “cross-outs” I’m using. I’m just trying to be more precise in my description.) Writing it recursively is pretty easy. You just do a translation from the mathematical classical algebraic notation to Scheme code. It speaks for itself. The challenging part is writing the same thing a solution that gives you the same result using an iterative process. Before you say it can’t be done, it can!

I won’t say never, but you probably won’t see me describing how I solve any of the exercises, because that makes it too easy for CS students to just read this and copy it. I want people to learn this stuff for themselves. I will, however, try to give some “nudges” in the right direction.

  • I’ll say this right off the bat: This is not a (classical) mathematical an algebra problem you’re dealing with. It’s easy to fall into thinking this, especially since you’re presented with some algebra as something to implement. This is a computing problem. I’d venture to say it’s more about the mathematics of computing than it is about algebra. As developers we often think of the ideal as “expressing the code in a way that means something to us.” While this is ideal, it can get in the way of writing something optimally. This is one of those cases. I spent several hours trying to optimize the math algebraic operations, and looking for mathematical patterns that might optimize the recursive algorithm into an iterative one. Most of my mathematical the patterns I thought I had fell to pieces. It was a waste of time anyway. I did a fair amount of fooling myself into thinking that I had created an iterative algorithm when I hadn’t. It turned out to be the same recursive algorithm done differently.
  • Pay attention to the examples in Section 1.2.1 (Linear Recursion and Iteration), and particularly Section 1.2.2 (Tree Recursion). Notice the difference, in the broadest sense, in the design between the recursive and iterative algorithms in the sample code.
  • As developers we’re used to thinking about dividing code into component parts, and that this is the right way to do it. The recursive algorithm lends itself to that kind of thinking. Think about information flow instead for the iterative algorithm. Think about what computers do beyond calculation, and get beyond the idea of calling a function to get a desired result.
  • It’s good to take a look at how the recursive algorithm works to get some ideas about how to implement the iterative version. Try some example walk-throughs with the recursive code and watch what develops.
  • Here’s a “you missed your turn” signpost (using a driving analogy): If you’re repeating calculation steps in your iterative algorithm, you’re probably not writing an iterative procedure. The authors described the characteristics of a recursive and an iterative procedure earlier in the chapter. See how well your procedure fits into either description. There’s a fine line between what’s “iterative” and what’s “recursive” in Scheme, because in both cases you have a function calling itself. The difference is in a recursive procedure you tend to have the function calling itself more than once in the same expression. Whereas In an iterative procedure you tend to have a simpler calling scheme where the function only calls itself once in an expression (though it may call itself once in more than one expression inside the function), and all you’re doing is computing an intermediate result, and incrementing a counter, to input into the next step. You should not have operators which are “lingering”, waiting for a function call to return, as a rule, though they did show an example earlier of a function that was mostly iterative, with a little recursion thrown in now and then. With this exercise I found that I was able to find a solution that was strictly iterative.
  • As I believe was mentioned earlier in this chapter (in the SICP book), remember to use the parameter list of your function as a means for changing state.
  • I will say that both the recursive and the iterative functions are pretty simple, though the iterative function uses a couple concepts that most developers are not used to. That’s why it’s tricky. When I finally got it, I thought, “Oh! There it is! That’s cool.” When you get it, it will just seem to flow very smoothly.

Happy coding!

Advertisements

16 thoughts on “SICP Exercise 1.11: “There is no spoon”

  1. Hi, Mark

    I started reading SICP recently and I’m stuck with the very same exercise.
    I wish I had saw this article before finding the solution somewhere else… Now I have already cheated… I’m just so impatient sometimes 😦

    Keep posting about SICP! I’ll keep reading you!

    Cheers
    Richo

  2. @Richo:

    I was tempted to do a write up on how I solved this problem, just because I was so excited about it. When I figured out the idea and got the implementation working it was very beautiful to me. The exhilaration came from struggling with my own mindset and then being able to “punch through” that, and realize something beautiful. I didn’t want to deny that to others.

    There was also the temptation as well of wanting to help those who were struggling with this, since they might give up and just think this sort of thing is not for them. But then I realized that it’s better to preserve the “surprise”. I figured that was the whole point of it, to challenge students to change how they think.

    I have heard of other bloggers posting solutions to stuff in SICP, and I don’t see the point of that. I think you realize this by now, but if the goal is to learn, when you just get the answer from someone else you’re really cheating yourself. I think SICP is a rather unique book. It seems like the authors really tried to make it worthwhile, to help students think differently and see computing from a different perspective, rather than just have it be make-work. In that light, working through the exercise is the goal. The answer at the end is just a side-effect.

    I’ve been going through SICP at my own pace, and I will not be doing postings on every single section and exercise. Just what I find exciting/interesting.

  3. One of the things I’ve noticed as I’ve gone on beyond this section is the authors get into more analysis problems, where, like with this problem, it’s helpful to run through what the code is doing, get some data from those run-throughs, and then analyze what you see. As I’ve written about earlier, this is a habit of work that’s necessary for looking at computing from a scientific perspective. This is qualitatively different from how most so-called computer science programs do things.

  4. I’ve come to relent the idea that others should not post solutions to SICP exercises. The SICP book itself doesn’t have answers in it.

    I recently worked on an exercise that I found really hard (different from this one). I’ve been going through the book with a local user group, focused on Lisp and Clojure, and such, and none of them worked on this exercise that was giving me such a headache. So no one knew what the right answer was. I went looking around on Google and I was glad to see that someone had posted a solution. I had gotten the answer wrong, but I was glad to see how someone else worked it out so I could learn from it.

    Still, I won’t be doing that here. I think it’s valuable to give some coaching and not blurt out the answer, to still give people an opportunity to find the answers themselves. Other people can give out the answers, and they provide a valuable service, so long as people don’t use them as “cheat sheets”.

  5. Pingback: SICP Exercise 2.32 « Tekkie

  6. i tried to get it, i tried really hard, its just not coming together. I’ll continue reading though for best results.

    thanx ALOT

  7. @Latoya:

    I know how it feels. I also felt frustrated with this problem, but I think it’s the most important one to do in the book, because once you’ve figured it out you will have learned a big lesson that will help you solve further problems as you go through the book’s exercises. Keep at it.

  8. AAAHHHHH!!! I GOT IT!!!
    HOLY CRAPPING CRAP BALLS IT WORKS!!!
    I TOLD MYSELF IT WAS IMPOSSIBLE FOR SO LONG, BUT IT WORKS!! THANK YOU SO MUCH FOR THE “NUDGES” IN THE RIGHT DIRECTION AND NOT THROWING THE ANSWER IN MY FACE AND STEALING ALL THE JOY THAT I HAVE NOW FOUND!!!
    MARK YOU ARE MY HERO FOR PUSHING ME TO BE THE BEST CSCI 101 PROGRAMMER I COULD BE!!!

  9. @Will:

    Thanks so much for sharing your experience. What you describe is what I was going for when I wrote this article. 🙂 There is no other way to really share what I experienced when I solved this problem than to go through what you went through, and then to see it!

    The great thing about SICP is that there are lessons in some of the exercises. The difference from most textbooks is *you* have to discover what the lesson is!

  10. Pingback: The 150th post « Tekkie

  11. A bit late to the show, but I found this problem interesting. My naive recursive solution was good through about n=30 before it got really slow.

    (somewhat) SPOILER ALERT************

    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    *
    After fumbling about trying to come up with a non recursive solution, I happily settled on a while loop which solves it in O(n) and requires a simple array of three elements.

    While I was pleased as punch with my solution, I didn’t have a Keanu Reeeves. “Whoa” moment. I haven’t read the text, so I may be missing the larger point.

    My question is, does a while loop solution count as an iterative solution, or is there something else involved to be iterative?

  12. @Jason Eriksen

    Hi Jason,

    You should read the text in the book. You can find an electronic copy at the link I put in my post. This exercise is under Section 1.2.2, but you should also read Section 1.2.1 – Linear Recursion and Iteration, before doing the problem. I only put the exercise in my post for reference. The book was designed to have students go from the first chapter through to the last chapter, assuming that none of them knew Scheme ahead of time. Secondly, it emphasizes Scheme from a pure functional approach (no mutating operations), though it gets into non-functional programming later, and the reasons to use operations that mutate values (these operations are any function with a “!” suffix, like set!).

    A simple rule I followed with the exercises is I only used the constructs that had been introduced to me up to the point of each exercise (which was pretty easy, since I had no exposure to Scheme prior to reading it, though I avoided the temptation to consult the internet for alternative constructs). My experience with the book is this is the way the authors wanted students to progress through it. While-loops were not discussed by the point of this exercise, nor were mutating operations. The section only discusses looping as a function that calls itself. As I said in my post, in the book there’s a fine line between what the authors considered iterative and recursive. I gave brief descriptions of both. I found their descriptions rather confusing at first, since both methods looked recursive, but I eventually got it. They *are* both recursive, strictly speaking, but one leaves state behind, and one doesn’t (it only passes state forward as the loop iterates). In any case, I was able to come up with an iterative solution to the exercise without using a while-loop. I encourage you to try doing it without a while loop, and with no mutating operations, since I think that’s what the authors were after.

    This is just my observation, but it seemed to me the reason they put this exercise in there was to help students get past an essential threshold in understanding functional programming.

    Best of luck.

  13. Honestly guys, I don’t know what the big deal is. I just started FP a couple of months ago and I was able to come up with an answer in a whole 5 minutes.
    I wasn’t sure so I double checked the solution on the ol’ inter Webs. Sure enough, I had come up with the solution.

    On the other hand, I am trained as a mathematician.

    It’s interesting because I hear developers complain all the time that “functional programming is hard”. Just found one clue as to why….

  14. @Uriel A:

    When I hear people like yourself act like it was easy, I get suspicious that they didn’t do both parts of the exercise, or didn’t do the iterative part the way that the authors intended for them to practice. Since you checked your solution against others on the internet, that indicates to me you probably solved both parts just fine.

    Perhaps your background in mathematics really did give you an edge. I had more of an algorithmic/modular approach to programming in my education, as do most programmers (I mentioned that in my post), so making the switch to how you need to think in FP was a challenge for people like me, but it’s still possible, and the revelation when I finally “got it” was exhilarating!

    Dijkstra had some insights into this, I think, saying that people who began their programming lives with almost all of the languages out there came into CS “brain damaged,” because they had trained their brains such that they couldn’t think mathematically about what they were doing. He made several complaints over the years that American programmers in particular have an anti-math bias in their approach, since Americans generally hate math, and avoid it like the plague. That could very well be the difference between your experience and mine, and that of others.

    On Quora.com, someone asked, “What are some myths of functional programming.” The sentiment in my answer was the same as yours. I said, “That it’s hard.” Once someone like me gets over some thresholds, such as what’s demonstrated in this exercise, one realizes that it’s pretty easy, and that it’s pleasurable to work in it. I don’t think that’s anything to sneer at, but rather is a good thing. That’s the reason I talked about it here. I wanted people who would find this problem hard to take up the challenge and get over that hump.

  15. @Mark Sorry, I didn’t mean to sound like was a sneering.

    We’ve actually been struggling to hire programmers who can do FP/FRP.
    Either (1) they write standard Java programs in Scala syntax, or (2) or transforming data (with map and whatnot) is Mayan to them…an indecipherable language.

    In the future, I’ll be looking at strong math skills as a predictor of raw FP/FRP skills.

  16. @Uriel A:

    Your struggle to find skilled programmers is not unusual. I’ve been hearing about it from other senior engineers for several years now. There were a couple famous posts on this written in 2007. You can see commentary on this, and links to the others at Why Can’t Programmers…Program? The gist of it was people with many years of experience in some kind of app. development, and degrees in CS, lacked even basic programming skills that people like you and me take for granted.

    In a follow-up blog post to his famous “Beating The Averages,” Paul Graham said that after he sold ViaWeb to Yahoo, they translated his entire system to C++ and Perl (from Lisp). They said it was because they couldn’t find enough skilled Lisp programmers to work on it, which he thought was a lame excuse.

    Dijkstra’s criticism of American programmers I think continues to have merit. Before I encountered Lisp for the first time in college, I had been programming in imperative languages for about 10 years. Our professor insisted we use it in the pure FP style. It threw me for a loop. I really couldn’t make head or tails of FP, and it gave me a headache. I thought of myself as good at math. I got decent grades in it in secondary school. B’s and A’s, as I recall. It didn’t help. Up until I encountered Lisp, I really thought imperative was the only kind of programming there was. My experience with it was so bad, I swore I would never look at it again. It was only when I read Graham’s “Beating The Averages” 9 years ago, and many other accounts from Lisp programmers about how much it improved the experience of programming that I reconsidered my opinion, and gave it another shot. Even so, I know that while Lisp can be used for FP, it’s not a functional language. In any case, I’ve heard similar stories from other CS students from good schools over the years. There is something to be said for getting exposure to a variety of different types of languages early, rather than getting a “monoculture” of imperative programming that goes on for years. Unfortunately, CS programs across the country no longer take this approach.

    Another thing to consider is, as Alan Kay has said, computing is a kind of mathematics, but it’s not the same as classical mathematics (algebra, calculus, etc.). This is where he differed strenuously with Dijkstra, incidentally, who insisted on applying a classical mathematical approach to computing, saying that all code should be proven, like a theorem. To me, computing is a kind of operational math that takes inferences in steps, where time (when things happen) is a critical component. People new to mathematics and programming (and I include myself, when I was young) can get the two confused, and eventually find out the hard way that they’re not the same thing.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

w

Connecting to %s