Syllabus
Quick links
Logistics
- Communicating with course staff: we will use Piazza for course communication. By default, your messages will send to the entire class, but please make use of the instructors-only and private message features: this is strongly preferable to email and will get your questions answered faster.
- Software: The lecture material and assignments will use (and ask you to use) the Racket programming language, specifically the Plait hashlang.
- Submitting homework: all homework will be submitted on Gradescope unless told otherwise.
- Course materials and resources: all other course materials and resources will be published on this website.
- Office hours: each course staff member will post office hours on Piazza; you are encouraged to go to these if you need help. If you cannot make the posted times, you may contact instructors (on Piazza) to request an appointment.
Course Description
Our goal in this course is to study programming languages (PL) from first principles: the basic elements that they are made of, the design choices available for each of these elements, and the mathematical properties and human affordances determined by these choices. To do this, we will study mathematical representations of languages meant to illustrate the essence of “big ideas”, such as higher-order functions, abstraction, recursion, imperative programming, and concurrency.
We will use methodologies of formal definition and proof considered the standard in the PL research community, such as definition by inference rules, type systems, operational and denotational semantics. These are mathematical formalisms that can describe a language as a set of rules for how programs may put together syntactically and what they mean semantically., a distinction that PL shares in common with the study of natural language linguistics.
At the end of this course, you should be able to:
- Write interpreters and type checkers for small languages.
- Systematically derive the meaning of a program “on paper”, without reference to its implementation or execution.
- Explain how the design of a language’s type system affects which programs are syntactically valid and which runtime errors are eliminated.
- Explain your favorite programming language’s features in terms of syntax, types, and semantics.
- State and prove type safety for a simple language; provide counterexamples to type safety for languages that aren’t type safe; explain the practical implications and non-implications of type safety.
- Describe how mathematical properties of languages motivate certain language design choices, such as the introduction and elimination forms for types.
- Describe different language design choices and their tradeoffs.
- Explain how different language features interact with one another, including situations where a combination of features leads to unexpected behavior not present with either feature by itself.
- Make a small change to an existing programming language and justify it with respect to the desired properties of the language.
Modules
This course will cover the following topics in roughly the order given.
- Module 1: Representing Languages. Our goal of this module is to introduce and motivate the topic of programming languages and become familiar programming in Racket/Plait. We will learn how to program in functional style, program with inductively defined datatypes and higher-order functions, and use these ideas to implement a first interpreter for a tiny language.
- Module 2: The λ-calculus. Our goal in this module is to understand how languages are defined, starting with a small but surprisingly rich programming language. First, we will introduce “on paper” notation for defining programming languages and describe how it maps to a Plait implementation. Then, we will use it to describe a language with let-bindings, requiring notation and representation strategies for scope and substitution. Next, 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 introduce inference-rule notation and use it to “run a program on paper.”
- Module 3: Types. Our goal in this module is to implement and design type systems for practical programming languages. We will start by adding simple types to the λ-calculus and implementing a type-checker. We will see how to describe type systems using inference rules, and how to draw typing derivation trees. Then we will slowly grow the underlying features of the language, introducing recursive types and polymorphism, to arrive at a language not unlike Plait itself. Along the way, we will translate type system definitions to type checking and inference implementations in Plait.
- Module 4: Continuations. Our goal in this module is to be able to understand and implement programming languages with expressive 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: State and Effects. Our goal in this module is to be able to understand and implement effectful programming features such as mutable state, exceptions, and input/output. We will describe how to start from a restricted setting without these features and build them up using call-by-push-value and/or monads.
- Module 6: Proof assistants and dependent types. 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.
Graded work
Grades for the course will be calculated as follows.
- Assignments (40% of total): About 5 assignments consisting of programming and written responses to questions. These will be posted on the website and/or Gradescope. Programming portions will be autograded, but we may also read your code and add or subtract credit accordingly.
- Concept Checks (10% of total): Administered weekly on Gradescope, expected to take about 10-15 minutes. These will serve mainly as a diagnostic for instructors and for yourself on reaching the course learning objectives; you will be given credit based only on completion (rather than correctness).
- Midterm exam (20% of total): There will an in-class written midterm exam prior to Spring Break.
- Mini-project + presentation (20% of total): The final assignment in the class will combine everything you’ve learned and allow some creative freedom to explore a topic in more depth. In lieu of a final exam, during our scheduled final exam period, you will give a presentation to your instructor and classmates about your final assignment topic, to be graded on how well your work demonstrates the learning objectives of the course.
- Intake forms, reflections, and participation (10% of total): There will be an initial intake form, a mid-semester reflection/feedback form, and in-class interactive activities/discussions that everyone is expected to participate in (although we will not formally track attendance). You will be given credit for these based on your (timely) completion of them. Extra credit may be granted for exceptional “classroom community” efforts, such as answering classmate questions on Piazza.
Late work policy
Assignments and concept checks 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 and facilitate our ability to discuss the solutions in class.
If you require special accommodations or a grading extension in case of an emergency, please post a private Piazza question for the the instructors in advance of the deadline.
Late work for exams will not be accepted.
Regrade requests
Instructors make mistakes, so you should check over your graded work when we return it to you, and let us know if you think there’s an error.
Please make all regrade requests through Gradescope within one week of receiving your grade. Regrade requests pasts the one-week window will not be addressed without special permission, which you must request and receive in writing.
Academic honesty
The work you submit for this class is expected to represent your individual skills and knowledge, helping both us and you understand where you are relative to the learning objectives. If someone else did the work, and you claim credit for it, you are undermining not only the people who did that work, but also your peers, Northeastern University’s credibility, and your own ability to learn.
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. When in doubt, ask the instructor or consult the Northeastern academic honesty page here.
In particular, when completing the programming assignments, you are expected to fully understand and be able to explain verbally every line of code, comment, and written response that you submit. We may periodically/stochastically request these verbal explanations in class.
The easiest way to be able to do this is to complete the work yourself without outside sources. If you do refer to outside sources, including code on the internet or generated from tools like ChatGPT or Claude, you must provide the URL, author(s), specific prompts/transcripts of AI tool interactions, and any other details necessary to reproduce the use of these outside sources.
However, we strongly encourage not relying on these tools in the first place, as you will likely struggle in other aspects of the course.
You may discuss assignments with classmates and instructors while you are working on them, and you may facilitate these discussions with whiteboards/blackboards (not screens). However, you may not come away from those discussions with notes or submit any code/responses written by your classmates. You must also document the names of all instructors and classmates with whom you discussed the assignment.
Recordings and remote attendance
By default, the class meetings will be in person, and we make no guarantee about any lecture material being recorded (in video, written note form, or otherwise). You are expected to take your own notes in class and attend lecture. If you miss a lecture, you do not need to inform the instructor, but you are responsible for catching up with what you missed e.g. by asking a classmate for their notes. (If the class supports video recording, we may be able to provide this, but again, we do not make this guarantee.)
If you know in advance that you must miss a lecture but can attend remotely, let the instructor know. We make no guarantees about supporting remote attendance, but we will do our best if the situation warrants it (e.g., you are sick.) Please do not come to class in person if you are sick; we will accommodate you.
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.
Disability accommodation
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.
home