Null pointers

[treeowl]

It's been said that null pointers were a billion dollar mistake. I see it a bit differently—misuse of null pointers was a billion dollar mistake. Nulls are often used in inferior languages as a distinguished value in an arbitrary type. This is trouble for all sorts of well known reasons. In Haskell, we have types like Maybe to do that better. However, null pointers are very useful for something else: adding a distinguished value to each element of a container. Doing this with Maybe or similar is quite expensive, and doing it with null pointers is harmless. As @ekmett has explained to me, the way to do this in Haskell is with unsafeCoerce. For example, here's a type like a strict array of strict maybes.

data Null = Null -- not exported
ptrEq :: a -> b -> Bool
ptrEq a b = isTrue# (reallyUnsafePtrEquality# a b)

data SMaybe a = SNothing | SJust !a

checkNull :: a -> SMaybe a
checkNull !a
  | ptrEq a Null = SNothing
  | otherwise = SJust a

newtype SMArray s a = SMArray (MutableArray s a)
writeSMArray :: SMArray s a -> Int -> SMaybe a -> ST s ()
writeSMArray (SMArray mar) k ma = case ma of
  SNothing -> writeArray mar k $! unsafeCoerce Null
  SJust a -> writeArray mar k a

readSMArray :: SMArray s a -> Int -> ST s (SMaybe a)
readSMArray (SMArray mar) k = do
  ma <- readArray mar k
  pure $! checkNull ma

This will be much more compact and efficient than an array of SMaybes.

Here's a version with lazy Maybes:

checkNull :: a -> Maybe a
checkNull a
  | ptrEq a Null = Nothing
  | otherwise = Just a

newtype MArray s a = MArray (MutableArray s a)
writeMArray :: MArray s a -> Int -> Maybe a -> ST s ()
writeSMArray (MArray mar) k ma = case ma of
  Nothing -> writeArray mar k $ unsafeCoerce Null
  Just a -> writeArray mar k a

readMArray :: MArray s a -> Int -> ST s (Maybe a)
readMArray (MArray mar) k = do
  ma <- readArray mar k
  pure $! checkNull ma

Note also that this technique can support multiple null pointers—just add more constructors to the Null type and check for each of them.

So what's wrong? There are three problems:

1. This is a hideous abuse of unsafe coercions and unsafe pointer equality, and GHC developers therefore won't guarantee that they won't change things in a way that would mess it up.
2. When working with multiple nulls, each additional null will need to be checked separately, reducing performance.
3. The lazy version feels very fragile: it relies on the nulls never being suspended.

Can we add some magic to support this better? Imagine we have some primops to do so, whatever those may look like. How do we deal with the multiple constructor issue? Require the type of nulls to match up with the type of SMaybe things. A single unsigned comparison should be able to determine whether a pointer is a null, and if so, a simple pointer offset should take us from the null constructor to its corresponding SMaybe. The other way around should work as well. I don't know how to address the fragility of the lazy version.

[jvanbruegge]

Wouldn't it be better to implement something like Rust's null pointer optimization for strict (unlifted?) datatypes? That way using a maybe for all elements would not incur in a performance penalty without adding (more) footguns

[AntC2]

null pointers are very useful for something else: adding a distinguished value to each element of a container.

The reason they're a mistake is you can't stop the compiler/code/machine allocating an address that happens to coincide with (one of) your distinguished value(s). So your 'magic' would need to look something like:

• 'distinguished nulls' must be values below (say) 100 Int#.
• genuine pointers must be values above 100 Int#.
• so now the compiler's memory allocation routines (in the object code) must check the address after every allocation. Or make a bunch of assumptions and enforce them about the target architecture's behaviour -- for every architecture the compiler produces.

I appreciate the likelihood of an actual clash is vanishing small -- which is why null pointers work in practice. But Haskell is supposed to come with memory-safety guarantees, which your reallyUnsafePtrEquality#, unsafeCoerce, "hideous abuse", etc are not giving us.

[treeowl]

@AntC2 , I don't know what you're talking about. My nulls are addresses of nullary data constructors, which GHC already allocates statically. There are definitely safely concerns with my hacked up implementation, but that isn't one of them.

[treeowl]

Wouldn't it be better to implement something like Rust's null pointer optimization for strict (unlifted?) datatypes? That way using a maybe for all elements would not incur in a performance penalty without adding (more) footguns

That optimization sounds nice, but it seems to be limited to certain fairly monomorphic contexts. I don't see how to apply it to anything polymorphic like Maybe or SMaybe. Based on that SO answer, it also doesn't seem to support multiple nulls, though I imagine it could probably be extended to do so.

[AntC2]

My nulls are addresses of nullary data constructors, ...

Then I suggest calling them 'Null pointers' is completely misleading -- especially in the same breath as Hoare's "billion dollar mistake". In re-reading your post, I don't know what you're talking about. Specifically in

   data Null = Null
   ...
   data SMaybe a = SNothing | SJust !a

• How do we know the compiler allocates a different address to Null vs to SNothing? I don't see any requirement for that in the language spec. "GHC developers therefore won't guarantee that they won't change things in a way that would mess it up"
• How do we know the compiler allocates a different address to Null vs to some legitimate value for an a in a (MutableArray s a)? (Perhaps the a is a type with a nullary constructor aot.)
• But anyway why use unsafeCoerce Null in writeArray? Why not just write unsafeCoerce SNothing?
• Wouldn't we gain better efficiencies by having the array contain unboxed values? But in that case, how to distinguish an unboxed Int# vs whatever unsafeCoerce Null produces?

[treeowl]

in

   data Null = Null
   ...
   data SMaybe a = SNothing | SJust !a

* How do we know the compiler allocates a different address to `Null` vs to `SNothing`?

We know it empirically

I don't see any requirement for that in the language spec. "GHC developers therefore won't guarantee that they won't change things in a way that would mess it up"

Yes, the implementation could totally change to mess that up. That's part of why I want proper support for something of similar power.

* How do we know the compiler allocates a different address to `Null` vs to some legitimate value for an `a` in a `(MutableArray s a)`? (Perhaps the `a` is a type with a nullary constructor aot.)

As above.

* But anyway why use `unsafeCoerce Null` in `writeArray`? Why not just write `unsafeCoerce SNothing`?

Because SNothing is a value someone might legitimately want to story in an SMArray. The nulls are rather private affairs, hidden under curtains in library code.

* Wouldn't we gain better efficiencies by having the array contain unboxed values? But in that case, how to distinguish an unboxed `Int#` vs whatever `unsafeCoerce Null` produces?

Unboxed arrays are available. If we have something like Int, we can totally have a UArray Bool and a UArray Int or whatever. That's a whole different issue, no?

[AntC2]

If we have something like Int,

I meant something like MutableArray s (Maybe Int#). (UArray doesn't allow Maybes AFAICT.)

Then what are the use cases for (Maybe a) in a MutableArray? If it's a sparse structure (most cells are Nothing) would that be better expressed as a (hash-?) indexed tree?/lookup list? Storing a load of Nothings seems like the wrong end to tackle the problem.

[AntC2]

this technique can support multiple [niladic constructors]

The problem is more with multiple non-niladic constructors, or more-than-unary constructors:

data MaybeEither a = JustLeft a | JustRight a | Neither

data Maybe2 a      = Just2 a a | Nothing2

So now we need an explicit constructor to tell which case; or to tell what memory footprint. Then your use case is only Maybe (or something isomorphic); and per my preceding comment, there might be more memory-compact ways to achieve that.

[treeowl]

If we have something like Int,

I meant something like MutableArray s (Maybe Int#). (UArray doesn't allow Maybes AFAICT.)

The representation I was suggesting was an unboxed array of Ints and an unboxed array of Bool (i.e., a bit array), where the bit array indicates which entries are populated.

Then what are the use cases for (Maybe a) in a MutableArray? If it's a sparse structure (most cells are Nothing) would that be better expressed as a (hash-?) indexed tree?/lookup list? Storing a load of Nothings seems like the wrong end to tackle the problem.

I think your question contains its own answer. As long as the array is (expected to be) sufficiently dense, a dense representation will perform well.

[treeowl]

this technique can support multiple [niladic constructors]

The problem is more with multiple non-niladic constructors, or more-than-unary constructors:

data MaybeEither a = JustLeft a | JustRight a | Neither

data Maybe2 a      = Just2 a a | Nothing2

So now we need an explicit constructor to tell which case; or to tell what memory footprint. Then your use case is only Maybe (or something isomorphic); and per my preceding comment, there might be more memory-compact ways to achieve that.

No. There can be multiple nullary constructors.

data Result a =
    Success a
  | PermanentFailure
  | Retry

How common will that be? Dunno, but it's possible.

[nomeata]

Could GHC automatically apply this optimization to any unlifted data type (ping @sgraf812) that contains of at most one data constructor with exactly one lifted argument, and arbitrary many nullary constrictors.

Then GHC could implement them as you describe: static pointers for the nullary ones, and simply the underlying argument pointer for the lifted constructor.

And because this data type has a different kind than the types you can nest within, there is no risk of confusion with nested Nothings.

The implementation could be confined to the STG to Cmm phase, I believe, with different code to match and create these values.

(This suggestion was brought to you on the phone during breakfast, so I may miss something.)

This seems to have similarities with #530, but seems independent. @clyring @AndreasPK

[sgraf812]

Connection to denesting proposal #530

Indeed this feels very close to #530, but I'm doubtful that we could tweak the denesting idea to data types like SMaybe.
The whole denesting idea needs to be very careful about "tag inheritance", that is, if we were to denest

data Lazy (a :: UnliftedType) = Lazy a

then Lazy a inherits/embeds all the proper tags of a. If we were to add a constructor as in the SMaybe case

data SMaybe a = SNothing | SJust {-# DENEST #-} !a

then we can no longer denest SJust, because the proper tag of ,e.g., SJust () coincides with the proper tag 1 of SNothing. (Same problem if you switch the order of constructors, then SJust True has the same tag 2 as SNothing).

Distinguished elements

The "distinguished element" idea here is a different one: Since ptrEq does not only compare tags but complete pointers, the restrictions above do not apply.

Indeed, it is impossible for GHC to allocate a pointer of type SMaybe a that aliases with the static pointer to Null. So it's easy to see that this approach works as a library solution.

Unfortunately, GHC might also argue that due to that aliasing rule, a pointer comparison between different types will never return true and optimise checkNull (unsafeCoerce Null :: Bool) to SJust b in the future. That is perhaps the danger described by problem (1) in this approach, not that I'm aware that GHC is doing this kind of alias analysis.

Regarding problem (2): I don't see how we can meaningfully get around checking for multiple null values. I don't think it matters much until it does (let's work from concrete evidence/profiles).

Regarding problem (3): Yes, the lazy version indeed looks broken, turning every thunk into an SNothing. And I don't think it can be fixed either; it's quite fundamental that Just a is not isomorphic to a; similar limitation in #530.

One simple solution to obscure the no alias realtionship would be to use OPAQUE (NOINLINE should already be sufficient, but this is about intent):

ptrEqHomo :: a -> a -> Int#
ptrEqHomo a b = reallyUnsafePtrEquality# a b
{-# OPAQUE ptrEqHomo #-}

ptrEq :: a -> b -> Bool
ptrEq a b = isTrue# (ptrEqHomo a (unsafeCoerce b))
{-# INLINE ptrEq #-}

Or advocate for (a new variant of?) reallyUnsafePtrEquality# that GHC agrees to never exploit aliasing info based on types in the way I alluded to above. I think the OPAQUE idea is simpler and quite unlikely to be broken by GHC (unless there's a bug).

A more involved way to put the library solution on firm grounds that is forward compatible with optimisation shenanigans would be to provide a builtin, auto derived type class (like Coercible)

class Distinguishable a
  distinguishedRubbish :: a

and that could be used for pointer comparisons with the guarantee that ptrEq distinguishedRubbish a is false iff a =/= distinguishedRubbish without any analysis being able to interfere.

Indeed we already have something in Core that is already quite similar: LitRubbish. See this Note below. Unfortunately, at the moment we allocate exactly one rubbish lit per representation, and I think we pick () for all boxed ones, meaning it doesn't satisfy the rule above. So perhaps not a good match after all.

Note [Rubbish literals]
~~~~~~~~~~~~~~~~~~~~~~~
Sometimes, we need to cough up a rubbish value of a certain type that is used
in place of dead code we thus aim to eliminate. The value of a dead occurrence
has no effect on the dynamic semantics of the program, so we can pick any value
of the same representation.

Exploiting the results of absence analysis in worker/wrapper is a scenario where
we need such a rubbish value, see examples in Note [Absent fillers] in
GHC.Core.Opt.WorkWrap.Utils.

It's completely undefined what the *value* of a rubbish value is, e.g., we could
pick @0#@ for @Int#@ or @42#@; it mustn't matter where it's inserted into a Core
program. We embed these rubbish values in the 'LitRubbish' case of the 'Literal'
data type. Here are the moving parts:

1. Source Haskell: No way to produce rubbish lits in source syntax. Purely
   an IR feature.

2. Core: 'LitRubbish' carries a `Type` of kind RuntimeRep,
   describing the runtime representation of the literal (is it a
   pointer, an unboxed Double#, or whatever).

   We have it that `RUBBISH[rr]` has type `forall (a :: TYPE rr). a`.
   See the `LitRubbish` case of `literalType`.

   The function GHC.Core.Make.mkLitRubbish makes a Core rubbish literal of
   a given type.  It obeys the following invariants:

   INVARIANT 1: 'rr' has no free variables. Main reason: we don't need to run
   substitutions and free variable finders over Literal. The rules around
   levity/runtime-rep polymorphism naturally uphold this invariant.

   INVARIANT 2: we never make a rubbish literal of type (a ~# b). Reason:
   see Note [Core type and coercion invariant] in GHC.Core.  We can't substitute
   a LitRubbish inside a coercion, so it's best not to make one. They are zero
   width anyway, so passing absent ones around costs nothing.  If we wanted
   an absent filler of type (a ~# b) we should use (Coercion (UnivCo ...)),
   but it doesn't seem worth making a new UnivCoProvenance for this purpose.

   This is sad, though: see #18983.

3. STG: The type app in `RUBBISH[IntRep] @Int# :: Int#` is erased and we get
   the (untyped) 'StgLit' `RUBBISH[IntRep] :: Int#` in STG.

   It's treated mostly opaque, with the exception of the Unariser, where we
   take apart a case scrutinisation on, or arg occurrence of, e.g.,
   `RUBBISH[TupleRep[IntRep,DoubleRep]]` (which may stand in for `(# Int#, Double# #)`)
   into its sub-parts `RUBBISH[IntRep]` and `RUBBISH[DoubleRep]`, similar to
   unboxed tuples. `RUBBISH[VoidRep]` is erased.
   See 'unariseRubbish_maybe' and also Note [Post-unarisation invariants].

4. Cmm: We translate 'LitRubbish' to their actual rubbish value in 'cgLit'.
   The particulars are boring, and only matter when debugging illicit use of
   a rubbish value; see Modes of failure below.

5. Bytecode: In GHC.ByteCode.Asm we just lower it as a 0 literal, because it's
   all boxed to the host GC anyway.

6. IfaceSyn: `Literal` is part of `IfaceSyn`, but `Type` really isn't.  So in
   the passage from Core to Iface we put LitRubbish into its own IfaceExpr data
   constructor, IfaceLitRubbish. The remaining constructors of Literal are
   fine as IfaceSyn.

Wrinkles

a) Why do we put the `Type` (of kind RuntimeRep) inside the literal?  Could
   we not instead /apply/ the literal to that RuntimeRep?  Alas no, because
   then LitRubbish :: forall (rr::RuntimeRep) (a::TYPE rr). a
   and that's an ill-formed type because its kind is `TYPE rr`, which escapes
   the binding site of `rr`. Annoying.

b) A rubbish literal is not bottom, and replies True to exprOkForSpeculation.
   For unboxed types there is no bottom anyway.  If we have
       let (x::Int#) = RUBBISH[IntRep] @Int#
   we want to convert that to a case!  We want to leave it as a let, and
   probably discard it as dead code soon after because x is unused.

c) We can see a rubbish literal at the head of an application chain.
   Most obviously, pretty much every rubbish literal is the head of a
   type application e.g. `RUBBISH[IntRep] @Int#`.  But see also
   Note [How a rubbish literal can be the head of an application]

c) Literal is in Ord, because (and only because) we use Ord on AltCon when
   building a TypeMap. Annoying.  We use `nonDetCmpType` here; the
   non-determinism won't matter because it's only used in TrieMap.
   Moreover, rubbish literals should not appear in patterns anyway.

d) Why not lower LitRubbish in CoreToStg? Because it enables us to use
   LitRubbish when unarising unboxed sums in the future, and it allows
   rubbish values of e.g.  VecRep, for which we can't cough up dummy
   values in STG.

Automatic "distinguished element" optimisation

The idea of Joachim sounds like a generalisation of Rust's null pointer optimisation. I don't think it works well for polymorphism. E.g.

data SMaybe a = SNothing | SJust !a

f :: a -> Int
f a = I# (getTag a)

SMaybe qualifies for the null pointer optimisation. If GHC were to eliminate the indirection, what were f (SJust ()) to report? Certainly it can't report 1, because that would be the same result as for f SNothing. And so we hit the same limitation as for constructor denesting again. The only way to guarantee proper tags is to allocate a box for SJust, perhaps whenever we instantiate some type variable to SJust blah (which feels similarly to Java's Autoboxing). Not quite satisfying.

Conclusion

• The distinguished element optimisation can't work for a data type that is both lifted and has a lifted (non-strict) field

• It doesn't work with polymorphism at all, hence the appeal of automating it is quite low

• It can be implemented as a library solution today, in a way that is quite forward compatible, as far as I can see

• I don't see how the generated code for checkNull could be sped up substantially by making it a primop or otherwise blessed by the compiler. Specifically

  A single unsigned comparison should be able to determine whether a pointer is a null, and if so, a simple pointer offset should take us from the null constructor to its corresponding SMaybe.

  I'm doubtful that the machine code equivalent of if p == Null then p + (SNothing-Null) else p is really that much faster compared to the machine code equivalent of if p == Null then SNothing else p. Both SNothing-Null and SNothing are constants.

[treeowl]

@sgraf812 This is quite a substantial analysis, and I won't have time to read it until later today, but I wanted to respond to a few points:

Regarding problem (2): I don't see how we can meaningfully get around checking for multiple null values. I don't think it matters much until it does (let's work from concrete evidence/profiles).

Why not? Doesn't (or couldn't) GHC lay out the nullary representatives of a type in a contiguous memory block? As you say, maybe it won't be a big deal in practice because people won't use types with many constructors for this purpose, but $O(n)$ always makes me a bit nervous.

Regarding problem (3): Yes, the lazy version indeed looks broken, turning every thunk into an SNothing. And I don't think it can be fixed either; it's quite fundamental that Just a is not isomorphic to a; similar limitation in #530.

I'm sorry for the confusion. The lazy version was expressed a bit sloppily. It would be cleaner to describe it in terms of

type UMaybe :: Type -> UnliftedType
data UMaybe a = UNothing | UJust a

That is, the maybeness is not lazy; only the contents are lazy.

[phadej]

FWIW, there is unsafePtrEquality# restricted to unlifted types.

I think as far as we stay in Unlifted universe, GHC gives us the needed bits already.

It would be great to be able to have top-level unlifted value bindings (and syntactically values could be enough - GHC already allows that for Addr# literals!). Then we won't need to rely on GHC always using the same value for nullary constructors. (EDIT: Actually comparing to Addr# value - that one you can have at top-level).

With that, you can program in a strict Haskell using tricks from strict languages: like a distinguished pointer one.

GHC also uses unsafePtrEquality# for example to compare StableNames of different types: eqStableName, so I don't think that aliasing analysis will break unsafePtrEquality# at least without providing an escape hatch.

EDIT: if one really wants to speedup n-distinguished comparison, then asking for unsafePtrDifference :: forall (a :: UnliftedType) (b :: UnliftedType). a -> b -> Int# could do the trick (using e.g. Addr# as base point to "reserve" enough space so aliasing won't happen)

EDIT2: Is there a Box# :: Type -> UnliftedType which actually doesn't add indirection? Just makes type "strict" (i.e. value of Box# a are never a thunk)?

[treeowl]

@sgraf812 To be very precise operationally, the idea is that my MArray would be an array of pointers. Each pointer is either to a distinguished constructor ("null"), or to anything else, including a thunk. A null is UNothing. Anything else is a UJust.

[sgraf812]

Regarding problem (2): I don't see how we can meaningfully get around checking for multiple null values. I don't think it matters much until it does (let's work from concrete evidence/profiles).

Why not? Doesn't (or couldn't) GHC lay out the nullary representatives of a type in a contiguous memory block?

I guess you are right, it's theoretically to do such checks in O(1). But doing so would be quite an extensive feature for GHC, from exposing the proper primops to their implementation in the code generator. I'd rather say we sit it out until we have a client pushing for this feature.

I'm sorry for the confusion. The lazy version was expressed a bit sloppily. It would be cleaner to describe it in terms of

type UMaybe :: Type -> UnliftedType
data UMaybe a = UNothing | UJust a

That is, the maybeness is not lazy; only the contents are lazy.

Ah yes, that makes a lot more sense, working around the "can't work for a data type that is both lifted and has a lifted (non-strict) field" issue. Perhaps edit your OP with that Maybe type when you find time.

Note that this only works as long as you can control that you never need to store an SJust Null/UJust Null in your array. This would be impossible to ensure if the flattening would be done automatically.

Anyway, since this is not the run-of-the-mill Maybe data type, the optimisation is applicable in far fewer cases.

[treeowl]

@sgraf812 Null is a private thing. No one but the provider of the "array of unlifted maybes" type should have access to it or its constructor. I haven't framed this pre-proposal in terms of automatic flattening for the simple reason that I have no idea how to do that well/sensibly. From the "null as a general way to add a distinguished value to a type" (or "inside out") standpoint, I guess we could say

data (forall x. a ≠ Shmaybe x) => Shmaybe a
  = Shnothing | Shjust a

but that's very much not the perspective I'm taking, and it's really not what I want—polymorphism goes out the window. The "outside in" approach doesn't suffer from the nesting problem, but I don't know how to think about automating it, if that's possible at all.

[nomeata]

In my suggestion I was also hoping that by making SMaybe an unlifted data type we can avoid the polymorphism issues? Does getTag need to work on unlifted types as well?

(In my idea above, case analysis would work by looking at pointer values, not at the tag, and thus getTag should either simply not be available.)

Note that this only works as long as you can control that you never need to store an SJust Null/UJust Null in your array. This would be impossible to ensure if the flattening would be done automatically.

Is your Null @treeowl ’s UNothing?

If so, isn’t SJust Null ill-kinded, because SMaybe :: Type -> UnliftedType, so you cannot put a SMaybe in a SMaybe?

[treeowl]

@nomeata Pointer tagging is an important optimization for unlifted sum types as well as all lifted types. data-elevator also blurs the lifted/unlifted distinction a bit for performance, and it's very possible that GHC will end up offering a mechanism like that of its own.

[nomeata]

Hmm, ok. I was assuming that for your use case you'd be willing to give up pointer tagging for this special data type to get the distinguished element optimization. Because if you don't, how can you do anything at all (which I guess is Sebastian's point).

[treeowl]

@nomeata I think I must have misunderstood you. Nevertheless, I don't think it should be necessary to give up pointer tagging. The pointer tag will mean different things depending on whether the value is a distinguished one or not, but that can be determined before actually following the pointer.

[nomeata]

I'm not sure that the pointer tag means anything useful (after all the UJust thing, being just the underlying pointer, can have any pointer tag value, can it?). But the pointer itself has enough information to discern the constructors, so one doesn't have to follow the pointer either - not exactly pointer tagging, but the same effect.

[treeowl]

@nomeata the pointer tag (if set) indicates either which distinguished value it is or which constructor of the underlying type. If there's only one distinguished value, or the relevant distinguished values are arranged contiguously, then it's quite cheap to determine which situation applies.

[treeowl]

I guess the "which distinguished value" aspect of the tag is useless, so never mind that. It's only useful if it's not a distinguished value.

[nomeata]

Right, but you first have to check if it's even in that range, as the arbitrary pointer could else have a similar tag, so you have to look at the full pointer (not just the tags), but don't have to follow it. I think we are jn agreement?

What I don't know is whether we can even have different such “pointer bits interpretation strategies” for different (unlifted) data types.

[treeowl]

Yes, we agree. I don't see any issue with having different tag interpretation strategies in this context; the tagging itself is essentially the same, right?

[AndreasPK]

What I don't know is whether we can even have different such “pointer bits interpretation strategies” for different (unlifted) data types.

If it comes with a requirement for the type to be statically know we can. Otherwise probably not in a way that's desirable.

EDIT2: Is there a Box# :: Type -> UnliftedType which actually doesn't add indirection? Just makes type "strict" (i.e. value of Box# a are never a thunk)?

I argued we should have such a thing in the past but GHC currently doesn't support anything like that.

---

If I understand this proposal correctly the goal here is to enable Maybe-like behaviour without the cost of the indirection. I think something in that direction is possible but as others already pointed out it causes problems with getTag#. I know @clyring has a proposal somewhere that would make getTag a method of a "magic" dictionary.

This would prevent getTag from working in a polymorphic context but allow this distinguished value optimization.

Because the implementation for any such type could be given a special method that returns the semantically correct tag eve if operationally we have a different tag.

That is we could have interface along the lines of:

mkDistinguishedValue :: Proxy (WithDistinguishedValue a) -> WithDistinguishedValue a
wrapWithDistinguishedValue :: a -> WithDistinguishedValue a

isDistinguishedValue :: WithDistinguishedValue a -> Bool

instance GetTag (WithDistinguishedValue a) where
  getTag x = if isDistinguishedValue x then 1 else 2

I see two possible ways to implement this sort of thing:

Using one definite "distinguishedValue" that is statically allocated once and for all and used by all types. Which would break if one would nest WithDistinguishedValue so we would have to restrict the type of a to non-WithDistinguishedValue types.
It would basically be a less cursed version of this CursedMaybe implementation I came up with some time ago: https://twitter.com/AndreasK_Tweets/status/1545112873290153991 (which was broken any many non-obvious different ways in different contexts).

Using one definite "distinguishedValue" for every concrete data type. This could be done implicitly by having WithDistinguishedValue be a derivable typeclass where the instance contains the distinguished value. This wouldn't be much different from what Typeable does and I think that's more or less what rusts implementation does.

[clyring]

This has also been previously discussed at ghc issue 21726, and perhaps elsewhere.

The library code makes a hidden assumption that there any two Null values will compare pointer-equal. Today, this assumption is wrong: A compact region can create a fresh Null.

If I understand this proposal correctly the goal here is to enable Maybe-like behaviour without the cost of the indirection. I think something in that direction is possible but as others already pointed out it causes problems with getTag#. I know @clyring has a proposal somewhere that would make getTag a method of a "magic" dictionary.

This is haskell/core-libraries-committee#104, which has been accepted. So there's no problem with giving getTag a different implementation for some types.

Could GHC automatically apply this optimization to any unlifted data type (ping @sgraf812) that contains of at most one data constructor with exactly one lifted argument, and arbitrary many nullary constrictors.

Then GHC could implement them as you describe: static pointers for the nullary ones, and simply the underlying argument pointer for the lifted constructor.

And because this data type has a different kind than the types you can nest within, there is no risk of confusion with nested Nothings.

For there to be no risk of confusion, the unlifted Nothing cannot ever become the value of a lifted variable. That means this idea is incompatible with strict box denesting without some awkward restrictions on the latter.

There is a version of this idea that should be safe: Representing an unboxed sum (# (# #) | SomeBoxedType #) with a single pointer. We can't currently store such a thing in a boxed array, but perhaps that can change.

---

I'll also mention that in a less polymorphic context there are usually efficient designs available for working with null-like dummy values that don't need unsafeCoerce# hacks today. Here's one that I previously came up with in the context of Kmett's structs library:

data RawObject n s where
  Obj :: SmallMutableArray# s Any -> RawObject n s
  Null :: RawObject MaybeNull s

newtype Object s = MkObject (forall n. RawObject n s)
newtype NullableObject s = MkNullable (RawObject MaybeNull s)

runObject :: Object s -> SmallMutableArray# s Any
runObject (MkObject v) = case v @DefinitelyNotNull of
  Obj a -> a

toNullable :: Object s -> NullableObject s
toNullable (MkObject v) = MkNullable (v @MaybeNull)

[treeowl]

The library code makes a hidden assumption that there any two Null values will compare pointer-equal. Today, this assumption is wrong: A compact region can create a fresh Null.

Yuck! Why not check for staticness when compacting?

[AndreasPK]

The library code makes a hidden assumption that there any two Null values will compare pointer-equal. Today, this assumption is wrong: A compact region can create a fresh Null.

Yuck! Why not check for staticness when compacting?

Static regions can only point to data within the region by design as far as I know. Iirc this is so that it can be stored/loaded to outside the heap. So even if we check it would entail some code randomly failing to compact. Which isn't all that promising.

[treeowl]

@AndreasPK I don't understand. Compact regions can only be inspected by identical binaries, which I imagine should have identical static data in identical places.

[clyring]

The library code makes a hidden assumption that there any two Null values will compare pointer-equal. Today, this assumption is wrong: A compact region can create a fresh Null.

It seems I was wrong about this: The compaction code can and does sometimes copy static data but it tries not to for things that cannot reference a CAF. My apologies for presenting this mis-information. I remember testing this at some point but perhaps I made a mistake while so doing.

(Mind, it's not entirely obvious to me that it is even feasible to not clone static data: Remember that deserialization of compact objects needs to perform a pointer-fixup pass because in general the deserialized blocks can end up at different locations in memory than they were for the original serialized compact object.)

Maybe this unsafeCoerce#/reallyUnsafePtrEquality# way of using Nulls is currently safe. But GHC's runtime is complex and I'm still not confident we actually enforce this no-duplicate-Nulls guarantee everywhere.