The GHC reading list

Suppose you want to start contributing to GHC: what should you read by way of background? Here is an annotated list. Please add to it as you come across useful material. When you do so, please consider adding a link to a place where you are reasonably confident the resource will be available in 10 or 20 years. ​doi purports to enable such links.

You can ask questions on ghc-devs@haskell.org. People are friendly. See also working on GHC and The GHC Team.

See also ​Stephen Deihl's Haskell implementation reading list.

General background

• The GHC Commentary is a Wiki that describes GHC's implementation. It is a Wiki. That means that you can, and should, fix errors and write new chapters.

• ​The Glasgow Haskell Compiler, in ​The Architecture of Open Source Applications, Volume II, ed Brown & Wilson. This paper gives an up to date (2012) technical overview of GHC.

• Simon PJ's ​home page and ​publications page have lots of relevant papers. Some key ones appear below but not all.

• Simon PJ's books:
  • ​The Implementation of Functional Programming Languages
  • ​Implementing Functional Languages: a tutorial give useful general background. They are not GHC-specific at all, but they have lots of information about functional-language compilers.

Types and type inference

• ​System FC, as implemented in GHC (2013), Richard Eisenberg.

• ​Modular type inference with local assumptions ​doi link, Simon Peyton Jones, Dimitrios Vytiniotis, Tom Schrijvers, Martin Sulzmann, Journal of Functional Programming, 2011. This epic 83-page JFP paper brings together, in a single uniform framework, a series of our earlier papers on type inference for type systems involving local constraints, including GADTs and indexed type families.

• ​Practical Type Inference for Arbitrary-Rank Types. Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, Mark Shields. JFP '07. ​doi ​technical appendix Describes type inference for higher-rank types.

• ​Papers about type equalities in GHC's intermediate language
  • ​System FC with Explicit Kind Equality. Stephanie Weirich, Justin Hsu, Richard A. Eisenberg. ICFP '13. ​doi Merges types with kinds, allowing promotion of GADTs and type families. Implementation not yet merged (July 2015).
  • Equality proofs and deferred type errors, Simon Peyton Jones, Dimitrios Vytiniotis and Pedro Magalhaes (ICFP 2012). An exploration of what happens when you take equality proofs seriously in a compiler. ​doi ​pdf
  • Giving Haskell a promotion, Brent Yorgey, Stepanie Weirich, Julien Cretin, Simon Peyton Jones, and Dimitrios Vytiniotis (TLDI 2012). How to (a) add kind polymorphism and (b) promote data types to become data kinds. ​doi ​pdf
  • Evidence Normalization in System FC. Dimitrios Vytiniotis, Simon Peyton Jones. RTA '13. ​doi ​pdf Explains the coercion optimizer.
  • System F with Type Equality Coercions, Martin Sulzmann, Manuel Chakravarty, and Simon Peyton Jones (TLDI 2007). The first paper about System FC. ​doi ​extended pdf

• Type families:
  • ​Associated Types with Class. Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, Simon Marlow. POPL '05. ​doi Introduces associated data families.
  • ​Associated Type Synonyms. Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones. ICFP '05. ​doi Introduces associated type families.
  • ​Closed Type Families with Overlapping Equations. Richard A. Eisenberg, Dimitrios Vytiniotis, Simon Peyton Jones, Stephanie Weirich. POPL '14. ​doi ​extended version Introduces closed type families.
  • ​Injective Type Families for Haskell. Jan Stolarek, Simon Peyton Jones, Richard Eisenberg. Haskell '15. ​doi. Introduces injective type families.

• ​Safe Zero-Cost Coercions for Haskell. Joachim Breitner, Richard A. Eisenberg, Simon Peyton Jones, Stephanie Weirich. ICFP '14. ​doi ​extended pdf Introduces the Coercible mechanism.

• ​Partial Type Signatures for Haskell. Thomas Winant, Dominique Devriese, Frank Piessens, Tom Schrijvers. PADL 2014 ​TR ​doi Introduces partial type signatures.

• ​Understanding Functional Dependencies via Constraint Handling Rules. Martin Sulzmann, Gregory J. Duck, Simon Peyton Jones, Peter J. Stuckey. JFP '07. ​doi

• ​Type Classes in Haskell, Cordelia Hall, Kevin Hammond, Simon Peyton Jones, and Philip Wadler, European Symposium On Programming 1994. Type inference for type classes.

• ​Derivable type classes, Ralf Hinze and Simon Peyton Jones; Haskell Workshop 2000.

• ​Once Upon a Polymorphic Type, Keith Wansbrough and Simon Peyton Jones, POPL 1999.

Please add: System FC, GADTs, kind polymorphism etc

Optimisations

• ​A transformation-based optimiser for Haskell, SL Peyton Jones and A Santos, Science of Computer Programming 32(1-3), pp3-47, September 1998. Gives an overview of many of the transformations GHC does on Core. Andre's ​PhD thesis gives more details.

• ​Secrets of the GHC inliner, Simon Peyton Jones and Simon Marlow, Journal of Functional Programming 12(4), July 2002, pp393-434. Describes how the Simplifier does inlining.

• ​A short cut to deforestation, A Gill, SL Peyton Jones, J Launchbury, Proc Functional Programming Languages and Computer Architecture (FPCA'93), Copenhagen, June 1993, pp223-232. The famous foldr/build rule. Andy's ​PhD thesis has more.

• ​Playing by the rules: rewriting as a practical optimisation technique in GHC, Simon Peyton Jones, Andrew Tolmach and Tony Hoare, Haskell Workshop 2001. Describes how RULES work, which are heavily used in GHC.

• ​Call-pattern Specialisation for Haskell Programs, Simon Peyton Jones, ICFP 2007. Describes the specialisation optimiser.

• ​Let-floating: moving bindings to give faster programs, Simon Peyton Jones, Will Partain, and Andre Santos, ICFP 1996. Describes the let floating and full laziness optimisation passes.

• ​Modular, Higher-Order Cardinality Analysis in Theory and Practice, Ilya Sergey, Dimitrios Vytiniotis, Simon Peyton Jones, POPL 2014. Describes cardinality analysis and optimisations that it enables or improves (eg. let-floating).

• ​Constructed Product Result Analysis for Haskell, Clem Baker-Finch, Kevin Glynn, and Simon Peyton Jones, Journal of Functional Programming 14(2), 211–245, March 2004. Describes optimisation that allows to return tuple components in registers (for functions that return tuples).

• ​Demand analysis, Simon Peyton Jones, Peter Sestoft, and John Hughes, draft, 2006.

• ​Arity Analysis, Dana N. Xu and Simon Peyton Jones, Working Notes, 2006

• ​Call Arity, Joachim Breitner, TFP, 2014, as well as ​Formally Proving a Compiler Transformation Safe, Joachim Breitner, Haskell 2015

Data Parallel Haskell and concurrency

• ​Data Parallel Haskell: a status report, Manuel M. T. Chakravarty, Roman Leshchinskiy, Simon Peyton Jones, Gabriele Keller, and Simon Marlow. , DAMP 2007: Workshop on Declarative Aspects of Multicore Programming, 2007

• ​Harnessing the Multicores: Nested Data Parallelism in Haskell, Simon Peyton Jones, Roman Leshchinskiy, Gabriele Keller, and Manuel M. T. Chakravarty , IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008), IBFI, Schloss Dagstuhl, 2008.

• ​Vectorisation Avoidance, Gabriele Keller, Manuel M. T. Chakravarty, Roman Leshchinskiy, Ben Lippmeier, and Simon Peyton Jones, Proceedings of ACM SIGPLAN Haskell Symposium 2012, ACM Press, 2012.

• ​Work Efficient Higher-Order Vectorisation, Ben Lippmeier, Manuel M. T. Chakravarty, Gabriele Keller, Roman Leshchinskiy, and Simon Peyton Jones, The 17th ACM SIGPLAN International Conference on Functional Programming, ACM Press, 2012

• ​Runtime Support for Multicore Haskell (Simon Marlow, Simon Peyton Jones, Satnam Singh) In ICFP '09: Proceeding of the 14th ACM SIGPLAN International Conference on Functional Programming, Edinburgh, Scotland, August 2009

• Concurrent Haskell, Simon Peyton Jones, Andrew Gordon, Sigbjorn Finne. Deals with the various concurrency constructs in GHC and the Haskell language. E.g., MVars.

• ​Composable Memory Transactions, Tim Harris, Simon Marlow, Simon Peyton-Jones, and Maurice Herlihy. In Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP '05)

• ​Transactional Memory with Data Invariants, Tim Harris and Simon Peyton Jones. In TRANSACT '06

Intermediate Representation of GHC (Core & Related)

• An External Representation for the GHC Core Language Gives an overview of the semantics and syntax of Core, GHC's internal intermediate representation for Haskell that most of the optimisation work is done on. A good language to understand when starting with GHC.

• Unboxed Values as First-Class Citizens, Simon L Peyton Jones and John Launchbury, Conference on Functional Programming Languages and Computer Architecture, September 1991. Describe the design of GHC language and internals for handling machine values and boxing / unboxing them as lazy values.

Code generation and virtual machine

• ​How to make a fast curry: push/enter vs eval/apply, Simon Marlow and Simon Peyton Jones, International Conference on Functional Programming, Snowbird, Sept 2004, pp4-15.

• ​Faster laziness using dynamic pointer tagging (Simon Marlow, Alexey Rodriguez Yakushev, Simon Peyton Jones) In ICFP '07: Proceedings of the ACM SIGPLAN international conference on Functional programming, Freiburg, Germany, ACM Press, October 2007

• ​Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine, SL Peyton Jones, Journal of Functional Programming 2(2), Apr 1992, pp127-202. The original STG paper but still highly relevant.

• The STG runtime system (revised), Simon Peyton Jones and Simon Marlow. A highly-detailed description of STG. It is probably the most up-to-date description, aside for later additions from ​dynamic pointer tagging paper and ​fast curry paper.

• ​Hoopl: A Modular, Reusable Library for Dataflow Analysis and Transformation, Norman Ramsey, John Dias, and Simon Peyton Jones. Haskell Symposium 2010

• ​C--: a portable assembly language that supports garbage collection, Simon Peyton Jones, Norman Ramsey, and Fermin Reig. Invited talk at PPDP'99.

• ​A Single Intermediate Language That Supports Multiple Implementations of Exceptions, Norman Ramsey and Simon Peyton Jones, PLDI 2000.

• ​An LLVM Backend for GHC, David Terei and Manuel M. T. Chakravarty. Haskell Symposium 2010

IO and Related

• ​Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell, Simon Peyton Jones. Deals with the incarnation of IO in Haskell and GHC. The history getting to monads, handling exceptions and handling concurrency.

• Imperative Functional Programming, Simon Peyton Jones, Philip Wadler. POPL, Jan 1993, pp71-84. Presents Monads as a way of implementing IO in Haskell.

• Lazy Functional State Threads, John Launchbury and Simon Peyton Jones. PLDI 1993. A follow-up on "Imperative Functional Programming" paper.

• ​Asynchronous Exceptions in Haskell, Simon Marlow, Simon Peyton Jones, Andrew Moran and John Reppy, 2006.

• A semantics for imprecise exceptions, Simon Peyton Jones, Alastair Reid, Tony Hoare and Simon Marlow, PLDI '99.

• ​Imprecise Exceptions, Co-Inductively, Andy Moran, Soeren Lassen, and Simon Peyton Jones, HOOTS'99.

The run-time system, garbage collector, profiling, FFI

• ​Parallel Generational-Copying Garbage Collection with a Block-Structured Heap (Simon Marlow, Tim Harris, Roshan P. James, Simon Peyton Jones) In ISMM '08: Proceedings of the 7th international symposium on Memory management, Tucson, Arizona, ACM, June 2008

• ​Haskell on a Shared-Memory Multiprocessor (Tim Harris, Simon Marlow, Simon Peyton Jones) In Haskell '05: Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, pages 49--61, Tallinn, Estonia, ACM Press, September 2005

• Time and space profiling for non-strict, higher-order functional languages, Patrick M. Sansom and Simon Peyton Jones, POPL 1995.

• The Concurrent Haskell Foreign Function Interface, Wolfgang Thaller. An Addendum to Haskell 98 FFI Report.

Modules & Packages

• ​A Formal Specification of the Haskell 98 Module System (Iavor S. Diatchki, Mark P. Jones, Thomas Hallgren) In Haskell '02.

• ​Backpack: Retrofitting Haskell with Interfaces (Scott Scott Kilpatrick, Derek Dreyer, Simon Peyton Jones, Simon Marlow), POPL 2014.

Other GHC features

• ​Template Meta-programming for Haskell. Tim Sheard, Simon Peyton Jones. Haskell '02. ​doi Introduces Template Haskell.

• ​Scrap your Boilerplate: a Practical Design Pattern for Generic Programming. Ralf Lämmel, Simon Peyton Jones. TLDI '03. ​doi Introduces Typeable and Data.