CS37: Structure and Interpretation of Computer Programs
Spring 2006
Swarthmore College

Professor: Lisa Meeden
Course: Tuesdays and Thursdays 11:20-12:35, SCI 240
Email: meeden AT cs.swarthmore.edu
Office: SCI 243
Phone: 328-8565
Office hours: Thursdays 1:30-3:30pm, or by appointment

Contents

Course Description

This course emphasizes the development of abstraction techniques for controlling the complexity of programs. This is an important skill applicable to almost all areas of design. For the majority of the course, we will be using a dialect of the Lisp programming language, called Scheme. Scheme's great flexibility and power, combined with its very simple syntax, will allow us to concentrate on exploring interesting computer science concepts, without getting sidetracked by irrelevant and distracting details of syntax or other language idiosyncrasies. We will also explore the logic programming language called Prolog.

Topics to be covered include functional programming, recursion, data abstraction, higher-order procedures, lists and symbol processing, sets, object-oriented programming and local state, logic programming, and metalinguistic abstraction. The course culminates in the development of an interpreter, written in Scheme, for a substantial subset of the Scheme language itself. Class periods will consist of a combination of lectures and hands-on interaction at the computer.

Course Materials

Grading

25% Homework Assignments
25% Exam 1
25% Exam 2
20% Final Project
5% Class Participation (based on attendance and quizzes)

Homework Policy

Weekly homework assignments will be posted on this web page. Late homework is not accepted, unless you obtain prior approval from me. Even if you miss a deadline, you are strongly encouraged to complete the assignment anyway, since this really is the only effective way to learn the material. You will turn in your homework assignments electronically using handin37. Generally homework will be assigned on Thursday and be due by midnight on the following Wednesday.

Good Programming Style

In its purest form, programming is the art of expressing abstract ideas about computation in language that is as clear, unambiguous, and explicit as possible. To become an expert programmer, it is not enough simply to write programs that work correctly when run on a computer. Your programs must also be easy for other people to read and understand. Indeed, good programming is as dependent on a deeply-developed sense of aesthetics as is good writing or other types of artistic activity. In short, style matters. Accordingly, programs will be graded with respect to both style (40%) and correctness (60%). Good programming style typically includes the following:
WEEK DAY ANNOUNCEMENTS READING HW
1 Jan 17   Basic Scheme / Lists
Section 1.1		 1: Basic Scheme
Jan 19  
2 Jan 24   Recursion and Iteration
Section 1.2 - 1.2.2		 2: Recurcsive Functions
Jan 26 Last Day to Add/Drop (Jan 27)
3 Jan 31   Abstractions with Higher-Order Functions
Section 1.3		 3: Higher-Order Functions
Feb 02  
4 Feb 07   Data Abstraction
Section 2.1		 4: Animation
Feb 09  
5 Feb 14   Hierarchical Data
Section 2.2 - 2.2.2		 None
Feb 16 Exam 1
6 Feb 21   Trees and Sets
Section 2.3		 5: Huffman encoding
Feb 23  
7 Feb 28   Object-Oriented Programming
Chapter 3 Introduction & Section 3.1		 None
Mar 02  
  Mar 07 Spring Break
Mar 09
8 Mar 14   Mutable Data
Section 3.3		 6: Simulating Circuits
Mar 16  
9 Mar 21   Streams
Section 3.5		 7: Streams
Mar 23 Last Day to Withdraw with W (Mar 24)
10 Mar 28   Logic Programming and Prolog 8: Prolog
Mar 30  
11 Apr 04   None
Apr 06 Exam 2
12 Apr 11   Interpreter Project Part 1: Environments
Apr 13   Part 2: Mutating environments
Extension 1: Syntax checking & Quasiquote
13 Apr 18   Part 3: Primitive procedures
Apr 20   Part 4: Special forms
Extension 2: Tracing
14 Apr 25   Part 5: Lambda and let
Apr 27   Part 6: Meta-circularity
Extension 3: Marcos
  May 08 Final project due Monday May 8 at noon