CS 456: Programming Languages
|
about
Instructor:
bendy at purdue.edu
Office Hours: Tuesdays 3:30-5:00 in LWSN 2116M
Teaching Assistant:
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:
- Write programs in two languages with
state-of-the-art type systems, Rust and
Haskell.
- Compare and contrast different
language-provided abstractions, including
ad-hoc and parametric polymorphism,
user-defined data types, and static and
dynamic memory safety.
- Precisely formulate the syntax and runtime
behavior of a programming language.
- 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:
- Programming in an imperative language, e.g. Java / C / Python, etc.
- 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.
- 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) |
|
|
|