Syllabus
This is the syllabus for CS4400/5400. Please read the syllabus in its entirety.
1 Logistics
Piazza: This course has a Piazza page, sign up here
Input/Output: Important messages will be sent as Piazza announcements; you are responsible for ensuring that you receive these messages. All graded work will be submitted to GradeScope. A course code for joining the GradeScope is on Canvas.
This course will be taught primarily using the Racket programming environment.
You are expected to attend all lectures in-person. Lectures consist of live programming, whiteboard work, and group activities. Lecture notes will be posted online on this webpage before the lecture.
2 Course description
Our goal in this course is to study the essentials of programming languages: their purpose, their design, and their implementation. You have all programmed before, probably in multiple programming languages. You may have noticed differences and similarities between the programming languages and wondered: why are there so many languages? Why are they different and similar in these particular ways? Why is programming in one language sometimes easier than others? How (and why) are new programming languages made? We will study these questions bottom-up: we will grow a tiny language and add features to it iteratively, along the way encountering many of the core ingredients that go into today’s modern programming languages. We will also see some of the core formal notions that have been so effective in designing many of today’s languages: in particular, we will see formal language semantics and type systems. Finally, we will go beyond our tiny language and explore some exotic languages that are radically different from ones you may have seen before. In the end, you should be equipped to learn new programming languages quickly, understand the key design decisions made by many of today’s languages, and be prepared for a world where new programming languages are being made all the time.
Module 1: Introduction. Our goal of this module is to introduce and motivate the topic of programming languages and become familiar programming in Racket. We will learn how to program in functional style, program with inductively defined datatypes, and become familiar with notation for describing induction.
Module 2: The λ-calculus. Our goal in this module is to grow a small but surprisingly rich programming language. We will add features slowly: first, we will add let-bindings and study scope and substitution. Then, we will introduce the λ-calculus, and become familiar with programming in it: we will see how to compile programs into the λ-calculus (Church encoding), how to program with recursion (Y-combinator), and how to implement the λ-calculus efficiently on a Von-Neumann architecture (environments and closures). Along the way, we will learn how to implement interpreters from big-step style inductive notation, and how to draw a derivation tree for an interpreter.
Module 3: Types. Our goal in this module is to implement and design type systems for practical programming languages. Many of today’s modern programming languages have types: it is important to understand what they are and how they are made. We will start by adding simple types to the λ-calculus and implementing a type-checker. We will see how to describe type systems using inductive notation, and how to draw a derivation tree for well-typed programs. Then we will slowly grow the underlying features of the language.
Module 4: Control and effects. Our goal in this module is to be able to implement programming languages with rich control-flow primitives. We will study continuations and and understand how to write programs in tail-form. We will use these ideas to implement interpreters for languages with exceptions, coroutines, or non-determinism. Then, we will see how to compile continuation-passing style, and understand how it is used to add exotic control-flow constructs into languages that don’t natively have them.
Module 5: Abstract machines. Our goal in this module is to be able to describe the low-level behavior of how programs are executed on a simple model of a CPU called an abstract machine. We will develop an increasingly rich hierarchy of CPU models and describe how to evaluate programs on these models. We will explore memory safety, performance, and dynamic safety.
Module 6: Proof assistants. Our goal in this module is to explore proof assistants and how they can be used to proof properties of and reason about programming languages. We will use the Lean proof assistant to state and prove basic meta-theoretic properties of the languages we have developed so far in the course.
3 Reference materials
The primary reference for this course will be the course notes, provided after each lecture and available on this website. You are strongly encouraged to review the course notes after each lecture. The following textbooks are good additional resources and will be occasionally referenced in class:
Krishnamurthy, Shriram. Programming Languages: Application and Interpretation. Link
Friedman, Daniel P. and Mitchell Wand. Essentials of programming languages. Third edition. MIT press, 2008.
Pierce, Benjamin C. Types and programming languages. MIT press, 2002.
Harper, Robert. Practical foundations for programming languages. Cambridge University Press, 2016.
Ramsey, Norman. Programming Languages: Build, Prove, and Compare. Cambridge University Press, 2022.
4 Coursework and Grading Policies
The course will consist of the following graded material, subject to change as the semester progresses (all changes to the grading scale will be announced in class and on Piazza):
Assignments (30% Of Total): About 8 in total. Posted on this webpage, turned in on GradeScope. You may discuss the problems with other students, but you must submit your own solutions.
Concept Check Quizzes (10% Of Total): Once a week due at 11:59PM Monday each week. Each should take no more than 15 minutes, and will be released on GradeScope no later than Monday morning at 9AM on Monday. The lowest concept check quiz score will be dropped.
Exams (60% of total): There will an in-class written midterm exam on Feb 26 and an in-person final exam during the scheduled final exam period. Each exam will be worth 30% of the total for this category.
Grades are allocated by points, and the percentage is determined by the percentage of total points within each category.
4.1 Late work policy
Assignments will be due at 11:59PM, and late work will be penalized according to the following scale:
Less than 24 hours late: 5% penalty
24 – 48 hours late: 20% penalty
More than 48 hours late: no longer accepted (at this point we will begin grading and require all work to be turned in).
This timeline is in place to ensure timely return of grades. If you require special accommodations or a grading extension, please post a private Piazza question for the the instructors in advance of the deadline; we are very willing to work with you to find a suitable accomodation.
Late work for exams and concept check quizzes will not be accepted.
4.2 Grading thresholds
Letter grades will be assigned according to a standard grading threshold based on percentage of total points:
Score range | Letter grade |
>93 | A |
≥90 | A- |
≥87 | B+ |
≥83 | B |
≥80 | B- |
≥77 | C+ |
≥73 | C |
≥70 | C- |
≥67 | D+ |
≥63 | D |
≥60 | D- |
<60 | F |
The instructor may curve final grades up based on course circumstances. Individual assignments and exams may be curved up as well; in the event that this is necessary, the curving scheme will be explained in a Piazza post.
5 Academic Honesty
Cheating and other acts of academic dishonesty will be referred to Khoury College. There are very serious penalties here, so please do not take any chances by copying any material from the Internet or from other past or present students of this course or related courses. In particular, when completing the programming assignments, it is important that you do not refer to any completed solutions that you find on the Internet. When in doubt, ask the instructor or consult the Northeastern academic honesty page here.
Usage of code generation tools. Code generation tools like ChatGPT and Claude are now widely available. You may use these tools if you find them helpful to you. However, be warned that these tools can be a crutch: you will likely find yourself struggling in the course if you rely too heavily on these tools to automatically produce your code for your assignments, since many of the assignments are cumulative. You are encouraged to first attempt all assignments yourself, without any assistance.
Remote policy The instructor will follow university policies on whether or not the course is to be taught in-person. The class is assumed by default to be in-person: the instructor will make an announcement if it will not be in-person. If the class is to be remote, it will be taught online using Zoom, and a link will be available in Canvas under the Zoom tab. Lectures may be recorded under certain circumstances. Please feel free to contact the instructor if you have any questions.
5.1 Title IX
Title IX of the Education Amendments of 1972 protects individuals from sex or gender-based discrimination, including discrimination based on gender-identity, in educational programs and activities that receive federal financial assistance.
Northeastern’s Title IX Policy prohibits Prohibited Offenses, which are defined as sexual harassment, sexual assault, relationship or domestic violence, and stalking. The Title IX Policy applies to the entire community, including male, female, transgender students, faculty and staff.
If you or someone you know has been a survivor of a Prohibited Offense, confidential support and guidance can be found through University Health and Counseling Services staff (https://www.northeastern.edu/uhcs/) and the Center for Spiritual Dialogue and Service clergy members (https://www.northeastern.edu/spirituallife/). By law, those employees are not required to report allegations of sex or gender-based discrimination to the University.
Alleged violations can be reported non-confidentially to the Title IX Coordinator within The Office for Gender Equity and Compliance at: mailto:titleix@northeastern.edu and/or through NUPD (Emergency 617.373.3333; Non-Emergency 617.373.2121). Reporting Prohibited Offenses to NUPD does NOT commit the victim/affected party to future legal action.
Faculty members are considered "responsible employees" at Northeastern University, meaning they are required to report all allegations of sex or gender-based discrimination to the Title IX Coordinator.
In case of an emergency, please call 911.
Please visit https://www.northeastern.edu/titleix for a complete list of reporting options and resources both on- and off-campus.
5.2 Students With Disabilities
Students who have disabilities who wish to receive academic services and/or accommodations should visit the Disability Access Services at 20 Dodge Hall or call (617) 373-2675. If you have already done so, please provide your letter from the DRC to me early in the semester so that I can arrange those accommodations.