| Goals | Paradigms | Execution | Language | 3-2-1 | Status |
The Introductory Computer Science sequence at Haverford College provides a novel way to achieve several recommendations of the Liberal Arts Computer Science Consortium, namely the relationship of a mathematical thinking style to computer science and the use of three different programming paradigms. Our approach is novel in a number of ways, including our technique of introducing three paradigms using a single multi-paradigm language rather than two or three different languages.
Our approach to teaching CS1 grew out of a need for a single course to both lay a foundation for a liberal arts computer science major and minor, and to provide programming skills suitable for science majors and students seeking programming jobs. We wish to provide exactly what our course title suggests -- an introduction to computer science, specifically, an introduction to the objects studied by computer scientists (programs, algorithms and data structures) and the ways in which computer scientists study them. We emphasise both mathematically formal techniques (such as the use of proof techniques to reason about programs) and informal "getting a feel for what happens" when a program is run, as both of these skills are important to the practice of computer science. We minimize time spent on language features, providing just enough to let us express a wide variety of algorithms in each paradigm, and focus our energy on exploring ways of thinking about algorithms and data structures, and posing and solving interesting and fun problems in the lectures and labs.
Because we introduce language features and programming techniques alongside formal (and informal) ways of using them as thinking tools, we describe our introductory sequence as a "rigor-first" approach. We have found that this mixture of programming and reasoning skills has a number of advantages, including giving students an accurate image of what is involved in the academic study of computer science, providing a range of fundamental skills that will be important for programming work, and "levelling the playing field" by letting us pose problems that will be challenging for students with prior programming experience as early as Question 5 of the first lab.
We introduce the functional and imperative paradigms in our first semester, and object-oriented programming in the second. We discuss these paradigms as both ways of looking at programs (i.e., a program is viewed as a function relating input to output, a sequence of instructions, or a collection of objects that communicate via messages) and as software design techniques (e.g., think about the relationship of input to output vs. think about taking steps to produce a solution (vs. all the other design techniques we discuss)). Increasing sophistication with the functional and object-oriented paradigms comes later, in our Principles of Programming Languages course, where we cover techniques like functions that create and return other functions, currying, and multiple or non-public inheritance.
We distinguish models of program execution from programming paradigms. Execution can be viewed as a process of substitution of equals for equals, as in mathematics or most work on pure functional programming, or as a process of working step-by-step through a set of instructions (with call trees serving to connect steps in different function calls). The step-by-step model is typically associated with the imperative paradigm, but it is relevant to functional programming in that it is involved in the actual execution of the program by hardware. This connection to the implementation of the functional program helps students who learn best when they see how something works, and is important to all students when they use the debugger or reason about execution time (which can be affected dramatically by multiple executions of repeated subexpressions). Execution of imperative programs is also discussed in terms of both of our cognitive models, and we note that the steps involved in executing a C++ program (given its source code) includes both a process of substitution (in the compiler) and then step-by-step following of the translated instructions.
We believe our approach is best suited to a multi-paradigm language such as Scheme or C++; it may be possible (but ugly) to make it work in languages that are designed to enforce a single paradigm, such as Java or Smalltalk. Our course needs to serve potential computer science majors (who might be best served by Scheme or Haskell) as well as students who wish to learn programming skills that will be applicable in work for other sciences or employment (who are less enthusiastic about Scheme and Haskell).
We currently use a subset of C++ that allows us to defer most of the "sharp edges" of C++ for later courses -- for the first half of the first semester, we use a subset that allows a functional style (function definitions, return statements, conditionals, and local variable declarations (with initialization but not assignment); in the second half semester we introduce imperative features (assignment, loops, reference parameters, global variables); in the second semester we introduce classes and inheritance. We are currently exploring the possibility of porting our course to Java and/or Python.
This, then is our 3-2-1 approach: A discussion of the formal and informal ways computer scientists look at problems and the algorithms and data structures we use to solve them, employing Three paradigms (Functional, Imperative, Object-Oriented) and Two models of program execution (as substitution of equals for equals, or step-by-step following of instructions) in One programming language (such as C++).
A paper describing our approach appeared at SIGCSE '05. We have developed our own course notes for part of the first semester, and are in the process of completing these and exploring options for materials for the second semester. Copies of the CS1 notes are available by email request from Dave W. Lab assignments for our first two semesters can be found through the course web pages for CMSC205 and CMSC206.
For more information about course notes or other aspects of our approach, contact Dave Wonnacott or John Dougherty.
Valid XHTML 1.1 generated by W3C's open source amaya and maintained by Dave Wonnacott.