McMaster University
Programming Languages

CAS 706 — Fall 2010

Lecture Notes

14 September:

• What is a programming language?
  • A language (has syntax)
  • A language used to ``tell the computer what to do''
  • Needs an implementation concept (semantics)
  • Typicallly expressive power theoretically equivalent to that of a Turing machine is expected.
• What defines a programming language?
  • Syntax
  • Semantics
  • Pragmatics
• What is a formal language?
• What is a grammar?

16 September:

• History and Paradigms
• Haskell: First Introduction

21 September: Chomsky Hierarchy of Formal Languages

• Wikipedia: Formal Grammar
• Wikipedia: Chomsky Hierarchy
• Wikipedia: Parsing, Wikipedia: GLR parser
• Attribute Grammars
  • Wikipedia
  • Computing Surveys paper by Jukka Paakki
  • Why Attribute Grammars Matter
  • UUAGC is the Utrecht University Attribute Grammar Compiler
• Additional pointers for those interested:
  • Wikipedia: Parsing Expression Grammar, Packrat Parsing
  • Wikipedia: Boolean Grammars
  • TATA: Tree Automata Techniques and Applications

23 September: Haskell: Types and Type Classes

• Type synonyms
• newtype
• Type classes and instances
  • Prelude type classes Eq, Show
  • deriving
• data
  • infix data constructors
• Show instances using show
  • “Beginner-friendly”
  • No interface for conditional parenthesisation — would require separate definition.
  • String result type with inefficient concatenation (++)
  • show for recursive datatypes, defined this way, can have quadratic complexity.
• Show instances using showsPrec
  • Additional precedence argument for minimal parenthesisation
  • ShowS result type with efficient concatenation (.)
  • show defined properly via showsPrec has linear complexity.

5 October

• Literate Programming
  • The original ``Literate Programming'' paper
  • Wikipedia: Literate Programming
  • Useful quotes and links: literateprogramming.com
  • Book: Donald Knuth: Literate Programming, Thode: QA 76.6 .K644 1992
  • An annotated bibliography of literate programming
  • CWeb
  • FunnelWeb
  • Noweb (LyX has Noweb support)
• λ-Calculus
  • Untyped λ-calculus: variable binding, free variables, substitution, α-conversion, α-equivalence, β-reduction, η-reduction
    • Barendregt, Barendsen 2000: Introduction to Lambda Calculus

7 October

• Untyped λ-calculus continued
  • Congruences of λ-expressions: α-equivalence, β-equality, β-η-equality
  • Reduction is non-deterministic and can be non-terminating
  • Abstract syntax trees of λ-expressions; reduction strategies
• Rewriting Theory
  • Normal forms, termination
  • Confluence, local confluence, diamond property, Church-Rosser
  • Wikipedia: Abstract Rewriting Systems (also covered on the Rewriting page)
• Term Rewriting and Pattern Matching
  • Term rewriting systems, term rewriting rule application
  • Pattern-matching Haskell function definitions as term rewriting rules
  • Haskell case-expressions as internalised (“nameless”) pattern matching
  • Wikipedia: Term Rewriting

12 October

• Semantics: Overview
• Operational Semantics: Natural (big-step) semantics
• Read: SwA Chapters 1 & 2

14 October — Operational Semantics: Natural (big-step) semantics

• Properties of natural (big-step) semantics
• Haskell implementation of the natural semantics definition of the While language
• Read: SwA Chapters 1 & 2

19 October — Operational Semantics

• Structural Operational Semantics (SOS) — small-step
• Equivalence of small-step and big-step semantics for the While language
• Extending the language: abort
• Extending the language: or (non-determinism)
• Read: SwA Chapters 1–3

21 October — Operational Semantics: Extensions

• Small-step versus big-step semantics — recapitulation
• Extending the language: par (concurrent composition)
• Extending the language: begin ... end (blocks)
• Extending the language: proc, call (procedures)
• Read: SwA Chapter 3