Some Books on C

I have gathered such introductory books on the C programming language as I own or could borrow. The result is an eight-storey tower. A quick scan shows that I could easily buy another half dozen, but I doubt whether that would yield any new insights.

For most teachers “an introductory programming book with C” is an oxymoron. The extreme wing in this school of thought consider only designedly friendly languages suitable for an introduction to programming. BASIC is an early example. My current favourite friendly language is Python [1]. But the mainstream of teachers of introductory programming has settled on Java as a compromise between friendliness and attractiveness to prospective employers.

 

These employers will not include Joel Spolsky, as he explains in The Perils of Java Schools:

All the kids who did great in high school writing pong games in BASIC for their Apple II would get to college, take CompSci 101, a data structures course, and when they hit the pointers business their brains would just totally explode and the next thing you knew, they were majoring in Political Science because law school seemed like a better idea. I’ve seen all kinds of figures for drop-out rates in CS and they’re usually between 40% and 70%. The universities tend to see this as a waste; I think it’s just a necessary culling of the people who aren’t going to be happy or successful in programming careers.

What Spolsky isn’t saying (and certainly should not be thinking) is that it is inevitable that there are brains that can’t get themselves around pointers. I think that those seemingly handicapped brains are the result of unfortunate teaching—the kind of teaching that surrounds pointers with that aura of trickiness and disreputability that comes with that other bugaboo of programming, the goto statement. Of course the author of the textbook is not in total control of the instructor, but at least he can introduce pointers in a matter-of-fact way, as just another feature of the C programming language.

This brings me to the top of the pile of books on my desk: Elements of Programming by Maarten van Emden, which recently became available worldwide. It is also available without charge as a pdf file. This book is an example of one where pointers are introduced as just another feature of C. In this respect Programming for Engineers by Aaron Bradley is even better and is the most powerful antidote I know of against the phenomenon noted by Spolsky. Bradley doesn’t start with the usual cutesy “Hello world” program. Instead, the first program, on page 2, has five lines. It declares some variables and performs some assignments. The program is followed by the memory maps for the initial state, and for each of the computational states afterwards. For each cell it shows the address, the identifier of the variable, and its content. On page 4 any mysteries around pointers are dispelled once and for all with a similarly small program. It declares a pointer variable, assigns it a value, and assigns the result of de-refencing it. Again a memory map for each change in state. Bradley shows that, by fearlessly digging down to bedrock, pointers become crystal-clear.

As far as I know, Bradley’s approach is unique. I would recommend his book, were it not for the fact that so little is covered. I’m allergic to fat books, but there is only so much you can say in eight thousand words [2].

The best book on the pile is The C Programming Language by Kernighan and Ritchie (“K&R”). It was the natural choice when we created a new introductory course where the language was mandated to be C. However, K&R assumes that the reader is a programmer and only needs to learn C as a new language. The choice of K&R for the new course would have put an undue burden on the instructor, who would have to provide a considerable amount of introductory material. The instructor, Jason Corless, believed that I could do better than the alternatives to K&R that were on the market. This led to my writing the first edition of Elements of Programming, of which you can now buy the fourth edition.

K&R stands out in several ways. It is not only the best introduction to C, but it is itself part of the history of C. When the first edition of K&R was published in 1978, the language was not standardized. As a result the various C compilers did not implement the same language. In this chaotic landscape “K&R C”, the version of C described in the book, served as the de facto standard.

Another way in which K&R stands out is Kernighan’s excellent writing style. It is of course an indiscretion to enquire into the ways in which co-authors have contributed and even worse than an indiscretion to make guesses. I’m sticking my neck out in this case because I have read four books by Kernighan and six different co-authors [3] in total, and they all have the same crisp and agreeable writing style, better than what is found in your typical non-Kernighan book.

A telling difference between these books is the attention given to the choice of examples. The most basic kind of exposition is to describe the next feature and then to give an example. Logically speaking, all that the example needs to do is to illustrate the feature. But wouldn’t it be more rewarding, if instead of half a dozen lines for such a parsimonious example, a function is given that is worth knowing about, independently of the feature being illustrated? If necessary at the expense of another half dozen lines? In this I have tried to emulate K&R, which is hard to beat in this respect.

An idiosyncratic way to classify these books is according to whether they include in their examples the Quicksort sorting algorithm. It is essential neither for illustrating features of C, nor of programming. Yet it pops up in surprisingly many of the books on my pile. In the case of my Elements of Programming the appearance is not surprising. Soon after I was introduced to any kind of programming, I had the dubious luck of being told about Quicksort, which promptly caused a year of bouts of brain fever. The result has been my induction into Knuth’s The Art of Programming [4], which some regard as a Hall of Fame in programming, though it is more accurate to view it as a monument to Knuth as a sleuth. In Knuth’s book my variant of Quicksort is awarded the dubious distinction of being the only one that has resisted Knuth’s attempts at mathematical analysis of its performance. Thus, the inclusion of Quicksort in The Elements of Programming is excusable. It is intriguing that K&R, with their more mature perspective, also go out of their way to include Quicksort.

The third book on my pile that includes a listing of Quicksort is Engineering Problem Solving with C by Delores M. Etter. The code for partition (called “separate” here) looks unusually complicated. As an obscure alternative may be the result of clever optimizations, perhaps in array accesses or item comparisons, I entered the code to find out.

To get it to compile it was sufficient to change one opening brace to an closing one. I assume that the result is the intended source code. Apparently it was not mechanically transferred to the book file. One error is excellent when one has to rely on manual retyping and proof reading.

Of course one cannot be absolutely sure that the character substitution I made did indeed result in the intended algorithm. All I can do is to report that the substitution resulted in successful compilation and in the correct sorting of the example, which is a random-looking sequence of eight integers. Exchanging the first two elements of this sequence gives an array that is not sorted correctly. After this baffling observation I generated a thousand randomly selected random permutations of {0,1,2,3,4,5,6,7}. Of these 73% were incorrectly sorted.

Before leaving the topic of Quicksort, I note that C How To Program (8th edition) by Paul and Harvey Deitel explains Quicksort in an exercise that asks the reader to implement it. Those who remember my confession to an allergy to fat books might infer that I disapprove of the Deitel and Deitel text. With its thousand pages and its weight of 1.3 kilograms, the book is not really portable. But the pages are used well: the examples are simple and illustrative and the coverage is impressive (an introduction to C++ is included). The level of expertise is impressive as well. E.g. (a very gratuitous example) decks of cards are shuffled using the Fisher-Yates shuffle. This is a fast algorithm of which it can be proved that it is as random as the underlying random-number generator. The Deitels are in love with programming. Witness Appendix D of the easily downloadable 7th edition, which is a lengthy discourse on Sudoku puzzles: how to solve them and how to generate them.

A Book on C by Kelley and Pohl first appeared in 1984 and is in print in its 4th edition. I am looking at the smaller 2nd edition. Its strength lies in what is left out: after all, a mortal will only read so much, and finding the necessary parts is easier in a small book than in a big one. A Book on C, first edition, was followed by C by Dissection in 1987 by the same authors. It has the same merits as its predecessor: it is more concise and emphasizes teaching by exhibiting program examples of which the structure is analysed by “dissecting” the program.

Most introductions to programming teach the elements first and postpone the packaging of code as a library to be treated as an advanced topic. The reality of software development is the building of an application using an existing library as much as possible. The quick and dirty approach is to write calls to library functions with a minimum amount of glue code. The better approach is to wonder what is missing from the library so that glue code becomes necessary. That may suggest extending library and proceeding with the application with the extended library, using less glue code. This is the approach chosen by The Art and Science of C by Eric Roberts. Even if one does not want to follow Roberts in his distinctive approach to learning C, his book is worth perusing for the examples and exercises, where his rich professional background shows.

References

[1] Python started as an offshoot of Geurts, Meertens, and Pemberton’s ABC, a programming language intended as a replacement of BASIC that would be palatable to computer scientists. See also my article on Python.
[2] Estimated from the 180 small pages in the C part of his book.
[3] Listed here, so I don’t have to look them up again, the co-authors are: Aho, Pike, Plauger, Ritchie, and Weinberger.
[4] The Art of Computer Programming, Volume 3 / Sorting and Searching, by Donald E. Knuth, Addison-Wesley, 1973.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s


%d bloggers like this: