CS 43: Principles of Programming Languages

Fall Semester 1999
Swarthmore College
Professor Jim Marshall

Course Description

This course provides a thorough introduction to fundamental concepts involved in the design of programming languages. It is not a survey course of existing languages; rather, it explores general issues in programming language methodology through the study and implementation of interpreters. We will see how a very high-level, almost mathematical, specification of the semantics of a language can be used to systematically derive a low-level implementation for it, almost at the assembly-language level, through the application of a series of correctness-preserving program transformations. Along the way, we will become acquainted with the lambda calculus (the mathematical basis of modern programming language theory), representation independence, syntactic abstraction, continuations and continuation-passing style, lazy evaluation, nondeterministic evaluation, and, if time permits, compiler derivation and logic programming. Throughout the course, we will use the Scheme programming language as our meta-language for exploring these issues in a precise, analytical fashion---in much the same way that the language of mathematics is used to precisely describe and analyze phenomena in the natural sciences. Our great advantage over mathematics, however, will be the ability to directly test out our ideas about languages, expressed clearly and unambiguously in the form of Scheme programs, by running them on the computer and observing the results.

Contact Info

Office Hours: Tuesdays and Thursdays 2:45-4:30pm, and by appointment.
Office: Sproul Observatory Room 6
Office Phone and Voice Mail: 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, please contact me by e-mail or leave a message on my voice mail.


Essentials of Programming Languages, by Friedman, Wand, and Haynes.


50% Homework Assignments
25% Exam 1 (date to be negotiated)
25% Exam 2 (date to be negotiated)

We will be using the SCM Scheme Interpreter on the Computer Science Suns. Assignments will generally be due every week. You should submit both hardcopy and electronic versions of your code. Your grade will be strongly influenced by the legibility of your code, so it is very important to use a clear and aesthetically-pleasing programming style. Late homework is not accepted. You are strongly encouraged to do the assignments, even if you miss the deadline, since this is really the only way to learn the material.

Weekly Course Schedule and Reading Assignments

Note: You will get the most out of the class time if you do all of the week's reading PRIOR to the first class meeting of that week.

Week 1 (9/2): Review of Scheme and Recursion (Reading: EOPL 1.1-2.2, 3.2-3.3)

Week 2 (9/7-9/9): Static Properties of Variables; Records and Data Abstraction (Reading: EOPL 2.3)


Week 3 (9/14-9/16): The Lambda Calculus (Reading: EOPL Chapter 4)

Weeks 4-5 (9/21-9/28): Interpreters (Reading: EOPL Chapter 5)

Weeks 5-6 (9/30-10/5): Continuation-Passing Style (Reading: EOPL Chapter 8)

EXAM 1 (around October 5-7)

* * * F A L L * * * B R E A K * * *


Weeks 7-8 (10/19-10/28): Continuation-Passing Interpreters (Reading: EOPL Chapter 9)

Weeks 9-10 (11/2-11/11): Imperative Form and Stack Architecture (Reading: EOPL Chapter 10)

Week 11 (11/16-11/18): Lazy Evaluation

EXAM 2: (around November 16-18)

* * * T H A N K S G I V I N G * * * B R E A K * * *

Weeks 12-14 (11/23-12/9): Nondeterministic Evaluation, Compiler Derivation, Logic Programming, other topics if time permits (Reading: TBA)