---------- Forwarded message ---------
From: Andrew Martin <andrew.thaddeus@gmail.com>
Date: Wed, Oct 14, 2020, 4:14 PM
Subject: Re: Restricted sums in BoxedRep
To: David Feuer <david.feuer@gmail.com>

You'll have to forward this to the ghc-devs list to share it with others since I'm not currently subscribed to it, but I've had this same thought before. It is discussed at https://github.com/andrewthad/impure-containers/issues/12. Here's the relevant excerpt:

Relatedly, I was thinking the other day that after finishing implementing https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0203-pointer-rep.rst, I should really look at seeing if it's possible to add this maybe-of-a-lifted value trick straight to GHC. I think that with:
data RuntimpRep
  = BoxedRep Levity
  | MaybeBoxedRep Levity
  | IntRep
  | ...

data BuiltinMaybe :: forall (v :: Levity). TYPE v -> TYPE ('MaybeBoxedRep v)
This doesn't have the nesting issues because the kind system prevents nesting. But anyway, back to the original question. I would recommend not using Maybe.Unsafe and using unpacked-maybe instead. The latter is definitely safe, and it only costs an extra machine word of space in each data constructor it gets used in, and it doesn't introduce more indirections.

On Tue, Oct 13, 2020 at 5:47 PM David Feuer <david.feuer@gmail.com> wrote:

Null pointers are widely known to be a lousy language feature in general, but there are certain situations where they're *really* useful for compact representation. For example, we define

newtype TMVar a = TMVar (TVar (Maybe a))

We don't, however, actually use the fact that (Maybe a) is lifted. So we could represent this much more efficiently using something like

newtype TMVar a = TMVar (TVar a)

where Nothing is represented by a distinguished "null" pointer.

While it's possible to implement this sort of thing in user code (with lots of fuss and care), it's not very nice at all. What I'd really like to be able to do is represent certain kinds of sums like this natively.

Now that we're getting BoxedRep, I think we can probably make it happen. The trick is to add a special Levity constructor representing sums of particular shapes. Specifically, we can represent a type like this if it is a possibly-nested sum which, when flattened into a single sum, consists of some number of nullary tuples and at most one Lifted or Unlifted type. Then we can have (inline) primops to convert between the BoxedRep and the sum-of-sums representations.

Anyone have thoughts on details for what the Levity constructor arguments might look like?

-Andrew Thaddeus Martin