I have read somewhere that GHC does not use graph reduction for compiling/evaluating expressions. Is this right? If yes, what does it use as an alternative?

  • 2
    $\begingroup$ I don't know how GHC works today, but a couple of years ago it worked something like this: (1) The compiler desugars Haskell into a small language called Core which is an extension of System Fω called FC with pattern matching, let and coercions. (2) Core is compiled into STG code, which stands for Spineless-Tagless G-machine and is a refinement of the older G-machine (short for Graph-Reduction Machine, and for the lazy evaluation of functional programs in supercombinator form). (3) STG is compiled into C--. (4) C-- can be piped into any of the following: $\endgroup$ Jan 19 at 20:04
  • 2
    $\begingroup$ (i) into direct machine code generation, (ii) into C for feeding to gcc, (iii) into LLVM's intermediate representation. $\endgroup$ Jan 19 at 20:04
  • 2
    $\begingroup$ Here is a 2012 document: microsoft.com/en-us/research/wp-content/uploads/2012/01/aos.pdf $\endgroup$ Jan 19 at 20:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.