Web Home

ea

Contents

Implementing lazy evaluated languages efficiently on current hardware is no easy task; simple and elegant implementation models exist but are slow, and building implementations that run as fast as their imperative, strictly evaluated counterparts is still not possible.

In this seminar we will study, by reading papers together and discussing them, how functional languages are currently implemented, and how program analysis and program transformation may result in faster implementations.

Literature

Papers from the open literature, see CourseLiterature.

Specific material for 2006:

• A description to install EHC and the tools it requires on your system. (updated)
• An overview of the EHC Architecture
• Comments on GHC implementation

Course Form

Seminar in which we jointly read papers. Depending on the number of participants we will hand out separate subjects for which you will have to prepare a presentatation. In order to give the work a concrete basis we will try to study areas as much as possible in the context of the current implementation of the Utrecht Haskell Compiler and EHC.

Planning

Monday 12 Nov 2007: Introduction. We'll start reading

• (PJ92): Simon Peyton Jones, "Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine", JFL 2 (1992)
• (MPJ06): Simon Marlow and Simon Peyton Jones, "Making a fast curry: push/enter vs. eval/apply for higher-order languages", JFL 16 (2006).

Wednesday 14 Nov 2007:

• Read PJ92 sec 1-3
• Read MPJ06 sec 1-3

Monday 19 Nov 2007 (15.15-17.00 in room BBL-471):

• Read PJ92 sec 4: Haskell to STG translation
• Read MPJ06 sec 4: operational semantics
• Skim PJ92 sec 5: operational semantics
• Skim MPJ06 sec 5: implement push/enter
• Read MPJ06 sec 6: implement eval/apply

Wednesday 21 Nov 2007:

• Read PJ92 sec 6-8: jumps in C, heap layout,
• Skim PJ92 sec 9: compilation to C
• Read MPJ06 sec 7-8: results
• Puzzle: where in the GHC source is the stgApplyNP function? (hint: spelled stg_ap_)

Monday 26 Nov 2007: We'll start reading (Boq99) Urban Boquist, "Code Optimisation Techniques for Lazy Functional Languages", 1999. At the same time, we'll study the implementation in EHC.

• Read Boq99 chapter 1 (skip sec 1.3) (=16 pages)
• Read Boq99 chapter 2 (=37 pages)
• View EHC/src/ehc/GrinCode/AbsSyn.cag

Wednesday 28 Nov 2007

• Read Boq99 chapter 3 (=13 pages)
• View EHC/src/grinc/GrinCode/PointsToAnalysis.cag and /src/grinc/HeapPointsToFixpoint.cag which may be easiest to read in this document, sec 4.1-4.3

Monday 3 Dec 2007

• Read Boq99 chapter 4 section 4.1 and 4.2 (=35 pages)
• View EHC/src/grinc/GrinCode/Trf/*.cag

Wednesday 5 Dec 2007

• Read Boq99 chapter 4 section 4.3.1 to 4.3.9 (=23 pages)

Monday 10 Dec 2007

• Read (MRPJ) Marlow, Rodrigues, Peyton Jones, Dynamic Pointer Tagging, ICFP 2007

Wednesday 12 Dec 2007

• Read Boq99 chapter 4 section 4.3.10 to 4.3.16 and 4.4 (=27 pages)

Monday 17 Dec 2007

• Read (GR07) Andy Gill and Colin Runciman, "Haskell Program Coverage", Haskell Workshop 2007

Wednesday 19 Dec 2007

• Read (PJM02) Peyton Jones and Marlow, "Secrets of the Glasgow Haskell Compiler inliner", JFL 2002

Monday 7 Jan 2008

• First session in the new year

Intriguing questions:

• In MPJ06 figure 2, if rule PAP2 recorded the arity of f, PCALL would know the arity of g. Does ghc do this?

Assignment

Projects from 2008:

• HPC Profiling project
• Intermediate Language
• Optimizing Case UBS project

Projects from 2004:

• EHC to GHC core project/assignment
• EHC to Clean core project/assignment
• Meiage project/assignment
• LVM implemented in Java project/assignment

-- JeroenFokker - 4 Dec 2007