www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Can non-nullable references be implemented as a library?

reply "Denis Koroskin" <2korden gmail.com> writes:
Since many people think that non-nullable references can be implemented as  
a library and thus don't belong to core language, I've decided to show  
that it is in fact impossible to do so.

How do you enforce the following behavior:

class Foo
{
     this()
     {
	// error: variable nonNull not initialized
     }

     this()
     {
         nonNull.someMethod(); // error: variable used before initialized
         auto s = toString(); // error: can't call any methods before  
initialized

         nonNull = new Bar();
         s = toString(); // okay
     }

     string toString() { return nonNull.toString(); }

     NonNull!(Bar) nonNull;
}

class Bar : Foo
{
     this()
     {
         nonNull.someMethod(); // error: variable used before initialized

         super(); // initializes nonNull
         nonNull.someMethod(); // fine
     }
}

Without support of these use-cases NonNull!(T) is useless.

There can be other examples, but I think these are enough to prove that  
non-nullable references can not be implemented in library.
Nov 07 2010
next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Denis Koroskin <2korden gmail.com> wrote:

 Since many people think that non-nullable references can be implemented  
 as a library and thus don't belong to core language, I've decided to  
 show that it is in fact impossible to do so.

 How do you enforce the following behavior:

 Without support of these use-cases NonNull!(T) is useless.

 There can be other examples, but I think these are enough to prove that  
 non-nullable references can not be implemented in library.

Indeed. There is also the arrays I've mentioned before, and as you mention here, fields of classes and structs. Good catch. -- Simen
Nov 07 2010
next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Simen kjaeraas <simen.kjaras gmail.com> wrote:

 Denis Koroskin <2korden gmail.com> wrote:

 Since many people think that non-nullable references can be implemented  
 as a library and thus don't belong to core language, I've decided to  
 show that it is in fact impossible to do so.

 How do you enforce the following behavior:

 Without support of these use-cases NonNull!(T) is useless.

 There can be other examples, but I think these are enough to prove that  
 non-nullable references can not be implemented in library.

Indeed. There is also the arrays I've mentioned before, and as you mention here, fields of classes and structs. Good catch.

Worth adding: Even if non-null references/pointers cannot be perfectly implemented in a library, they may still be a worthwhile addition to Phobos, to mark function arguments and the like. -- Simen
Nov 07 2010
parent reply Kagamin <spam here.lot> writes:
Simen kjaeraas Wrote:

 Worth adding:
 Even if non-null references/pointers cannot be perfectly implemented in a
 library, they may still be a worthwhile addition to Phobos, to mark
 function arguments and the like.

Hmm... this doesn't work: struct NonNull(T) { T value; this(T v) { assert(value); value=v; } } class A {} void foo(NonNull!A a){} void goo() { A a=new A(); foo(a); } test.d(23): Error: function test.foo (NonNull!(A) a) is not callable using argument types (A) test.d(23): Error: cannot implicitly convert expression (a) of type test.A to NonNull!(A)
Nov 07 2010
next sibling parent reply Adam Burton <adz21c gmail.com> writes:
Kagamin wrote:

 Simen kjaeraas Wrote:
 
 Worth adding:
 Even if non-null references/pointers cannot be perfectly implemented in a
 library, they may still be a worthwhile addition to Phobos, to mark
 function arguments and the like.

Hmm... this doesn't work: struct NonNull(T) { T value; this(T v) { assert(value); value=v; } } class A {} void foo(NonNull!A a){} void goo() { A a=new A(); foo(a); } test.d(23): Error: function test.foo (NonNull!(A) a) is not callable using argument types (A) test.d(23): Error: cannot implicitly convert expression (a) of type test.A to NonNull!(A)

nullable so you force the user to assess that is correct and provide an override. Based on that I've had a crack at this myself. http://myweb.tiscali.co.uk/adz21c/nonnull.d http://myweb.tiscali.co.uk/adz21c/test.d Upto now I've only concentrated on mutable class references, but I figured I would post what I have up to now and see what people think. I've pulled NonNull (NN to save my fingers) construction out into a separate function. toNN performs the runtime null check rather than the struct constructor. This allows us to use opAssign to convert NN!Derived to NN!Super without a null check, you only check for nulls when crossing from the nullable world to non-nullable using toNN. It also means code like below is not possible without explicitly saying I want to cross from nullable to non-nullable (using toNN) which offers some sort of compile time check (not as good as a compiler checking for "if is null" but it is something). A a = null; NN!A b = a; // will not compile NN!A b = toNN(a); // inserts the null runtime check NN!A c = b; // No null check as there is no need. I've attempted where possible to try and keep it looking like a reference (as you can see above). So far I have come across a few snags in my plan. 1. Default struct constructor. This means the NN can be created without assigning a value. I have tried to get around this issue somewhat by adding a null check in the invariant but it seems the invariant is not called when using the default constructor. Should it be or should it not? If it is then atleast while contracts are enabled we get to know about uninitialised NNs. 2. opAssign and alias this on function parameters a. For assignment I used opAssign to perform a conversion from NN!B to NN!A. This doesn't work for function parameters of NN!A when passing NN!B so I am forced to use toNN adding unnecessary runtime check and nasty looking code. b. When passing NN!A to A I assume the alias this kicks in and passes NN!A.value to A. However on function parameters this is not happening so I am forced to manually call NN!A.value. 3. Assigning new gets checked Below is annoying, clearly it does not need a null check. NN!A a = toNN(new A()); I figure a function that does not do a null check *could* be offered for this situation, but unfortunately that also destroys whatever guarantuees you get with NN. The other idea I have had is somehow passing in the "new A()" as an expression and evaluating if the expressions purpose is to create an object then remove the null check, but I don't know how to do that. 4. Double checking nulls foo(A a) { if (a is null) // check one doSomething(); else bar(toNN(a)); // check two } bar(NN!A a) {} If the user checks for null before assigning nullables to NN then 2 null checks are performed, one by the user and another by toNN. Would the compiler be smart enough to remove the redundancy? If not then the only way round it I can see is allow a delegate to be passed to toNN which holds the isnull code path. Problem with this is I think it would make code quite difficult to read. Otherwise we suck it up. 5. Consider if someone is altering code with toNN in it, the toNN will hide a bug (if they removed a required check) till runtime that could be identified at compile time. But I guess thats the diff between a library version and compiler version. At least the code will die earlier at runtime though. Thoughts up to now? Am I barking up completely the wrong tree?
Nov 07 2010
next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
Adam Burton wrote:
 Thoughts up to now? Am I barking up completely the wrong tree?

I think it's a good start on figuring this out.
Nov 07 2010
prev sibling parent reply Kagamin <spam here.lot> writes:
Adam Burton Wrote:

 The above seems correct to me. You are assigning a nullable to a non-
 nullable so you force the user to assess that is correct and provide an 
 override. Based on that I've had a crack at this myself.

This becomes not just an annotation, but another type. When you pass argument by ref, you don't have to convert it to ref, you just pass it.
 NN!Super without a null check, you only check for nulls when crossing from 
 the nullable world to non-nullable using toNN. It also means code like below 
 is not possible without explicitly saying I want to cross from nullable to 
 non-nullable (using toNN) which offers some sort of compile time check (not 
 as good as a compiler checking for "if is null" but it is something).
 
 A a = null;
 NN!A b = a;	// will not compile
 NN!A b = toNN(a);	// inserts the null runtime check
 NN!A c = b; // No null check as there is no need.

This way or another, you need a null check. Why extra syntax?
Nov 07 2010
parent Adam Burton <adz21c gmail.com> writes:
Kagamin wrote:

 Adam Burton Wrote:
 
 The above seems correct to me. You are assigning a nullable to a non-
 nullable so you force the user to assess that is correct and provide an
 override. Based on that I've had a crack at this myself.

This becomes not just an annotation, but another type. When you pass argument by ref, you don't have to convert it to ref, you just pass it.

attempt to also get a basic NN compile-time check.
 
 NN!Super without a null check, you only check for nulls when crossing
 from the nullable world to non-nullable using toNN. It also means code
 like below is not possible without explicitly saying I want to cross from
 nullable to non-nullable (using toNN) which offers some sort of compile
 time check (not as good as a compiler checking for "if is null" but it is
 something).
 
 A a = null;
 NN!A b = a;	// will not compile
 NN!A b = toNN(a);	// inserts the null runtime check
 NN!A c = b; // No null check as there is no need.

This way or another, you need a null check. Why extra syntax?

explicitly authorise. I thought that is a key part of the NN feature request. Granted with a template I can't get it inspecting the code around it for null checks but by making the cross from null to NN explicit it can help people potentially catch code where they've maybe not fully assessed the impact of the potential null floating around their code.
Nov 08 2010
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, November 07, 2010 18:42:08 Adam Burton wrote:
 1. Default struct constructor.
 This means the NN can be created without assigning a value. I have tried to
 get around this issue somewhat by adding a null check in the invariant but
 it seems the invariant is not called when using the default constructor.
 Should it be or should it not? If it is then atleast while contracts are
 enabled we get to know about uninitialised NNs.

There are no default constructors for structs. They use init, which is known at compile-time, so there is no constructor for the invariant to be called after. It's quite easy to create structs which pass their invariant when you construct them with a constructor but whose init fails the invariant. The fact that the invariant gets called before opAssign() doesn't help either: http://d.puremagic.com/issues/show_bug.cgi?id=5058 The result is that at this point, you pretty much either need to have init pass your invariant or have no invariant. - Jonathan M Davis
Nov 08 2010
prev sibling parent reply so <so so.do> writes:
 This way or another, you need a null check. Why extra syntax?

This is also how it is done in those languages no? They also have null checks at every assignment, but since compiler puts those lines, you don't know anything. Maybe this is not what you mean? -- Using Opera's revolutionary email client: http://www.opera.com/mail/
Nov 08 2010
parent Kagamin <spam here.lot> writes:
so Wrote:

 This way or another, you need a null check. Why extra syntax?

This is also how it is done in those languages no? They also have null checks at every assignment, but since compiler puts those lines, you don't know anything. Maybe this is not what you mean?

Do you care about performance? If you zealously design with non-nulls, you won't have too many checks.
Nov 08 2010
prev sibling next sibling parent reply steveh <steveh57 useshotmai.l> writes:
Denis Koroskin Wrote:

 Since many people think that non-nullable references can be implemented as  
 a library and thus don't belong to core language, I've decided to show  
 that it is in fact impossible to do so.
 
 How do you enforce the following behavior:
 
 class Foo
 {
      this()
      {
 	// error: variable nonNull not initialized
      }
 
      this()
      {
          nonNull.someMethod(); // error: variable used before initialized
          auto s = toString(); // error: can't call any methods before  
 initialized
 
          nonNull = new Bar();
          s = toString(); // okay
      }
 
      string toString() { return nonNull.toString(); }
 
      NonNull!(Bar) nonNull;
 }
 
 class Bar : Foo
 {
      this()
      {
          nonNull.someMethod(); // error: variable used before initialized
 
          super(); // initializes nonNull
          nonNull.someMethod(); // fine
      }
 }
 
 Without support of these use-cases NonNull!(T) is useless.
 
 There can be other examples, but I think these are enough to prove that  
 non-nullable references can not be implemented in library.

Andrei's stance is, either a library addon or ship D without that feature. D's library already contains both tuples and algebraic data types. They're simple to use, almost like in Python. The reason for library addons isn't that builtin features make less sense, the reason is that TDPL is already out and we can't improve the language in any radical way.
Nov 07 2010
next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Sun, 07 Nov 2010 20:21:49 +0300, steveh <steveh57 useshotmai.l> wrote:

 Andrei's stance is, either a library addon or ship D without that  
 feature. D's library already contains both tuples and algebraic data  
 types. They're simple to use, almost like in Python. The reason for  
 library addons isn't that builtin features make less sense, the reason  
 is that TDPL is already out and we can't improve the language in any  
 radical way.

People have proposed syntax that won't break existing code (e.g. T vs T). It also means T is still nullable by default, and that's good enough for me. Better than nothing anyway. In addition, I really hope there will be TDPL 2nd edition some day.
Nov 07 2010
prev sibling next sibling parent reply so <so so.do> writes:
 Andrei's stance is, either a library addon or ship D without that  
 feature. D's library already contains both tuples and algebraic data  
 types. They're simple to use, almost like in Python. The reason for  
 library addons isn't that builtin features make less sense, the reason  
 is that TDPL is already out and we can't improve the language in any  
 radical way.

Lets talk about solution in this thread more than politics, politics "never" improve anything. Also It is not only Andrei, every single people here agreed on stopping "lets add this new feature to D today". For the topic, i am trying to understand the use cases and implementations in other languages first. D was born to solve problems right? If supporting a feature looks/is impossible for user we should improve the language to help us solve this not just add the specific feature. You know there'll never be enough features :) -- Using Opera's revolutionary email client: http://www.opera.com/mail/
Nov 07 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
so:

 Also It is not only Andrei, every single people here agreed on stopping  
 "lets add this new feature to D today".

What's stopped is adding features to D2, but I have meant nonull types for D3. I don't think D evolution is finished right now. On the other hand new features add complexity, so they may refused in many cases (there are several other things that may be added to D3, like macros, pattern matching, integral overflows, ranged integrals, etc. But some such features add a lot of complexity to a language that's not simple already).
 If supporting a feature looks/is impossible for user we should improve the  
 language to help us solve this not just add the specific feature.
 You know there'll never be enough features :)

Are you saying that D may be improved to allow defining good enough nonnull types in user code? This is possible, but it's very hard. It requires macros and a powerful type system that's probably beyond what D will ever hope to have, because maybe not even CommonLips macros are enough for this (and even if such changes will be implemented, the resulting language will be harde to use as ATS or more, I don't think lot of people here will be happy with it). So to not increase the language complexity too much, some features need to be implemented at front-end level. It's a matter of trade-offs. Bye, bearophile
Nov 07 2010
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
retard:

 There are these DIPs in wiki4d. Were they useful? At least it seems that 
 this thread is leading nowhere. Half of the people don't know what non-
 nullable means. It's hard to trust this process when it seems to go 
 nowhere. No one wants to validate the design decisions.

If a language feature is too much complex to understand&design for the community of people that use the language, then it may be better to not add that feature to the language. Maybe nonnullabile types are too much complex to design for D. Even D2 immutability and D1 type system seem borderline to the max complexity of things that may be added to D. The design of the module system and immutability have some important holes still. Bye, bearophile
Nov 07 2010
parent bearophile <bearophileHUGS lycos.com> writes:
retard:

 I bet even the basic class/interface/exception system of D is too complex 
 to explain for some members of the audience. You can't assume that the 
 same people who *use* the language can/want to understand the 
 implementation of the features.

You are right. The people that use the language&compiler don't need to understand it fully. So are nonnull references too much hard to use? Their syntax is simple. The limited typestate they need to be implemented well is easy to use by the programmer. The initialization of collections is simple enough to understand, in my opinion. So what's left is the delayed types. So in the end I think that you are right, once well implemented the nonnullables in D may be usable by normal programmers, despite they add some complexity to the language. Bye, bearophile
Nov 07 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/7/10 1:54 PM, retard wrote:
 Sun, 07 Nov 2010 19:39:09 +0200, so wrote:

 Andrei's stance is, either a library addon or ship D without that
 feature. D's library already contains both tuples and algebraic data
 types. They're simple to use, almost like in Python. The reason for
 library addons isn't that builtin features make less sense, the reason
 is that TDPL is already out and we can't improve the language in any
 radical way.

Lets talk about solution in this thread more than politics, politics "never" improve anything.

There was this other thread here -- "why a part of d community do not want to go to d2?" One reason is, there's no good process for handling these feature proposals. Walter attends useless bikeshed discussions and spreads misinformation about things he doesn't get, Andrei has excellent knowledge of languages but he often prefers staying in the background. There are these DIPs in wiki4d. Were they useful? At least it seems that this thread is leading nowhere. Half of the people don't know what non- nullable means.

In all honesty, the distribution of those who don't understand non-null is about equal across the proponents and the opponents :o).
 It's hard to trust this process when it seems to go
 nowhere. No one wants to validate the design decisions.

This thread does have a good outcome: Walter will at least consider improving flow analysis in constructors to support disable'd default constructors. That is the key improvement that allows NonNull as a library. Andrei
Nov 07 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Andrei:

 This thread does have a good outcome: Walter will at least consider 
 improving flow analysis in constructors to support  disable'd default 
 constructors. That is the key improvement that allows NonNull as a library.

Good :-) Bye, bearophile
Nov 07 2010
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/7/10 11:34 PM, spir wrote:
 On Sun, 07 Nov 2010 19:12:02 -0600
 Andrei Alexandrescu<SeeWebsiteForEmail erdani.org>  wrote:

 On 11/7/10 1:54 PM, retard wrote:
 Sun, 07 Nov 2010 19:39:09 +0200, so wrote:

 Andrei's stance is, either a library addon or ship D without that
 feature. D's library already contains both tuples and algebraic data
 types. They're simple to use, almost like in Python. The reason for
 library addons isn't that builtin features make less sense, the reason
 is that TDPL is already out and we can't improve the language in any
 radical way.

Lets talk about solution in this thread more than politics, politics "never" improve anything.

There was this other thread here -- "why a part of d community do not want to go to d2?" One reason is, there's no good process for handling these feature proposals. Walter attends useless bikeshed discussions and spreads misinformation about things he doesn't get, Andrei has excellent knowledge of languages but he often prefers staying in the background. There are these DIPs in wiki4d. Were they useful? At least it seems that this thread is leading nowhere. Half of the people don't know what non- nullable means.

In all honesty, the distribution of those who don't understand non-null is about equal across the proponents and the opponents :o).

Perhaps a great help would be to approach it so-to-say backwards: option types à la Haskell http://en.wikipedia.org/wiki/Option_type

That would be Algebraic.
 (The fact that our pointers are nullable by default makes it difficult to
imagine the opposited pov, I guess.)

Agreed. Andrei
Nov 08 2010
prev sibling next sibling parent retard <re tard.com.invalid> writes:
Sun, 07 Nov 2010 19:39:09 +0200, so wrote:

 Andrei's stance is, either a library addon or ship D without that
 feature. D's library already contains both tuples and algebraic data
 types. They're simple to use, almost like in Python. The reason for
 library addons isn't that builtin features make less sense, the reason
 is that TDPL is already out and we can't improve the language in any
 radical way.

Lets talk about solution in this thread more than politics, politics "never" improve anything.

There was this other thread here -- "why a part of d community do not want to go to d2?" One reason is, there's no good process for handling these feature proposals. Walter attends useless bikeshed discussions and spreads misinformation about things he doesn't get, Andrei has excellent knowledge of languages but he often prefers staying in the background. There are these DIPs in wiki4d. Were they useful? At least it seems that this thread is leading nowhere. Half of the people don't know what non- nullable means. It's hard to trust this process when it seems to go nowhere. No one wants to validate the design decisions.
Nov 07 2010
prev sibling next sibling parent retard <re tard.com.invalid> writes:
Sun, 07 Nov 2010 17:06:12 -0500, bearophile wrote:

 retard:
 
 There are these DIPs in wiki4d. Were they useful? At least it seems
 that this thread is leading nowhere. Half of the people don't know what
 non- nullable means. It's hard to trust this process when it seems to
 go nowhere. No one wants to validate the design decisions.

If a language feature is too much complex to understand&design for the community of people that use the language, then it may be better to not add that feature to the language. Maybe nonnullabile types are too much complex to design for D. Even D2 immutability and D1 type system seem borderline to the max complexity of things that may be added to D. The design of the module system and immutability have some important holes still.

I bet even the basic class/interface/exception system of D is too complex to explain for some members of the audience. You can't assume that the same people who *use* the language can/want to understand the implementation of the features. Of course it's benefical to understand how everything works, but in some practical tasks 1) you write some high level code 2) compile it 3) analyze the output (the generated binary) and 4) perhaps hand optimize some parts. You don't need to understand what the compiler actually did in all phases.
Nov 07 2010
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On Sun, 07 Nov 2010 19:12:02 -0600
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

 On 11/7/10 1:54 PM, retard wrote:
 Sun, 07 Nov 2010 19:39:09 +0200, so wrote:

 Andrei's stance is, either a library addon or ship D without that
 feature. D's library already contains both tuples and algebraic data
 types. They're simple to use, almost like in Python. The reason for
 library addons isn't that builtin features make less sense, the reason
 is that TDPL is already out and we can't improve the language in any
 radical way.

Lets talk about solution in this thread more than politics, politics "never" improve anything.

There was this other thread here -- "why a part of d community do not want to go to d2?" One reason is, there's no good process for handling these feature proposals. Walter attends useless bikeshed discussions and spreads misinformation about things he doesn't get, Andrei has excellent knowledge of languages but he often prefers staying in the background. There are these DIPs in wiki4d. Were they useful? At least it seems that this thread is leading nowhere. Half of the people don't know what non- nullable means.

In all honesty, the distribution of those who don't understand non-null=20 is about equal across the proponents and the opponents :o).

Perhaps a great help would be to approach it so-to-say backwards: option ty= pes =C3=A0 la Haskell http://en.wikipedia.org/wiki/Option_type (The fact that our pointers are nullable by default makes it difficult to i= magine the opposited pov, I guess.) Denis -- -- -- -- -- -- -- vit esse estrany =E2=98=A3 spir.wikidot.com
Nov 07 2010
prev sibling parent spir <denis.spir gmail.com> writes:
On Sun, 07 Nov 2010 18:12:50 -0500
bearophile <bearophileHUGS lycos.com> wrote:

 retard:
=20
 I bet even the basic class/interface/exception system of D is too compl=


 to explain for some members of the audience. You can't assume that the=


 same people who *use* the language can/want to understand the=20
 implementation of the features.

You are right. The people that use the language&compiler don't need to un=

ntax is simple. The limited typestate they need to be implemented well is e= asy to use by the programmer. The initialization of collections is simple e= nough to understand, in my opinion. So what's left is the delayed types. So= in the end I think that you are right, once well implemented the nonnullab= les in D may be usable by normal programmers, despite they add some complex= ity to the language. I'm unsure of that. For the implementation, sure; but are all wasinhg machi= ne users specialists in fluid dynamics? The semantic side on the other hand= seems clean to me (or, maybe I don't get it right myself). Imagine pointers in a language where one cannnot declare vars without init.= Then, one would either make one pointer point to an existing var, or to a = newly allocated "target cell"; itself initialised explicitely (or by the la= nguage's init value for that type). Something like auto p =3D &n; auto p =3D &(new int =3D 1); auto p =3D &(new int); // *p =3D=3D 0 Then, you have no null ref. Or do I miss a point? An equivalent of the seco= nd form is verboten in D, I guess, because there is no lvalue. It could be = avoided by requiring a temp var for the target. By the way, is it always possible to avoid pointer declarations without ini= t, or are there cases where one must have this feature? In other words, is = the whole null-ref feature just convenience? Denis -- -- -- -- -- -- -- vit esse estrany =E2=98=A3 spir.wikidot.com
Nov 07 2010
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/7/10 11:13 AM, Denis Koroskin wrote:
 Since many people think that non-nullable references can be implemented
 as a library and thus don't belong to core language, I've decided to
 show that it is in fact impossible to do so.

Changes are necessary to constructors. Andrei
Nov 07 2010