Madhavan Mukund



Implementation of Functional Programmming Languages,
Jan-Apr 2016

Implementation of Functional Programmming Languages

Jan–Apr, 2016


Administrative details

  • Instructors:

    • Madhavan Mukund

    • S P Suresh

  • Evaluation:

    • TBA

    • Copying is fatal.

  • Textbook:


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