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 Fellein,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}@plt-scheme
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 cour from the tyranny of syntax.Instead of arranging a cour around the syntax of a currently fashionable programming language,sicp focud thefirst cour 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 cour to sicp and Scheme.The book became a major bestller 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].
2Fellein et al.
1975;Steele Jr.&Sussman,1978;Clinger,1985;Clinger&Rees,1991;Kely et al., 1998)became widely ud.It was no longer the subject of a few individual cours at Indiana University,MIT,and Yale,but the language of choice in introductory cours all over the world.
Unfortunately,the u of Scheme and sicp quickly dwindled again in the early 1990s.After working wi
th 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 cour have become legends.Jackson and Chapin,who both have significant expe-rience teaching sicp at MIT,recently wrote that
morethan[f]rom an educational point of view,our experience suggests that undergraduate com-puter science cours should emphasize basic notions of modularity,specification,and data abstraction,and should not let the 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 cours and thus fail to meet a basic need. Advocates of Scheme and functional programming alike must be concerned about the reactions.To address them and to overcome the
绿色生命problems of the sicp ap-proach,we prent 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 esnce of Scheme and functional programming.
2Structure
2.1Solving constraints霓虹语>sat网校
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 t of goals for the introductory curriculum is a difficult task becau various groups impo 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 cour.To some,thefirst 2We cho sicp as our yard stick becau it is the most widely ud and known text that us functional programming and becau 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 cour teach languages that are ud in upstream cours.Sometimes they believe that the instructor of the cond cour should not have to start from scratch and that the simplest solution is to u a single programming language.Sometimes they wish to expo students to languages that are ud in popular upstream cours 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 e some of the things in a freshman cour.Some ba their understanding on prior experiences in high schools.The latter group is ud 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 t of constraints to the mix.Some understand calculus;for others,even rudimentary algebra is a minefield.pads
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 the constraints pos 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 cours must introduce programming and must choo 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 propo to solve this constraint problem with a cond 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 cour content fast enough and maintain a curriculum that pass on test
ed 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 cond mester 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 expod to principled ideas on a regular
4Fellein 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 the principles apply to the real world.Nobody can expect students to take this step on their own.In short,teach good habits early;otherwi bad habits become ingrained and require costlyfixes—just like bugs in programs.
Applied to thefirst-year cours,the suggestions say that the year should start with a heavy empha
sis on principles and should add some industrially relevant com-ponents during the cond mester.Even more precily,thefirst mester should emphasize programming principles and habits;the cond part should illustrate the u of the principles in currently fashionable programming languages.Of cour, the“principled”mester 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
Thefirst challenge is thus to identify technical principles for thefirst-year program-ming cours.Clearly,we should teach good program design habits(not just syntax and programming style).Bad on our experience,we have identified the following t of program design ideas that afirst cour should translate into habits:
1.Students must learn to read problem statements carefully,extract informa-
tion,and rewrite it into uful pieces:
(a)a conci purpo statement for the program and each of its major pieces;
(b)a description of the class of data that play a role;
(c)a collection of examples that illustrate both the class as well as the
purpo 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-
unfriend you
scriptions of item1b.For example,a functional programmer must define datatypes and functions on the types who 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 u 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.youtobe是什么
More concily,students must learn that programming requires far more than writ-ing down code and running it on some haphazardly chon examples afterwards.
Structure and Interpretation5 The last point in particular suggests that functional languages with their nat-ural model-view paration 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 ur(the“view”).They then u the model in two distinct contexts:with a test suite and with the view.In order to re-u 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 cond challenge for afirst-year instructor is to understand the teaching prior-ities concerning th
efirst language and thefirst cour.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 u it,and then assign some exercis from a text book.Students copy the examples and modify them tofit the homework exercis.Since the exercis 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 revers 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 paraphrad by Raymond(Raymond,1998).When we reason about a program, we want to know the format of the data that it us,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 increa the co
mplexity of the data and show how to design programs for the class 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 ud.The examples must,however,focus on the 3Challenging instructors throw in ideas from data structures and algorithms or,wor,po problems that require significant domain knowledge,that is,knowledge about non-computing topics.The problem is then that students tend to confu 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.
6Fellein et al.
u of program design principles in new situations instead of the u of language constructs.i was wrong
In summary,thefirst cour 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 cour should not po problems from complex application domains and it should not u a complex langua
ge that distracts from the design principles.
3Interpretation:functional versus object-oriented programming Now that we have discusd the structure of thefirst-year curriculum and its teach-ing methods,we can turn to the choice of programming language.If we accept the premi thatfirst-year students should learn to u two programming languages, we now face the question which(kind of)languages we should choo.If we also accept the premi that thefirst language should facilitate the teaching of design principles,choosing a simple functional language for thefirst cour is natural. The cond cour can then u a(subt 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 subction and explain our concrete choice in the cond 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 the types.An object-oriented programmer defines class and adds methods to the class.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 mantics 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 purpos requires class,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 condary 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 u the same rules tofigure out why a program pro-duces the wrong values,which it often will.Teaching an object-oriented language
