Sum Types - first draft

[Richard (Rikki) Andrew Cattermole]

On 11/09/2024 5:23 AM, Paul Backus wrote:
> On Tuesday, 10 September 2024 at 17:05:49 UTC, Walter Bright wrote:
>> Thanks for your detailed response. Let me address just one for the 
>> moment:
>>
>> On 9/10/2024 9:20 AM, Paul Backus wrote:
>>>> * std.sumtype cannot optimize the tag out of existence, for example, 
>>>> when having:
>>>>
>>>>       enum Option { None, int* Ptr }
>>>
>>> A built-in sum type would not be able to do this either, because in 
>>> D, every possible sequence of 4 bytes is a potentially-valid int* value.
>>>
>>> The reason Rust is able to perform this optimization is that Rust has 
>>> non-nullable reference types [2]. If D had non-nullable pointer 
>>> types, then std.sumtype could perform the same optimization using 
>>> reflection and `static if`.
>>
>> I was approaching it from the other way around. Isn't a non-nullable 
>> pointer a sumtype? Why have both non-nullable types and sumtypes?
> 
> You have it exactly backwards. A _nullable_ pointer type is the sum of a 
> non-nullable pointer type and typeof(null).
> 
> A non-nullable pointer type is a pointer type with its range of valid 
> values restricted. You could think of it as a "difference type"--if you 
> take T*, and _subtract_ typeof(null) from it (i.e., take the set 
> difference [1] of their values), you get a non-nullable pointer type.
> 
> [1] 
> https://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement

Yes, Paul is correct.

A non-null pointer is guaranteed by the compiler (at compile time), that 
it may ONLY point to a valid value that is directly usable.

A nullable pointer replaces guarantees for UNCERTAINTY.

It could point to unmapped memory (i.e. null), junk, or something 
completely different. The only guarantee is that the pointer itself 
exists, what it holds is entirely unknown.

To resolve this you introduce type state analysis to make guarantees of 
non-null. Which I have wanted for quite a while now. The amount of 
uncertainty for pointers in D right now are not good enough if you want 
to guarantee memory safety.

An interesting paper on this subject is [Blame for 
Null](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2020.3).

It reviews a number of languages, and proves using lambda calculus that 
only nullable pointers can introduce runtime errors (null dereferencing).

Of note is that sum types are only discussed as an implementation detail 
of Scala.

"
Keeping λnull simple. We could reduce the number of function types and 
avoid the need for safe applications through a combination of sum types 
and case analysis. For example, in Scala nullable values are represented 
with sum types (e.g. a nullable string has type String | Null). The case 
analysis in turn requires support for flow-typing:
"