CS 456: Programming Languages

GRIS 133 12:00-1:15 TTh



Ben Delaware

bendy at purdue.edu

Office Hours: Tuesdays 2:00-3:30p in LWSN 2116M

Teaching Assistant:

Patrick La Fontaine

plafonta at purdue.edu

Office Hours: Thursdays 11:00a-12:00n in HAAS 143 and 5:00p-6:00p HAAS G50

Course Description:

This is a course on the principles of programming languages and their application. The emphasis is on ideas and techniques relevant to practitioners, but includes theoretical foundations crucial for deeper understanding: abstract syntax, formal semantics, type systems, and abstraction. Work in the course involves exploring programming languages and features as both a user (by writing programs in those languages) and a language designer (by implementing interpreters for various languages), and as a scholar (by proving mathematical properties of them). We will investigate language-based techniques for analyzing program behavior, and discuss what guarantees a programming language can provide its users about the abstractions it provides. The course will also offer some historical perspective on the evolution of programming languages and why some designs thrive while others fail. Upon successfully completing this course, students will be able to:

  1. Write programs in two languages with state-of-the-art type systems, Rust and Haskell.
  2. Compare and contrast different language-provided abstractions, including ad-hoc and parametric polymorphism, user-defined data types, and static and dynamic memory safety.
  3. Precisely formulate the syntax and runtime behavior of a programming language.
  4. Specify different notions of safety for a programming language and employ language-based techniques to ensure the safety of programs.

The first half of the course will discuss these topics in the context of the (mostly) pure functional language, Haskell, while the second half will use the modern systems language Rust.


A Proviso:

The information on this webpage reflects the current plan for the course, and its format may be changed to adapt to pandemic-related developments.


Barring any pandemic-related craziness, we will have in-person lectures Tuesdays and Thursdays, which students are expected to attend. If you are sick or otherwise unable to attend a lecture, please let the instructor know as soon as possible. We are planning to use Boilercast to record lectures, and to make these videos available on Brightspace.

Office Hours:

Each Tuesday, the instructor will have office hours from 2:00-3:30p in LWSN 2116M, and the TA will hold office hours somewhere (TBD) each Thursday from 4:00-5:30. In the event that students cannot attend scheduled office hours, they should contact the instructor via email to schedule a time to meet individually.


Homeworks will be posted (roughly) every other week according to the course schedule. Homeworks are to be submitted via Brightspace by 6PM on their assigned due date. Make sure that any programs compile without errors (and ideally without any warnings). If they do not, they will not be graded. Everyone will receive three courtesy late days for the semester. Once all these days have been used, students will need to notify the instructor or the TA ahead of time with an explanation and plan for completion. These requests will be accepted at my discretion and may include a point penalty of 5% per day late. Asking for an extension does not guarantee it will be granted.

Course Project:

This course project asks students to either implement a suggested projects in either Rust or Haskell, or to propose and implement a project of their choosing. Projects can be completed either individually or in groups of two. As these projects are less structured than the homeworks, there will be three milestones to help keep you on track. A list of project ideas and a timeline will be posted on Brightspace.


How to Succeed in this Course

In order to be successful, students should be familiar with:

  1. Programming in an imperative language, e.g. Java / C / Python, etc.
  2. Basic logic and proofs techniques found in an undergraduate discrete math course like CS182: sets, relations, functions, proof by induction, proof by case analysis; recursion; and propositional logic.
  3. The sorts of basic data structures and algorithms encountered in an undergraduate course like CS 251, e.g. lists, trees, heaps, graphs, sorting, graph traversals, and search.

We'll briefly review important concepts as needed, but this will be a refresher and not an introduction.

In this course, we will be programming in both Rust and Haskell. As an upper-level undergraduate course, some assignments may be slightly underspecified; you may need to proactively ask questions to clarify your understanding. You are expected to test your programs before submitting, and you should ensure that every program you submit compiles without errors.


Course Texts:

Our resource for learning Haskell will be the e-book Learn You a Haskell for Great Good! by Miran Lipovaca; for learning Rust we will use The Rust Programming Language by Steve Klabnik and Carol Nichols. The (optional) textbook Types and Programming Languages by Benjamin Pierce has an excellent in-depth treatment of semantics and type system; the Software Foundations series has a similar presentation of many of those topics using a proof assistant.

Discussion Forum:

The course Ed Discussion site will serve as the discussion board; all course announcements will also be posted there. In lieu of emailing the instructor or the TA with any general questions about using Haskell / Rust or assignments, please post them to the discussion board so that any other students with the same question can see the answer.



Final grades will be assigned according to the following breakdown:

Homework Assignments 45%
Project 20%
Midterm: October 13 (Tentative) 10%
Final: TBD 15%
Participation 10%

(tentative) schedule

Date Topic Notes Homework
08/23 Course Introduction + Haskell Hello HW1 assigned
08/25 Algebraic Datatypes
08/30 Inductive Datatypes + Recursive Functions
09/01 Property-Based Testing
09/06 First-Class Functions
09/08 Untyped Lambda Calculus + Operational Semantics HW1 due (09/09)
09/13 Parametric Polymorphism HW2 assigned
09/15 Ad-Hoc Polymorphism (Typeclasses)
09/20 Embedded DSLS
09/22 Type Systems + Type Safety HW2 Due (9/24)
09/27 The Simply Typed Lambda Calculus HW3 Assigned
09/29 Type Inference
10/4 Let Polymorphism + System F
10/06 Midterm Review HW3 Due (10/07)
10/11 October Break
10/13 Midterm
10/18 Monads or
Who left state in my functional language!?
HW4 Assigned
10/20 Demo Day: Liquid Haskell (Refinement Types)
10/25 Intro to Rust
Who left functional concepts in my systems language!?
10/27 Who left functional concepts in my systems language!? HW4 Due (10/28)
11/01 Memory Mangagement + Ownership HW5 Assigned
11/03 References + Borrowing
11/08 Semantics of State
11/10 Affine + Linear Types
11/15 Data Abstraction
11/17 Subtyping HW5 Due (11/18)
11/22 Subtyping
11/24 Thanksgiving Break
11/29 Advanced Topics (e.g. Curry Howard, Dependent Types, Coq)
12/6 Project Presentations
Course Wrapup