Syllabus

Welcome to the Fall 2024 offering of CS4400/5400: Programming Languages! Please read this syllabus in its entirety.

1. Syllabus
2. Logistics
3. Course overview
   1. Module 1: Introduction
   2. Module 2: The $\lambda$-calculus
   3. Module 3: Types
   4. Module 4: Control
   5. Module 5: Topics
4. Reference materials
5. Coursework and Grading Policy
   1. Late-work policy
   2. Grading Thresholds
6. Academic Honesty
   1. Usage of code generation tools
7. Remote policy
8. General resources
   1. Disability Resource Center
   2. Title IX Notice

Logistics

• Instructor: Steven Holtzen s.holtzen@northeastern.edu. When emailing Steven or any of the TAs about course content, please include CS4400 somewhere in the subject of your email.
• Teaching Assistants:
  • Vadym Matviichuk. Email: matviichuk.v@northeastern.edu
  • Brianna Marshall. Email: marshall.br@northeastern.edu
  • Abdelrahman Madkour. Email: madkour.a@northeastern.edu
• Course time: Monday/Wednesday 2:50PM – 4:30PM
• Course location: Robinson Hall 109
• 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.
• 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.

Course overview

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 $\lambda$-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 $\lambda$-calculus, and become familiar with programming in it: we will see how to compile programs into the $\lambda$-calculus (Church encoding), how to program with recursion (Y-combinator), and how to implement the $\lambda$-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 $\lambda$-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: we will add mutable state, recursion, sums, and products. Then, we will add polymorphism and modules. With these features, we will have implemented a simplified version of the ML programming language.

Module 4: Control

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: Topics

Now we will reap the benefits of our strong foundations in programming languages by quickly exploring some advanced, modern, and/or emerging trends in programming languages. This module is subject to change based on available time and/or interest. Possible topics include macros, laziness, effects, probabilistic programming, and dependent types.

Reference materials

The primary reference for this course will be the instructor’s course notes, provided after each lecture and available on this website. The following textbooks are good additional resources and will be occasionally referenced in class:

• 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.

If you have not programmed in Racket before, we recommend the following resources:

• How To Design Programs, Second Edition
• The Racket Guide

Coursework and Grading Policy

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 (55% Of Total): Roughly weekly. Posted on this webpage, turned in on Gradescope. You may discuss the problems with other students, but you must submit your own solutions.
• Module quizzes (45% of total): One after each module. These will cover content from the module (non-cumulative), will be take-home and given 24 hours. Quizzes 1, 2, and 3 are each worth 10% of this total. Quiz 4 is cumulative, and will be worth 15% of this total.

Some assignments, quizzes, and sub-problems will be marked as 5400 problems. These problems are designated for students enrolled in CS5400. Students enrolled in CS5400 are required to complete these exercises. They will not be graded for students enrolled in CS4400.

Late-work policy

All course 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 email the instructor in advance of the deadline.

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
$\ge$90	A-
$\ge$87	B+
$\ge$83	B
$\ge$80	B-
$\ge$77	C+
$\ge$73	C
$\ge$70	C-
$\ge$67	D+
$\ge$63	D
$\ge$60	D-
<60	F

The instructor reserves the right to curve up based on course circumstances.

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 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 will get out of the class what you put in: if you are simply copy and pasting code from ChatGPT, you will not learn very much. I strongly encourage you to first attempt all assignments yourself, without any assistance. Ask the TAs, Piazza, or your classmates for help if you are stuck; you are paying money for access to our outstanding TAs, and they want to help you.

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.

General resources

Disability Resource Center

Students who have disabilities who wish to receive academic services and/or accommodations should visit the Disability Resource Center at 20 Dodge Hall or call (617) 373-2675. Please be sure to provide your instructor with DRC’s accommodations letter early in the semester in order to avoid logistical challenges. As-per the DRC’s policy, it is the student’s responsibility to coordinate with the instructor in order to provide suitable accommodations.

Title IX Notice

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 students, faculty and staff of all gender identities.

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.

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 and the Center for Spiritual Dialogue and Service clergy members. 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 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.

In case of an emergency, please call 911.

Please visit here for a complete list of reporting options and resources both on- and off-campus.