<p>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?</p>

CC BY-SA 4.0
2023-01-19T20:04:07.343Z
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:
Martin Berger
CC BY-SA 4.0
2023-01-19T20:04:12.107Z
(i) into direct machine code
generation, (ii) into C for feeding to gcc, (iii) into LLVM's
intermediate representation.
Martin Berger
CC BY-SA 4.0
2023-01-19T20:05:02.110Z
Here is a 2012 document: https://www.microsoft.com/en-us/research/wp-content/uploads/2012/01/aos.pdf
Martin Berger
<graph-algorithms><reductions><compilers><haskell>
Does GHC use graph reduction?
geeko
# Does GHC use graph reduction?

(Asked by: username_0 on 2023-01-19)

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?

**Tags:** graph-algorithms, reductions, compilers, haskell
> **Comments:**
> **username_1**: 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:  
> **username_1**: (i) into direct machine code generation, (ii) into C for feeding to gcc, (iii) into LLVM's intermediate representation.  
> **username_1**: Here is a 2012 document: https://www.microsoft.com/en-us/research/wp-content/uploads/2012/01/aos.pdf  

---

## 0 answers

