Restricted sums in BoxedRep

Sebastian Graf sgraf1337 at gmail.com
Wed Oct 14 11:54:16 UTC 2020


I believe Simon told me once that NULL pointers in places we assume
BoxedRep things are not an option, because the GC assumes it is free to
follow that pointer. It won't check if it's NULL or not.
That's also the reason why we lower `LitRubbish` (which we use for absent
BoxedRep literals) as `()` when going to STG
<https://gitlab.haskell.org/ghc/ghc/-/blob/0fc1cb54d1afc0f002deb4d080c9b824f423b647/compiler/GHC/CoreToStg.hs#L380-383>
-- We can't use NULL, so supply an arbitrary (untyped!) closure that we
know can be followed by the GC.

Am Mi., 14. Okt. 2020 um 13:46 Uhr schrieb Spiwack, Arnaud <
arnaud.spiwack at tweag.io>:

> I may have misunderstood, but my understanding is the following:
>
> - Since a is a boxed type, it can never be the null pointer
> - So I can use a null pointer unambiguously
>
> Let's call this null-pointer expanded type, `Nullable# a`, it is now a
> different sort than `a`, since it can have the null pointer in it. Is that
> still what you wish for? The risk being that combining such a `Nullable# a`
> with another data structure may very well require an additional boxing,
> which is what, I believe, you were trying to avoid.
>
> /Arnaud
>
> On Tue, Oct 13, 2020 at 11: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?
>> _______________________________________________
>> ghc-devs mailing list
>> ghc-devs at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>>
> _______________________________________________
> 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/20201014/281541f0/attachment.html>


More information about the ghc-devs mailing list