Forwarded from Andrew Martin below. I think we want more than just Maybe (more than one null), but the nesting I described is certainly more convenience than necessity.
---------- Forwarded message --------- From: Andrew Martin <andrew.thadd...@gmail.com> Date: Wed, Oct 14, 2020, 4:14 PM Subject: Re: Restricted sums in BoxedRep To: David Feuer <david.fe...@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.fe...@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
_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs