This proposal for participation in the ChiliPlop '98 hot topic Elementary Patterns and their Role in Instruction is in two parts. In the section on current practice I describe how we currently use patterns in our three course sequence introduction to programming and computer science at Duke University. In the section on proposed pattern use in CS1 I outline a proposal for introducing patterns differently in a a first course in Computer Science. The intent of this proposal is both to make the first course a better introduction to programming and design for students and to set the stage for a more in-depth study of patterns in subsequent courses.
Current Practice in Using Patterns at Duke
In brief, we currently use a spiral introduction to patterns. We show
students design patterns as part of a library of classes we provide
and that students use in the first two courses. We explicitly study
design patterns in our third course; all these courses are described
below. The other feature of our introduction is to show patterns in
context: solving problems in programs that students understand at
their current level of program-understanding. We have had to develop
several program frameworks to support this context, we expand on this
below and in the future directions section.
We have a three course sequence introducing students to programming and computer science. Each course and its core is summarized below:
Course | Purpose |
---|---|
CPS 06 | Introduces students to programming in C++ and to computer science. Students use a library of classes on which they build their programs, and generally implement a design provided to them, or implement a piece of a larger program, rather than designing and implementing programs from scratch. A string and vector class are used rather than their "raw" C++/C counterparts. |
CPS 100 | Continues the study of programming, again in C++. Data structures and analysis of algorithms are covered as are more object-oriented programming concepts such as inheritance. Again, most of the programs rely on provided infrastructure in terms of classes, design, or scaffolding on which students build. |
CPS 108 | This is a course in software design and implementation. Roughly the first half uses C++, then Java is used. This is a course organized around team projects with much larger programs than in the first two courses. Students typically implement two to three 1,000-2,000 line programs with 10-15 classes, and one 5,000 line program, often with 100 or more classes. The emphasis in the course is on design, but this is also the first course in which students see some low-level details of C++ (e.g., arrays allocated with new rather than using a vector class). |
In the spiral approach, a design pattern is introduced and used in programs and classes in the first course. A name is associated with the pattern, but to date we have not discussed why the pattern/solution is appropriate (see future directions). The pattern is used again in the second course, often in a new context, but to solve the same problem for which the the pattern was originally introduced. Our intent is that students see the pattern, and subsequently patterns in general, as a normal part of their programming and design toolkit; not as a special topic discussed as advanced, extra, or somehow different than core programming. In our software design course, we use a more rigorous introduction, using either GOF [1] or Buschmann et al [3] as a resource. Since we have built a concrete context on which to discuss specific patterns in our first two courses, the more abstract and general concept of design patterns is more accessible to students. In summary, the approach we use is
Once students understand iteration, we can discuss the code above. We do not discuss the implementation of the WordStreamIterator class since this requires somewhat esoteric knowledge of resetting and rereading streams. When we get to arrays, we can study how to make this code more efficient. However, we have designed the course to emphasize conceptual understanding before concerns of efficiency. The key point here is that students understand the first, isDone, next pattern for iterating without knowing how the code supports the iteration.
In our second course, we use a map class with an external iterator that uses the same naming conventions. The code below uses the same class WordStreamIterator, in conjunction with a hash-table based map class, to count occurrences of all words in a file.
The essential point here is that we use the same iterator pattern, but in a new way: as part of an inheritance hierarchy of abstract and concrete iterator classes. Note that the makeIterator function above is an example of the GOF factory pattern. When we initially show this example to students we do not talk about the factory pattern, but we highlight the creation of a concrete HashIterator internally within the hash map class that appears to clients as an abstract Iterator.
Finally, in our third course, we discuss how iterators are implemented, the trade-offs between internal and external iterators, and the memory-responsibility problem of the makeIterator factory method (solved by using a stack-based pointer Proxy class, where Proxy is another GOF pattern). We expect students to develop iterators on their own to solve problems that arise in conjunction with programming projects they design and implement.
We use software cadavers in the same way: we introduce programs and program frameworks to provide a setting in which students explore programming and design patterns. In our current use of these program frameworks (aka software cadavers) we have emphasized building a structure that facilitates the study of design patterns (but see the future directions section for some ideas on how other patterns can be incorporated).
Conceptual Cadavers We use conceptual cadaver to mean a concept for a program that we implement in several different ways, or a basic idea that we use in different ways. The idea is repeated in one course and across courses. For example, in the word-reading code above we read words from a text file. In the next course we read words from a text file but use a map to store them. Processing textfiles (e.g., as accessible from Project Gutenberg [5] as large sources of data facilitates discussions of trade-offs in algorithms, data structures, and program design. For example, in the 1998 offering of our CPS 108 course one of the student projects develops file-based and web-based search engines (e.g., see Glimpse [6]). This requires iterating over a source of words. The source can be a file or a web-page specified by a URL, with the right interface the differences should be minor or non-existent. Our students use a factory to return the word source, an iterator to access the words, an adaptor to ensure the URL source and the file source have the same interface, and so on.
Concrete Cadavers Our conceptual cadavers are designed to provide a familiar setting in which to study GOF (and other) design patterns. Students, however, need concrete examples rather than abstract explanations. To this end we have developed pattern software cadavers. These are working programs that provide a framework for seeing patterns in action.
We are working on developing several software cadavers, at this point we have three developed, two in active use. We use a C++ program that models the game of roulette to show OO concepts and idioms in practice, we omit a detailed coverage of this software framework here. Our most useful program is both a conceptual and concrete cadaver. It builds on a program for manipulating bitmap images that we use in our introductory courses and described in [7] written in C++. As we use currently use the program it is object-based rather than object-oriented. However, in our CPS 108 course we introduce an object-oriented, pattern-based version of the program in C++. The idea of using the same program before and after [8] patterns have been used has worked very well. This version uses several GOF patterns including Command, Adapter, and Model/View/Controller. A class diagram is shown below
We use a Java version of the pixmap program in our CPS 108 course to introduce the language, supplying another conceptual connection to a familiar setting. A screen dump from the Java program is shown below. In addition to the patterns employed in the text version, the Java version uses the Observer/Observable pattern.
We are in the process of developing a C++ version very close to the Java version, but which uses the Qt widget set.
The main idea in our proposed direction for the first course is for students to recognize and choose appropriate patterns for solving programming problems. We want students to become accustomed to thinking about the forces and consequences that exist in a problem, and to choose a pattern to help solve the problem. When confronted with a programming problem students often have trouble starting to derive a solution. We propose that an appropriate pattern tool-kit will assist in starting the programming process and direct students towards appropriate solutions. However, there cannot be too many patterns or students will think that programming is about looking through a book of solutions to find the right one. The hard work here is in developing ten to fifteen programming patterns (this number may be too high, it may be that five to ten is more appropriate). These core patterns will help students develop low-level programming expertise rather than higher level design expertise which we believe will come in later courses. In some ways, very basic code-design patterns such as Simply Understood Code are about designing code rather than designing programs. These simple patterns are as important as the programming patterns we have in mind. In [11] Wallingford provides some example of the kinds of patterns we plan on developing and using.
We propose the following pattern, outlined in [4] as the kind of programming pattern we hope to build a course around.
Consider the problem of processing sequential data, e.g., all the values in an array, or the values in a file. When the processing is complex, beginning students often try to use two loops where one loop leads to code that is easier to understand and easier to develop correctly. To see this problem in context, ask students to write code to remove all zeroes from an array, leaving the order of the other elements unchanged, i.e., to change the array on the left below to the array on the right.
In our experience, most students write one loop to process all the array entries, and one loop to try to find and remove zeros. This invariably leads to off-by-one bugs, problems running off the end of the array, and problems with boundary cases (e.g., first zero, last zero). A simple loop with an if statement tracking the last non-zero index leads to short, concise code; see [13]. A similar example is the partition part of quicksort. Most approaches use an outer loop with two inner loops: one moving from left-to-right and the other from right-to-left. It is easy to get this loop wrong, and it is not as amenable to optimizations needed in production quicksorts as the simple one-loop with an in if statement outlined in [15]. As another example, consider processing run-length encoded representations of black and white pixel data for rectangular images, e.g., 4 1 2 3 represents 0000100111. With no guidance, students often try to write nested loops to fill a matrix, rather than a single loop to read the file and populate the matrix. Captured as a pattern we might call this problem One Loop for Linear Structures and categorize it briefly as
Therefore, use the structure of the data to guide the
programmed solution: one loop for sequential data with appropriately
guarded conditionals to implement the control.
Algorithmically, a problem may seem to call for multiple loops to
match intuition on how control structures are used to program a
solution to the problem, but the data is stored sequentially, e.g., in
an array or a file (or even a matrix). Programming based on control
leads to more problems than programming based on structure.
The key issues here are:
Again we propose to use both a spiral approach and software cadavers that are part of our apprentice style of learning in building our introductory courses around programming and design patterns.
[2] A Computer Science Tapestry.
Owen Astrachan. McGraw-Hill. 1997.
[3]
A System of Patterns: Pattern-Oriented Software Architecture
Frank Buschmann and Regine Meunier and Hans Rohnert
and Peter Sommerlad and Michael Stal.
John Wiley. 1996.
[4] Design Patterns: An Essential
Component of CS Curricula.
Owen Astrachan, Geoffrey Berry, Landon Cox and Garrett Mitchener.
SIGCSE Technical Symposium on Computer Science
Education. Atlanta, GA, February 1998. (to appear)
[6] Glimpse: a tool to search file systems.
[7] Animation, Visualization, and Interaction in CS 1 Assignments. Owen Astrachan and Susan Rodger. SIGCSE Technical Symposium on Computer Science Education. Atlanta, GA, February 1998. (to appear)
[8] Before and After. Technique discussed at the first Using Patterns Conference: (UP97).
[9] AAA and CS1 : The Applied Apprenticeship Approach to CS 1. Owen Astrachan and David Reed. SIGCSE Technical Symposium on Computer Science Education. Nashville, TN, March 1995.
[10] Application-based Modules using Apprentice Learning for CS 2. Owen Astrachan and Robert Smith and James Wilkes. SIGCSE Technical Symposium on Computer Science Education. San Jose, CA, February 1997, pp 233--237.
[11] Toward a First Course Based on Object-Oriented Patterns. Eugene Wallingford. The Papers of the Twenty-Seventh SIGCSE Technical Symposium on Computer Science Education. 1996. pages 27--31.
[12] Simply Understood Code. Richard Gabriel. Located at the wiki-wiki web.
[13]Pictures as Invariants.
Owen Astrachan. The Papers of the Twenty-Second SIGCSE Technical
Symposium on Computer Science Education. 1991. 112-118.
[14]Programming Pearls.
Jon Bentley. Addison-Wesley. 1986.
ola@cs.duke.edu
Last modified: Tue Feb 24 22:32:22 EST 1998