Program By Design


Dr. Stephen Bloch, Adelphi University

What is this workshop about?

This workshop grew out of work done at Houston's Rice University on teaching beginning computer programming. Rice faculty worked out an approach that worked well for their freshmen, then adapted it for use at the high school level and started offering summer workshops for high school math and computer science teachers. Over the past 20 years, these techniques have indeed been implemented successfully in computer science and/or math courses at hundreds of high schools, ranging from wealthy suburban districts to poor inner-city districts.

At the same time, a number of colleges and Universities -- large and small, ranging from community colleges to elite research universities -- have incorporated the approach into their beginning programming courses, either for majors or for non-majors ("Programming for Poets"). The present series of workshops seeks to disseminate the approach more widely at both college and high school levels.

The approach has even been used successfully at the middle-school level; see Bootstrap World, a set of modules (suitable for either after-school or in-class use) teaching middle-school students algebraic concepts in the guise of writing video-games. The Bootstrap curriculum, language, and software are extremely similar to what we'll cover in this week's workshop.

So what is this approach?

Language and environment issues

What are students supposed to learn in a first programming class? Which of the things they're supposed to learn are important and fundamental concepts, and which are merely necessary skills, to be obsolete in a few years? My answer:

Principle 1 The first programming course is not about learning a programming language, it's about learning to solve problems algorithmically.

Students in first programming courses invariably think the course is about programming language syntax: they spend much of their time fixing syntax errors and much of their mental energy memorizing syntax rules, when as instructors we would prefer that they concentrated on more fundamental concepts, principles, and methodologies. From this perspective, any programming language is a necessary evil: necessary in order to write real programs that really run on real computers, but evil insofar as it distracts students from thinking about problem-solving.

Corollary 2 Introduce only those language constructs that are necessary to teach programming principles, when they are necessary to teach programming principles.

No matter how "nifty" or powerful a language construct is, if it doesn't help you teach a CS1 principle, it doesn't belong in CS1.

Corollary 3 For a first programming course, choose a language with as few language constructs as possible, and in which it's possible to introduce them one at a time.

In many popular languages (notably Java and C++), there are hundreds of syntactic constructs, of which a dozen or more are needed to write even a "hello, world" program. The usual approach to teaching in these languages is "boilerplate" code which is given to students with the assurance that "you'll understand this in a month or two." Unfortunately, this sends students the message that it's OK to write and turn in code that you don't understand.

We choose, instead, to use a small subset of the Racket language (related to Scheme and Lisp). I can get through an entire semester of Programming for Poets on half a dozen syntax rules, one every few weeks -- and by the end of that semester, my Theatre and History majors are writing real-time video-games involving higher-order functions that recursively traverse linked lists and trees, without ever writing a line of code that they didn't understand.

Another problem with teaching CS1 in complex languages such as Java and C++ is that, by misplacing a few punctuation marks, students can accidentally invoke advanced language features they haven't been told about, getting obscure error messages (or worse, obscure run-time behavior). Consider, for example, a beginning C++ student who writes

hours * wage = pay;

It's an obvious mistake: it looks like algebra, and in algebra the "=" sign is symmetric, so it shouldn't matter what's on the left and what's on the right. But C++ interprets it as a declaration of a variable wage, of type "pointer to hours", initialized to pay. The error message may complain that wage is already defined (which the student already knows -- that's why (s)he used it!), or that hours isn't a data type (and why should it be?), or that pay isn't of pointer type (huh?) None of this makes sense to a student at this level.

Corollary 4 For a first programming course, choose a development environment that enforces pedagogically-oriented language subsets.

The freely-downloadable DrRacket development environment provides over a dozen subsets and variants of the Racket and Scheme languages. With language subsets, the compiler can give level-appropriate error messages when a student accidentally invokes features that, while legal in the full language, have not yet been introduced in class. As students grow to need more language features, a few mouse-clicks allow them to move to the next larger language subset.

We also want to motivate our students using exciting technologies such as graphics, animation, GUI programming, networking, etc. But many of these things inherently require some of the language features that we exclude from beginner-level language subsets. So we've developed a number of libraries in the full language that can be invoked by student programs in beginner-level language subsets. Some are general-purpose libraries for graphics, animation, etc. while others focus narrowly on a particular problem, e.g. providing a graphical interface to a student-written program that converts between Fahrenheit and Celsius.

We recognize that realistically, most students will find Java, C++, or Python more useful in the job market than Racket, so we teach those languages too -- after students have developed a solid grounding in principles and methodology in the simpler, more consistent Racket setting. Depending on the demands of a particular course or department, we switch languages after 10-15 weeks, teaching the Java approach to the same concepts and techniques that students have already learned in Racket.

Pedagogical/curricular issues

But it's useless to turn students' attention away from language and towards problem-solving unless they have some principles of problem-solving to learn. We teach students a step-by-step "design recipe" that takes them from an English-language problem description, through precise specification of the program's desired behavior, including test cases (written before the code they are to test), through development and testing of code. Each step of the design recipe has concrete questions that students can ask themselves, and concrete deliverables without which they cannot go on to the next step. The design recipe places a heavy emphasis on data types -- in identifying the input and output data types of a function, in choosing test cases based on those data types, in following type-driven coding patterns, and in analyzing bugs revealed in testing.

An important part of our curriculum is test-driven development. This is a widely-used industry practice, but it turns out extremely useful for beginning programmers as well: it forces students to clarify their understanding of a problem and make its behavior explicit, before getting muddled up in code. Having the test cases already written also makes it unlikely that a student under last-minute deadline pressure will skip the testing stage altogether.

The type-driven coding patterns are also particularly useful, often providing as much as 90% of the code for a particular function. We teach students that the shape of the data determines the shape of the code. For example, if the input data type is a union of three choices, the code will almost certainly be a three-branched conditional; if the input data type is a structure with two fields, the code will almost certainly access those fields; if the input data type is self-referential on a particular field, the code will almost certainly recur on that field; and so on. These principles apply equally well (albeit with different syntax) in Racket, Java, and any other high-level language.

Recursion, in particular, falls out automatically as the straightforward application of already-learned coding patterns to a self-referential data type; my students don't know that recursion is hard and mysterious. Furthermore, it's a particular restricted form of recursion, structural recursion (i.e. recursion on the self-referential parts of a structure) which cannot go infinite unless the input itself is infinite or circular. We then introduce two generalizations, accumulative recursion and generative recursion, with how and when to use each. Again, these topics are taught in Racket and then again in Java.

Higher-order functions are easy to write and use in Racket, and motivated not only by general considerations of abstraction and re-use but by the need for callback functions in a GUI. Our students learn to use higher-order functions comfortably in Racket, and then learn how to accomplish the same things in Java.

But don't take my word for how well all this works. Read what other teachers have said about the approach.

This material is based upon work supported by the National Science Foundation under Grant Nos. 618543 and 0010064, both now expired. This year's workshop is funded by Google's CS4HS program. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or Google.

Last modified: 
Stephen Bloch /