CS 47A. Completion of Work in Computer Science 61A

Catalog Description: 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, self-paced version of 61A for students who have already taken a course equivalent to 61B.

Units: 1

Prerequisites: COMPSCI 61B, COMPSCI 9D, and consent of instructor.

Credit Restrictions: Students will receive no credit for 47A after taking 61A.

Spring: 0.0 hours of self-paced per week
Fall: 0.0 hours of self-paced per week

Grading basis: letter

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

Class Schedule (Fall 2023):
CS 47A –John DeNero

Class Schedule (Spring 2024):
CS 47A –John DeNero

Class homepage on inst.eecs

Department Notes:

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.