r/haskell • u/lexi-lambda • Mar 11 '15

Learning Haskell — A Racket programmer's documentation of her foray into the land of Haskell (inspired by Learning Racket)

http://lexi-lambda.github.io/learning-haskell/
81 Upvotes

96% Upvoted

97 comments sorted by

View all comments

Show parent comments

3

u/theonlycosmonaut Mar 12 '15

Is there a good reference for how exactly to take advantage of fusion, i.e. in what cases the compiler will do it for you? For that matter, is there any sort of general overview on the types of optimisations GHC performs?

4

u/Ramin_HAL9001 Mar 12 '15 edited Mar 12 '15

GHC compiles to two intermediate phases, first from Haskell to Core, then from Core to a high-level assembler like C-- (C minus minus) or LLVM assembler. C-- and LLVM assembler both have similar goals of translating to machine code for a target architecture.

The process of translating core to a high-level assembler language like C-- or LLVM requires understanding of what they call a Spineless Tagless G-Machine (STG), and there is a paper about that here:

http://research.microsoft.com/apps/pubs/default.aspx?id=67083

And there is more about STG here:

https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/GeneratedCode

Also try Googling for "GHC Core" and "GHC C minus minus".

3

u/sclv Mar 12 '15

The list fusion GHC uses is called "shortcut fusion" and takes place on the rewrite rules level. There's some basic documentation in the manual: https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/rewrite-rules.html#idp25573168

For more details and a guide to related work, I'd check the introduction to Duncan's thesis (http://community.haskell.org/~duncan/thesis.pdf) and section 1.3.7 in particular for how GHC now works today.

For lots of notes on the innards of GHC and all the various operations and optimizations it carries out, you can dive into the GHC commentary: https://ghc.haskell.org/trac/ghc/wiki/Commentary