Fwd: Restricted sums in BoxedRep

Andreas Klebinger klebinger.andreas at gmx.at
Thu Oct 15 09:31:53 UTC 2020


 From a implementors perspective my main questions would be:

* How big is the benefit in practice? How many use cases are there?
* How bad are the costs? (Runtime overhead, rts complexity, ...)

The details of how this would be exposed to a user would are important.
But if the costs are too high for the drawbacks then it becomes a moot
point.

David Feuer schrieb am 14.10.2020 um 22:21:
> 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
> <mailto: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 <mailto: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
> <mailto: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
>
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20201015/5f5607b6/attachment.html>


More information about the ghc-devs mailing list