Madhavan Mukund

Implementation of Functional Programmming Languages

Jan–Apr, 2017

Administrative details

• Instructors:

  • Madhavan Mukund

  • S P Suresh

• Evaluation:

  • TBA

  • Copying is fatal.

• Textbook:

  • The Implementation of Functional Programming Languages
    Simon L. Peyton Jones
    Prentice-Hall (1987)
    Read online, Download djvu, Download pdf.

Course plan

We will cover as much of the SLPJ book as we can. The tentative plan is to address the following topics:

• lambda calculus (Chapter 2),
• translating a high-level functional language into the lambda calculus (Chapters 3, 6),
• pattern matching (Chapters 4, 5),
• list comprehensions (Chapter 7),
• polymorphic type-checking (Chapters 8, 9),
• graph reduction (Chapters 10, 11 and 12),
• super combinators (Chapters 13, 14),
• G-machine (Chapters 18, 19, 20).

Assignments

Lecture summaries

• Lecture 1, 3 January 2017 (SPS)

  Lambda calculus: basic syntax, adding built-in functions and constants, lambda abstractions, beta reduction, currying, bound and free variables, beta/alpha/eta conversion, name capture, normal order reduction, optimal reduction orders

  SLPJ book, 2.1-2.3

• Lecture 2, 5 January 2017 (SPS)

  Lambda calculus: recursive functions and the Y operator, denotational semantics, strict and lazy functions

  SLPJ book, 2.4-2.5

• Lecture 3, 10 January 2017 (SPS)

  Enriched lambda calculus: let and letrec, translating definitions and expressions from functional language to enriched lambda calculus, TE and TD translation schemes

  SLPJ book, 3.1-3.5

• Lecture 4, 12 January 2017 (SPS)

  Patterns: translating function definitions for structured types, pattern-matching lambda abstractions, multiple equations and failure, multiple arguments

  SLPJ book, 4.1, 4.2.1-4.2.6

• Lecture 5, 17 January 2017 (SPS)

  Patterns: translating function definitions for structured types, conditional equations, repeated variables, where clauses, patterns on lhs of definitions

  Lazy pattern-matching for product constructors

  SLPJ book, 4.2.6-4.2.10, 4.3

• Lecture 6, 19 January 2017 (SPS)

  Efficient compilation of pattern matching Case expressions & compiling to case expressions. The match function: variable rule and the constructor rule.

  SLPJ book, 5.1, 5.2.1-5.2.5