Under consideration for publication in J.Functional Programming1
E D U C A T I O N A L P E A R L
The Structure and Interpretation of the
Computer Science Curriculum
Matthias Felleisen,Northeastern University,Boston
Robert Bruce Findler,University of Chicago,Chicago
Matthew Flatt,University of Utah,Salt Lake City
Shriram Krishnamurthi,Brown University,Providence
Email:{matthias,robby,mflatt,shriram}@
1History and critique
The publication of Abelson and Sussman’s Structure and Interpretation of Com-puter Programs(sicp)(A
belson et al.,1985)revolutionized the landscape of the introductory computing curriculum in the1980s.Most importantly,the book lib-erated the introductory course from the tyranny of syntax.Instead of arranging a course around the syntax of a currently fashionable programming language,sicp focused thefirst course on the study of important ideas in computing:functional ab-straction,data abstraction,streams,data-directed programming,implementation of message-passing objects,interpreters,compilers,and register machines.
Over a short period,many universities in the US and around the world switched theirfirst course to sicp and Scheme.The book became a major bestseller for MIT Press.1Along with sicp,the Scheme programming language(Sussman&Steele Jr., 1According to Bob Prior(editor at MIT Press),sicp sold45,000copies in itsfirstfive years [personal communication,9June2003].
2Felleisen et al.
1975;Steele Jr.&Sussman,1978;Clinger,1985;Clinger&Rees,1991;Kelsey et al., 1998)became widely used.It was no longer the subject of a few individual courses at Indiana University,MIT,and Yale,but the language of choice in introductory courses all over the world.
Unfortunately,the use of Scheme and sicp quickly dwindled again in the early 1990s.After working wit
h sicp and Scheme for a while,instructors started to complain.Some said that sicp’s content was too difficult for students outside of MIT.Others blamed Scheme directly,claiming that functional programming in Scheme was too different from programming in other languages.Even the functional programming community criticized the sicp approach;around this time,Wadler wrote his Critique of sicp and Scheme(Wadler,1987).
Nowadays the critics even include professors at MIT,where the book and the course have become legends.Jackson and Chapin,who both have significant expe-rience teaching sicp at MIT,recently wrote that
[f]rom an educational point of view,our experience suggests that undergraduate com-puter science courses should emphasize basic notions of modularity,specification,and data abstraction,and should not let these be displaced by more advanced topics,such as design patterns,object-oriented methods,concurrency,functional languages,and so on(Jackson &Chapin,2000).
In short,sicp,Scheme,and functional programming don’t prepare students prop-erly for other programming courses and thus fail to meet a basic need. Advocates of Scheme and functional programming alike must be concerned about these reactions.To address them and to overcome the
problems of the sicp ap-proach,we present this pearl.It consists of three pieces:a structural framework for analyzing thefirst-year computing curriculum;an interpretation of sicp with re-spect to this framework;2and our alternative to the sicp approach that overcomes sicp’s problems while retaining the essence of Scheme and functional programming.
2Structure
2.1Solving constraints
The primary goal of a computing curriculum is to produce programmers and soft-ware engineers.After all,most of its graduates accept industry positions and pro-duce software.Many will stay involved with software production for a long times, even if only as managers,and therefore also need to learn to adapt to the ever-evolving nature of thefield.
Translating the primary goal into a set of goals for the introductory curriculum is a difficult task because various groups impose a range of unrelated constraints. Faculty colleagues(inside and outside of computer science)often have an emotional preference for a specific language in the introductory course.To some,thefirst 2We chose sicp as our yard stick because it is the most widely used and known text that uses functional programming and because we believe that all other texts—
of almost equal age(Bird &Wadler,1988)or of recent vintage(Hudak,2000)—on functional programming suffer from similarflaws.
Structure and Interpretation3 language is the one that they know and work(ed)with.To others,it is the currently fashionable industry ,C++and Java over the past ten years. Some computer science faculty demand that thefirst course teach languages that are used in upstream courses.Sometimes they believe that the instructor of the second course should not have to start from scratch and that the simplest solution is to use a single programming language.Sometimes they wish to expose students to languages that are used in popular upstream courses such as operating systems. First-year students also come with strong,preconceived notions about program-ming and computing.Some students(or their parents)have read about the latest industry trends in popular magazines,such as(in the US)Time,Newsweek and US News and World Report,and expect to see some of these things in a freshman course.Some base their understanding on prior experiences in high schools.The latter group is used to sophisticated development environments(IDE s)that include mechanical support for syntactic conventions,GUI development,etc.
The state of thefirst-year students’education adds another set of constraints to the mix.Some understand calculus;for others,even rudimentary algebra is a minefield.
Finally,students also have a wide range of expectations.Some students wish to learn what computer science is about;others have three years of programming experience.Some wish to know why things work;others want to learn how to construct games.Almost everyone expects that the college training will help them find internships and professional positions.
Satisfying the primary goal of producing software professionals subject to these constraints poses a complex problem.On one hand,learning to program well re-quires a lot of practice and in particular a lot of hands-on practice.Hence,early courses must introduce programming and must choose a specific programming lan-guage.On the other hand,choosing one language over another must disappoint some constituents,and we must therefore convey to them our choices with good reasons.After all,education is as much about satisfying human needs as it is about technical correctness.
We propose to solve this constraint problem with a second look at the primary goal and the timing constraints.Clearly,a computer science curriculum must not, and doesn’t have to,become a vocational training ground for the latest industrial programming language and programming tools.Superficial aspects of industrial practice change as fast as fashion trends.No academic department can switch its course content fast enough and maintain a curriculum that passes on teste
d wisdom. Still,when students cross over from academia into industry,they must be prepared to program and ideally to program well.From this perspective,two points in the curriculum take on special meaning:thefirst summer,when students work in in-ternship positions,and the last year,when students interview for theirfirst full-time positions.
Following this reasoning,we believe it is natural to concentrate on principles for most of the time and to accommodate industrial needs during the second semester of thefirst year and the last year of a college program.Considering that college is the only time in a programmer’s life when he is exposed to principled ideas on a regular
4Felleisen et al.
and rigorous basis,the idea of emphasizing principles in college is obvious.Once a programmer has a full-time position,there are too many constraints and distraction for principled additional education.At the same time,however,a curriculum must also teach how these principles apply to the real world.Nobody can expect students to take this step on their own.In short,teach good habits early;otherwise bad habits become ingrained and require costlyfixes—just like bugs in programs.
Applied to thefirst-year courses,these suggestions say that the year should start with a heavy empha
sis on principles and should add some industrially relevant com-ponents during the second semester.Even more precisely,thefirst semester should emphasize programming principles and habits;the second part should illustrate the use of these principles in currently fashionable programming languages.Of course, the“principled”semester may integrate fashionable parts where they aren’t an ob-stacle,and,more importantly,the“fashionable”part of thefirst year must continue to practice good design habits.
2.2Principles of programming
steeleThefirst challenge is thus to identify technical principles for thefirst-year program-ming courses.Clearly,we should teach good program design habits(not just syntax and programming style).Based on our experience,we have identified the following set of program design ideas that afirst course should translate into habits:
1.Students must learn to read problem statements carefully,extract informa-
tion,and rewrite it into useful pieces:
(a)a concise purpose statement for the program and each of its major pieces;
(b)a description of the classes of data that play a role;
(c)a collection of examples that illustrate both the classes as well as the
purpose statements.
Ideally the latter should(eventually)make up a rigorous test suite for the program and its functions.
2.Students must learn to organize programs so that they match the class de-
scriptions of item1b.For example,a functional programmer must define datatypes and functions on these types whose structure matches the type;
an object-oriented programmer must define class hierarchies and appropri-ately distributed methods.
If students learn to organize programs in this manner,they quickly learn that small changes to the problem statement translate into small changes in the program’s code.Considering the rapid changes in the requirements for real-world software,we consider this principle central to our effort.
3.Students must learn to use the examples developed in item1c above.They
must learn to calculate through examples before they code.They must learn to translate the examples into automatic test suites,so that they can test programs as they create them and as the programs evolve later.
More concisely,students must learn that programming requires far more than writ-ing down code and running it on some haphazardly chosen examples afterwards.
Structure and Interpretation5 The last point in particular suggests that functional languages with their nat-ural model-view separation are superior choices for thisfirst year.When students write automatic test suites,they must to split a program into a part that deals with computation proper(the“model”)and another part that interacts with the user(the“view”).They then use the model in two distinct contexts:with a test suite and with the view.In order to re-use the model in a test suite context,they don’t want to print results but hand them over directly to a comparison function. Put differently,teaching good software architecture principles to beginners requires function composition and discourages a programming style that is primarily about reading and printing values.
2.3Principles of teaching
The second challenge for afirst-year instructor is to understand the teaching prior-ities concerning th
efirst language and thefirst course.Currently,most instructors teach programming with examples.In a typical week,they introduce a new(con-trol)construct,explain with a few examples how to use it,and then assign some exercises from a text book.Students copy the examples and modify them tofit the homework exercises.Since these exercises tend to change the context for the new construct,students also begin to appreciate its general powers and pitfalls. Put differently,the teaching of(control)constructs is explicit while the teaching of design principles remains implicit;instructors leave it to the students to discover how to go from a blank screen to a full-fledged program.3
We believe that the conventional approach to teaching programming reverses the natural roles of data and control.Recall Brooks slogan page102 Show me your[code]and conceal your[data structures],and I shall continue to be mystified.Show me your[data structures],and I won’t usually need your[code];it’ll be obvious.
as paraphrased by Raymond(Raymond,1998).When we reason about a program, we want to know the format of the data that it uses,and we can almost imagine how it works.In analogy,when we teach how to program,we should let data drive the syllabus.First we show how to design a program that works on simple data and what kind of(control)constructs this requires.Then we increase the comple
xity of the data and show how to design programs for these classes of data.Such a step may,or may not,require new constructs,but in the end it forces students to understand how to go from data to design explicitly,and they will pick up language constructs implicitly.
Since most students are active learners,it is important to retain the example-driven strategy that is currently used.The examples must,however,focus on the 3Challenging instructors throw in ideas from data structures and algorithms or,worse,pose problems that require significant domain knowledge,that is,knowledge about non-computing topics.The problem is then that students tend to confuse algorithms and application domain knowledge with program construction,and neither helps students come up with good program organizations on their own when they are left to their own devices.
6Felleisen et al.
use of program design principles in new situations instead of the use of language constructs.
In summary,thefirst course should introduce the principles of program design, state them explicitly as habits,and have students practice them with numerous ex-amples.To avoid any confusion,the course should not pose problems from complex application domains and it should not use a complex langua
ge that distracts from the design principles.
3Interpretation:functional versus object-oriented programming Now that we have discussed the structure of thefirst-year curriculum and its teach-ing methods,we can turn to the choice of programming language.If we accept the premise thatfirst-year students should learn to use two programming languages, we now face the question which(kind of)languages we should choose.If we also accept the premise that thefirst language should facilitate the teaching of design principles,choosing a simple functional language for thefirst course is natural. The second course can then use a(subset of a)complex,industrially fashionable language,such as C#or Java,and show how the design principles apply there. We justify this suggestion in more detail in thefirst subsection and explain our concrete choice in the second one.
3.1Functional and object-oriented programming
Functional and object-oriented programming share the desired curricular focus on data as the starting point for program design.A functional programmer begins with the definition of types and then defines functions on these types.An object-oriented programmer defines classes and adds methods to these classes.Once the vocabulary of data and operations are defined,programs are usually just a function or a method call.
Functional programming and object-oriented programming differ with respect to the syntax and semantics of the underlying languages.The core of a functional lan-guage is small.All a beginning programmer needs are function definition,function application,variables,constants,a conditional form,and possibly a construct for defining algebraic types.In contrast,using an object-oriented language for the same purposes requires classes,fields,methods,inheritance in addition to everything that a functional language needs.Furthermore,the computational model of a functional language is a minor extension of that of secondary school algebra.The model of object-oriented computation requires far more sophistication,especially its focus on method dispatch(instead of conditional reasoning)and early state modification. Using a functional language followed by object-oriented language is thus the natural choice.The functional language allows students to gain confidence with program design principles.They learn to think about values and operations on values.They can easily comprehend how the functions and operations work with values.Better still,they can use the same rules tofigure out why a program pro-duces the wrong values,which it often will.Teaching an object-oriented language

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。