On Fri, Jan 18, 2019 at 12:45:19AM +0100, Johannes Loher via Digitalmars-d wrote:
> Am 18.01.19 um 00:34 schrieb H. S. Teoh:
[...]
> > In any case, coming back to TBottom*, another issue that makes me wary of defining TBottom* == void is the top pointer `void*`.  Since any pointer implicitly converts to `void*`, this means TBottom* implicitly converts to `void*` too, which in turn means `void` should also implicitly convert to `void*`:
> > 
> > 	void procedure(...) { }
> > 
> > 	void* ptr = procedure(...); // valid if TBottom* == Unit == void
> > 
> > I think the problems that such a construct would cause would far outweigh whatever benefits that we may have reaped from introducing Unit and Bottom types!
> 
> You are absolutely correct. I don't think it makes any sense to define `void` to be `Tbottom*` if we don't fix the problem with `void*`.
[...]

Well, void* is simply a bad name for Any*, where Any is the top type. Even if we fix void* by renaming it to Any* (so that `void*` actually means a pointer to a unit type, whatever we decide that would be), we still have the problem of the chain of implicit conversions:

	void --> TBottom* --> Any*

so as long as you define void == TBottom*, you have the weirdness:

	void procedure(...) {}
	Any* ptr = procedure();
	// subsequent fun with casting and dereferencing ptr.

This is why I don't think we should define void == TBottom*, even though
both are ostensibly unit types.  Besides, following the same logic, one
would have to conclude typeof(null) == void too (since typeof(null) also
only contains a single value), which leads to other weird situations.


Anyway, you brought up an excellent point that D's types are not structural types. So perhaps pointers, including TBottom*, aren't as simple as we thought they were.  Perhaps we could analyze pointers as having an implicit (and unrepresented) component identifying themselves as a pointer type, in addition to holding the pointer value itself. If you will, they're a product type of an atomic isPointer object with the pointer value to their specified type.  So TBottom* isn't the same as the real unit type, which conveys no information; it (implicitly) conveys the information that it is a pointer, so it may be distinguished from the unit type as being the product of isPointer with Unit, not just Unit itself.

Then we can still define void as the unit type, and TBottom* would be a distinct type that always has the (explicit) value null (with an associated implicit isPointer attribute).  Dereferencing TBottom* would then be identical to dereferencing null, which should cause a runtime abort.

(And similarly, empty structs would not be true unit types either, but product types of their names with the types of their fields. True product types in the type theoretic sense would have to be anonymous structs or entities like std.typecons.Tuple.)

Or alternatively, we can think of TBottom* as a *decorated* type (decorated with isPointer or TBottom as the type of its target) that is to be distinguished from the (undecorated) true unit type. Similarly with named empty structs.


T

-- 
Too many people have open minds but closed eyes.

Am 18.01.19 um 01:17 schrieb H. S. Teoh:
> 
> Well, void* is simply a bad name for Any*, where Any is the top type. Even if we fix void* by renaming it to Any* (so that `void*` actually means a pointer to a unit type, whatever we decide that would be), we still have the problem of the chain of implicit conversions:
> 
> 	void --> TBottom* --> Any*
> 
> so as long as you define void == TBottom*, you have the weirdness:
> 
> 	void procedure(...) {}
> 	Any* ptr = procedure();
> 	// subsequent fun with casting and dereferencing ptr.
> 
> This is why I don't think we should define void == TBottom*, even though
> both are ostensibly unit types.  Besides, following the same logic, one
> would have to conclude typeof(null) == void too (since typeof(null) also
> only contains a single value), which leads to other weird situations.

I actually think this is ok. I don't reall have an issue with it. But I am also not convinced that we _need_ to do it that way. As I mentioned ealier, Kotlin for example does not do this (you have to replace pointers with optional types). They have distinct `Unit` and `Nothing?` types and this is fine in my opinion.

On the other hand, I definitely think we should make `Tbottom* ==
typeof(null)`.

>
> Anyway, you brought up an excellent point that D's types are not structural types. So perhaps pointers, including TBottom*, aren't as simple as we thought they were.  Perhaps we could analyze pointers as having an implicit (and unrepresented) component identifying themselves as a pointer type, in addition to holding the pointer value itself. If you will, they're a product type of an atomic isPointer object with the pointer value to their specified type.  So TBottom* isn't the same as the real unit type, which conveys no information; it (implicitly) conveys the information that it is a pointer, so it may be distinguished from the unit type as being the product of isPointer with Unit, not just Unit itself.
> 
> Then we can still define void as the unit type, and TBottom* would be a distinct type that always has the (explicit) value null (with an associated implicit isPointer attribute).  Dereferencing TBottom* would then be identical to dereferencing null, which should cause a runtime abort.
> 
> (And similarly, empty structs would not be true unit types either, but product types of their names with the types of their fields. True product types in the type theoretic sense would have to be anonymous structs or entities like std.typecons.Tuple.)
> 
> Or alternatively, we can think of TBottom* as a *decorated* type (decorated with isPointer or TBottom as the type of its target) that is to be distinguished from the (undecorated) true unit type. Similarly with named empty structs.
> 
> 
> T
> 

This sounds very reasonable.

On Fri, Jan 18, 2019 at 01:13:28AM +0100, Johannes Loher via Digitalmars-d wrote:
> Am 18.01.19 um 00:53 schrieb H. S. Teoh:
> > Another case to consider: what should .typeid of Tbottom return?
> > 
> Indeed an interesting question. Since `Tbottom` is a type like any other, it needs to return an instance of TypeInfo.

Right.


> The even more interesting question is what the methods should return. Take for example `TypeInfo.equals`. Because there are no values of type `Tbottom`, any two instances of type `Tbottom` are equal and the method should return true. On the other hand, by the same argument, any two instances of `Tbottom` are not equal and the method should return false.

Actually, since there can be no instances of Tbottom, that in theory also means TypeInfo.equals should never get called.  Which means its implementation should simply be `assert(0);`.


> From a more pragmatic point of view: It does not really matter what this method returns. It does take pointers to void which internally will be cast to `Tbottom*` (becasue we are actually comparing `Tbottom`s) and then dereferencing it will simply abort the program (`null` dereferencing).

This would be consistent with the implementation of .equal being
`assert(0);`.


> I think it is similar for the other methods. Some simply return some information about the type, e.g. `talign` should return 0.

Yeah, .compares should also be `assert(0);`, not sure about .tsize: what's the size of something that doesn't exist?  I'm tempted to say .tsize should abort, but then returning 0 doesn't seem amiss either (if the instance doesn't exist, it also does not take up any space). It would help generic code not abort needlessly if they're just querying type information without actually trying to create an instance.

Certainly .swap should assert(0), .next should return null, and
.initializer should assert(0).

In fact, I wonder if making .initializer call assert(0) would be enough to implement the "initializing Tbottom == assert(0)" rule -- maybe even without the compiler specifically checking for this case!  (Though compiler checking will probably still be necessary in order to emit sane error messages at compile-time rather than seemingly-unexplained aborts at runtime. But it could be enough for an MVP.)

Then .flags... 0 I suppose?  And .offTi: null; .destroy and .postblit: assert(0).  .talign... dunno, I suppose 0 is as good a value as any other?

No idea what .argTypes is supposed to do.

.rtInfo should probably return some generic no-op information. Or should it assert(0)? Since I'd expect someone calling .rtInfo implies that they've somehow created an instance of Tbottom, which is impossible. Though it's hard to say if the GC may pre-initialize buffers or what-not based on traversing all TypeInfo's.  Don't know.


T

-- 
If you think you are too small to make a difference, try sleeping in a closed room with a mosquito. -- Jan van Steenbergen

Am 18.01.19 um 01:33 schrieb H. S. Teoh:
> .talign... dunno, I suppose 0 is as good a value as any other?

This really made me laugh :D It should be consistent with `Tbottom.alignof` obviously. The DIP suggests 1 (although the DIP calls the property `alignsize`, which doesnt exist), but I am not sure if there is any thought behind that.

> No idea what .argTypes is supposed to do.
> 
> .rtInfo should probably return some generic no-op information. Or should it assert(0)? Since I'd expect someone calling .rtInfo implies that they've somehow created an instance of Tbottom, which is impossible. Though it's hard to say if the GC may pre-initialize buffers or what-not based on traversing all TypeInfo's.  Don't know.
> 

Unfortunately I also don't know enough make a judgement here. But I believe this is something enough other people can give pragmatic suggestions for.

On Thursday, 17 January 2019 at 22:33:35 UTC, H. S. Teoh wrote:
> On Thu, Jan 17, 2019 at 09:43:52PM +0000, Jonathan Marler via Digitalmars-d wrote:
>> On Thursday, 17 January 2019 at 20:15:20 UTC, H. S. Teoh wrote:
>> > On Thu, Jan 17, 2019 at 06:51:13PM +0000, Jonathan Marler via Digitalmars-d wrote: [...]
>> > > To summarize, the bottom type allows you to declare a special pointer with no storage!
>> > > 
>> > >     TBottom*.sizeof == 0
>> > > 
>> > > This is also something that should be in the DIP and Walter should chime in with whether or not he thinks these semantics can actually be implemented.
>> > 
>> > This would introduce an asymmetry with the rest of the pointer types in the language which all have equal sizes, and this asymmetry will percolate down to other language constructs, causing special cases and inconsistencies everywhere.  I don't recommend doing this.
>> 
>> Yes that's kind of the point :)  It's a new pointer type that has a unique size from all other pointer types.  This means you can no-longer assume all pointers types are the same size, you have a special case where it's size can be zero. This might warrant some code changes to handle this case, but does enable some new semantics which can be useful for library writers.  Case in point was you can now have a template parameter T* that the user can instantiate in such a way as to eliminate the pointer alltogether.
>
> No, that's backwards.  (1) Introducing asymmetry, i.e., special cases, is bad, because inevitably people will forget to check for it, leading to endless bugs. It will also percolate all over the language, creating exceptions and new corner cases, which are what we're trying to *reduce* here.

This is definitely not true in all cases, therefore, is itself not a valid argument.

(2) Eliminating a
> field is achieved by passing in a Unit type, not a Bottom type. E.g., if you have a struct template:
>
> 	struct S(T, U) {
> 		T t;
> 		U u;
> 	}
>
> then you could instantiate a single-field struct by doing:
>
> 	S!(Unit, int) s;
> 	// Equivalent to: struct { int u; }
>
> or:
>
> 	S!(string, Unit) t;
> 	// Equivalent to: struct { string t; }
>
> Instantiating it with Bottom means forcing a compile error (or runtime
> abort).
>


Checkout this comment: https://forum.dlang.org/post/zxkgzziaoygkynqndpds@forum.dlang.org


>
>> > A better approach might be to make TBottom* always equal to null -- i.e., it's always illegal to dereference it because no instances of TBottom can exist.
>> > 
>> 
>> That's conceptually the same thing.  Saying that TBottom* is "always equal to null" is the same as saying it's a Unit Type, which is the same as saying that it contains no information so the storage needed is 0 (same as void).
>
> I'm not so sure about that.  A true Unit type conveys no information, yet TBottom* conveys at least this information: that it's a pointer, and that the pointer cannot be dereferenced.  A true Unit type would be the return type of a void function; would you equate TBottom* with the return type of a void function?  That would be very strange indeed.
>
>
> T

You're mixing up what you know about programming languages like C/C++ and D with type theory.  TBottom* by definition is a unit type.  It is a pointer to nothing, which can only ever have one value.  It may not "seem" like a unit type, but when you spend enough time in set theory and logic you'll find most things are not what they seem.

Note that there are multiple ways to express and define a unit type. I suggest you read up on the definitions of these types and try to understand them a bit more, it becomes much clearer once you do.

On Thu, 17 Jan 2019 14:21:45 -0800, H. S. Teoh wrote:
> If instead we allow the declaration of `Bottom var;`, with the stipulation that it corresponds with the runtime code for halting the program (e.g., assert(0)), then the implementor of func wouldn't even have to think about the possibility of T == Bottom.  When the user passes Bottom to func, the function naturally just aborts where var is declared.

This is also an asymmetry: the following two functions abort at different places only when passed TBottom. In fact, they only abort when passed TBottom.

void foo1(T)()
{
  writeln("line 1");
  T value = void;
  writeln("line 2");
}
void foo2(T)()
{
  T value = void;
  writeln("line 1");
  writeln("line 2");
}

On Thu, 17 Jan 2019 23:07:54 +0100, Johannes Loher wrote:
> Am 17.01.19 um 22:59 schrieb Neia Neutuladh:
>> On Thu, 17 Jan 2019 12:15:20 -0800, H. S. Teoh wrote:
>>> A better approach might be to make TBottom* always equal to null -- i.e., it's always illegal to dereference it because no instances of TBottom can exist.
>> 
>> Dereferencing TBottom* would have to be rewritten as `assert(false);` to make this type of illegal work with generic code.
>> 
> No, dereferencing an instance of type `Tbottom*` is always dereferencing
> `null`, i.e. programm abbortion (which is not the same as `assert(0)`).

Oh, I misread that as "assume that TBottom* is null", sorry. Forcibly converting it to null also works. You would have to do that with every expression of type TBottom*, not just on cast.

On Fri, Jan 18, 2019 at 01:41:43AM +0100, Johannes Loher via Digitalmars-d wrote:
> Am 18.01.19 um 01:33 schrieb H. S. Teoh:
> > .talign... dunno, I suppose 0 is as good a value as any other?
> 
> This really made me laugh :D It should be consistent with `Tbottom.alignof` obviously. The DIP suggests 1 (although the DIP calls the property `alignsize`, which doesnt exist), but I am not sure if there is any thought behind that.
[...]

Sure, but what's the alignment of an instance that doesn't (and can't) exist?  A "nonsensical" value like 0 might not be unreasonable, since you can't actually align any instances of Tbottom, there being none of them to begin with.


T

-- 
It said to install Windows 2000 or better, so I installed Linux instead.

On Thursday, 17 January 2019 at 22:13:13 UTC, H. S. Teoh wrote:
> [...]
> This also lets us write sanity-checking expressions such as:
>
> 	float sqrt(float x) {
> 		return (x >= 0.0) ? ... /* implementation here */
> 			: Bottom.init;
> 	}
>
> This is valid since Bottom converts to any type. Then at runtime, if x < 0.0, assert(0) gets triggered.

While unrelated to the DIP discussion, I will insist that x >= 0.0 and x < 0.0 can both be wrong: x can be NaN.

On Fri, Jan 18, 2019 at 12:54:52AM +0000, Jonathan Marler via Digitalmars-d wrote:
> On Thursday, 17 January 2019 at 22:33:35 UTC, H. S. Teoh wrote:
> > On Thu, Jan 17, 2019 at 09:43:52PM +0000, Jonathan Marler via Digitalmars-d wrote:
[...]
> > > That's conceptually the same thing.  Saying that TBottom* is "always equal to null" is the same as saying it's a Unit Type, which is the same as saying that it contains no information so the storage needed is 0 (same as void).
> > 
> > I'm not so sure about that.  A true Unit type conveys no information, yet TBottom* conveys at least this information: that it's a pointer, and that the pointer cannot be dereferenced.  A true Unit type would be the return type of a void function; would you equate TBottom* with the return type of a void function?  That would be very strange indeed.
[...]
> You're mixing up what you know about programming languages like C/C++ and D with type theory.  TBottom* by definition is a unit type.  It is a pointer to nothing, which can only ever have one value.  It may not "seem" like a unit type, but when you spend enough time in set theory and logic you'll find most things are not what they seem.
[...]

I don't argue that it's not a unit type.  But that's not the same thing as saying it's *the* unit type.  There may be multiple, distinct unit types, because D types are not structural types in the type theoretic sense; for example:

	struct A { int x; }

is a distinct type from:

	struct B { int x; }

in spite of being identical product types according to type theory.  And indeed,

	struct C { }

is distinct from:

	struct D { }

in spite of both C and D being, ostensibly, "unit types".

Similarly:

	enum E1 { A }

is distinct from

	enum E2 { A }

even though they are supposedly "unit types" inhabited by the same, identical value.  (Well, actually they are logically distinct values, E1.A and E2.A according to the language spec, even if they are represented in machine code as the same integer value 0, and even if they are the only value of their respective types.)

So the mapping from the concepts of type theory to D is not as straightforward as it might appear at first glance -- at least not if you want to retain any semblance of backward compatibility. You could, I suppose, gut the entire existing system and replace it with something directly derived from type theory, with a single, unique unit type that encompassess all unit types in the language. But that would also basically break all D code in existence, which makes it not a viable approach.

At the very least, to account for the distinctness of differently-named (D) types with identical contents you'd have to decorate the (type-theoretic) type with some kind of distinguishing feature, such as something that encodes the name of the struct / enum.  Once you have that, it's not so unreasonable to also say that pointer types are inherently distinct from non-pointer types, even if a particular pointer type happens to only ever allow 1 value, just as a particular non-pointer type also only ever allows 1 value.  Nothing dictates that this single value must be the same value across the two types (I could have `enum F { A=1 }` and `enum G { A=2 }` for example).  There may exist multiple unit types that are not necessarily compatible with each other.

Which makes the idea of Tbottom* and void being distinct types a definite, well-founded possibility.  (Though whether or not it's a good idea remains to be seen.)


T

-- 
Without outlines, life would be pointless.