Restricted sums in BoxedRep

[David Feuer]

I don't know your terminology, sorry. By "null" I'm referring to something
distinguished, of which there can be more than one. These can be pointers
to statically allocated objects if necessary, though pointers in an unused
address range would probably be nicer. My goal is to be able to shove a
compact representation of something like (# (##) | (##) | (##) | a #) into
an array/MutVar/etc., rather than needing to box it to do so.

On Wed, Oct 14, 2020, 7:45 AM Spiwack, Arnaud <arnaud.spiwack at tweag.io>
wrote:

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