Organization of Programming Languages

Date	Topic	Do	Read	Note
Jan 16	MLK Jr Day			No class
Jan 18	What are Programming Languages?		CIPL, Ch. 1 OpSem, Ch. 1
Jan 20	What Can a Computer Do?	Begin: Assgn. 1	CIPL, Ch. 2
Jan 23	Induction Primer		PLLC, Ch. 2 OpSem, Ch. 2
Jan 25	Syntax & Grammars		CIPL, Ch. 4.1 OpSem, Ch. 3
Jan 27	Big-Step Operational Semantics		OpSem, Ch. 4
Jan 30	Small-Step Operational Semantics	Due: Assgn. 1	OpSem, Ch. 5
Feb 1	Putting Evaluation into Context	Begin: Assgn. 2	OpSem, Ch. 5
Feb 3	Alpha, Beta, Eta		CIPL, Ch. 4.2
Feb 6	A Variable by Any Other Name	Due: Assgn. 2	CIPL, Ch. 4.2
Feb 8	Lambda Calculus in Small Steps	Begin: Assgn. 3	PLLC, Ch 4.1&4.2
Feb 10	Lambda Calculus in Big Steps		PLLC, Ch 4.1&4.2
Feb 13	Intro to Ruby	Due: Assgn. 3	Intro to Ruby Why's, Ch. 3	Notes Script
Feb 15	Classes & Objects	Begin: Assgn. 4	CIPL, Ch 10 Prog. Ruby, Classes	Notes Script
Feb 17	Compositional Interpreters			Notes Script
Feb 20	President's Day			No class
Feb 21	List Processing	Due: Assgn. 4	CIPL, Ch 3&4.4	Notes Script
Feb 22	Higher-Order Functions	Begin: Assgn. 5	CIPL, Ch 3&4.4	Notes Script
Feb 24	Algebraic Data Types		CIPL, Ch 5	Notes Script
Feb 27	Syntactic Interpreters	Due: Assgn. 5		Notes Script
Mar 1	The Extensibility Matrix	Begin: Assgn. 6		Notes Script
Mar 3	MIDTERM EXAM
Mar 6	Spring Break			No class
Mar 8	Spring Break			No class
Mar 10	Spring Break			No class
Mar 13	The Rules of Types	Due: Assgn. 6	CIPL, Ch 6 Static Semantics
Mar 15	Abstraction & Polymorphism	Begin: Assgn. 7	CIPL, Ch 6
Mar 17	Type Checking & Inference	Extra Credit: E.C. 1	CIPL, Ch 6	Notes Script
Mar 20	Variable Binding	Due: Assgn. 7	CIPL, Ch 7
Mar 22	Static & Dynamic Scope	Begin: Assgn. 8	CIPL, Ch 7
Mar 24	Implementing Recursion		CIPL, Ch 7
Mar 27	Abstract Machines	Due: Assgn. 8	CIPL, Ch 8
Mar 29	Closures	Begin: Assgn. 9	CIPL, Ch 8
Mar 31	Stacks & Machines		CIPL, Ch 8
Apr 3	Guest Lecture: Prof. Harper	Due: Assgn. 9
Apr 5	Type Theory & Safety	Begin: Assgn. 10
Apr 7	Variable Lookup	Extra Credit: E.C. 2	CIPL, Ch 8
Apr 10	No Class
Apr 12	Effective Machines		CIPL, Ch 8	Notes Script
Apr 14	Programming with Continuations		CIPL, Ch 15	Notes Script
Apr 17	Continuation Passing Style	Due: Assgn. 10		Notes Script
Apr 19	Metaprogramming			Notes Script
Apr 21	The Paradox of Computation
Apr 24	Logic Programming		CIPL, Ch 15	Notes Script
Apr 26	Concurrent Programming		CIPL, Ch 14 LYSE	Notes Script
Apr 28	Final Review	Due: Paper
May 1	Final Submission Cutoff	Due: Everything
May 1 - May 5	FINAL EXAM	Due: Assgn. 10

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