Organization of Programming Languages

Date	Topic	Do	Read	Note
Sep 2	Convocation			No class
Sep 4	What Can a Computer Do?		CIPL, Ch. 1 & 2 OpSem, Ch. 1
Sep 9	Induction Primer		PLLC, Ch. 2 OpSem, Ch. 2
Sep 11	Syntax & Grammars		CIPL, Ch. 4.1 OpSem, Ch. 3
Sep 16	Big-Step Operational Semantics	Due: Assgn. 0	OpSem, Ch. 4
Sep 18	Small-Step Operational Semantics		OpSem, Ch. 5
Sep 23	Alpha, Beta, Eta	Due: Assgn. 1	CIPL, Ch. 4.2
Sep 25	Lambda Calculus in Small Steps		PLLC, Ch 4.1&4.2
Sep 30	Lambda Calculus in Big Steps	Due: Assgn. 2	PLLC, Ch 4.1&4.2
Oct 2	Intro to Ruby: Classes & Objects		CIPL, Ch 10 Intro to Ruby Prog. Ruby, Classes Why's, Ch. 3	Notes Script 1 Notes Script 2
Oct 7	Compositional Interpreters	Due: Assgn. 3		Notes Script
Oct 9	List Processing		CIPL, Ch 3&4.4	Notes Script
Oct 14	Higher-Order Functions	Due: Assgn. 4	CIPL, Ch 3&4.4	Notes Script
Oct 16	MIDTERM EXAM
Oct 21	Algebraic Data Types		CIPL, Ch 5	Notes Script
Oct 23	Syntactic Interpreters			Notes Script
Oct 28	The Extensibility Matrix	Due: Assgn. 5		Notes Script
Oct 30	The Rules of Types		CIPL, Ch 6 Static Semantics
Nov 4	Subtyping & Polymorphism	Due: Assgn. 6	CIPL, Ch 6
Nov 6	Type Checking & Inference	Extra Credit: E.C. 1	CIPL, Ch 6	Notes Script
Nov 11	Veteran's Day	Due: Assgn. 7		No class
Nov 13	Static & Dynamic Scope		CIPL, Ch 7
Nov 18	Abstract Machines	Due: Assgn. 8	CIPL, Ch 8
Nov 20	Closures & Stacks		CIPL, Ch 8
Nov 25	Effective Machines	Due: Assgn. 9	CIPL, Ch 8
Nov 27	Thanksgiving			No class
Dec 2	Continuations & Control	Extra Credit: E.C. 2	CIPL, Ch 8	Notes Script 1 Notes Script 2
Dec 4	The Paradox of Computation			Notes Script 1 Notes Script 2
Dec 9	Logic Programming	Due: Assgn. 10	CIPL, Ch 15	Notes Script
Dec 11	Concurrent Programming	Due: Paper	CIPL, Ch 14 LYSE	Notes Script
Dec 15	Final Submission Cutoff	Due: Everything
Dec 15-19	FINAL EXAM

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

  • Concepts in Programming Languages, Chapters 1 & 2
  • Operational Semantics, Chapter 1

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

  • Concepts in Programming Languages, Chapter 4.1
  • Programming Languages and Lambda Calculi, Chapter 2
  • Operational Semantics, Chapters 2 & 3

• • 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

  • Operational Semantics, Chapters 4 & 5

• • 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

  • Concepts in Programming Languages, Chapter 4.2
  • Programming Languages and Lambda Calculi, Chapters 4.1 & 4.2

• • 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

  • Tour of Ruby (interactive Ruby script)
  • Classes & Objects (interactive Ruby script)
  • Compositional Interpreters (interactive Ruby script)

• • Reading

  • Concepts in Programming Languages, Chapter 10
  • Try Ruby in your browser
  • Quick Introduction to Ruby
  • Why's (Poignant) Guide to Ruby, Chapter 3
  • Programming Ruby: Classes, Objects, and Variables

• • Software

  • The Ruby programming language

• • 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

  • Higher-Order Functions (interactive Scheme script)
  • Algebraic Data Types (interactive SML code)

• • Reading

  • Concepts in Programming Languages, Chapters 3, 4.4, & 5

• • 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

  • Syntactic Interpreter (in Standard ML)
  • Extensibility Matrix of Syntax and Interpreters (interactive Ruby script)

• • Exercises

  • Assignment 6 DUE: March 13

Type Systems

• • Concepts

  • The Rules of Types
  • Generic Polymorphism
  • Subtyping
  • Type Checking & Inference
  • Type Safety

• • Notes

  • Simple Type Checker (in Ruby)

• • Reading

  • Concepts in Programming Languages, Chapter 6
  • Notes on Static Semantics (a.k.a Type Systems)
  • Practical Foundations for Programming Languages, Chapters 2 & 4

• • Exercises

  • Assignment 7 DUE: March 20
    Assignment 8 DUE: March 27
  • Extra Credit 1 DUE: Final Submission Cutoff

Binding & Scope

• • Concepts

  • Variable Binding
  • Static and Dynamic Scope
  • Implementing Recursion

• • Reading

  • Concepts in Programming Languages, Chapter 7

• • 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

  • Concepts in Programming Languages, Chapter 8

• • Exercises

  • Assignment 10 DUE: April 17

Continuations: Capturing the Future

• • Concepts

  • Continuations in Machines
  • Programming with Continuations
  • Continuation-Passing Style

• • Notes

  • Programming With Continuations (in Ruby)
  • Continuation-Passing Style (in Ruby)

• • Exercises

  • Extra Credit 2 DUE: Final Submission Cutoff