Consider top-level unlifted bindings

A conversation in !2218 (closed) (the implementation of the UnliftedData proposal https://github.com/ghc-proposals/ghc-proposals/pull/265) centers on whether or not GHC should support unlifted bindings at top-level. I am moving that conversation here, as it is too easy to lose in an MR about something only tangentially related.

@AndreasK (!2218 (comment 239893)):

Possible issues with the current state (no top level unlifted bindings allowed).

isKnownKey :: MyThing -> Bool
isKnownKey x = x `elem` knownThings

knownThings :: MyList MyThing
knownThings = foo : bar : baz : MyNil

Now we want the most efficient code for isKnownKey so we use the new unlifted types extensions.

isKnownKey :: MyThing -> Bool
isKnownKey x = x `elem` knownThings

knownThings :: UMyList MyThing
knownThings = <staticData>

However this will not compile as UMyList is unlifted and on the top level.

So a user might change this to this:

isKnownKey :: MyThing -> Bool
isKnownKey x = 
    let knownThings = <staticData> :: UMyList MyThing
    in x `elem` knownThings

And expect it to be equivalent in performance to the original (lifted) code. But it's not!

GHC can't float knownThings to the top level because it's unlifted. So we have to allocate it on the heap inside the body of isKnownKey.

This is, compared to the original lifted code, quite horrible.

@bgamari (!2218 (comment 239919)):

@AndreasK and I discussed this. We generally agreed that this issue is quite orthogonal to the present patch.

However, looking ahead, the matter of top-level unlifted definitions indeed is something that deserves some thought. To be clear, the central problem here is that the user might write a function application at the top level:

f :: Int -> SomeUnliftedType
f = ...

x :: SomeUnliftedType
x = f 42

The problem here is that there is no way to compile x short of full compile-time evaluation or computation during program start-up (which I personally would oppose since such run-time initialization would be complicated to ensure and incur an essentially unbounded cost on program start-up time). For this reason I argue that this is not a case we want to admit.

Of course, there are other cases where unlifted types are desireable at the top-level (e.g. saturated data constructor applications). In principle it would be fairly straightforward to incorporate a validity check that admits top-level constructor applications which rejecting function applications if we wanted.

On the whole I am not too concerned about the inability to write top-level unlifted function applications. Afterall, you can very easily accomplish something similar to the run-time initialization described above using nothing more than lazyness. For instance, perhaps we have a large unlifted value (say, an UnliftedMap) that we want to memoize at the top-level but that requires non-trivial computation. This could be accomplished:

data unlifted UnliftedMap = ...

data Lazy (a :: TYPE 'UnliftedPtrRep) = Lazy a

bigMap :: Lazy UnliftedMap
bigMap = {- compute big map here -}

This allows bigMap to be treated as a CAF, achieving the desired memoization. While this doesn't completely eliminate evalulatedness the check, I would argue that the cost that we care about is the cost of traversing the map, not accessing its head.

The only other question that remains is what float-out should be allowed to do. Regardless of whether we want top-level unlifted data constructor applications in source Haskell, I think we really should admit them in Core (lest use of unlifted datatypes incurring unexpected costs on users). I suspect this wouldn't be hard to arrange as this is just a small refinement on FloatOut's existing rules surrounding unlifted things.