CS 135/136: An Alternate First-Year CS Sequence at UW

(Version 2.1, 14 March 2004)

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.


The 9 March 2004 meeting of SCS Council approved pilot sections of CS 135 and CS 136 to be taught in Fall 2004 and Winter 2005 respectively, with full rollout provisionally scheduled for Fall 2005.

Useful Links

Table of Contents

  1. Curricular Models
  2. History of the Functional-First Approach
  3. The New Alternate Course Sequence
  4. Logistics
  5. Timetable
  6. Conclusion (plus References, Revision History)

1. Curricular Models

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.

2. History of the Functional-First Model

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 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.

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.

3. The New Alternate Course Sequence

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.

3.1 A First Course in Scheme, A Second in Java

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.

3.2 Criticizing The New Sequence

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.

4. Logistics

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.

5. Timetable

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.

6. Conclusion

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.


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)

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.