Preface

This book is an introduction to computer programming aimed at the level of a first college course. It is also suitable as a monograph for people beyond the introductory level who are unfamiliar with its methodological content.

A typical introductory programming textbook begins with the notions of algorithm, program, computer, program execution, memory, input, and output. The rest of the book presents a programming language. Each language feature is defined by its syntax, i.e., how to punctuate it, and its semantics, i.e., what the feature does during program execution. Small programs or program segments illustrate each feature and its utility. Because modern programming languages are large, such books are also large. Their organization tends toward completeness; they are broad, e.g., cover many features, and detailed, e.g., address many fine points of features. These books are intimidating in their length, but not in their depth.

Where in such language-oriented books are students explicitly instructed in how to program? Guidance and suggestions are scattered throughout the text, but are usually subordinate to the main chapter structure, e.g., the assignment statement, the if-statement, loops, etc. Illustrative examples are critical, but are usually presented as completed programs. The text typically explains how code works, but not how it was derived. Programming, the dynamic and synthetic activity of creating a program, often gets short shrift, as if you are supposed to learn how to do it by osmosis from staring at code samples. You can know a programming language thoroughly, but still not know how to program. Confronted with a programming problem, you may have no idea where to begin. Or worse, you may head off in the wrong direction, and soon find yourself mired in a morass from which the best path forward may be to back up and start all over again.

In contrast, this book is a methodology-oriented introduction to computer programming. Its subject is programming principles, not language features. To keep focus and avoid distraction, we limit ourselves to a minimal programming language, one so small that it can be said to be universal. Programming skill is measured by the ease with which you can turn a problem statement into a working program, not by the number of language features you know. The methodology presented is not specific to a particular language; rather, it applies to programming, in general.

The notation we use is essentially a small subset of Java, but we hasten to repeat: The book is about programming, not programming in Java. Appendix III: Language Similarities provides mappings between this Java language subset and Python, C/C++, and JavaScript. For our purposes, these languages share a common core. In elementary Physics, one doesn't start learning mechanics by studying one or another brand of springs and pulleys; rather, one learns Newton's Laws and how to apply them in arbitrary situations. Similarly, in this book, I eschew the study of any particular brand of programming language, opting instead to focus on fundamental laws formulated as rules of program composition.

The approach is distinctive in that it presents content to beginners that is often considered advanced. In particular, the following concepts are covered early, and are incorporated into the methodology: States described by diagrams or Boolean expressions, specifications written in terms of preconditions and postconditions, loop invariants, data-structure invariants, loop variants, and programming by stepwise refinement. Notwithstanding the subtlety of these ideas, we aim to retain the introductory character of the book --- by avoiding formalism, offering intuitive analogies, and providing elementary explanations.

Any introduction to programming must deal with disparate student backgrounds. Those with significant prior exposure may be easily bored by a treatment that belabors what they already know. Such students are well-served by our focus on principles, and our deemphasis on programming-language details. Specifically, the programming notation we use (up until Chapter 18) is so limited that it is readily summarized, in toto, in Chapter 2: Prerequisites. For students with a modicum of background, this chapter will be a succinct refresher that firms up prior knowledge, provides standard vocabulary, and establishes a common baseline for the rest of the book. Students with no background whatsoever can learn the material from the chapter, but may wish to supplement it, e.g., with one of the many excellent and free resources on the Internet. Instructors may wish to offer a lecture, or a few recitation sections, to bring everyone up to speed.

A premise of this book is that much of programming can be reduced to a set of rules you can follow in cookbook fashion. The conceit is that programming can (almost) be algorithmic. You, the programmer, just follow the rules, and out will pop a program. And not just any program, but a reasonably good program, at that. You play the role of a computer, and just follow the programming precepts taught in the book. Your input data is a description of the problem for which a solution is desired, and your output is a program that solves the problem. The book chapters teach the precepts, and illustrate how they are applied. Some take just a paragraph to explain; others whole chapters. The precepts as a whole are a codification of the book's subject matter, and are listed in Appendix I.

Precepts are written as imperatives, albeit they are couched in equivocating phrases such as "seek", "consider", "if possible", "prefer", etc. to allow for the possibility that other (perhaps contradictory) precepts take precedence. Thus, I straddle the gap between the fiction that coding can be deterministic (just follow the rules) and the fiction that coding is pure design (inexplicable creativity).

One of my themes is the use of programming patterns, short fragments of code that perform frequently needed tasks. These patterns arise so often that they are best mastered as if they were primitives of the programming language. Patterns are introduced and discussed throughout the book. You are encouraged to learn each pattern so well that it becomes an atomic notion in your programming vocabulary. When, in the course of programming, you see the need to do something for which there is an established pattern, you should be able to recognize the pattern's applicability, and then immediately blast it into your program in one indivisible action. In the parlance of cognitive psychology, you should have chunked the pattern, and should no longer think of it in terms of its constituent parts. The programming patterns are listed in Appendix II.

The book's focus is synthesis, not analysis. Thus, no substantial code is presented as a fait accompli for interpretation. Rather, the essential content of the book is the stepwise development of solutions rather than the solutions per se. In cases where more than one approach comes to mind, each will be considered, explored, and evaluated. A few examples are consequential algorithms. My purpose, however, is instruction in programming, not algorithms. As such, although an example may have a well-deserved reputation and a noteworthy asymptotic running-time complexity, these will be incidental to its use in illustrating how you might develop the program yourself.

Code is presented in a sequence of incremental steps that are displayed in numbered "movie" frames. That way, you are shown a recommended order of development, and not just the final program. Each coding "movie" starts with a specification in frame one, and ends with the finished product. Some motivating examples are sufficiently substantial to warrant chapters of their own. One of these, Running a Maze, serves in multiple chapters throughout the book. The final versions of three examples with long piecewise developments are presented whole in Appendices IV-VI.

Many notions that are conceptually part of the canon of object-oriented programming, e.g., encapsulation, information hiding, and modularity, are addressed prior to objects. They are introduced first at the level of statement-level specifications and implementations, and are subsequently reiterated using the easily-understood concept of a class's lexical scope --- without reference to objects. In contrast, essentially all discussion of objects per se is deferred until the end of the book. This approach lets me focus on core programming skills, and effectively defers a plethora of distracting details (such as object instantiation, the class hierarchy, inheritance, polymorphism, and dynamic method dispatch) until they are finally introduced in the penultimate chapter. A benefit of this delay is that most of the book is truly language independent, even if Chapter 18 is not.

Much of the power of a modern programming language comes from libraries. If you plan to do any serious programming in a given language, you will surely want to master its libraries, and use them rather than "reinventing the wheel". Despite this important fact, for pedagogical purposes I focus on how to program in the base programming language, and largely ignore libraries. Although their use is eschewed, libraries are far from forgotten. In fact, the text foreshadows the need for generic collections, and then implements the library class ArrayList as a motivating example in Chapter 18: Classes and Objects. Thus, you are led right to the pearly gates of libraries, armed with the ability to read and understand library interface specifications, and to use them to advantage.

We advocate a cautious approach to programming throughout the book, but mistakes are inevitable. Debugging code is like trying to find "a needle in a haystack", and the topic is not realistically discussed in the context of short program segments. Accordingly, the subject is deferred until the final chapter, where we deliberately introduce bugs into the largest program example of the book, and then discuss how to find them.

Language-oriented introductions to programming tend toward being encyclopedic tomes; in contrast, I have aimed for a comparatively short, coherent, and digestible book. I have aspired to tell a compelling story, knitted together by interesting, nontrivial examples that are woven throughout --- a book that invites cover-to-cover reading.

The text is supplemented by Exercises in Appendix VII that give you the opportunity to test your knowledge. It is one thing to follow along and convince yourself (passively) that you understand material; it's quite another matter to confirm (actively) that you have really absorbed the message. Toward that end, you are encouraged to do as many exercises as possible. They are organized by chapter, so a reasonable approach is to turn to them after reading each chapter. Some exercises are direct applications of ideas presented in the text; others push the envelope on related topics, and in effect incorporate new material.

Many exercises call for writing programs. You are encouraged to not only solve these "on paper", but to test out your solutions on a computer. The BlueJ programming environment is recommended for this purpose, but any programming environment will do.

Keep in mind that the exercises are your opportunity to apply the book's principles. Don't just come up with correct solutions; rather, do so with conscious attention to the guidance being offered. One way to reinforce the material is to articulate explicitly the precept or pattern number you are applying on each coding step. My hope is that the methodology I'm advocating will eventually be second nature to you.

The Internet is an amazing resource that you can and should use to augment the text. You can find relevant articles on virtually every concept discussed in the book, and you are encouraged to Google for such supplemental material. Most of the book's literature citations refer to convenient online web pages rather than original primary sources; thus, they are only a click away. Enjoy the background provided by Wikipedia, but be sure to stop reading before its details overwhelm and discourage you.

The book's Index is rather thorough, and can be used in a manner akin to flashcards, e.g., if you have read the text up through page k, then you should understand each term in the index that refers to a page between 1 and k.

My aim in writing this book is your proficiency in programming. I wish you well.

Tim Teitelbaum
Ithaca, NY