Organization of Programming Languages

Date	Topic	Do	Read	Note
Jan 19	What are Programming Languages?		CIPL, Ch. 1 OpSem, Ch. 1	Online lecture
Jan 21	What Can a Computer Do?		CIPL, Ch. 2	Online lecture
Jan 24	Induction Primer	Begin: Assgn. 1	PLLC, Ch. 2 OpSem, Ch. 2
Jan 26	Syntax & Grammars		CIPL, Ch. 4.1 OpSem, Ch. 3
Jan 28	Big-Step Operational Semantics	Due: Assgn. 1 Begin: Assgn. 2	OpSem, Ch. 4
Jan 31	Small-Step Operational Semantics		OpSem, Ch. 5
Feb 2	Alpha, Beta, Eta	Due: Assgn. 2	CIPL, Ch. 4.2
Feb 4	Lambda Calculus in Small Steps	Begin: Assgn. 3	PLLC, Ch 4.1&4.2
Feb 7	Lambda Calculus in Big Steps		PLLC, Ch 4.1&4.2
Feb 9	Intro to Ruby	Due: Assgn. 3	Intro to Ruby Why's, Ch. 3	Notes Script
Feb 11	Classes & Objects	Begin: Assgn. 4	CIPL, Ch 10 Prog. Ruby, Classes	Notes Script
Feb 14	Compositional Interpreters			Notes Script
Feb 16	Higher-Order Functions	Due: Assgn. 4 Begin: Assgn. 5	CIPL, Ch 3&4.4
Feb 18	Algebraic Data Types		CIPL, Ch 5
Feb 21	Holiday - No Class
Feb 22	Midterm Review	Due: Assgn. 5		Online lecture
Feb 23	Midterm Review
Feb 25	MIDTERM EXAM			Snow day
Feb 28	MIDTERM EXAM
Mar 2	Syntactic Interpreters	Begin: Assgn. 6		Notes Script
Mar 4	The Extensibility Matrix			Notes Script
Mar 7	Spring Break
Mar 9	Spring Break
Mar 11	Spring Break
Mar 14	The Rules of Types	Begin: Paper	CIPL, Ch 6 Static Semantics
Mar 16	Abstraction & Polymorphism	Due: Assgn. 6	CIPL, Ch 6
Mar 18	Type Checking & Inference	Begin: Assgn. 7	CIPL, Ch 6
Mar 21	Type Checking & Inference		CIPL, Ch 6	Notes Script
Mar 23	Type Safety	Due: Assgn. 7	PFPL, Ch 2 & 4
Mar 25	Variable Binding	Begin: Assgn. 8	CIPL, Ch 7
Mar 27	Static & Dynamic Scope	Extra Credit: E.C. 1	CIPL, Ch 7
Mar 30	Implementing Recursion	Due: Assgn. 8	CIPL, Ch 7
Apr 1	Abstract Machines	Begin: Assgn. 9	CIPL, Ch 8
Apr 4	Closures		CIPL, Ch 8
Apr 6	Mutable State	Due: Assgn. 9	CIPL, Ch 8
Apr 8	Handling Exceptions	Begin: Assgn. 10	CIPL, Ch 8
Apr 11	Continuations in Machines
Apr 13	Programming With Continuations			Notes Script
Apr 15	Continuation-Passing Style	Extra Credit: E.C. 2		Notes Script
Apr 18	Holiday - No Class
Apr 20	Logic Programming	Due: Assgn. 10	CIPL, Ch 15	Notes Script
Apr 22	Concurrent Programming		CIPL, Ch 14 LYSE	Notes Script
Apr 25	Metaprogramming			Notes Script
Apr 27	The Paradox of Computation	Due: Paper		Notes Script
Apr 29	Final Review	Due: All Extra Credit
	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 31

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 2

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 9

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 16

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

• • Exercises

  • Assignment 5 DUE: February 22

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 16

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 8 DUE: March 30
  • Extra Credit 1 DUE: Last Day of Class

Binding & Scope

• • Concepts

  • Variable Binding
  • Static and Dynamic Scope
  • Implementing Recursion

• • Reading

  • Concepts in Programming Languages, Chapter 7

• • Exercises

  • Assignment 9 DUE: April 6

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 20

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: Last Day of Class

Other Programming Paradigms

• • Concepts

  • Logic Programming: proof search, Prolog
  • Concurrent Programming: actor model, Erlang

• • Notes

  • Logic Programming (in Prolog)
  • Concurrent Programming (in Erlang)

• • Reading

  • Concepts in Programming Languages, Chapters 14 & 15
  • Prolog (Basics)
  • Learn You Some Erlang

Programs About Programs

• • Concepts

  • Metaprogramming
  • The Paradox of Computation

• • Notes

  • Functions = Data (in Ruby)
  • The Paradox of Computation (in Ruby)