CS 456: Programming Languages

LWSN B134 12:00-13:15 TTh

about

Instructor:

Ben Delaware

bendy at purdue.edu

Office Hours: Tuesday 3:30-5:00, LWSN 2116M

Teaching Assistant:

Shivaram Gopal

gopals at purdue.edu

Office Hours: Monday+Wednesday 4:00-5:00, HAAS 264

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 modularity. Work in the course involves exploring programming languages and features both as a user (by writing programs in those languages), as a language designer (by implementing interpreters for those languages), and as a scholar (by proving mathematical properties of them). We will investigate approaches to modularity such as data abstraction, inheritance, and polymorphism independent of their realization in any particular language. The course will also offer a 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 efficient and correct programs in a functional programming language, Haskell.
  2. Precisely formulate the syntax and runtime behavior of a programming language.
  3. Specify different notions of type safety for a programming language and reason about a programming language's semantics via mathematical induction.
  4. Distinguish between different approaches to modularity and abstraction provided by programming languages.

The course is structured into five sections, the first four of which roughly align with these topics. The final section will consider the realization of some of these ideas in Rust, a modern systems programming language.

resources

Course Text:

Types and Programming Languages . Benjamin Pierce.

Learn You a Haskell for Great Good! . Miran Lipovaca.

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 Coq 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 40%
Midterm: March 6th (Tentative) 20%
Final: May 1st 30%
Participation 10%

Homework Submission:

Homeworks are to be submitted via turnin by 9PM on their assigned due date. You receive two courtesy late days for the semester. Once you have used both those days, any late homeworks will not be accepted. While students can discuss assignments at a high-level, each student should produce the solutions they submit individually. A more detailed discussion of academic honesty can be found here.

schedule

Note: This schedule is preliminary; it will likely change over the course of the semester to adapt to reality.

Date Topic Notes / Homework
01/09 Introduction
Functional Programming in Haskell
01/11 Basic Data Structures
01/16 Inductive Data Structures
01/18 Recursion + Higher Order Functions
01/23 Polymorphism + Type Classes Homework 1 (Due 2/2)
01/25 Embedded Domain Specific Languages
01/30 Purity + Reasoning about Programs Equationally
02/01 Free Theorems and Haskell Revue Theorems for Free!
Dynamic Semantics
02/06 Concrete and Abstract Syntax; Binding scope Homework 2 (Due 2/16)
02/08 Operational Semantics
02/13 Evaluation Strategies
02/15 Imperative Languages; Monads
02/20 Cultural Enrichment: Equational Reasoning in Coq
02/22 Monads, continued
02/27 Non-local control flow; Deliminted Continuations Go-to statement
considered harmful
03/01 Meta-Programming via Partial Evaluation
03/06 Reasoning about programs inductively;
Midterm Review
03/08 Midterm
Static Semantics
03/13 Spring Break!!
03/15 Spring Break!!
03/20 Basic Type Checking and Type Inference
03/22 Language Metatheory: Proving Type Safety
03/27 Polymorphic Type Systems
Modularity and Abstraction
03/29 Data Abstraction: Interfaces and Implementation
04/03 Abstract Data Types; Representation Invariants
04/05 Representation Independence
04/10 Objects vs. ADTs On Understanding
Data Abstraction,
Revisited
04/12 Inheritance + Behavioral Subtyping
Putting It All Together: Rust
04/17 Traits
04/19 Memory Safety, Linear and Affine Types
04/24 Putting it all together: a look at Rust
04/26 Course Wrap-up