To appear in the proceedings of the 29th Small College Computing Symposium, April, 1996, St. Cloud, Minnesota. This is one panelist's contribution to a panel discussion entitled "Which Language/Paradigm for Computer Science I?" moderated by Karen Sutherland.
At Gustavus, we have an overarching goal for our introductory computer science course, from which the specific course objectives are derived. Our goal is that students shall get a representative trial experience of thinking and working like a computer scientist. In our opinion, this means that students must experience the power of abstraction: they must work smart rather than hard by working in sufficient generality, and they must benefit from doing so. It also means that the students must have hands-on involvement in all the primary activities of computer scientists: not only programming, but also proving, analyzing, predicting, measuring, and writing. Finally, they must see these activities as part of a coherent whole: theory is not a contrast to practice but rather an integral part of practice.
The easiest setting for students to derive eye-opening power from abstraction in is programming, so our concrete objectives include several that center around abstraction-oriented programming activities. Students should experience the power of higher-order programming, in which rather than writing multiple procedures that have the same general form, they write a single higher-order procedure to capture the computational pattern. Students should also experience the full benefits of data abstraction, i.e., of adopting the operational stance that anything that quacks like a duck is a duck. In our experience, they experience the power inherent in this stance most fully through polymorphism, i.e., through being able to uniformly interface with diversity.
Another of our concrete objectives is that students should use induction both for proving procedures correct and for designing procedures in the first place. The essential feature of induction is that it allows you to think about only one layer of a recursive or iterative process, taking for granted that the remaining layers will perform as intended. This is a substantial degree of mental leverage when compared with tracing around and around a loop in your head or, worse yet, trying to descend through a recursion in your head and then find your way back out.
Our final objective is that students should adopt the asymptotic outlook on performance, asking not which algorithm is faster, but rather which more quickly grows slow as the input size increases. This includes not only mathematically analyzing algorithms, with the results expressed using the big-theta notation, but also the making of predictions and the testing of those predictions with measurements.
We use the Scheme programming language in our CS1 course because it provides three forms of support for the above objectives:
In Scheme, procedures are first-class values that can be passed as
arguments to other procedures, returned as results from
procedure-producing procedures, embedded in data structures, etc. One
example of the opportunity this provides us for showing the power of
abstraction is a lab exercise on constructing verifier procedures for
ISBN (book) numbers, UPC (grocery) numbers, credit card numbers, etc.
Each of the many kinds of identifying numbers we look at has some
distinctive arithmetic property used to catch errors. If we use d[i]
to represent the ith digit of the number, the properties are all of
the form that the sum over i of f(d[i],i) is divisible by m. The
difference between a UPC code and a credit card number, for example,
is that a different function f and modulus m are used. Using Scheme,
our students can write a general verifier generator procedure, which
receives f and m as arguments (f being a procedure), and returns a
newly constructed verifier procedure as its result. That verifier can
then be applied to a specific number, and returns a true or false value
to indicate whether the number has the correct form. All the hard
work is shared between the various verifiers in the verifier
generator, since that's where the common structure of summing over the
number's digits is implemented.
Our students also use Scheme to develop systems in which generic operations can be applied to a diverse collection of data in a uniform manner, with the actual implementation used in each instance determined by the operand's actual data type. (This kind of dynamic polymorphism is of course also a key ingredient of object-oriented programming.) As an example, we have used an assignment in which each student independently develops some sort of biographical "database" system -- one might do women scientists, another baseball players, etc. Although there are operations unique to each type (like finding the batting average), there are others (like finding the name) that are common. However, since the students worked independently, there is no representational commonality -- in one case, the name might be first in the list representation, while in another case it might come later, and be separated into first and last names. Thus, on the surface, a different name access procedure is needed for each type, and the prospects for unifying the databases seems dim. But -- presto change-o -- by layering a polymorphic operator over the surface, the students can uniformly access any person's name. They use this to do things like ask for the names of everyone born before 1910 and have a mixture of scientists and players returned. The code to do this simply steps through all the people in the combined database (regardless of type), checking the date of birth in a uniform way and, where appropriate, retrieving the name in a uniform way.
Little needs to be said about the fact that Scheme's simplicity leaves room for topics other than programming-language mechanics. However, there is less appreciation for another way in which Scheme supports the introduction of mathematical activities, such as proving, into CS1. Namely, rather than merely having some time in which to do induction (for example) but still needing to do a radical switch of mental gears to get between programming and proving, our experience is that with Scheme the students can fluidly switch back and forth between the activities because they are so similar. This helps us to integrate them very closely -- we introduce recursion and induction simultaneously, then iteration and invariants simultaneously.
The biggest disadvantage to Scheme is that it is far removed from how computers compute. At an intellectual level, this means that a student exposed only to Scheme will miss one aspect of the computer science discipline: an understanding of computers. (They are also likely to miss interesting state-based algorithmic techniques, such as dynamic programming.) At a more practical level, this creates difficulties making a successful transition to other languages, such as C++. Although a good C++ programmer needs to be an abstraction-oriented thinker (such as Scheme helps us develop), there is no question that a C++ programmer also needs a firm grasp of the machine model: memory locations, allocation and deallocation, storing and retrieving, etc.
In our experience, the difficult part is not imperativeness per se -- students have little trouble moving from purely functional programming to programming of the "do this, then do that" form, so long as the actions are all I/O. Where the problem starts is with the computer's memory: numerically indexed locations used for computational state. Functional programmers have a difficult time adjusting to the idea that one part of their program can store a value in a location, and then another part of their program can later retrieve the most-recently stored value from that location.
We have chosen to take this bull by its horns. Our students' first exposure to any form of state (at the beginning of the second semester) is when we present the organizational structure and assembly language of a simplified RISC machine. We make a big deal in that context out of memory locations: allocating and deallocating, storing and retrieving, etc. We also get to show how computers work (at a high level), how recursion and iteration play out in assembly, etc.
Once students have accepted the new concept of memory location, we abandon assembly language programming in favor of a higher-level language in which to explore the new programming possibilities we have opened up, such as dynamic programming and object-oriented programming. Since students are already familiar with Scheme, our choice has been to use Scheme, simply adding its vectors (one-dimensional arrays) to our earlier functional subset. We tie Scheme's vectors to the machine's memory in two ways: we describe them as chunks of the machine's memory "showing through," and we show how to use vectors to write a machine simulator in Scheme.
Our first-semester students program only functionally and only in Scheme. Our graduating seniors are also capable of doing object-oriented programming in C++. When and how does this change occur?
The most important change is not the change in superficial notation (prefix to infix, for example) but rather the paradigm shift. This includes not only the shift from functional to object-oriented, but also the shift from high-level to machine-level, since the C++ programmer is faced with issues hidden from the Scheme programmer, such as that a memory location may not be big enough to hold a particular integer or that an object needs to be deallocated exactly once, and only after its last use.
As indicated above, we pave the way for this transition at the beginning of our second semester, by introducing a simplified computer architecture and doing some assembly language programming for it. The remainder of the second semester continues the paradigm shift. First we do imperative programming using vectors, such as one might do in Fortran; we start with simple examples like producing histograms, but work up to dynamic programming. Next we use vectors as the basis for introducing object-based programming, i.e., programming centered around mutable abstract data types. (Immutable abstract data types were covered in the first semester.) Finally, we blend in dynamic polymorphism (also from the first semester) and inheritance, arriving at object-oriented programming as the synthesis of our earlier emphasis on abstraction and our new emphasis on state. At this point, we have object-oriented programmers, but they are still programming in Scheme. A few weeks remain in the second semester. Starting this Spring, we are going to use those few weeks for a crash course in C++.
Naturally, this second semester course is not the end of the transition, but rather just the beginning. Another key course is "C++ programming and software development," in which intermediate-level students learn not only more of C++ than we could introduce in our second semester introductory course, but also a modicum of such vocational skills as requirements analysis, design, and quality assurance. Finally, there is quite a bit of informal learning that goes on through peer-to-peer instruction, the application of C++ (as well as Scheme) in advanced courses and independent projects, etc. Not least of all, our students benefit enormously from internship opportunities.
We are now starting our sixth year of using Scheme in our introductory sequence, and we are quite satisfied with the outcome. Our students have proven to be unusually well attuned to what it is to be a computer scientist, and have not experienced the "culture shock" in advanced courses that befell students in earlier days, when we had a more traditional introduction based on Pascal programming. Moreover, they have proven to be good programmers, able to write real programs in languages other that Scheme, such as compilers in C in the senior-level compilers course, while still retaining the emphasis on abstraction that allows them to write better C programs that most born-and-bred C programmers ever do. We have received good feedback from internship supervisors, alumni in graduate school, and alumni in the workforce.