This post is the second episode of my GHC Core by example series. See the first one here.
What do you mean, “evaluation” ?
You are probably aware, whatever your level is, that Haskell is really different from the usual mainstream languages. One of the key differences is that evaluation happens “as needed”. To know more about this, read about lazy evaluation (I have a work-in-progress article here).
It means that most values in your program will first be a thunk until they are actually required, for the evaluation of another expression in which the value appears generally. Every Haskell code compiled with GHC gets translated to Core, so can we see evaluation appear more explicitly in Core? Well, yes. Let’s see how that goes.
A first example
Let’s just look at a simple function, in a
Let’s inspect the generated core with
ghc -O2 -ddump-simpl -dsuppress-idinfo -dsuppress-coercions -dsuppress-type-applications -dsuppress-uniques -dsuppress-module-prefixes Eval.hs. We get:
So the argument being an
Int, it’s a boxed integer, thus a normal Haskell value. That means that if
x hasn’t been evaluated yet, the evaluation of the expression yielding
x will happen through that
case x of ... expression.
Wait, we are talking about that
case expression, but it looks quite different than what we are used to. Generally, there is no
_ after the
of keyword. Why is there one there? That’s just a small detail, but let’s get this out of the way so we can get used to it easily. The general pattern is:
ident will just bind to the evaluated
expr so that you can refer to it on the right hand side of the different clauses of your
case ... of expressions. For example:
1 2 3 4 5 6
Int is defined by
data Int = I# Int# where
Int# is the actual machine integer type, unboxed and all. So we really see here that the
case ... of “pattern matches” on the
Int, which has only one constructor. However, the value stored inside being an unboxed integer means that it’s really sitting there, there’s no laziness going on there. So we actually have fully evaluated that Int. After that, we perform the native
Int# addition with
(+#) and repack that into a
Int with the
Maybe a second?
Let’s introduce another level of laziness.
1 2 3
We’re basically doing the same, except that, this time, we’re adding 1 to an
Int wrapped in
Maybe. What does the Core for that look like?
1 2 3 4 5 6 7
So, when passed a
Maybe Int value,
g will evaluate whether that value is
Just <some int>. That’s achieved by the first (outermost)
case ... of. The inner
case ... of is the place where we actually evaluate what the value of that
Int is (it could be a non-terminating computation like
product [1..], we don’t know yet and didn’t need to). You even may have noticed that the inner
case is identical to the Core we saw for
I haven’t mentionned this yet, but you may have noticed that we initially were doing the pattern matching by writing two
equations, one for each constructor of
Maybe, whereas it’s a
case ... of in the Core code: that’s how it always ends up being rewritten in Core, meaning our Haskell version is just some syntactic sugar around a
case ... of.
And your everyday haskell code gets evaluated the very same way, evaluating outermost constructors, and then going deep inside algebraic data types as much as necessary for the calling code, not more. Everything you compute in your Haskell code boils down to
case ... of expressions in Core, that’s how values are evaluated.
Consider this code:
1 2 3 4 5 6
Quite short right? Here’s the Core.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
This is all complicated, because GHC inlines functions quite agressively (in particular with
-O2 – there are really noticeable differences in the Core between
-O2, or even
-O1). But that was just to show you that everything in Core is really about function calls (including constructors) and case expressions. Among other things, we can see for example that GHC named our
(+5) function (it’s
lvl in the Core). The structure of this Core code is the result of mixing the original definitions of the functions and the way GHC’s inliner works.
That is all for this second episode. It’s quite short but I wanted to get evaluation out of the way in order to emphasize on important transformations GHC does at the Core level in later posts. I apologize for the delay, I will most likely push new posts in this series more regularly.