GHC Handbook

Chapter 6

Desugaring to Core

Where the whole of Haskell collapses into nine constructors, and where GHC works out, on the way past, whether your patterns were exhaustive.

Where this lives in the tree

Everything so far has operated on HsSyn, a syntax tree that mirrors Haskell’s surface language: if, where, guards, do, list comprehensions, sections, multi-equation definitions, record syntax. The desugarer’s job is to delete all of it.

What comes out is Core, whose expression type fits on one screen:

data Expr b
  = Var   Id
  | Lit   Literal
  | App   (Expr b) (Arg b)
  | Lam   b (Expr b)
  | Let   (Bind b) (Expr b)
  | Case  (Expr b) b Type [Alt b]
  | Cast  (Expr b) CoercionR
  | Tick  CoreTickish (Expr b)
  | Type  Type
  | Coercion Coercion

Nine constructors, and three of them (Tick, Type, Coercion) are bookkeeping. Everything you can write in Haskell arrives here as variables, literals, application, lambda, let and case.

That collapse is what makes the rest of the compiler possible. An optimiser for the surface language would need a case for every syntactic form and every extension; an optimiser for Core needs six.

Everything becomes case

Multi-equation definitions, nested patterns, guards, where, if: all of them become case. The interesting part is that this is not a simple rewrite. Given

area (Circle r) = pi * r * r
area (Rect w h) = w * h
area Point      = 0

a naive translation would test each equation in turn, re-examining the scrutinee every time. The pattern-match compiler instead groups patterns by constructor and produces a single case with one alternative each. This is the algorithm from The Implementation of Functional Programming Languages, and the reason GHC/HsToCore/Match.hs is one of the older and more intricate files in the tree.

Strictness needs care here too, since desugaring decides when things are forced:

Note [Desugar Strict binds] GHC/HsToCore/Binds.hs:629 
See https://gitlab.haskell.org/ghc/ghc/wikis/strict-pragma

Desugaring strict variable bindings looks as follows (core below ==>)

  let !x = rhs
  in  body
==>
  let x = rhs
  in x `seq` body -- seq the variable

and if it is a pattern binding the desugaring looks like

  let !pat = rhs
  in body
==>
  let x = rhs -- bind the rhs to a new variable
      pat = x
  in x `seq` body -- seq the new variable

if there is no variable in the pattern desugaring looks like

  let False = rhs
  in body
==>
  let x = case rhs of {False -> (); _ -> error "Match failed"}
  in x `seq` body
Show the rest of this Note (103 more lines) 
In order to force the Ids in the binding group they are passed around
in the dsHsBind family of functions, and later seq'ed in GHC.HsToCore.Expr.ds_val_bind.

Consider a recursive group like this

  letrec
     f : g = rhs[f,g]
  in <body>

Without `Strict`, we get a translation like this:

  let t = /\a. letrec tm = rhs[fm,gm]
                      fm = case t of fm:_ -> fm
                      gm = case t of _:gm -> gm
                in
                (fm,gm)

  in let f = /\a. case t a of (fm,_) -> fm
  in let g = /\a. case t a of (_,gm) -> gm
  in <body>

Here `tm` is the monomorphic binding for `rhs`.

With `Strict`, we want to force `tm`, but NOT `fm` or `gm`.
Alas, `tm` isn't in scope in the `in <body>` part.

The simplest thing is to return it in the polymorphic
tuple `t`, thus:

  let t = /\a. letrec tm = rhs[fm,gm]
                      fm = case t of fm:_ -> fm
                      gm = case t of _:gm -> gm
                in
                (tm, fm, gm)

  in let f = /\a. case t a of (_,fm,_) -> fm
  in let g = /\a. case t a of (_,_,gm) -> gm
  in let tm = /\a. case t a of (tm,_,_) -> tm
  in tm `seq` <body>


See https://gitlab.haskell.org/ghc/ghc/wikis/strict-pragma for a more
detailed explanation of the desugaring of strict bindings.

Wrinkle 1: forcing linear variables

Consider

  let %1 !x = rhs in <body>
==>
  let x = rhs in x `seq` <body>

In the desugared version x is used in both arguments of seq. This isn't
recognised a linear. So we can't strictly speaking use seq. Instead, the code is
really desugared as

  let x = rhs in case x of x { _ -> <body> }

The shadowing with the case-binder is crucial. The linear linter (see
Note [Linting linearity] in GHC.Core.Lint) understands this as linear. This is
what the seqVar function does.

To be more precise, suppose x has multiplicity p, the fully annotated seqVar (in
Core, p is really stored inside x) is

  case x of %p x { _ -> <body> }

In linear Core, case u of %p y { _ -> v } consumes u with multiplicity p, and
makes y available with multiplicity p in v. Which is exactly what we want.

Wrinkle 2: linear patterns

Consider the following linear binding (linear lets are always non-recursive):

  let
     %1 f : g = rhs
  in <body>

The general case would desugar it to

  let t = let tm = rhs
              fm = case tm of fm:_ -> fm
              gm = case tm of _:gm -> gm
           in
           (tm, fm, gm)

  in let f = case t a of (_,fm,_) -> fm
  in let g = case t a of (_,_,gm) -> gm
  in let tm = case t a of (tm,_,_) -> tm
  in tm `seq` <body>

But all the case expression drop variables, which is prohibited by
linearity. But because this is a non-recursive let (in particular we're
desugaring a single binding), we can (and do) desugar the binding as a simple
case-expression instead:

  case rhs of {
    (f:g) -> <body>
  }

This is handled by the special case: a non-recursive PatBind in
GHC.HsToCore.Expr.ds_val_bind.

The coverage checker

While it is here, GHC answers two questions you may have asked for: are these patterns exhaustive, and is any of them redundant. That is GHC/HsToCore/Pmc.hs, and it is much more than a syntactic check: it reasons about what values can actually reach each equation, using the same constraint machinery as the typechecker.

This is why GADTs get precise warnings. In

data T a where
  TInt  :: T Int
  TBool :: T Bool

h :: T Int -> Int
h TInt = 42

there is no missing TBool case, because TBool :: T Bool cannot have type T Int. The checker knows because it asks the solver.

It also propagates what earlier matches have already ruled out:

Note [Long-distance information] GHC/HsToCore/Pmc.hs:666 
Consider

  data Color = R | G | B
  f :: Color -> Int
  f R = …
  f c = … (case c of
          G -> True
          B -> False) …

Humans can make the "long-distance connection" between the outer pattern match
and the nested case pattern match to see that the inner pattern match is
exhaustive: @c@ can't be @R@ anymore because it was matched in the first clause
of @f@.

To achieve similar reasoning in the coverage checker, we keep track of the set
of values that can reach a particular program point (often loosely referred to
as "Covered set") in 'GHC.HsToCore.Monad.dsl_nablas'.
We fill that set with Covered Nablas returned by the exported checking
functions, which the call sites put into place with
'GHC.HsToCore.Monad.updPmNablas'.
Call sites also extend this set with facts from type-constraint dictionaries,
case scrutinees, etc. with the exported functions 'addTyCs', 'addCoreScrutTmCs'
and 'addHsScrutTmCs'.

That “long-distance information” is why GHC can tell you a case in the body of an equation is redundant because of the pattern in the equation’s head.

Dictionaries become arguments

The elaboration the typechecker performed becomes concrete here. Class constraints turn into lambda-bound dictionary parameters, and evidence bindings turn into ordinary lets. Coercions, the evidence for type equalities, become Cast nodes.

By the end, types are still present (Core is explicitly typed) but classes are gone entirely.

Seeing it happen

What you wrote.

-- | Everything Haskell offers for taking things apart (multi-equation
-- definitions, nested constructor patterns, guards, `where`, `if`, `let`)
-- collapses into exactly one Core construct: `case`.
--
-- The desugared Core shows the pattern-match compiler's output, including the
-- default alternatives that make matching exhaustive.
module Patterns where

data Shape
  = Circle Double
  | Rect Double Double
  | Point

area :: Shape -> Double
area (Circle r) = pi * r * r
area (Rect w h) = w * h
area Point = 0

classify :: Int -> String
classify n
  | n < 0 = "negative"
  | n == 0 = "zero"
  | n < small = "small"
  | otherwise = "large"
  where
    small = 10

firstTwo :: [a] -> Maybe (a, a)
firstTwo (x : y : _) = Just (x, y)
firstTwo _ = Nothing
Three equations for `area`, guards in `classify`, and a nested pattern in `firstTwo`, all reduced to case.

Look at classify. The guards, the where-bound small, and the fall-through to otherwise have all become nested case. Note also the default alternatives the compiler inserted: Core case must be exhaustive, so anything the source left implicit is now explicit.

What comes next

The desugarer’s output is checked by Core Lint (in a debug compiler, or with -dcore-lint) and then handed to the optimiser. From here on, every phase’s input and output is Core, and every transformation must preserve its typing, which is the subject of the next chapter.

Reading the source yourself

  1. GHC/Core.hs: read the Expr type and its Notes before any desugaring code. It is the target; the translation makes little sense without it.
  2. GHC/HsToCore/Expr.hs for the straightforward cases.
  3. GHC/HsToCore/Match.hs for the pattern-match compiler, which is where the real work is.
  4. GHC/HsToCore/Pmc.hs separately, when you care about warnings rather than code generation. It is nearly independent of the rest.

-ddump-ds shows the output directly, and comparing it with -ddump-ds-preopt reveals how much tidying happens even before the simplifier runs.