On imperative vs functional programming

This is really an essay about my thoughts on the book Structure and Interpretation of Computer Programs.

I came to this book with enthusiasm and left with disappointment.

Why sicp is not a good book

I am not anyone special and so my words have little weight against MIT professors. But this is a good thing as my arguments will have to stand on their own weight. Had the book been originally written to be used for a course at Podunk University, I wonder if it would have become so well regarded...

Computer Programs? Computer Programming?

First let us look at the beginning of the book.

The preface to the first edition declares that the design of this introductory computer-science course reflects two major concerns. The first is the desire to establish the idea that a computer language is not just a way of getting a computer to perform operations but rather that it is a novel formal medium for expressing ideas about methodology. Thus, programs must be written for people to read, and only incidentally for machines to execute. Second, the authors believe that what is important is not the syntax of particular programming language constructs, nor clever algorithms, nor the mathematical analysis of algorithms and the foundations of computing, but rather the techniques used to control the complexity of large software systems.

We will return to these two points shortly, but a further idea from this section is that as a consequence of the first point. They belive that the importance of computer science is not much to do with computers but with new ways of thinking. Specifically moving from the traditional declaritive point of view of classical mathematics to the imperative point of view. Mathematics (classical) provides a framework for dealing with "what is", and computation provides a framework for dealing with "how to".

Again we will set this aside and add a third idea, this time from the introduction to the first chapter. Here we are told that we are about to study the idea of a computational process.

So now we have three points: the goals of the authors in designing the course, the authors' idea of computer science, and the authors' idea of what we are going to study.

First the idea of a computer language as a way of expressing ideas for people first and computers second. Well this is a strange idea, because most ideas expressed for people are declarative (logic and statements) and not imperative (algorithms). Which would have been fine to say except the authors state in their second point that the transition to imperative thinking and dealing with how to is the heart of computer science.

I believe that a major shift in thinking that is necessary for computer programming is to realize that the computer has no common sense. That the computer executes instructions faithfully and reliably. And thus we must learn to express things in this fashion. The goal is not to express algorithms so that a reasonable person can carry them out, for in this case we could be entirely too vague and we should be limited to a short term memory of about 7 elements (give or take 2 elements).

Therefore computer programming must be about instructing computers. Our wish we must make their command. It is true that we should also write programs so that people can read them, but this is because we wish first to understand our own programs and secondly that others should be able to use them to achieve similar ends.

Terrible exercises...

In his Foreward to the book Alan J. Perlis mentions Fortran as another ancient programming language that has survived and remained active.

It is interesting because Fortran is in some sense the opposite of Lisp. It is perhaps the most imperative language of all. Subroutines and functions are passed arguments by refence, and there is no recursion (or at least there was no recursion).

But more fundamentally the machines on which Fortran was born did not support the concept of a stack (this is what Wikipedia says). And lisp/scheme is all about a stack and recursion.

I have no problem with this idea that Fortran is a language to deal with a sequential machine, and Lisp a language to deal with a stack-based machine.

What I have a problem with is that practically all the exercies in the first chapter of the book are numerical problems. Compute the square root, compute the cube root, compute the this or the that function.

In fact the first non-trivial function we really look at is the square root function. It is called square-root-iterate or some such thing, but defined using tail-recursion. Fine but what do we gain, expressing a straightforward iterative algorithm in this pseudo-recursive way. How is this is better?

We have taken something closer to the machine and closer to human reasoning and found an alternative and entirely equivalent formulation that is marginally worse in both respects.

There is an exercise to write a function that takes 3 arguments and returns the sum of squares of the two greatest arguments (or the two lowest). And really with what they had covered until there it would be somewhat challenging for 3 arguments and pretty hard for the student to generalize this to 100 elements.

The worst is that the dedication of the book mentions that it's important to keep the fun in computing, and there is no fun to be found in these exercies. There is no exercise where one solves some problem which is novel or interesting. We don't find out how to get out of a maze, we don't analyze a piece of text, we don't do any of this.

We do get to do some of this in the second chapter. We get to draw pretty pictures and solve some logic problems. But the problem is that we are not left to discover the how. We are told how, and we are told to tell the computer how.

The n-queens problem and other similar problems are fun to solve, and there is much to gain by coming up with a solution on one's own.

Wait I forgot: Computational process?

The book spends a good deal of time avoiding/delaying the introduction of mutable objects, or basically changes in state. This is funny given that the stated goal is to understand or deal with computational processes.

The abstract is put before the concrete. And our doubts about the usefulness of the abstraction or the dangerousness of the reality (!?!) are brushed aside with weak reasoning. The sort of statement that imperative programming with assignment is error prone.

In the end maybe I'm just bitter

Really maybe I'm being too harsh. Maybe I'm just upset that this way of programming is so alien to me and seems so roundabout. All I can say is that if this was my introduction to computer programming, I doubt whether I would have ever taken to it. Many things here seem like solutions looking for a problem.

The fun in computer programming is building your own abstractions out of the concretest of building blocks. Then you can know when to reach for a ready made abstraction when appropriate.

The authors have put the cart before the horse. Here is recursion and now you can solve this problem you didn't even know about. And then finally at the end of the book they deal with register machines.

Conclusion

I'm not satisfied with my arguments. But I was so unsatisfied with the book I needed to say something. Hopefully I can improve this essay.

However I feel like improving this essay would require reading the book or otherwise mastering Lisp/scheme. So if you know of a good book about Lisp send me an email

A quote from a blog posting that advocates mastering the basics before tackling the abstract: "the abstractions save us time working, but they don't save us time learning", because "all abstractions, leak, and the only way to deal with the leaks competently is to learn about how the abstractions work and what they are abstracting."

This site best viewed with Lynx or Mozilla or Konqueror or any standards compliant browser!

and also. The all-powerful ed has also contributed!.