Restricted sums in BoxedRep

David Feuer david.feuer at gmail.com
Tue Oct 13 21:46:49 UTC 2020


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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20201013/b06f3a4a/attachment.html>


More information about the ghc-devs mailing list