Madhavan Mukund

Implementation of Functional Programmming Languages

Jan–Apr, 2016

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

• TBA

Lecture summaries

• Lecture 1, 6 January 2016

  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, 11 January 2016

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

  SLPJ book, 2.4-2.5

• Lecture 3, 13 January 2016

  Enriched lambda calculus: let and letrec, translating definitions and expressions from functional language to lambda calculus

  Patterns: translating function definitions for structured types, pattern-matching lambda abstractions

  SLPJ book, 3.1-3.6, 4.1-4.3 (parts)

• Lecture 4, 18 January 2016

  Patterns: translating function definitions for structured types, pattern-matching lambda abstractions

  SLPJ book, 4.1-4.3

• Lecture 5, 20 January 2016

  Patterns: lazy pattern-matching for product constructors

  Efficient compilation of pattern-matching: Case expressions, the function "match"

  SLPJ book, 4.3-4.4, 5.1, 5.2.1-5.2.5

• Lecture 6, 25 January 2016

  Efficient compilation of pattern-matching: Case expressions, the function "match", variable rule, constructor rule, mixture rule

  SLPJ book, 5.2

• Lecture 7, 27 January 2016

  Efficient compilation of pattern-matching: Optimizations

  SLPJ book, 5.4

• Lecture 8, 1 February 2016

  Transforming the enriched lambda calculus: Transforming pattern-matching lambda abstractions, transforming let and letrec

  SLPJ book, 6.1-6.2

• Lecture 9, 3 February 2016

  Transforming the enriched lambda calculus: Transforming let and letrec, transforming case expressions, fatbar and FAIL

  SLPJ book, 6.2-6.4