61A Course Description

Course Title
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

Catalog Data
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.

Prerequisites
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.

Catalog Description
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.

Expanded Description
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.