Organization of Programming Languages

Date	Topic	Do	Read	Note
Jul 6	What are Programming Languages?		CIPL, Ch. 1 OpSem, Ch. 1
Jul 6	What Can a Computer Do?	Begin: Assgn. 1	CIPL, Ch. 2
Jul 7	Induction Primer		PLLC, Ch. 2 OpSem, Ch. 2
Jul 7	Syntax & Grammars		CIPL, Ch. 4.1 OpSem, Ch. 3
Jul 11	Big-Step Operational Semantics	Due: Assgn. 1	OpSem, Ch. 4
Jul 11	Small-Step Operational Semantics	Begin: Assgn. 2	OpSem, Ch. 5
Jul 13	Alpha, Beta, Eta		CIPL, Ch. 4.2
Jul 13	Lambda Calculus in Small Steps	Begin: Assgn. 3	PLLC, Ch 4.1&4.2
Jul 14	Lambda Calculus in Big Steps	Due: Assgn. 2	PLLC, Ch 4.1&4.2
Jul 18	Intro to Ruby	Due: Assgn. 3	Intro to Ruby Why's, Ch. 3	Notes Script
Jul 18	Classes & Objects	Begin: Assgn. 4	CIPL, Ch 10 Prog. Ruby, Classes	Notes Script
Jul 20	Compositional Interpreters			Notes Script
Jul 21	Higher-Order Functions	Due: Assgn. 4 Begin: Assgn. 5	CIPL, Ch 3&4.4	Notes Script
Jul 25	Algebraic Data Types		CIPL, Ch 5	Notes Script
Jul 27	MIDTERM EXAM
Jul 28	Syntactic Interpreters	Due: Assgn. 5		Notes Script
Jul 28	The Extensibility Matrix	Begin: Assgn. 6		Notes Script
Aug 1	The Rules of Types	Due: Assgn. 6	CIPL, Ch 6 Static Semantics
Aug 1	Abstraction & Polymorphism	Begin: Assgn. 7	CIPL, Ch 6
Aug 3	Type Checking & Inference	Extra Credit: E.C. 1	CIPL, Ch 6	Notes Script
Aug 4	Variable Binding	Due: Assgn. 7	CIPL, Ch 7
Aug 4	Static & Dynamic Scope	Begin: Assgn. 8	CIPL, Ch 7
Aug 8	Implementing Recursion	Due: Assgn. 8	CIPL, Ch 7
Aug 8	Abstract Machines	Begin: Assgn. 9	CIPL, Ch 8
Aug 10	Closures		CIPL, Ch 8
Aug 10	Mutable State	Begin: Assgn. 10	CIPL, Ch 8
Aug 10	Handling Exceptions	Extra Credit: E.C. 2	CIPL, Ch 8
Aug 11	Continuations in Machines	Due: Assgn. 9
Aug 11	Programming With Continuations			Notes Script
Aug 11	Continuation-Passing Style			Notes Script
Aug 15	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: July 11

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: July 13

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: July 18

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: July 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: July 28

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: August 1

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: August 4
    Assignment 8 DUE: August 8
  • 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: August 10

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: August 15

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