Principles of Programming Languages

This is a course from a previous year. View the current courses

This course explores the principles of programming language design through the study and implementation of interpreters, which are computer programs that process other programs as input. A famous computer scientist once remarked that if you don't understand interpreters, you can still write programs—and you can even be a competent programmer—but you can't be a master. We will begin by studying functional programming using the strangely beautiful and recursive programming language Scheme. After getting comfortable with Scheme and recursion, we will see how to design our own languages by starting from a high-level description and systematically deriving a low-level implementation through the application of a series of program transformations. Along the way, we will become acquainted with the lambda calculus (the basis of modern programming language theory), scoping mechanisms, continuations, lazy and nondeterministic evaluation, and other topics if time permits. We will use Scheme as our “meta-language” for exploring these issues in a precise, analytical way, similar to the way in which mathematics is used to describe phenomena in the natural sciences. Our great advantage over mathematics, however, is that we can test out our ideas about languages, expressed in the form of interpreters, by directly executing them on the computer. Permission of the instructor is required. No prior knowledge of Scheme is needed, but at least one semester of prior programming experience is expected.