CAS CS 320
Concepts of Programming Languages

Links
Schedule (Compact)
Calendar
Course Staff
Schedule (Full)

CS320 is a course about programming languages: their design and implementation. We take up the programming language as an object of formal study.

Schedule (Compact)

Date	Topic	Notes
09-02	Lab 0: Installation Party	Read the course manual
09-03	Introducing OCaml	A1 out
09-08	Recursion and Lists
09-09	Lab 1: Practice, Practice, Practice
09-10	Designing Functions (Workshop)	A2 out, A1 due
09-15	Polymorphism
09-16	Quiz 1	Last day to add or change to audit
09-17	Products, Sums, Algebraic Data Types	A3 out, A2 due
09-22	Inference Rules
09-23	Lab 2: Calculator
09-24	Derivations	A4 out, A3 due
09-29	Higher-Order Programming
09-30	Quiz 2
10-01	Practical Functional Programming (Workshop)	A5 out, A4 due
10-06	Formal Grammar
10-07	Lab 3: Writing Tests	Last day to drop without a "W"
10-08	Basic Parsing	A5 due
10-13	No Lecture	Substitute Monday
10-14	Midterm Review
10-15	Midterm 1	A6 out
10-20	Operational Semantics
10-21	Lab 4: S-Expressions
10-22	Substitution (Workshop)	A7 out, A6 due
10-27	Simple Types
10-28	Quiz 3
10-29	Progress and Preservation	A8 out, A7 due
11-03	Environment-based Semantics
11-04	Quiz 4
11-05	Closures	A8 due
11-06		Last day to drop w/ "W" or designate P/F
11-10	Pattern Matching
11-11	Midterm Review
11-12	Midterm 2	A9 out
11-17	Type Inference
11-18	Lab 5
11-19	Unification (Workshop)	FP out, A9 due
11-24	Principal Types and Specialization
11-25	No Lab	Thanksgiving Recess
11-26	No Lecture	Thanksgiving Recess
12-01	Designing Rules
12-02	Quiz 5
12-03	A Case Study (Workshop)	FP Check-in due
12-08	Advanced Topic
12-09	Final Exam Review
12-10	Advanced Topic	FP due
12-17	Final Exam	3:00PM–5:00PM

Calendar

Course Staff

Instructors: Ankush Das and Nathan Mull
Teaching Fellow: Jared Pincus
Teaching Assistant: Vivian Tvedt

Do not contact course staff directly except in extenuating circumstances. If you have course-related questions/concerns, post on Piazza.

Schedule (Full)

09-02 WED (Lab 0)

Week: 1
Title: Installation Party
Reading:
- Lab 0: Installation Party
Topics:
- Github
- Opam and Dune
Learning Objectives:
- Create a private mirror of our course repository where you'll put solutions to assignments
- Verify that you have everything you'll need for labs and assignments installed on your machine

09-03 THU (Lecture)

Week: 1
Title: Introducing OCaml
Reading:
- Required:
  - Course Manual
  - Lecture Notes (LN) 1: Introduction
  - OCaml Programming (OP) 1: Better Programming Through OCaml
  - OP 2: The Basics of OCaml
- Optional:
  - Wallace Stevens: Disillusionment of Ten O'Clock
Topics:
- syntax, typing and semantics
- OCaml
- expressions and evaluation
- literals, let-expressions, if-expressions, functions and applications
Learning Objectives:
- Determine what the course is about (i.e., what is a programming language?)
- Start getting comfortable with OCaml
Notes:
- assignment 1 released

09-08 TUE (Lecture)

Week: 2
Title: Recursion and Lists
Reading:
- Required:
  - OP 2: The Basics of OCaml
  - OP 3.1: Lists
  - OP 3.6: Type Synonyms
- Optional:
  - Structural Geology 1: Introduction
Topics:
- more on expressions
- lists and pattern matching
- tail recursion
Learning Objectives:
- Start working with lists
- Determine the point of tail recursion
- Do many examples with lists

09-09 WED (Lab 1)

Week: 2
Title: Practice, Practice, Practice
Topics:
Learning Objectives:

09-10 THU (Workshop)

Week: 2
Title: Designing Functions
Reading:
- Required:
  - How to Design Programs: Systematic Program Design
- Optional:
  - Edsger W. Dijkstra: Why American Computing Science seems incurable
Topics:
- writing algorithms in OCaml
Learning Objectives:
- Practice, practice, practice OCaml
- Try to simulate "normal" programming reasoning in OCaml
Notes:
- assignment 2 released
- assignment 1 due

09-15 TUE (Lecture)

Week: 3
Title: Polymorphism
Reading:
- Required:
  - OP 3.2: Variants
  - OP 3.4: Records and Tuples
  - OP 3.8: Association Lists
- Optional:
  - George Saunders: She Who Helps See
Topics:
- parametric polymorphism vs. ad hoc polymorphism
- type parameters and type inference
Learning Objectives:
- Begin to get a sense of how to use parametric polymorphism to write general code
- Begin to get a sense of what restricts the type of an expression, i.e., when a function can and cannot be polymorphic (you should over time be able to determine the type of a small expression by reading it)

09-16 WED (Quiz 1)

Week: 3
Topics:

09-17 THU (Lecture)

Week: 3
Title: Products, Sums, Algebraic Data Types
Reading:
- Required:
  - OP 3.5: Advanced Pattern Matching
  - OP 3.7: Options
  - OP 3.9: Algebraic Data Types
  - OP 3.11: Example: Trees
  - OP 3.12: Example: Natural Numbers
- Optional:
  - Rebecca Burditt: Sweet Ruin: Cakes and the Visual Culture of Anxiety, 1945–1960
Topics:
- tuples and records
- algebraic data types
- constructors/variants
- designing expressive types
- general pattern matching
Learning Objectives:
- See how to organize data for a given programming task
- Learn to use pattern matching to design basic recursive functions
- Start thinking about data-driven programming
Notes:
- assignment 3 released
- assignment 2 due

09-22 TUE (Lecture)

Week: 4
Title: Inference Rules
Reading:
- Required:
  - LN 2.1: Inference Rules
- Optional:
  - Graham Priest: A Note on the Sorites Paradox
Topics:
- inference systems
- typing and semantic judgments
- variable declarations and contexts
Learning Objectives:
- Learn to read and write typing/semantic judgments
- See how inference rules can help us formally specify programming languages

09-23 WED (Lab 2)

Week: 4
Title: Calculator
Topics:
Learning Objectives:

09-24 THU (Lecture)

Week: 4
Title: Derivations
Reading:
- Required:
  - LN 2.2: Derivations
  - LN 2.3: Extended Example: RPN Calculator
- Optional:
  - John Berryman: Dream Song 14
Topics:
- metavariables in inference rules
- constructing derivations
Learning Objectives:
- Learn to build a derivation of a judgment within an inference system (and also understand what this establishes)
- Learn to translate formal derivation trees into English proof, and vice versa
- Work through a number of examples
Notes:
- assignment 4 released
- assignment 3 due

09-29 TUE (Lecture)

Week: 5
Title: Higher-Order Programming
Reading:
- Required:
  - OP 4: Higher-Order Programming
- Optional:
  - D. B. Newell et. al: The CODATA 2017 values of \(h\), \(e\), \(k\), and \(N_A\) for the revision of the SI
Topics:
- abstraction principle
- maps, filters, and folds
- higher-order programming and tail recursion
Learning Objectives:
- See how to use higher-order programming to further generalize code
- Learn to do basic "iterative" reasoning with folds

09-30 WED (Quiz 2)

Week: 5
Topics:

10-01 THU (Workshop)

Week: 5
Title: Practical Functional Programming
Reading:
- Required:
  - OP 3.3: Unit Testing with OUnit
  - OP 3.10: Exceptions
  - OP 4.6: Pipelining
  - OP 5.2: Modules
  - OP 5.4: Encapsulation
  - OP 5.6: Functional Data Structures
- Optional:
  - Mary Shelley: Frankenstein; or, the Modern Prometheus (letters)
Topics:
- OUnit
- exceptions
- modules
- "actual" OCaml programming
Learning Objectives:
- Get accustomed to a hodge-podge of topics that don't fit exactly into our schedule but are good to have seen
Notes:
- assignment 5 released
- assignment 4 due

10-06 TUE (Lecture)

Week: 6
Title: Formal Grammar
Reading:
- Required:
  - LN 3.(1-3): Formal Grammar
- Optional:
  - Mary Shelley: Frankenstein; or, the Modern Prometheus (ch. 1-5)
Topics:
- Backus-Naur Form (BNF)
- production rules
- derivations and parse trees
Learning Objectives:
- Begin to recognize if a sentence is recognized by a grammar
- Learn to draw parse trees for a sentence recognized by a grammar

10-07 WED (Lab 3)

Week: 6
Title: Writing Tests
Learning Objectives:
- Get some practice with OUnit so that you're prepared to write your own tests

10-08 THU (Lecture)

Week: 6
Title: Basic Parsing
Reading:
- Required:
  - LN 3.(4-6): Formal Grammar
  - OP 10.2: Parsing
- Optional:
  - Mary Shelley: Frankenstein; or, the Modern Prometheus (ch. 6-10)
Topics:
- grammatical ambiguity
- lexical analysis
Learning Objectives:
- Get a sense of what makes lexing and parsing challenging
- Get just enough background to build basic parsers we'll use for the remainder of the semester
Notes:
- assignment 5 due

10-14 WED (Midterm Review)

Week: 7

10-15 THU (Midterm 1)

Week: 7
Topics:
Notes:
- assignment 6 released

10-20 TUE (Lecture)

Week: 8
Title: Operational Semantics
Reading:
- Required:
- Optional:
  - Mary Shelley: Frankenstein; or, the Modern Prometheus (ch. 11-15)
Topics:
- small-step vs. big-step semantics
- evaluation strategies/orders
- semantic derivations
Learning Objectives:
- Review how to read and write semantic inference rules
- Review how to write semantic derivations, this time for small-step semantics
- Learn how formal semantics corresponds with evaluation in an interpreter

10-21 WED (Lab 4)

Week: 8
Title: S-Expressions
Learning Objectives:
- Build an S-expression parser that you can use for future assignments

10-22 THU (Lecture)

Week: 8
Title: Substitution
Reading:
- Required:
  - OP 10.3: Substitution Model
- Optional:
  - Mary Shelley: Frankenstein; or, the Modern Prometheus (ch. 16-20)
Topics:
- λ-calculus
- call-by-name vs. call-by-value
- capture-avoiding substitution
Learning Objectives:
- Discuss in detail substitution semantics for the (untyped) λ-calculus
- Understand the benefits and downsides to CBN and CBV evaluation strategies
Notes:
- assignment 7 released
- assignment 6 due

10-27 TUE (Lecture)

Week: 9
Title: Simple Types
Reading:
- Required:
  - OCP 10.5: Type Checking
- Optional:
  - Mary Shelley: Frankenstein; or, the Modern Prometheus (ch. 21-24)
Topics:
- simply typed lambda calculus
- type uniqueness
Learning Objectives:
- Discuss type systems in general
- Discuss the trade-offs of typed vs. untyped PLs
- Introduce the notation of type safety
- See more typing derivation examples

10-28 WED (Quiz 3)

Week: 9
Topics:

10-29 THU (Lecture)

Week: 9
Title: Progress and Preservation
Reading:
- Required:
  - LN A: Trees
- Optional:
  - Adriana Craciun: Writing the Disaster: Franklin and Frankenstein
Topics:
- structural induction
- induction over derivations
- substitution lemma
Learning Objectives:
- Learn how to prove things about PLs
- Demonstrate the type safety of STLC
Notes:
- assignment 8 released
- assignment 7 due

11-03 TUE (Lecture)

Week: 10
Title: Environment-based Semantics
Reading:
- Required:
  - OCP 10.4: Environment Model
- Optional:
  - Edwin Abbott Abbott: Flatland: A Romance of Many Dimensions (§1-7)
Topics:
- lexical vs. dynamic scoping
- environments and closures
Learning Objectives:
- See how to make our interpreter implementations more efficient by avoiding unnecessary substitutions and storing bindings in an environment

11-04 WED (Quiz 4)

Week: 10
Topics:

11-05 THU (Lecture)

Week: 10
Title: Closures
Reading:
- Required:
  - OCP 10.4: Environment Model
- Optional:
  - Edwin Abbott Abbott: Flatland: A Romance of Many Dimensions (§8-14)
Topics:
- named closures and recursion
Learning Objectives:
- Discuss how to deal with recursion when working with closures
Notes:
- assignment 8 due

11-10 TUE (Lecture)

Week: 11
Title: Pattern Matching
Reading:
- Required:
- Optional:
  - Edwin Abbott Abbott: Flatland: A Romance of Many Dimensions (§15-22)
Topics:
- patterns and match expressions
- shallow vs. deep pattern matching
Learning Objectives:
- Formally describe how pattern matching works

11-11 WED (Midterm Review)

Week: 11
Topics:

11-12 THU (Midterm 2)

Week: 11
Topics:
Notes:
- assignment 9 released

11-17 TUE (Lecture)

Week: 12
Title: Type Inference
Reading:
- Required:
  - OCP 10.6: Type Inference
- Optional:
  - Justin Prystash: Reality Games: Modeling the Universe in Dimensional Fiction
Topics:
- type parameters and quantification
- monotypes, polytypes, type schemes
- constraint-based inference
- Hindley-Milner type inference
Learning Objectives:
- Get a sense of how OCaml "actually" determines the type of an expression

11-18 WED (Lab 5)

Week: 11
Title:
Topics:

11-19 THU (Lecture)

Week: 12
Title: Unification
Reading:
- Required:
  - OCP 10.6: Type Inference
- Optional:
  - Samuel Beckett: Waiting for Godot (act I)
Topics:
- type unification
- unification constraints
- most general unifiers
Learning Objectives:
- Learn an algorithm for unifying a collection of type constraints generated by constraint-based inference
- Practice unifying type constraints
Notes:
- final project released
- assignment 9 due

11-24 TUE (Lecture)

Week: 13
Title: Principal Types
Reading:
- Required:
  - OCP 10.6: Type Inference
- Optional:
  - Samuel Beckett: Waiting for Godot (act II)
Topics:
- principal types
- generalization
Learning Objectives:
- Understand why we make the principal type of an expression the "most general" type it can have

12-01 TUE (Lecture)

Week: 14
Title: Designing Rules
Reading:
- Required:
- Optional:
  - Martin Esslin: The Theater of the Absurd
Topics:
Learning Objectives:

12-02 WED (Quiz 5)

Week: 14

12-03 THU (Lecture)

Week: 14
Title: A Case Study
Reading:
- Required:
- Optional:
  - The geologic history of the Moon 1: General Features
Topics:
Learning Objectives:
Notes:
- final project check-in due

12-08 TUE (Lecture)

Week: 15
Title: Advanced Topic
Reading:
- Required:
- Optional:
  - Juan Rulfo: They Have Given Us The Land
Topics:
Learning Objectives:

12-09 WED (Final Exam Review)

Week: 15

12-10 THU (Lecture)

Week: 15
Title: Advanced Topic
Reading:
- Required:
- Optional:
  - Odilon Redon: Beatrice
Topics:
Learning Objectives:
Notes:
- final project due

12-17 THU (Final Exam)

Week: 16
Topics:

CAS CS 320 Concepts of Programming Languages

Table of Contents

Links