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/0fc1cb54d1afc0f002deb4d080c9b824f4... -- 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@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 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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

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 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 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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Yes, I think you're getting the gist. Pattern matching with one or two nulls is just an equality test or three. In practice, we'd want a fixed number of evenly spaced nulls, allowing jump table techniques to be used when there are more cases. We'd presumably have a hard limit for the number of nulls a type is allowed to have. On Wed, Oct 14, 2020, 10:29 AM Spiwack, Arnaud wrote:

Ok, I believe get it now,

Let's imagine (to take only the simplest case) that we have a `Nullable# a` type, such that `Nullable# a = (# (##) | a #)`. What would be the kind of `Nullable#`? I imagine that it would be something like `TYPE (BoxedRep Lifted) -> TYPE (BoxedRep Nullable)`.

Then you would want to abstract the type of arrays/tvars/whatnot from `Type -> Type` to `forall r. TYPE (BoxRep r) -> Type`.

Is that a correct interpretation of your suggestion?

If so, my guess would be that all the above is fine, but I suspect (and I'm quite a bit out of my comfort zone here) that there can be considerable difficulties in implementing pattern-matching for such a type.