Principles of Programming Languages

Sarah Lawrence College
Fall 2021


If you don't understand interpreters, you can still write programs; you can even be a competent programmer. But you can't be a master.

—Hal Abelson, Professor of Electrical Engineering and Computer Science, MIT

Overview

This course explores the principles of programming language design through the study and implementation of computer programs called interpreters, which are 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 develop an interpreter for a Scheme-like language of our own design, gradually expanding its power in a step-by-step fashion. Along the way, we will become acquainted with the lambda calculus (the basis of modern programming language theory), scoping mechanisms, continuations, lazy evaluation, nondeterministic programming, 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.

Intermediate. No prior knowledge of Scheme is needed, but at least one semester of prior programming experience is expected.

Instructor

Prof. Jim Marshall
Office: Ilchman Science Center 100
Phone: 2673 (from off campus: 914-395-2673)
Email: j + my last name + @sarahlawrence.edu

Class Meeting Times

Textbooks

REQUIRED
The Little Schemer, 4th edition
Daniel P. Friedman and Matthias Felleisen
OPTIONAL
The Scheme Programming Language, 4th edition
R. Kent Dybvig

Attendance Policy

On-time attendance is expected for all class meetings and conferences. Given the fast-paced, cumulative nature of the course material, students who miss class risk quickly falling behind, and catching up can be difficult. Although I realize that missing class sometimes cannot be avoided, your cumulative attendance record will influence your final course grade, and you may receive reduced course credit if you miss more than 3 classes, for any reason. If you are unable to attend class, please contact me about it as soon as possible. Special note: Everyone is required to attend our last class meeting on Friday, December 17 — so plan accordingly. No student will be admitted to the course after the add/drop period ends.

Email

I will often send out announcements to the class through email, so you are expected to check your Sarah Lawrence email account at least once per day. I will use your @gm.slc.edu address because it is reliable and easy to remember. You should also check the course web pages frequently for code examples discussed in lecture, and for the homework assignments. I will be happy to answer your questions by email and will try to respond as quickly as possible to messages that pertain to the course.

Homework Assignments

We will have many homework assignments this semester, usually one or two per week. This is to give you as much hands-on practice with the course concepts as possible, which is the only effective way to learn the material. Homework assigned on Tuesday will typically be due later that week on Friday, whereas homework assigned on Friday will be due the following Tuesday.

The homework assignments are the heart of the course. Most assignments will involve writing, testing, and debugging Scheme code. We will start out by writing many small, recursive programs in order to get the hang of recursive programming in Scheme. After we are comfortable with recursion, we will turn our attention to interpreters and the fundamental concepts of programming language design. You should expect to spend a substantial amount of time — several hours, at least — outside of class each week working on the assignments. Fortunately, programming is a lot of fun, and many students are surprised to find that they eagerly look forward to doing their programming assignments each week!

You will use a web-based submission system to turn in your Scheme files for each assignment. Please DO NOT email your homework to me. You should always include your name and the assignment number in a comment at the top of each file that you turn in. More details about using this system will be provided in class.

Start each assignment as early as possible. Don't wait until the day before it is due. "I can't get Scheme to work on my computer!" or "My computer crashed!" or "I accidentally deleted my files!" are not acceptable excuses for failing to complete an assignment on time. You should always make backup copies of your files to avoid this type of situation.

Homework Evaluation Scale

Homework assignments are evaluated on both the functionality and style of your code, according to the following rubric. To receive a ☆, your code must not only work perfectly, it must also be logically well-organized and easy to read.

Work of excellent quality that clearly meets or exceeds all of the assignment expectations. All programs work correctly on all of the input data, and are written in a clear, easy-to-read style.
✓+ Work of very good quality that meets most of the assignment expectations. Programs work correctly or mostly correctly for most of the input data, though some programs may have a few minor deficiencies or stylistic problems.
Work of satisfactory quality that meets some of the assignment expectations and reflects a good effort overall, despite some deficiencies. Some programs work correctly or mostly correctly for most of the input data, but may have significant stylistic problems or other shortcomings.
✓− Work of subpar quality that falls short of assignment expectations and needs improvement. Some programs have serious deficiencies, and work incorrectly for a significant portion of the input data. Nevertheless, the work shows some degree of effort and understanding.
Work of poor quality that exhibits severe problems, reflecting minimal effort or understanding. Many programs crash or work incorrectly for most or all of the input data.

Getting Help

At times you may find some of the course material to be quite daunting. But don't be discouraged! If you find it difficult, most likely so does the rest of the class. This is just a normal part of the process of learning to program. You are strongly encouraged to contact me as soon as possible whenever you are having difficulty with the material. You should also be sure to attend one (or even both) of the weekly group conference sessions, during which we will discuss whatever concepts students are having trouble with, and work on practice exercises together. In short, if you are confused about something, don't stay that way! Staying confused will only make things worse later (remember the staircase metaphor). Contact me as soon as possible so that we can clear up the problem. There is no point in staring at the computer screen for hours trying to figure out why your code won't work, when just a few minutes is often all it takes to track down the problem together. I'll also be happy to answer questions over email or schedule a meeting with you on Zoom.

How to Succeed in This Course

Accommodations

If you have a disability that may interfere with your ability to participate in the activities, coursework, or assessment of the objectives of this course, or any of your other courses, you may be entitled to reasonable accommodations. Please contact Polly Waldman, Associate Dean of Studies and Disabilities Services located in Westlands 116. You may also call Disability Services at 914-395-2235 or email pwaldman at sarahlawrence.edu. Under the Americans with Disabilities Act and Section 504 of the Vocational Rehabilitation Act of 1973, all students, with or without disabilities, are entitled to equal access to the programs and activities of Sarah Lawrence College and the College will make reasonable accommodations when appropriate and necessary.

Collaboration Policy

The highest level of academic integrity is expected of every student. You are strongly encouraged to discuss ideas and approaches to solving problems on a general level with your fellow classmates, but you are not allowed to share your program files, code, or solutions with others, or to make use of another student's code or solutions obtained via email, the Internet, or any other means of communication. I can almost always tell when two different programs derive from the same original source code, even if cosmetic changes have been made to it. The code you hand in must have been written by you from scratch, with the following permitted exceptions: code provided in class by me, code from the textbook, or code developed together with a partner if you are collaborating on a homework assignment or project with my knowledge. In this case, you and your partner may freely exchange code developed as a team, and are jointly responsible for the work submitted. Under no circumstances may you hand in work under your own name that was done by someone other than yourself or your partner.

In all cases, if you make use of any code that was written by someone else in your assignment, including your partner, you must clearly acknowledge this in your code. This also goes for any help obtained via the Internet. When in doubt, credit the people or sources from whom you got help. If you are ever unsure about what constitutes acceptable collaboration, just ask. You are also responsible for carefully reading the College's official Policy on Academic Integrity in your SLC Student Handbook. Failure to abide by these rules is considered plagiarism, and will result in severe penalties, including possible failure in the course. Please do not put me, yourself, or anyone else in this unpleasant situation!