CS 61A - The Structure and Interpretation of Computer Programs
Abbreviated Course Title
STR INTERP CMP PRGS
Instructors in Charge
Mike Clancy Senior Lecturer
Brian Harvey, Lecturer
4 units; 3 hours lecture, 3 hrs combined lab and discussion section,
average 6 additional hours self-scheduled
programming laboratory. Offered fall, spring, and summer terms.
Math 1A (may be taken concurrently);
programming experience with recursion equivalent to that gained
in CS 3 or the Advanced Placement Computer Science A course.
Introduction to programming and computer science.
This course exposes students to techniques of
abstraction at several levels:
(a) within a programming language, using higher-order functions, manifest
types, data-directed programming, and message-passing; (b) between
programming languages, using functional and rule-based languages as examples.
It also relates these techniques to the practical problems
of implementation of languages and algorithms on a von Neumann machine.
There are several significant programming projects,
programmed using the Scheme programming language.
Lectures also introduce the use of the UNIX operating system,
computer science applications, and social implications.
We follow the textbook
Structure and Interpretation of Computer Programs
by Abelson and Sussman (second edition, MIT Press, 1996) fairly closely,
but with somewhat more emphasis on symbolic computation and less on
numerical examples from the calculus and number theory.
A course outline follows.
- Functional abstraction
This material comprises most of the first chapter of the text,
and covers roughly three weeks of the course.
In the first week, we talk about the fundamentals of Lisp computation:
names and values, evaluation, function definition and evaluation,
The first week also includes
an introduction to the UNIX operating system
and the editor students will use to create programs.
We introduce list processing procedures at the beginning
(the text defers lists to chapter 2) to allow for symbolic examples.
In the second week, we discuss higher-order functions, including
the use of functions as parameters,
the definition of functions with LAMBDA,
and the use of functions that return functions as values.
The third week moves to recursion
and covers the topic of processes and orders of growth,
introducing the use of iterative algorithms for efficiency.
Assignments provide practice in design and analysis via short exercises,
and culminate in a rather longer programming problem that tries to tie
- Data abstraction
This material appears in the second chapter of the text,
and takes around three weeks to cover.
We start with the idea of data abstraction
and techniques for implementing "abstraction barriers."
Next, we discuss the use of Scheme pairs
to implement lists, trees, and other data structures.
Finally, we spend a week on more advanced data abstraction techniques:
tagged data, data-directed programming, and message-passing.
Several assignments provide the students with practice in these areas,
and the second course project combines the techniques taught here
with the procedure-as-data concepts covered earlier in the course.
- State and assignment
In the next five weeks, we cover the use of state and local assignment
to write efficient programs; this material comes from the third
chapter of the text.
The first two weeks introduce the idea of object-oriented programming,
assignment, and the environment
model of evaluation that is needed to understand how local state is
maintained in Scheme. In the third week we discuss mutable data.
The fourth week is about concurrency; the fifth week cover streams,
an attempt to model time-varying state information within the
functional programming approach.
Short assignments during this section of the course are interspersed
with a substantial programming project using object-oriented techniques,
such as an adventure game.
- Metalinguistic abstraction
Another four-week period is devoted to the creation of new programming
languages, as a still more powerful abstraction technique. Two major
examples are presented: Lisp interpreters in the first two weeks and
a logic programming language in the next week. Assignments include the
last major programming project, an interpreter for another programming
language. This section of the course follows the fourth chapter of the text.