Prabhakar Ragde, School of Computer Science, University of Waterloo
This document describes a two-course first-year sequence, CS 135 - CS 136, to be offered in addition to the existing CS 133 - CS 134 sequence. The first course, CS 135 presents basic concepts in the functional language Scheme, preparing the way for transition to an object-oriented language. The second course, CS 136, introduces the Java language and covers elementary data structures and algorithms in a fashion similar to CS 134. The new approach is based on an excellent textbook, "How To Design Programs" (Felleisen, Findler, Flatt, Krishnamurthi) that is in use at several comparable institutions for the same sort of course sequence. Students would voluntarily choose one sequence or the other. The new sequence is aimed at students for whom the current sequence may not be working well: those who might be bored with CS133 but are not ready for 134; strong students, with or without prior experience, who may appreciate the more conceptual approach; those who struggle with Java syntax; those who are not getting enough exposure to programming fundamentals; and those who might be intrigued by the enrichment possibilities offered by a functional language.
ACM/IEEE's Computing Curricula 2001 (CC01) discusses several models for introductory computer science courses. We have tried three of these at UW. The traditional imperative-first model dates back to before Curriculum '78 twenty-five years ago. In the '80's, the breadth-first model was implemented in CS 131/132; when that proved not to work well, we retreated to the imperative-first model in the '90's, and more recently, made a natural transition to the objects-first model when Pascal was replaced by Java. The thesis of this proposal is that our program is now large and diverse enough to support yet another model, the functional-first model -- not as a replacement for the objects-first model, but as an alternate choice.
The benefits of the objects-first model are obvious: object-oriented languages are in widespread use in industry and academia, and the object-oriented paradigm has proved effective in the design, rapid deployment, and evolution of large software systems. Most institutions have adopted an OO language for the introductory sequence, though some may still be using it in an imperative fashion (first teaching control structures, procedures, and functions, an approach sometimes known as objects-late). CC01 makes the following criticisms of the objects-first approach:
At the same time, the objects-first model does not specifically address many of the disadvantages common to programming-first approaches [...]. In fact, the problems of the programming-first approach can be exacerbated in the objects-first model because many of the languages used for object-oriented programming -- particularly C++, but to a certain extent Java -- are significantly more complex than classical languages. Unless instructors take special care to introduce the material in a way that limits this complexity, such details can easily overwhelm introductory students.
That this complexity is a factor at UW can be seen by the introduction of the two-course sequence CS 131-132 to cover the same ground as CS 133, and the increasing number of students (currently 40% of the incoming class) who are opting for this longer sequence. We were all frustrated by the syntactic and semantic deficiencies of Pascal, and it is ironic that the move to Java has introduced new complications in this area at a higher level. For some semantic weaknesses of Java in a CS1 environment, see the paper by Andreae et al. (including at least one UW grad) on experiences at Victoria University of Wellington in New Zealand, as well as any paper which advocates replacing Java with C#. For some discouraging experiences related by early objects-first advocates, see the recent message by Stuart Reges, "Objects have failed us", on the SIGCSE Member Forum, as well as the recent WCCCE paper by Gregg and Ficocelli. A survey of thirty years of introductory CS textbooks by McConnell and Burhans (PDF format) demonstrates a decrease over the years in the coverage of foundational topics, which they define as "simple data types, selection statements, repetition statements, record structures, and arrays" and an increase in topics such as GUIs, often introduced very early in objects-first textbooks.
Since the object-oriented methodology was conceived while traditional imperative languages were dominant, many early textbooks grafted it onto the traditional treatment. This is essentially the imperative-first model taught in an OO language, and it may be one way of avoiding the complexity referred to above. But it comes at the cost of de-emphasizing the OO aspects of a language and encouraging students to program in old-fashioned ways. Gregg and Ficocelli term this "retrograde" even as they reluctantly adopt it as a partial retreat from objects-first.
The functional-first model takes a different route to avoid this complexity by using a functional programming language (e.g. Lisp, Scheme, ML, Haskell). These have a simple syntax based on the application of functions, both primitive and user-defined. Changing variables (assignment or mutation) can be introduced quite late, or not at all. Because of this drastic difference between functional and imperative languages, it is unlikely that students will pick up unhealthy imperative programming habits that will persist when they move to an OO language, and they may be able to shed unhealthy habits picked up by high-school exposure to, say, Visual Basic. CC01 lists the following generic advantages for the functional-first model:
To these I would add that the time saved by not having to master intricate syntax (that is useful to experienced programmers but an obstacle for beginners) might be spent in showing students how to analyze and deal with more complex situations; that is, how to think algorithmically. The above-linked paper by Gregg and Ficocelli identifies this as a weakness of the students they trained in an objects-first approach, and I as well as others have noticed this weakness in our students in upper-year courses.
CC01 goes on to list disadvantages of the functional-first model, also recommending that it be followed by an "Objects and Algorithms" second course.
There are, however, some dangers in this approach. The first is that students may react skeptically to learning a language that they see as outside of the mainstream. For students who are already committed to computer science, it is possible to overcome this objection by exploiting the expressive power of these languages and showing how much students can accomplish using these tools. For students who are taking an introductory computer science course to test the waters before jumping in, and particularly for students who see the course as a way to learn some practical programming skills, functional languages are a much harder sell. The second danger is that this approach typically requires students to think much more abstractly at an early stage than is true with more traditional programming languages. While forcing students to think in this way is certainly valuable and needs to be part of the curriculum at some point, placing it so early can discourage some students with less experience in that style of thought.
Some of these possible advantages and disadvantages are diminished and
others augmented by the peculiarities of our situation at UW: two
computing courses required of all students in a Faculty of Mathematics
(and hence with reasonable math skills), with future CS majors and
non-majors intermixed. This suggests that offering a choice of two
models, rather than forcing everyone into a single mold, may be more
beneficial.
The functional-first curricular model actually predates the
objects-first model by one to two decades, if we count early uses of
LISP and Smalltalk. The genesis of the current approach was at MIT in
the early '80's, with the development of the language Scheme (derived
from LISP) and the publication of the book "Structure and
Interpretation of Computer Programs" (SICP), by Abelson and
Sussman. The second edition of this book is still
in use at MIT, and
is
available in its entirety on the Web; it is also used at
Berkeley,
Caltech, and a few other institutions, and as a senior text in yet
more. I vividly recall the joy and wonder of my first reading of the
book, and I know many faculty members feel the same way.
But when I recently read through the second edition of SICP with an
eye to assessing it for use at UW, it was clear to me that a
relatively small number of first-year Math students
would both be able to handle such a course and be willing to take it.
This is probably the source of the comment in CC01
about the functional-first model forcing students to think too
abstractly too quickly. It is not inherent in the model, but a result
of this particular approach to it.
In a paper in the Journal of Functional Programming titled "The
Structure and Interpretation of the Computer Science Curriculum"
(available here in PDF format),
Felleisen et al. summarize two main problems with SICP:
SICP's second major problem concerns its selection of examples and
exercises. All of these use complex domain knowledge. [...] While
these topics are interesting to students who use computing in
electrical engineering and to those who already have significant
experience of programming and computing, they assume too much
understanding from students who haven't understood programming yet and
they assume too much domain knowledge from any beginning student who
needs to acquire program design skills.
These authors have produced a text that seeks to address these
deficiencies in the SICP approach in order to make the
functional-first model more attractive. "How To Design Programs"
(HtDP) by Felleisen, Findler, Flatt, and Krishnamurti, is available in
hardcover from MIT Press, as well as entirely available on the Web. An
associated team has developed a freely-downloadable cross-platform
integrated development and instructional environment called DrScheme, which allows one to load
restricted subsets of the language matching the incremental approach
of the text (or ones defined by the instructor).
HtDP is in use at
Northeastern,
Rice,
Chicago,
Utah,
and
Georgia Tech;
DrScheme is used
by many of the institutions that use other texts (including SICP). A
followup book making the transition to Java, "How To Design Class
Hierarchies" (HtDCH), is in development, and
preliminary chapters are also
available on the Web. A brief description of Scheme and HtDP's
approach is in Appendix A of this proposal.
Other authors have written introductory books on Scheme. "Simply
Scheme" by Harvey and "Exploring Computer Science with Scheme" by
Grillmeyer are used in self-paced "prequel" courses to Berkeley's SICP
course (thereby creating multiple approaches to the major, though
technically there is a single entry point, as students at Berkeley are
admitted to the major quite late). "Concrete Abstractions" by
Hailperin, Kaiser, and Knight includes a transition to Java. "The
Schematics of Computation" by Manis and Little was used at UBC in a
two-course introductory sequence until this year. None of these books
appears to be as widely used as HtDP.
Some institutions have Scheme-based courses that do not rely on a set
text, but use course notes. Examples include
Brown
and Texas
(Austin). Brown offers a choice of two two-course sequences, one a
standard Java-based CS1-2, and
one centred around Scheme, ML, and
Java. Although Brown's version is homebrewed, and more ambitious than
what I am proposing, their vision of two alternatives existing
harmoniously, each leading to
a common remaining CS core, is closest to mine.
Any curricular reform must have as its goal the creation and
maintenance of courses that are attractive to instructors, staff, and
students, and robust with respect to changes in personnel, platform,
and materials. The course sequence I am about to describe will not
supplant or replace our objects-first sequence. The alternate sequence
will always attract a minority of students, who of necessity must be
self-selecting. I will say more about the audience in subsection 3.2.
Applying the functional-first model to the SCS curriculum would create
two courses, CS 135 and CS 136, to be accepted as alternatives to CS
133 and CS 134 in all Faculty of Mathematics undergraduate degree
plans. The numbers were chosen so that the reader can keep this notion
of two parallel but convergent streams in
mind, and to avoid the impression that the new sequence is somehow an
advanced or elite version of the existing sequence in the same way that
the Math 14x courses are advanced versions of the Math 13x
course. That is not the case. In a sense, the analogy between CS 135
and Math 135 is more apt: Math 135 is an introduction to concepts and
techniques of mathematics, and CS 135 does the same for computer science.
CS 135 would be a 1A course using HtDP as a text and DrScheme as an
instructional development environment. The syllabus of CS 135 would be
very close to the syllabus of the existing courses at
Northeastern,
Rice, or
Utah.
I have created a mockup of a handbook
description reflecting how such a course might look.
For good students, I would suggest developing challenge labs and
assignments from the wealth of SICP-related material.
In keeping with both the recommendation of CC01 and my recommendation
to retain the existing Java sequence, CS 136 would make the transition
to Java while teaching CS2 material (elementary data structures),
using either HtDCH or a CS2 text in Java that offers sufficient
support for the transition (one example is "The Object of Data
Abstraction and Structures Using Java" by David Riley, which was used
at Northeastern before the development of HtDCH). The syllabus of CS
136 would aim at convergence with CS 134; in fact, the final exams of
the two courses should look very similar. As examples of such a
syllabus, we can look at the existing followup courses at Utah, Rice, or the new CSU
213 at Northeastern (new because Northeastern is undergoing a
transition from quarters to semesters). Note that Northeastern has a
co-op program like UW (though there is no equivalent of our 4-stream),
so they share many of our practical constraints. I have created a
mockup of a handbook description of CS
136. Both this and the description of CS 135 are provisional; they
will be subject to revision through our usual curricular process.
I would suggest extending the gradualist approach of DrScheme to the
transition to Java by using a development environment that provides
restricted subsets of Java. ProfessorJ, designed to accompany
HtDCH, is built on top of DrScheme. There are teaching tools that
provide a similar interactive environment with friendlier error
messages, syntax checkers, and debuggers than production IDEs, but
without implementing language subsets: DrJava from Rice, and BlueJ, originally developed at Monash.
This sequence, like Miss
Anne Elk's theory of the brontosaurus, is open to criticism at
three points: at one end, in the middle, and again at the other end.
At the near end we are faced with the problem of defining the audience
for this course and helping students to decide among the various entry
points for introductory CS. I believe that the audience should be
self-selected, because it is not clear what other selection criteria
to apply if the goal is to get the right students rather than to make
the logistics easier. This almost certainly means that some who might
benefit from the switch will not make it. There are also those who
won't need to switch but will be intrigued, and I don't think they
will be hurt.
For the first offering of CS 135/136, the audience is likely to
be mostly stronger students, with or without prior computing
experience. They are most likely to be adventurous, and to be
intrigued by the novelty of the approach. Some may find the material
slow, but there are enough opportunities for them to go beyond what
the course offers in ways that do not directly steal from upper-year
courses. In the long run, I hope that the audience will expand beyond
the pilot audience. Those who might benefit include:
The Felleisen et al. paper and another paper submitted to JFP by
Chakravarty and Keller on the
functional-first approach both give statistical evidence that women
prefer this approach. Although it is difficult to rule out other
factors (instructor interest, self-selection),
Margolis, Fisher and Miller, in one of a series of papers studying
the gender gap at CMU, identify differing levels of prior experience
as something that discourages women; in this sense, the
functional-first model is a leveller, since it is quite unlikely that
incoming students would have had experience with such languages. The
lightweight syntax of Scheme may also appeal to women who are less
enamoured of the technique of computing for its own sake and more for
what it can be used for. But women, who tend to underestimate their
abilities in computer science, may be discouraged by any perception
that CS 135/136 is an "advanced" sequence, or may prefer the more
obvious fallback options should they run into difficulties in the CS
13x sequences.
It is already difficult to advise students whether they should opt for
CS 131, CS 133, or CS 134, and adding CS 135/136 will only complicate
things. I think it is advantageous that the proposed textbook for CS
135 is available online for perusal; currently, much of the CS 133
text is also available online. I have drafted a document which
attempts to offer advice on CS 135/136 for
an incoming student, and would welcome suggestions on improving
it. Certainly students who are in 4-stream CS and anxious to put
"Java" on their CV, those who disparage any language or technique not
practiced in industry, and those who would be more comfortable with a
richer support system should opt for one of the CS 13x
courses.
The transition from Scheme to Java in the middle could, if poorly
handled, result in much confusion, and students being less fluent in
Java than those who go the traditional route. This has not been the
experience of those institutions using the functional-first model, but
again it is hard to extrapolate from these to a new offering. It will
help that HtDP (and HtDCH) are designed specifically for such a
transition, as opposed to being books just on Scheme or Java.
At the far end, the mixture of the two populations at the second-year
level needs to be examined. Of the 2A courses, CS 251 does not depend
on the first-year language; CS 241 uses Java to create small
algorithmically-rich programs associated with the process of
compilation, and arguably those who have gone through CS 135/136 will
be better equipped for these than their peers. There is a small Scheme
teaching module in CS 241 which will need to be replaced; both groups
will benefit from exposure to ML at this point, as it offers a mix of
declarative and functional constructs together with features such as
polymorphic type-inference that are useful to examine from the points
of view of programmer and compiler designer. Alternately, a short
Scheme tutorial can be offered to students who took CS 13x, since the
point of this section is not to teach students how to program in
Scheme, but to illustrate the difference between compilation and
interpretation. In either case, I will gladly assist in the
development of new material for CS 241. In 2B, assignments in CS 240,
while partly involving programming, do not depend heavily on OO
language features, and CS 246 moves everyone to a new language, C++,
which introduces new OO features.
Having taught CS1 and CS2 courses from 1987 to 1995, I am well
acquainted with the considerable logistical difficulties. My 1991
design for CS 134 has largely survived several changes in textbook,
language, and course coordinator. This is not due so much to my skill
in design as to the fact that it covers familiar CS2 ground, and so is
robust with respect to such changes. The course has a lightweight
footprint: a modest and easily modified set of lecture slides, three
hours of lecture, no programmed labs or practicums.
I would suggest a similar structure for CS 136, and for CS 135 with
the possible exception of lightly programmed labs (a brief description
of concepts to be reinforced by tutors or TAs, rather than a complete
instructional module).
Research faculty are not clamouring to teach CS 134, but it has a
respectable number of such instructors, and I believe that CS 135 and
CS 136 would be at least as attractive and probably more so. As for
lecturers and sessionals, I see no reason why they would be
uncomfortable with CS 135 and CS 136. The approach is unusual, but the
material is not esoteric or inaccessible; it has successfully been
used at the high-school level and in CS0-type courses (equivalent to
CS 100 at UW).
In the steady state, CS 135 needs to be offered at least in the fall,
and CS 136 at least in winter and spring. We can hold at this level if
we require Grade 11 computer science for CS 135, since those who fail
it can go into 133. But this diminishes the appeal of CS 135 for
non-CS Math students, who are less likely to have Grade 11 CS under
the new four-year high school curriculum, and would thus be forced
into 131. If CS 135 proves appealing and numbers merit, winter and
spring sections can be offered to those who fail the fall section and
those who enter the Faculty late or transfer in from other Faculties;
it may also be the case that parallel changes to CS 133 to bring back
students opting for CS 131 would also allow students failing CS 135 to
enter it.
CS 136 can be offered in winter only if we rule out 4-stream students
(who may be less likely to take CS 135) or in winter and spring if we
include them. This leaves out those 8-stream and regular students who
fail CS 135 in the fall, pass it in the winter, and then wish to take
CS 136 the following fall. Depending on the exact design of CS 136, it
may be possible to accomodate these students in a section of CS 134
with an extra tutorial hour. We may well end up with both CS 135 and
CS 136 being offered in all three terms.
If students wish to switch from CS 135 to CS 133 or vice-versa early
in a term, this should be possible with a bit of catching up. There
should be no need for an exit strategy from CS 136, since by the time
students run into difficulty, they will basically be doing the same
work as their peers in CS 134. A student failing CS 136 can take CS
134 in a subsequent term.
This proposal was first released in December 2003, and revised in
response to public comment (see the revision history below). It was
approved by the Undergraduate Academic Plans Committee in February
2004, and by SCS Council in March 2004. I will develop and teach a
pilot section of CS 135 in Fall 2004, and assist Mark Giesbrecht in
developing and teaching a pilot section of CS 136 in Winter
2005. These would formally be special sections of CS 133 and CS 134
respectively, with students made aware of the choice via their
registration materials and through presentations during Orientation
Week. These offerings will be assessed by an independent team which
will also make recommendations regarding continuation and modification
of the functional-first approach.
The idea of using Scheme to implement the functional-first curricular
model is at least twenty years old, but the simplicity and flexibility
of the language allows treatment of functional and data abstraction,
preparing the way for an easy transition to a modern object-oriented
second language. Textbooks and software environments that have been
tested over several years at several other comparable institutions are
available to implement this idea at UW. The possible benefits include
increased student choice, motivation of OO concepts without syntax
overload, a suitable balance between analytic and developmental
skills, mitigation of diversity due to prior computing experience,
appeal to a wider audience, and increased involvement of faculty in
first-year courses. The possible drawbacks include entry-point
confusion, perceived irrelevance of the language, difficulty in moving
between sequences, awkwardness in language transition, and diversity
issues in upper-year courses.
I believe that the functional-first model offers a way out of the
impasse between the imperative-first approach using an OO language and
the objects-first approach for students who are not well served by
either. It is a distinct alternative (as opposed to sliding back and
forth on the continuum between imperative-first and objects-first),
and we are sufficiently rich in resources and circumstances at UW to
be able to offer it as such.
Version 2.1 (this document): Slight restructuring after proposal for
pilot sections passed at SCS Council on 9 March 2004 (plus some
wording changes to reflect this status). Moved to new CS 135 Web page.
Version 2.0: Released 4 February
2004. Restructured after the proposal
passed UAPC, to make it easier for more casual readers; new materials
prepared for UAPC incorporated. CS 135/136 renamed from CS 143/44 to
avoid suggestions that this is an advanced sequence.
Version
1.1: Released 18 January 2004. Changes to take into account
feedback and discussions. Expanded discussion on target audience; more
details on pilot and steady state logistics.
Version
1.0: Released 15 December 2003.
2. History of the Functional-First Model
SICP doesn't state how to program and how to manage the design of a
program. It leaves these things implicit and implies that students can
discover a discipline of design and programming on their own.
The course presents the various uses and roles of programming ideas
with a series of examples. Some exercises then ask students to modify
this code basis, requiring students to read and study code; others ask
them to solve similar problems, which means they have to study the
construction and to change it to the best of their abilities. In
short, SICP students learn by copying and modifying code, which is
barely an improvement over typical programming text books.
3. The New Alternate Course Sequence
3.1 A First Course in Scheme, A Second in Java
3.2 Criticizing The New Sequence
4. Logistics
5. Timetable
6. Conclusion
References
Many of the links in this document, as well as others relating to use
of this approach elsewhere, have been collected in this
auxiliary page.
Revision History
Public
comment on the alternate sequence proposal (December 2003 to
March 2004)