CS 22: Structure and Interpretation of Computer Programs

Spring 2000
Swarthmore College
Professor Jim Marshall


Course Description

This course is a rigorous introduction to computer science, emphasizing the development of abstraction techniques for controlling the complexity of programs. This is an important skill applicable to almost all areas of engineering design. Throughout 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. Topics to be covered include functional programming, recursion, data abstraction, higher-order procedures, lists and symbol processing, sets, object-oriented programming and local state, stream processing, and metalinguistic abstraction. The course culminates in the development of an interpreter, written in Scheme, for a substantial subset of the Scheme language itself.

This course is a Natural Science PDC.


Course Materials

We will be using MacGambit Scheme for the Macintosh and/or DrScheme for PCs. DrScheme is available in a variety of formats including Mac, Windows, Linux, and Unix. Class periods will consist of a combination of lectures and hands-on interaction at the computer, so you should always bring disks and your textbook to class. The textbook we will be using is Structure and Interpretation of Computer Programs, 2nd Edition, by Abelson, Sussman, and Sussman.


Contact Info

Office Hours: 4:00-5:00pm Monday, Wednesday, and Thursday.
Office: Sproul Observatory Room 6
Office Phone and Voice Mail: (610) 328-8665
E-mail: marshall@cs.swarthmore.edu (or jmarsha1@swarthmore.edu)
If you need to see me but can't make it to my office hours, I'll be happy to schedule an appointment. Please contact me by e-mail or leave a message on my voice mail.


Grading

30% Homework Assignments
20% Exam 1 (Tuesday, February 22, 7:00-9:00pm, Location to be announced)
20% Exam 2 (Thursday, April 6, 7:00-9:00pm, Location to be announced)
25% Final Project (due 5:00pm Tuesday, May 2)
5% Class Participation


Homework Policy

Homework will generally be assigned on Tuesdays by email and will be due by the beginning of class the following Tuesday. Late homework is not accepted, except in dire circumstances and with 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 (no hardcopy printout is necessary). In order to receive credit for an assignment, you must do the following:

If, after submitting a file, you decide to revise it, you may resubmit it any number of times up to the deadline. Name the new version as before, except attach a letter to the assignment number. For example, "Jane Doe Homework 3b" (3c, 3d, etc.). I will only look at your most recent submission (before the deadline).

If a homework problem requires you to answer questions instead of (or in addition to) writing Scheme code, simply include your answers in the form of a clearly-labeled comment in your Scheme file.


Academic Integrity

The utmost level of academic integrity is expected of every student. Under no circumstances may you hand in work done with (or by) someone else under your own name. If in doubt, credit the person(s) from whom you got help. Discussing ideas and approaches to problems with others on a general level is fine (in fact, encouraged) but you should never read anyone else's code or solutions, or show your code or solutions to anyone else in the class. Failure to abide by these rules constitutes academic dishonesty, and will be dealt with severely. Please do not put me or yourself in this unpleasant situation.


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 a 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 humans 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:


Schedule of Topics (subject to change)

Key: SICP = Structure and Interpretation of Computer Programs, 2nd Edition

WEEK DATES TOPICS READINGS and ANNOUNCEMENTS
1 1/18 - 1/20 Introduction to Scheme and recursion SICP 1.1, Handout
2 1/25 - 1/27 Simple and deep recursion SICP 1.2 through 1.2.2 (Drop/add ends Friday 1/28)
3 2/1 - 2/3 Higher-order procedures SICP 1.3
4 2/8 - 2/10 Data abstraction SICP 2.1
5 2/15 - 2/17 Hierarchical data and sequences SICP 2.2 through 2.2.3
6 2/22 - 2/24 Graphics in MacGambit EXAM 1 Tuesday 2/22 7-9pm (Location TBA)
7 2/29 - 3/2 Graphics (continued), Sets SICP 2.2.4, 2.3.3
- 3/7 - 3/9 Fun and relaxation SPRING BREAK
8 3/14 - 3/16 Intro to object-oriented programming SICP 3.1 (Last day to withdraw Monday 3/13)
9 3/21 - 3/23 Object-oriented programming (continued) SICP 3.3.4
10 3/28 - 3/30 Mutable data, Streams SICP 3.3.1, 3.5
11 4/4 - 4/6 Streams (continued) EXAM 2 Thursday 4/6 7-9pm (Location TBA)
12 4/11 - 4/13 Interpreter project Handouts, SICP 4.1 through 4.1.6
13 4/18 - 4/20 Interpreter project (continued) Handouts
14 4/25 - 4/27 Interpreter project (continued) Handouts PROJECT DUE 5pm Tuesday, May 2