Compiling Functional Languages


OVERVIEW

This is a course in study period 4 2010/11 aimed at Master level and doctoral students who are interested in learning more about techniques for compiling functional languages like Haskell, F# and Erlang. It is intended as a specialization on top of a Compiler Construction course like TDA282 or DIT300; i.e., a broad understanding of how an imperative language is translated into machine code will be assumed. Course focus will be on analysis and transformation techniques applicable after parsing but before low-level machine code generation, such as optimization by source-to-source translation and type inference. To abstract away from platform details, a subset of C will be used as a compilation target throughout the course.


CONTENTS

Abstract syntax representation of functional languages, desugaring, compilation of pattern-matching, Hindley-Milner type inference, translation of Haskell-style overloading, optimizing transformations, C representation of data and functions, efficient memory management, implementing partial application, lazy evaluation.


ORGANIZATION

Seven lectures comprising the core of the course topics (three lectures each of week 12 and 15, one lecture week 19). A lab project to be carried out individually, consisting of a common core plus elective add-on assignments. One or two research paper presentations by each student in week 19, depending on enrollment.


LECTURE SLIDES


Lecture 1
Source-to-source transformations Monday March 21 1500-1700
D&IT room 6128
Lecture 2
C representation Wednesday March 23 1000-1200
D&IT room 3320
Lecture 3
Memory management
Friday March 25 1000-1200
D&IT room 3320
Lecture 4
Type inference
Tuesday April 12 1000-1200
D&IT room 3364 (Edit room)
Lecture 5
Haskell-style overloading
Wednesday April 13 1000-1200
D&IT room 3320
Lecture 6
Type-based optimization
Thursday April 14 1300-1500
D&IT room 3320
Lecture 7
Lazy evaluation
Friday May 13 0800-1000
D&IT room 3320


SEMINAR SCHEDULE


Presentations by Claudio, Willard, Niklas
Tuesday May 10 0800-1000
D&IT room 3320 (4128 2nd hour)
Presentations by Nico, Adam, Daniel & Olle F
Wednesday May 11 1000-1200
D&IT room 3320
Presentations by Olle B, Jonas & Simon & Arnar
Thursday May 12 0800-1000
D&IT room 3320
Presentation by Anders (as an initial part of the lecture)
Friday May 13 0800 - 1000
D&IT room 3320

LITERATURE

Parts of the course will be covered by

The Implementation of Functional Programming Languages
Simon Peyton Jones
Prentice Hall, 1987.

Parts I and II are still highly relevant reading, with the possible exception of sections 11.4 - 11.6, chapter 12 and chapter 16.

Research papers (for presentation during week 19, or simply for additional info):

Paper
Picked by
Let-floating: moving bindings to give faster programs. SL Peyton Jones, WD Partain and A Santos. ICFP, 1996. Claudio
Compiling Haskell by Program Transformation: A Report from the Trenches. Simon Peyton Jones. ESOP, 1996. Willard
Compiling pattern matching. Lennart Augustsson. FPCA, 1985.
Pattern Guards and Transformational Patterns. Martin Erwig and Simon Petyon Jones. Haskell Workshop 2000. Niklas
Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-machine. Simon Peyton Jones. JFP, 1993. Arnar
How to make a fast curry: push/enter vs eval/apply. Simon Marlow & Simon Peyton Jones. ICFP, 2004. Nico
Typed closure conversion. Yasuhiko Minamide, Greg Morrisett and Robert Harper. POPL, 1996.
A Type-Preserving Closure Conversion in Haskell. Louis-Julien Guillemette Stefan Monnier. Haskell workshop, 2007. Adam
Efficient and safe-for-space closure conversion. Zhong Shao and Andrew W. Appel. TOPLAS, 2000.
Unrestricted Pure Call-By-Value Recursion. Johan Nordlander, Magnus Carlsson and Andy Gill. ML workshop, 2008. Daniel
Compilation of extended recursion in call-by-value functional languages. Tom Hirschowitz, Xavier Leroy, and J. B. Wells. HOSC, 2009.
Unboxed objects and polymorphic typing. Xavier Leroy. POPL, 1992.
A concurrent, generational garbage collector for a multithreaded implementation of ML. Damien Doligez and Xavier Leroy. POPL, 1993.
Exploring the Barrier to Entry: Incremental Generational Garbage Collection for Haskell. A. Cheadle, T. Field, S. Marlow, S. Peyton Jones, and L. While. ISMM, 2004
Principal type-schemes for functional programs. Luis Damas and Robin Milner. POPL, 1982.
Typing Haskell in Haskell. Mark Jones. Haskell Workshop, 1999.
Heuristics for type error discovery and recovery. Jurriaan Hage and Bastiaan Heeren. IFL, 2006.
A system of constructor classes: overloading and implicit higher-order polymorphism. Mark Jones. FPCA, 1993. Simon
Implementing Haskell overloading. Lennart Augustsson. FPCA, 1993.
Type classes: exploring the design space. Simon Peyton Jones, Mark Jones, Erik Meijer. Haskell Workshop, 1997.
Simplifying and Improving Qualified Types. Mark P. Jones. FPCA, 1995.
Language and Program Design for Functional Dependencies. Mark P. Jones and Iavor Diatchki. Haskell symposium, 2008.
Putting type annotations to work. Konstantin Läufer and Martin Odersky.
A type system for bounded space and functional in-place update. Martin Hofmann. Nordic Journal of Computing, 2000. Olle F
Secrets of the Glasgow Haskell Compiler inliner. Simon Peyton Jones and Simon Marlow. JFP, 2002.
Positive Supercompilation for a Higher Order Call-By-Value Language. Peter A. Jonsson and Johan Nordlander. LMCS, 2010.
Partial Vectorisation of Haskell Programs. Manuel M. T. Chakravarty, Roman Leshchinskiy, Simon Peyton Jones, and Gabriele Keller. DAMP, 2008.
Harnessing the Multicores: Nested Data Parallelism in Haskell. Simon Peyton Jones, Roman Leshchinskiy, Gabriele Keller, and Manuel M. T. Chakravarty. FSTTCS, 2008. Olle B
Region-Based Memory Management. Mads Tofte and Jean-Pierre Talpin. Information and Computation, 1997.
Associated types with class. M. Chakravarty, G. Keller, S. Peyton Jones, S. Marlow. POPL, 2005.
Jonas
Types Are Calling Conventions. S. Peyton Jones, M. Bollingbroke. Haskell symposium, 2009.
Anders
Strictness analysis on non-flat domains. Philip Wadler. Chapter in Abstract interpretation, 1987.

...
Your suggestions!


EXAMINATION

Oral lab project demonstration together with a written lab report. Successful presentation of assigned research papers as well as participation in all scheduled presentations as announced mid-course.


LECTURER

Johan Nordlander <johan "dot" nordlander "at" ltu "dot" se>