COMP3610: Principles of Programming Languages
Lectures

Principal Lecturer: Dr. Clem Baker-Finch

Lecture Notes

There will be a two 1-hour lectures each week. The following syllabus is indicative. Changes are possible as the course progresses.

• Introduction
• Functional Programming in Haskell (Review)
• Lambda Calculus
• Fixpoint Theory of Recursive Function Definitions
• Syntax, Parsing & Translation
• Semantics of Programming Languages
• Unifying Examples

• Introduction
  • Notes: [pdf] [pdf 2×2]
  • Whitespace
  • Shakespeare
  • LOLCODE
  • Intercal
• Functional Programming in Haskell
  • Reading: the misleadingly titled A Gentle Introduction to Haskell
  • If you prefer to have the whole document: [ps] [ps × 2]
  • An exercise in program derivation
    • The Countdown Problem
    • Lecture slides [pdf] [pdf 2 × 2]
    • Scripts: [countdown.hs] [countdown2.hs]
  • Lecture slides:
    • Lazy Evaluation [pdf] [pdf 2 × 2]
  • Extra backgorund material (Haskell slides from 2005):
    • Haskell data structures
      • Reading: A Gentle Introduction to Haskell Sect.2
      • Notes: [pdf] [pdf 2 × 2]
    • The Haskell type system
      • Reading: A Gentle Introduction to Haskell Sect.2, Sect.5, Sect.8
      • Notes: [pdf] [pdf 2 × 2]
    • Higher-order functions
      • Reading: A Gentle Introduction to Haskell Sect.3, Sect.4
      • Notes:[pdf] [pdf 2 × 2]
    • Patterns of recursion: fold
      • Notes: [pdf] [pdf 2 × 2]
    • IO in a pure functional setting
      • Reading: A Gentle Introduction to Haskell Sect.7
      • Notes: [pdf] [pdf 2 × 2]
• Lambda calculus
  • Notes: [pdf] (updated 8 Aug)
  • Tool: Lambda Calculus Workbench
• Syntax, Parsing and Translation 1: Top-Down
  • Notes: [pdf]
  • Scripts: [ParseTypeDefs.hs] [Imp parser, scanner & interpreter]
• Fixpoint Theory of Recursive Function Definitions
  • Notes: [pdf]
  • Scripts:
    • [Fix.hs] [pdf]
    • [FixNewton.hs] [pdf]
• Syntax, Parsing and Translation 2: Bottom-Up
  • Notes: [pdf]
• Semantics of Programming Languages
  • Notes: [pdf] Section 3.3: Semantic Congruence is not examinable. Section 3.5: Continuations and control will not be examined in 2007.
  • Scripts: [Imp parser, scanner & interpreter]
• Unifying Examples This section will not be examined in 2007.
  • Abstract interpretation
    • Notes: [pdf] [pdf 2×2]
    • Scripts: [Sign1.lhs] [Sign2.lhs] [Sign3.lhs]
  • Strictness analysis
    • Notes: [pdf] [pdf 2×2]
    • Scripts: [Fun parser, interpreter and analyser]