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.
Papers from the open literature, see CourseLiterature
Specific material for 2006:
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
Monday 12 Nov 2007:
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
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
Wednesday 19 Dec 2007
Monday 7 Jan 2008
- First session in the new year
- In MPJ06 figure 2, if rule PAP2 recorded the arity of f, PCALL would know the arity of g. Does ghc do this?
Projects from 2008:
Projects from 2004:
- 4 Dec 2007