Note [NOINLINE withSomeSNat]

libraries/ghc-internal/src/GHC/Internal/TypeNats.hs:114 libraries 2 tickets

The function

    withSomeSNat :: forall rep (r :: TYPE rep).
                    Natural -> (forall k. SNat k -> r) -> r

converts a `Natural` number to a singleton natural `SNat k`, where the `k` is
locally quantified in a continuation (hence the `forall k`). The local
quantification is important: we can manufacture an `SNat k` value, but it can
never be confused with (say) an `SNat 33` value, because we should never be
able to prove that `k ~ 33`. Moreover, if we call `withSomeSNat` twice, we'll
get an `SNat k1` value and an `SNat k2` value, but again we can't confuse them.
`SNat` is a singleton type!

But how to implement `withSomeSNat`? We have no way to make up a fresh type
variable. To do that we need `runExists`: see #19675.

Lacking `runExists`, we use a trick to implement `withSomeSNat`: instead of
generating a "fresh" type for each use of `withSomeSNat`, we simply use GHC's
placeholder type `Any` (of kind `Nat`), thus (in Core):

  withSomeSNat n f = f @T (UnsafeSNat @T n)
    where type T = Any @Nat

***  BUT we must mark `withSomeSNat` as NOINLINE! ***
(And the same for withSomeSSymbol and withSomeSChar in GHC.TypeLits.)

If we inline it we'll lose the type distinction between separate calls (those
"fresh" type variables just turn into `T`). And that can interact badly with
GHC's type-class specialiser. Consider this definition, where
`foo :: KnownNat n => blah`:

  ex :: Natural
  ex = withSomeSNat 1 (\(s1 :: SNat one) -> withKnownNat @one s1 $
       withSomeSNat 2 (\(s2 :: SNat two) -> withKnownNat @two s2 $
       foo @one ... + foo @two ...))

In the last line we have in scope two distinct dictionaries of types
`KnownNat one` and `KnownNat two`. The calls `foo @one` and `foo @two` each pick
out one of those dictionaries to pass to `foo`.

But if we inline `withSomeSNat` we'll get (switching to Core):

  ex = withKnownNat @T (UnsafeSNat @T 1) (\(kn1 :: KnownNat T) ->
       withKnownNat @T (UnsafeSNat @T 2) (\(kn2 :: KnownNat T) ->
       foo @T kn1 ... + foo @T kn2 ...))
    where type T = Any Nat

We are now treading on thin ice. We have two dictionaries `kn1` and `kn2`, both
of type `KnownNat T`, but with different implementations. GHC may specialise
`foo` at type `T` using one of these dictionaries and use that same
specialisation for the other. See #16586 for more examples of where something
like this has actually happened.

`KnownNat` should be a singleton type, but if we allow `withSomeSNat` to inline
it won't be a singleton type any more. We have lost the "fresh type variable".

TL;DR. We avoid this problem by making the definition of `withSomeSNat` opaque,
using an `NOINLINE` pragma. When we get `runExists` (#19675) we will be able to
stop using this hack.

References 0

This Note does not link to any other.

Referenced by 1