TITLE: A Classic David Gries Article on Intro Courses AUTHOR: Eugene Wallingford DATE: July 26, 2006 2:27 PM DESC: ----- BODY: Summer is a great time to read old papers, though this summer has been too light on free reading time for my tastes. This morning, I read David Gries's 1974 SIGCSE paper What Should We Teach in an Introductory Programming Course?, which came up in a SIGCSE mailing list discussion earlier this year. Gries has long been involved in the effort to improve computer science instruction, from at least his 1973 PL/I-based intro text with Conway, An Introduction to Programming up to his recent multimedia effort Program Live!, with his son, Paul. In part because his work tends to be more formalist than my own, I usually learn a lot from his writing. This paper focuses on two of what Gries thinks are the three essential aspects of an intro course: how to solve problems and how to describe solutions algorithmically. His discussion of general problem solving was the reason the paper came up in the SIGCSE discussion, which considered how best to teach students "general problem-solving skills". Gries notes that in disciplines such as philosophy one studies problem-solving methods as philosophical stances, but not as processes to try in practice, and that in subjects such as mathematics one learns how to solve specific classes of problems by dint of repetition. By exposing students to several classes of problem, teachers hope that they generalize their learning into higher-order skills. This is true in many disciplines. But we in computer science face a more challenging problem. We strive to teach our students how to write programs that solve any sort of problem, whether from business or science or education. In order to program well across all the disciplines, our students must learn more general problem-solving skills. That said, I do not think that we can teach general problem-solving skills in our intro course, because I do not think the brain works that way. A lot of evidence from cognitive psychology shows that humans learn and tend to operate in specific contexts, and expertise transfers across boundaries only with great attention and effort. The the real question is not how we can teach general problem-solving skills in our intro course, but rather how can we help students develop general problem-solving skills over the course of our curriculum. My current belief is that we should teach programming in context, while opportunistically pointing out the patterns that students see and will see again later. Pick a context that students care about, so that they will have plenty of their own motivation to succeed. Then do it again, and again. By making explicit the more general patterns that students see, I think that we can do better than most CS and math curricula currently do. We would not be teaching general problem-solving skills in any course so much as creating an environment in which students can maximize their likelihood of "getting it". Our courses should not be weed-out courses, because I think most students can get it -- and we need them to, whether as CS majors or as non-majors prepared to participate in a technological society. When Gries looked at what people were teaching in intro CS courses back then, he found them doing what many of our courses do now: describing a set of tools available in a programming language, showing students a few examples, and then sending them off to write programs. Not much different than our math brethren teaching differentiation or integration. Gries exposes the folly in this approach with a little analogy:
Suppose you attend a course in cabinet making. The instructor briefly shows you a saw, a plane, a hammer, and a few other tools,letting you use each one for a few minutes. He next shows you a beautifully-finished cabinet. Finally, he tells you to design and build your own cabinet and bring him the finished product in a few weeks. You would think he was crazy!
(For some reason, this passage reminded me of a witty student evaluation that Rich Pattis shared in his SIGCSE keynote address.) Gries offers a few general principles from the likes of Descartes, Polya, and Dijkstra and suggests that we might teach them to students, that they might use the principles to help themselves organize their thoughts in the midst of writing a complex program. I suspect that their greatest value is in helping instructors organize their thoughts and keep the ultimate goal of the course in mind. For example, while reading this section, I was struck by Polya's fourth phase of solving problems: "Look back". We instructors must remember to give our students both the opportunity to look back at what they've done and think about their process and product, and the time to consolidate their learning. So often, we are driven by the need to cover more, more, more material, and the result is a treadmill from which students fall at the end of the course, exhausted and not quite sure what all just happened. Gries then offers a language for describing algorithms, very much in sync with the Structured Programming movement of the 1970s. My primary reaction to this discussion was "where are the higher-level patterns?" If all we teach students are basic statements, procedure definitions and calls, and control structures, we are operating only barely above the level of the programming language -- and thus leaving students to discover on their own fundamental patterns like Guarded Linear Search. What language should we teach in the intro course? Gries attacks this question with gusto. As I've written before, language sniping is a guilty pleasure of mine, and Gries's comments are delightful. Indeed, this whole paper is written in a saucy style not often seen in academic papers, then and especially now. I wonder if most SIGCSE referees would let such style pass these days? First, Gries reminds us that in an intro the programming language is only a vehicle for teaching the ideas we think are important. It should be as close as possible to the way we want students to think about programs, but also "simple, elegant, and modular, so that features and concepts not yet taught won't get in the way." (As a smug language weenie, I am already thinking Smalltalk or Scheme...) But we usually teach the wrong language:
The language taught is often influenced by people outside the computer science profession, even though their opinions are not educated enough to deserve recognition.
At the time he wrote the paper, Gries would like to have taught Pascal, BLISS, or a variant of Algol, but found that most departments taught Fortran, BASIC, or PL/I. Gries minces no words. On Fortran:
Fortran is out of date and shouldn't be used unless there is absolutely nothing else available. If this is the case, use it under protest and constantly bombard the manufacturers or other authorities with complaints, suggesting the make available a more contemporary.
I learned Fortran in my CS 1 course back in 1983! On Basic:
[It] should never have come into existence. When it was contemplated, its designers should have done their research to see what programming and programming languages are all about before plunging in.
I learned Basic as my first programming language in high school, in 1980! But then Gries expresses one of the tenets of his approach that I disagree with:
I have doubts about teaching students to think "on-line"; algorithms should be designed and written slowly and quietly at one's desk. Only when assured of correctness is it time to go to the computer and test the algorithm on-line.
First, notice the older sense of "on-line". And then ask yourself: Is this how you program, or how you want to program? I know I'm not smart enough to get any but the most trivial programs correct without testing them on-line. Of the choices realistically available, Gries decided that PL/I was the best alternative and so wrote his text with with Conway. I used the 1979 version of this text as the PL/I reference in my data structures course back in 1983. (It was the language companion to the language-independent Standish text I so loved.) Even though Gries grudgingly adopted PL/I, he wasn't happy:
What's wrong with PL/I? Its syntax is enough to offend anyone who has studied English grammar; its data structure facilities ... could have been less clumsy ...; it is not modular ...; its astonishment factor is much too high (e.g., what is 25 + 1/3 ?); ... and so on.
But with the right subset of the language, Gries felt he could teach structured programming effectively. That is just the sort of compromise that C++ advocates made in the 1990s. I willingly accepted C++ as a CS 1 language myself, though it didn't take long for me to realize that this was a mistake. By comparison, PL/I was a relatively nice language for novices. The last section of Gries's paper turns to the topic of program documentation. His central tenet will sound familiar to agile programmers of the new century:
Program documentation should be written while the program is being written, if not before, and should be used by the programmer in proving correctness and in checking his program out.
This is a fine argument for test-driven development! This is a common theme among formalist computer scientists, and one I've written about with regard to Edsger Dijkstra. The place where the agile folks diverge from folks like Gries and Dijkstra is in their strong conviction that we should use code -- executable tests -- to document the intended behavior of the system. If the documentation is so valuable, why not write it in a form that supports automated application and continuous feedback? Sitting quietly at one's desk and writing an outline of the intended algorithm by candlelight seems not only quaint but also sub-optimal. The outline form that Gries recommends is certainly more palatable than other alternatives, such as flowcharts. I think that the modern rendition of this approach is Matthias Felleisen's design recipe approach, described most completely in How to Design Programs. I have great respect for this work and am always looking for ways to use its ideas to improve how I teach. Gries concludes his paper with good advice on "practicing what you teach" for any instructor:
The students will easily sense whether you believe in what you tell them, and whether you yourself practice what you teach.
He wrote this at a time when many CS instructors needed to be retrained to teach the new orthodoxy of structured programming. It has been equally true over the last ten years or so, with the move to object-oriented programming and then agile approaches. One of the reasons I dislike textbooks these days is that too often I get the sense that the authors don't really believe what they are saying or, if they do, that the belief is more a skin they've put on than a deep grokking of the ideas. Gries advises ways in which to deepen one's understand, including the surprisingly surprising "write several programs, both large and small, using the tools and techniques advocated". Why should this be surprising to anyone? I don't know, but I wonder how many folks who now teach an OO intro course have ever written and lived inside a large object-oriented program. The end of this paper supports a claim I made about academic conservatism a couple of years ago, and brings us back to Dijkstra again. First he expresses hope:
You would think that the University, where one searches for truth and knowledge, would be the place for innovative thinking, for people are tuned to new and better ideas.
... and then he quotes Dan McCracken, who had surveyed academics about their intro courses:
      "Nobody would claim that Fortran is ideal for anything, from teachability, to understandability of finished programs, to extensibility. Yet it is being used by a whopping 70% of the students covered by the survey, and the consensus among the university people is that nothing is going to change much anytime soon." Does this sound like educators who are committed to teaching concepts, to teaching people what they need to know to prepare for the future?
As noted above, my alma mater was still teaching Fortran in CS 1 into the 1980s. Gries is hard on his colleagues, as I have been at times, but the truth is that changing how one programs and teaches is hard to do. And he and I have been guilty of making PL/I-like compromises, too, as we try to introduce our own ideas. The lesson here is not one of blame but one of continually reminding ourselves of what matters and trying to make those things happen in our courses. Reading this paper was a nice diversion from the other duties I've been facing lately, and a nice way to start preparing more for my fall CS 1 course. -----