intro computer science course at Brandeis

[HAL%MIT-OZ@MIT-MC.ARPA]

This past semester, Brandeis University changed its introductory
computer science subject to use "Structure and Interpretation of
Computer Programs" and Scheme (running on Texas Instruments PCs).

The following essay is by Harry Mairson, who was in charge of the
subject.


\magnification = 1200
\centerline
{\bf Structure and Interpretation of Computer Programs}
\centerline{Autumn Semester, 1985}
\medskip
\centerline{\sl by Harry Mairson}
\bigskip
\bigskip
\parskip = 5pt plus1pt minus .5pt

This year, the Brandeis computer science department introduced a new
introductory course for its prospective majors.  {\sl Structure and
Interpretation of Computer Programs}, a textbook and novel curriculum
under development at MIT for several years, replaced a standard course
teaching Pascal and modular programming.  I taught the course in
cooperation with Harold Abelson, one of the MIT professors who
developed the curriculum.  As the course comes to a conclusion this
term, I would like to make a few comments about its contents, and why
I believe it has been and will continue to be a success at Brandeis.

First of all, ``Structure and Interpretation of Computer Programs'' is
a sophisticated and high-powered course, presenting to students with
no presumed background in computer science an intensive introduction
to the subject of computation.  Among the subjects presented in this
course are: induction and recursion, lambda calculus, actor models,
tail recursion, orders of growth, abstraction mechanisms, data-driven
and procedure-driven (i.e., ``message passing'') computation, data
structures, substitution and environment models of computation, stream
processing, applicative- and normal-order evaluation, how interpreters
and compilers work, and logic programming.  All this as an {\sl
introduction} to computer science! I did not learn about many of these
subjects until I was in graduate school, and some I learned only while
teaching this innovative course.

Such an ambitious curriculum cannot succeed without a substantial
commitment of resources from both students and the University.  Students
worked 15 to 20 hours a week on this course, sometimes more.  The
computer science department bought 18 Texas Instruments Professional
Computers, with the latest version of the Scheme programming language that
was practically hot off the press; there were fewer than three students per
personal computer.  Hal Abelson gave a two-hour master class each week.
I gave two one-hour recitation lectures, plus interminable tutorials.
(I had no fixed office hours, tried to be in as much as possible, and
students badgered me with questions constantly, sometimes until early
morning...)  Three teaching assistants, Brandeis graduate students
Larry Bookman, Xiru Zhang, and Brandeis senior Moises Lejter ran
one-hour tutorials every week in groups of four to five students,
and worked as tutors in the laboratory.  They were unflagging in their
dedication and patience.  In addition, they were joined by three MIT
undergraduates, David Alcocer, Jos\'e Capo, and Scott Heeschen, providing
on-the-spot counseling and tutoring in the midst of programming crises.
The MIT students were great, but as I joked to them on their arrival,
``I'm delighted to have you help, and I can't wait to throw you out.''
Next year, Brandeis undergraduates will take their places.

The kids in the class knew every resource we could conceivably provide
them was there.  Given that total commitment, they showed beyond any
doubt their own commitment and willingness to work real hard and absorb
the material.

This course has something new and profound to say about computation and
learning.  With no time wasted, it immediately plunges into a discusssion
of the {\sl semantics} of computation, and treats almost peripherally
the questions of syntax.  The importance of this approach can best be
explained by considering the difference between learning a foreign
language (say, French) and a computer language.

Before learning my first word of French, I already understood the semantics
of the language, since ``meaning'' means the same thing in English as it
does in French, despite any Gallic claims to the contrary: the French
talk about tables, chairs, families, taxes, good food, vacations; they use
the same verbs, adjectives, and adverbs as we do, and essentially the same
notions of time.  So ``learning French'' meant learning a new grammar to
express the same ideas and thoughts I already knew how to express
in English.

The same cannot be said for learning a computer language, because there the
overriding questions of the {\sl d\'ebutant} are: what is the computer
doing, what {\sl can} it do, and what does my program {\sl mean?}
The grammar of any programming language is far simpler than that of
French; given enough compulsiveness, anyone can learn to make sure that all
the semicolons are in the right place, that for every {\tt BEGIN} there
is an {\tt END}, that left and right parentheses match.  These grammatical
rules are annoying, but not conceptually deep.

It happens that this course is taught using the Scheme language, a dialect
of a more famous programming language called Lisp.  But as the authors of 
the text write, ``After a short time we forget about syntactic details
of the language (because there are none), and get on with the real issues.''
The Scheme language is used because it expresses easily a wide range of
computational processes, but these processes, and not the language itself,
are the centerpiece of this course.

Such an emphasis, as well as many other aspects of the course, is in
the best tradition of liberal education.  The course is not simply a
compendium of ``current'' tricks of the programming trade that will 
doubtless change in the next six months, but presents a foundation from
which today's and tomorrow's issues and controversies in computer science
can be understood and put into perspective.  I expect this course will 
teach students to think for themselves.

Computer science often attracts the ire of specialists in other academic
fields, principally physicists and mathematicians, but philosophers and
just about everyone else too, because it seems so narrow and self-referential
that it doesn't relate to other fields of study.  This course goes a long
way to healing the wounds of that misconception, as well as teaching
students a healthy appreciation for the respective fields that are
not simply the ancestors of computer science, but its much needed partners
in the pursuit of knowledge and understanding.  That means I want my
students to take lots of math, physics, and philosophy courses, and know
what these subjects are about!

For example, no discussion of the meaning of language can take place outside
the tradition of philosophy and its profound contribution to the understanding
of language.  In the Scheme language, for example, the meaning of a simple
expression like {\tt (cons x y)} can be explored on many levels, none of them
artificial.  The mechanism used by the computer to evaluate this expression
can be implemented in several ways that are substantially different:
{\tt (cons x y)} could be interpreted as a memory structure, an integer,
or a procedural abstraction.  On the other hand, the expression has
precise meaning simply in its fixed use with respect to the other
constructs of the Scheme language.

I spent one lecture describing these two radically different points of
view, showing how the former view of ``meaning as implementation'' is the
direct descendant of logical atomism in the tradition of Bertrand Russell
and his followers, while the latter idea of ``meaning as use'' is a
natural consequence of the philosophy of language as proposed in the 
later writings of Ludwig Wittgenstein.  Similarly, in a discussion of the
so-called ``environment model'' of computation, the subject of denotation
is explored: we understand how classical problems of referential
transparency in language are resolved, and how conceptions of meaning and
time relate to each other.  The semantics of computation becomes a
controlled laboratory where we can discover more about the complex
relationship of meaning and language.

Apart from the usual arithmetic programming examples, the course draws on
problems and examples from mathematics and physics.  In one two-week problem
set, for example, the students implemented a video game called ``Lunar
Lander,'' where a spaceship with a fixed amount of fuel must be landed
under a gravitational force without crashing.  In doing so, they experimented
with a variety of landing strategies.  The principal goal of the problem set
is to teach the students how to use something called lambda expressions,
a programming language construct borrowed from mathematical logic.  But the
problem set also makes the students think about models of physical reality,
where computation is not simply {\sl sui generis} but an analog of the
physical world.  They implemented an optimal fuel-efficient landing
strategy, and I made them understand the ideas of calculus and elementary
physics that justifies calling the strategy optimal.

In other material developed in the course, methods of data structuring are
used to implement symbolic differentiation as in the differential calculus.
Stream processing provides a method for understanding integration, and
shows how the arithmetic of infinite power series can be automated.  The
connections of these methods to the Macsyma system of ``symbolic
mathematics,'' a computer system of great use to researchers in science
and mathematics, are no mere coincidences.

Finally and most profoundly, the material presented in this course teaches
a wonder and respect for computation.  It is true, as often repeated in that
hackneyed phrase, that computers only do what we tell them to.  Stated
otherwise, a computational process evolves in a deterministic fashion from
an initial state, subject to fixed and mechanical constraints on the nature
of that evolution.  But the potential richness, depth, and variety of that
evolution, as this course teaches, is truly mind-boggling.  In the 
introduction to their book, Harold Abelson and his co-author Gerald Jay
Sussman, also of MIT, write the following:

\bigskip

\item{}
We are about to study the idea of a {\sl computational process.}
Computational processes are abstract beings that inhabit computers.  As
they evolve, processes manipulate other abstract things called {\sl data.}
The evolution of a process is directed by a pattern of rules called a
{\sl program.}  People create programs to direct processes.  In effect,
we conjure the spirits of the computer with our spells.

\item{}
A computational process is indeed much like a sorcerer's idea of a spirit.
It cannot be seen or touched.  It is not composed of matter at all.  
However, it is very real.  It can perform intellectual work.  It can
answer questions.  It can affect the world by disbursing money at a bank
or by controlling a robot arm in a factory.  The programs we use to conjure
processes are like a sorcerer's spells.  They are carefully composed from
symbolic expressions in arcane and esoteric {\sl programming languages}
that prescribe the tasks that we want our processes to perform.

\item{}
A computational process, in a correctly working computer, executes programs
precisely and accurately.  Thus, like the sorcerer's apprentice, the
novice programmer must learn to understand and to anticipate the
consequences of his conjuring.

\bigskip

In the same way that a biochemist marvels at DNA as a code that directs
the amazing growth and development of living organisms, I marvel as I watch
computer programs provide the code for the creation and interaction of
Abelson and Sussman's computational ``spirits.'' Just as
a chemist sees the elementary chemical building blocks 
of nature interact, combine,
and recombine as she pours solutions together, the computer scientist
sees the rich and seemingly unpredictible interaction of computational
processes as a result of her procedural incantations.

For all those who have looked askance at the existence of computer science
in the university, Abelson and Sussman have written, ``Underlying our
approach to this subject is our conviction that `computer science' is
not a science and its significance has little to do with computers.
The computer revolution is a revolution in the way we think and in the way
we express what we think.''

I believe that nothing could be more exciting or more important at a
university than to understand the way we think and how we express those
thoughts.  This new introductory course comes face-to-face with these profound
issues, and brings its students into the heart of the consequent
intellectual debate, sometimes pushing them to within striking distance
of the frontiers of research.  I believe it will provide them with tools
to strike out on frontiers of their own, frontiers of personal discovery,
creativity, understanding and synthesizing of knowledge, driven on by
the powerful metaphors that the study of computational processes provide,
and by the personal intellectual success that this course provides them.

This new course demands a great commitment from its students and
teaching staff.  Students have five official ``contact hours'' per
week with the teaching staff, and many more on an informal basis.
Because of that great contact, I believe that this course has another
thing to say that is also profound, though perhaps peripheral to the
issues of computation.  The University is a place for teaching and
learning, not simply for the transmission of information.  Teaching
and learning reinforce the respect, encouragement, and love that any
society or university needs to flourish.  I hope this class says
loudly and clearly that students have a place in the crucial function
of this University, not as passive receivers of knowledge that spouts
 from the end of a pedagogical assembly line, but as partners in an
important dialogue that defines what the University is.

I want the students in this class to have learned two things.  First,
how much there is that they don't know.  And second, that they can
learn anything they want.  I hope that they will never forget the
former, and always be inspired by the latter.  Every conceivable thing
was done in this course to provide a fertile and inspiring environment
for learning and discovery.  What could students possibly do under
such circumstances but mature, grow, and learn?

The lesson for the teaching staff in this course is not so different.
While Newton said he saw further because he stood on the shoulders of
giants, I have always preferred Nietzsche's remark that a teacher is
poorly repaid if one only remains a student.  

What a tremendous debt we teachers owe to those who nurtured us!  We
honor those who taught us by nurturing students, and the way we
express that nurturing is to teach students to grow and think for
themselves, so they don't need us any longer.  A friend of mine who is
a physician once said that the responsibility of a doctor is to love
your patients.  I believe above all that the responsibility of a
teacher is to love your students, to show them what is known, and to
inspire them to confront the unknown.  The territory is vast, and
because computer science is still so new, largely unexplored.  The
rewards are great for those who simply press forward.

\bye