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:
- MacGambit users: Place a single MacGambit file containing your
Scheme definitions (not a transcript of your interactive session!) in the
"HOMEWORK DROP BOX" folder located in the CS 22 class folder on the server.
Use your name together with the assignment number as the name of your file.
For example: "Jane Doe Homework 3".
- DrScheme users: Email me a
copy of your DrScheme file in plain text format. Use your name
together with "CS 22" and the assignment number as the subject of your email
message. For example: "John Doe CS22 Homework 5".
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:
- a comment at the top of your file with your name and the assignment number
- concise comments summarizing each of the main procedures of your program
- good use of white space to separate sections of code and improve legibility
- descriptive variable and procedure names
- logically well-organized code
- consistent indentation
- avoidance of long, wrapped lines
- avoidance of in-line comments and overcommenting
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
|