CS 456: Programming Languages

MTHW 304 13:30-14:45 TTh

about

Instructor:

Ben Delaware

bendy at purdue.edu

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

Teaching Assistant:

Pedro Abreu

pdacost at purdue.edu

Office Hours: Wednesdays 4:00-5:30 in HAAS 175

A Proviso:

This website is only meant to provide an overview of this course. In the interest of giving students a unified dashboard for all their classes, we will be using Brightspace as the definitive repository for course content including lectures, homeworks, and announcements.

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.

logistics

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

Lectures:

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 3:30-5:00p in LWSN 2116M, and the TA will hold office hours in HAAS G050 each Wednesday 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:

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.

success

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.

resources

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 piazza 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 piazza so that any other students with the same question can see the answer.

policies

Grading:

Final grades will be assigned according to the following breakdown:

Homework Assignments 60%
Midterm: October 14 (Tentative) 10%
Final: TBD 20%
Participation 10%

(tentative) schedule

Date Topic Notes Homework
08/24 Course Introduction + Haskell Hello HW1 assigned
08/26 Algebraic Data Types
08/31 Recursive Functions + Interpreters
09/02 First-Class Functions
09/07 Untyped Lambda Calculus + Operational Semantics
09/09 Parametric Polymorphism (Generics) HW1 due (09/10)
09/14 Ad-Hoc Polymorphism (Typeclasses) HW2 assigned
09/16 Embedded DSLS
09/21 Type Systems + Type Safety
09/23 Type Inference HW2 Due (9/24)
09/28 Let Polymorphism
09/30 System F
10/05 Demo Day: Prolog (Logic Programming)
10/07 Haskell AMA / Midterm Review HW3 Due (10/08)
10/12 October Break
10/14 Midterm
10/19 Monads or
Who left state in my functional language!?
HW4 Assigned
10/21 Demo Day: Liquid Haskell (Refinement Types)
10/26 Intro to Rust or
Who left functional concepts in my systems language!?
10/28 Memory Mangagement + Ownership HW4 Due (10/29)
11/02 References + Borrowing HW5 Assigned
11/04 Semantics of State
11/09 Affine + Linear Types HW5 Due (11/13)
11/11 Interfaces in Rust (Traits) HW6 Due (11/23)
11/16 Data Abstraction HW6 Assigned
11/23 Subtyping HW6 Due (11/23)
11/25 Thanksgiving Break
11/30 Advanced Topics (e.g. Curry Howard, Dependent Types, Coq) HW7 Assigned
12/07 Future or Programming Languages
Course Wrapup
HW7 Due (12/10)