CS 61A. The Structure and Interpretation of Computer Programs

Catalog Description: An introduction to programming and computer science focused on abstraction techniques as means to manage program complexity. Techniques include procedural abstraction; control abstraction using recursion, higher-order functions, generators, and streams; data abstraction using interfaces, objects, classes, and generic operators; and language abstraction using interpreters and macros. The course exposes students to programming paradigms, including functional, object-oriented, and declarative approaches. It includes an introduction to asymptotic analysis of algorithms. There are several significant programming projects.

Units: 4.0

Prerequisites: MATH 1A (may be taken concurrently); programming experience equivalent to that gained from a score of 3 or above on the Advanced Placement Computer Science A exam.

Credit Restrictions: Students will receive no credit for Computer Science 61A after completing Computer Science 47A or Computer Science 61AS. A deficient grade in Computer Science 61AS may be removed by taking Computer Science 61A.

Fall: 3.0 hours of lecture, 1.5 hours of discussion, and 1.5 hours of laboratory per week
Spring: 3.0 hours of lecture, 1.5 hours of discussion, and 1.5 hours of laboratory per week
Summer: 6.0 hours of lecture, 3.0 hours of discussion, and 3.0 hours of laboratory per week

Grading basis: letter

Final exam status: Written final exam conducted during the scheduled final exam period

Class Schedule (Fall 2020):
MoWeFr 2:00PM - 2:59PM, Internet/Online – Hany Farid, John DeNero

Class Schedule (Spring 2021):
MoWeFr 2:00PM - 2:59PM, Internet/Online – Paul HILFINGER

Class homepage on inst.eecs

General Catalog listing

Department Notes:

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.

Related Areas: