Tests
| Date | Exam |
|---|---|
| Oct 15 | Midterm Exam |
| Final Exam |
Homework
| Due | Assignment |
|---|---|
| Sep 10 | Assignment 0 |
Lectures
| Date | Topic | Do | Read | Note |
|---|---|---|---|---|
| Sep 1 | What Is a Programming Language? |
CIPL, Ch. 1 & 2
OpSem, Ch. 1 |
||
| Sep 3 | What Can a Computer Do? |
CIPL, Ch. 1 & 2
OpSem, Ch. 1 |
||
| Sep 8 | Induction Primer |
PLLC, Ch. 2
OpSem, Ch. 2 |
||
| Sep 10 | Syntax & Grammars | Due: Assgn. 0 |
CIPL, Ch. 4.1
OpSem, Ch. 3 |
|
| Sep 15 | Big-Step Operational Semantics | OpSem, Ch. 4 | ||
| Sep 17 | Small-Step Operational Semantics | Due: Assgn. 1 | OpSem, Ch. 5 | |
| Sep 22 | Alpha, Beta, Eta | CIPL, Ch. 4.2 | ||
| Sep 24 | Lambda Calculus in Small Steps | Due: Assgn. 2 | PLLC, Ch 4.1&4.2 | |
| Sep 29 | Lambda Calculus in Big Steps | PLLC, Ch 4.1&4.2 | ||
| Oct 1 | Intro to Ruby: Classes & Objects | Due: Assgn. 3 |
CIPL, Ch 10
Intro to Ruby Prog. Ruby, Classes Why's, Ch. 3 |
Notes Script 1
Notes Script 2 |
| Oct 6 | Compositional Interpreters | Notes Script | ||
| Oct 8 | Functional Programming | Due: Assgn. 4 | CIPL, Ch 3&4.4 | Notes Script |
| Monday Schedule | No class | |||
| Oct 15 | MIDTERM EXAM | Study Guide | ||
| Oct 20 | Algebraic Data Types | CIPL, Ch 5 | Notes Script | |
| Oct 22 | Syntactic Interpreters | Due: Assgn. 5 | Notes Script | |
| Oct 27 | The Extensibility Matrix | Notes Script | ||
| Oct 29 | The Rules of Types | Due: Assgn. 6 |
CIPL, Ch 6
Static Semantics |
|
| Nov 3 | Subtyping & Polymorphism | CIPL, Ch 6 | ||
| Nov 5 | Type Checking & Inference | Extra Credit: E.C. 1 | CIPL, Ch 6 | Notes Script |
| Nov 10 | Static & Dynamic Scope | Due: Assgn. 7 | CIPL, Ch 7 | |
| Nov 12 | Abstract Machines | CIPL, Ch 8 | ||
| Nov 17 | Closures & Stacks | Due: Assgn. 8 | CIPL, Ch 8 | |
| Nov 19 |
Logic & Concurrent Programming
|
CIPL, Ch 14
LYSE CIPL, Ch 15 |
Notes Script 1
Notes Script 2 |
|
| Nov 24 | Effective Machines |
Due: Assgn. 9
Extra Credit: E.C. 2 |
CIPL, Ch 8 |
Notes Script 1
Notes Script 2 |
| Thanksgiving | No class | |||
| Dec 1 | The Paradox of Computation |
Notes Script 1
Notes Script 2 |
||
| Dec 3 | Flex day | Due: Assgn. 10 | ||
| Dec 8–10 | Final Review | |||
| Dec 14 | Final Submission Cutoff | Due: Everything | ||
| FINAL EXAM | Study Guide |
Topics
Programming Languages: What, Why, & How?
• Concepts
- What are Programming Languages? syntax vs semantics, interpreters vs compilers, expressive power vs Turing tarpit, safety and security, formal vs informal specifications
- What Can a Computer Do? limits of static analysis, the full employment theorem for compiler writers, the halting problem
-
• Reading
Induction: The Workhorse of Programming Languages
• Concepts
- Induction Primer: inductive sets and trees, proof by induction
- Syntax & Grammars: context-free grammar, BNF, abstract vs concrete syntax trees
-
• Reading
-
• Exercises
- Assignment 1 DUE: January 30
Operational Semantics: Big & Small
• Concepts
- Big-Step Operational Semantics: also known as "natural semantics", evaluation, derivation trees
- Small-Step Operational Semantics: reduction rules, evaluation contexts
-
• Reading
-
• Exercises
- Assignment 2 DUE: February 6
Lambda Calculus: The Laws of Functions
• Concepts
- Alpha, Beta, Eta: syntax of lambda calculus, variable names and alpha-equivalence, substitution and beta-equivalence, extensionality and eta-equivalence
- Lambda Calculus in Small Steps: beta-reduction, call-by-value versus call-by-name, normalization, confluence
- Lambda Calculus in Big Steps: evaluation order, normal forms, weak versus strong evaluation
-
• Reading
-
• Exercises
- Assignment 3 DUE: February 13
Object-Oriented Programming
• Concepts
- Introduction to Ruby: basic Ruby programming, variables and values, function definitions, interactive interpreter
- Classes & Objects: user-defined classes, objects and encapsulation, method calls, dynamic dispatch
- Compositional Interpreters: class-based representation of syntax trees, evaluation and interpretation methods, compositionality
-
• Notes
-
• Reading
-
• Software
-
• Exercises
- Assignment 4 DUE: February 21
Functional Programming
• Concepts
- Higher Order Functions: currying, list-processing functions (map, reduce, etc.)
- Algebraic Data Types: data type representation of syntax trees, pattern matching
-
• Notes
-
• Reading
-
• Software
- The Racket programming language — a dialect of Scheme, in the Lisp family of languages
- Standard ML of New Jersey — a feature-rich implementation of SML
- A list of other implementations of the Standard ML programming language
- An online interpreter for Standard ML you can run in your browser
- Another browser-based Standard ML interpreter
-
• Exercises
- Assignment 5 DUE: February 27
The Expression Problem
• Concepts
- Syntax Interpreter: modeling syntax as an algebraic data type, (mutual) recursion over abstract syntax trees, evaluation
- Visitor Pattern
- The Extensibility Matrix: modeling syntax as symbolic data structures (hash tables, lists), different methods of printing, functional versus object-oriented extensibility
-
• Notes
-
• Exercises
- Assignment 6 DUE: March 13
Type Systems
• Concepts
- The Rules of Types
- Generic Polymorphism
- Subtyping
- Type Checking & Inference
- Type Safety
-
• Notes
-
• Reading
-
• Exercises
-
Assignment 7
DUE: March 20
Assignment 8 DUE: March 27 - Extra Credit 1 DUE: Final Submission Cutoff
-
Assignment 7
DUE: March 20
Binding & Scope
• Concepts
- Variable Binding
- Static and Dynamic Scope
- Implementing Recursion
-
• Reading
-
• Exercises
- Assignment 9 DUE: April 3
Machines & Effects
• Concepts
- Abstract Machines: Efficient Semantics
- Closures: Remember Where You Came From
- Mutable State: Changing the World
- Raising Exceptions: And Handling the Unexpected
-
• Reading
-
• Exercises
- Assignment 10 DUE: April 17
Continuations: Capturing the Future
• Concepts
- Continuations in Machines
- Programming with Continuations
- Continuation-Passing Style
-
• Notes
-
• Exercises
- Extra Credit 2 DUE: Final Submission Cutoff