CS 61A. Structure and Interpretation of Computer Programs
Current Schedule (Spring 2015)
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, and predicates. 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 everything together.
- 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.