CS 47A. Interpretation of Computer Programs

Current Schedule (Spring 2015)


Catalog Description: (1 unit, self-paced, graded) Implementation of generic operations. Streams and iterators. Implementation techniques for supporting functional, object-oriented, and constraint-based programming in the Scheme programming language. Together with 9D, 47A constitutes an abbreviated version of 61A for students who have already taken a course equivalent to CS 61B.

Prerequisites: 61B or equivalent, plus CS 9D, plus consent of instructor. Students will not receive credit for CS 61A taken after CS 47A, or for CS 47A taken after CS 61A.

Course objectives: This self-paced course continues from where CS 9D left off, providing an abbreviated version of CS 61A for students who have already taken a course equivalent to CS 61B. Course activities include programming assignments and quizzes; quizzes focus on low-level language details or programming techniques, while programming assignments are broader in scope. The list of programming assignments appears below. All assignments use the Scheme programming language.

Topics Covered:

  • Rule-based programming: Students experiment with a rule interpreter and associated pattern matcher, and then write a set of rules that does simple type inference on a Scheme program.
  • Generic operations: Students first implement the set-of-integers data type both as a list of integers and as a sorted list of intervals. Then they convert these implementations to use data-directed programming. Finally, they recode the implementations in message-passing style.
  • Iterators and lazy evaluation: Students define Scheme streams to represent infinite data types and to implement iterators through multi-dimensional structures.
  • Scheme interpreter: Students work with and extend a Scheme interpreter written in Scheme.
  • Efficiency improvements: Students explore the efficiency benefits of mutation and vectors compared to side-effect-free programming using lists.

General Catalog

Undergraduate Student Learning Goals