Fwd: Restricted sums in BoxedRep

[David Feuer]

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.thaddeus at gmail.com>
Date: Wed, Oct 14, 2020, 4:14 PM
Subject: Re: Restricted sums in BoxedRep
To: David Feuer <david.feuer at 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 at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20201014/6e5b8dd1/attachment.html>