Non-null reference types

[André van Delft]

There are two ways to handle missing data in Scala: variables of reference type may hold null, and there is Option[T].

However, there is no statically checked way to prevent a reference variable from holding null. Such a prevention would often make sense, e.g. for most uses of Option[T].

Tony Hoare invented null references, and now calls this his "billion dollar mistake". He says the solution is offered by Spec#, a proposal from Microsoft Research.

http://qconlondon.com/london-2009/presentation/Null+References:+The+Billion+Dollar+Mistake
http://research.microsoft.com/en-us/projects/specsharp/

Spec# has "non-null types" and "possibly-null types"; a possibly-null type has a question mark; assigning null to variables of non-null types would be illegal:

  string? maybeAString = null;
  string s = null; // error

This idea did not go mainstream. 
C# got a Nullable<T> with shorthand notation T?, but only for a value type T.

Neither does Scala have non-null vs possibly-null reference types. 

Could anybody explain why?

(This may be a dumb question. But I am curious, so I take the risk, even though this mail archive may last for thousands, if not millions of years)

[Daniel Sobral]

On Thu, Aug 23, 2012 at 8:37 PM, André van Delft
<andre.v...@gmail.com> wrote:
> There are two ways to handle missing data in Scala: variables of reference
> type may hold null, and there is Option[T].
>
> However, there is no statically checked way to prevent a reference variable
> from holding null. Such a prevention would often make sense, e.g. for most
> uses of Option[T].
>
> Tony Hoare invented null references, and now calls this his "billion dollar
> mistake". He says the solution is offered by Spec#, a proposal from
> Microsoft Research.
>
> http://qconlondon.com/london-2009/presentation/Null+References:+The+Billion+Dollar+Mistake
> http://research.microsoft.com/en-us/projects/specsharp/
>
> Spec# has "non-null types" and "possibly-null types"; a possibly-null type
> has a question mark; assigning null to variables of non-null types would be
> illegal:
>
> string? maybeAString = null;
> string s = null; // error
>
> This idea did not go mainstream.
> C# got a Nullable<T> with shorthand notation T?, but only for a value type
> T.
>
> Neither does Scala have non-null vs possibly-null reference types.
>
> Could anybody explain why?

http://www.scala-lang.org/archives/downloads/distrib/files/nightly/docs/library/index.html#scala.NotNull

Note, however, that if you never saw it in use, there's probably a
good reason for that. Leaving bugs aside, it's difficult to use
because there's no "propagation" of non-nullability (that is, if you
call "map" on a non-nullable type, you don't automatically get a
non-nullable type back -- the function has to annotate it is returning
NotNull. And, to make matters worse, almost nothing is tagged as
NotNull in the scala library, and you must assume any Java API
returning a reference may return a null.

Note that making NotNull more useful is one of the alternatives raised
during a discussion initiated by Odersky on optimizing Option by
turning None into nulls, and Some into simple references. The problem
being that Option[T] may contain nulls, and the proposed solution
being only optimizing Option[T with NotNull].

--
Daniel C. Sobral

I travel to the future all the time.

[André van Delft]

If you could redesign Scala, how about 

- give it a trait Nullable (rather than NotNull)
- forbid null assignments to references that do not inherit from Nullable
- treat features from Java classes as if they inherit from Nullable
- offer an escape mechanism for that treatment

Op vrijdag 24 augustus 2012 01:46:00 UTC+2 schreef Daniel Sobral het volgende:

[Simon Ochsenreither]

Hi André!

I'm very sympathetic to your arguments!

There are a conceptual issues, which I'll try explain (so I can just bookmark this thread as a reminder for myself :-D).

There are two ways to handle missing data in Scala: variables of reference
type may hold null, and there is Option[T].

 

No, please don't do the former. Assigning nulls to variables is just malicious. It is there because of compatibility with Java and the JVM.
There have been some other approaches to it: http://medianetwork.oracle.com/video/player/1785452087001
So while it might sound great in theory, it is broken, cumbersome and painful in the Java reality we currently live in.

Conceptually, there are multiple, orthogonal nullability/non-nullability ideas:

Defining nullability/non-nullability at the declaration-site. This creates the issue that you would always need to define some "null object pattern", even for types where it doesn't make sense. Have a look at what happens when you call null.asInstanceOf[SomeValueClass] (value classes are non-nullable).

Defining non-nullability for method parameters: This is an approach which I consider to be more practical, because it could interoperate with other languages on the JVM and wouldn't be some language specific thing.
See http://jcp.org/en/jsr/detail?id=308. I expect that in the future Java will ship with some sort of @NonNull annotation. I think it would be a great idea if the Scala compiler would annotate every input parameter and result type as @NonNull by default. This would allow us to leverage all the tools which will be written for it, is minimally invasive and hard things like "Are these annotations inherited?" "Can a @NonNull method be overridden by a probably null method or does it need some explicit @Nullable annotation?"

Looking further, I hope that we will get union types in the future, so that stuff coming from Java would automatically get some "String|Null" type by default, which would let us track it through the typesystem.

Conclusion: I'm optimistic that improvements can be done on a method level, but I'm unsure there is a good, practical solution at the declaration-site level. All the solutions I have seen until now have severe issues.

Bye,

Simon

[Tony Morris]

Hello André,
I suspect the reason for lack of adoption is because there is a non-zero
penalty for using these constructs. For example, a counter-argument
might be made that using these constructs upsets source code aesthetics
and so it is not a simple matter of adoption.

Now personally, I find these arguments very weak and even if we were to
say, make the argument even stronger by have the code aesthetics be even
less appealing, then this cost is very insignificant in comparison to
the gain. However, *even having this debate with yourself* is costly and
I would be very much in favour of making the issue have zero
disadvantage, while keeping all the advantages that you mention.

I don't think it is too difficult to the imagination to hypothesise
about how one might go about doing this with appropriate language and
library support, so maybe you can consider it. That is to say, if this
matter is something valuable to you, I would suggest finding a means to
mitigate the perceived costs, even superficial ones. I happen to enjoy
these kind of challenges (that is, winning outright so the discussion
disappears), but I am engaged already on other vectors. Let me know if
you are interested in pursuing it and I will help where I can -- and I
am sure there are others who would do.

PS: not a dumb question

--
Tony Morris
http://tmorris.net/

[André van Delft]

Thank you Simon; that is a great video about Kotlin.

I try summarize the section "Fighting NPEs - Nullable Types; Annotating Java Code", starting from 22:45:

- possibly-null-types in Kotlin have a trailing question mark

- some code examples:

  val files = File("test").listFiles() 

    // type is Array<File?>?

  files.size // compile time error

  if (files != null) { // causes implicit cast

    files.size // Ok

  }

  files!!.size // Ok, throws NPE if files==null

  files?.size // Ok, is null if files==null

 

- Java types are by default nullable, except annotated @NotNull

  Such annotations may be in external files

I think Kotlin's approach solves Hoare's horror. 

- more complete than Spec#'s approach

- safer than the always nullable types that Scala inherits from Java.

- a much more concise way of handling nullables than Option.

If it works out really that good, I hope it would not be too late for adoption by Scala.

Op vrijdag 24 augustus 2012 11:49:15 UTC+2 schreef Simon Ochsenreither het volgende:

[André van Delft]

Hi Tony,

I estimate that source code aesthetics can live well with Kotlin's elegant and concise notation with "!!." and "?." etc. 

To change Scala in this direction the cost would IMO mostly be the breaking of current code.

As I recall, Martin presented some time ago a proposal to replace "if(...)..." with the "if...then...", with a realistic change path.

That precedent would give me some hope that Scala will get rid of Hoare's Horror.

Other than discussing the issue here I will not pursue it; I am also too busy with other things, and I do not think my effort would succeed if this the community would not be convinced by this discussion.

André

Op vrijdag 24 augustus 2012 11:58:01 UTC+2 schreef Tony Morris het volgende:

[Simon Ochsenreither]

Hi André!

Actually, these two lines belonged together: :-)

There have been some other approaches to it: http://medianetwork.oracle.com/video/player/1785452087001
So while it might sound great in theory, it is broken, cumbersome and painful in the Java reality we currently live in.

"broken, cumbersome and painful" was the description for the approach shown in the video. I hope Scala will never get near such a broken mess.

If it works out really that good, I hope it would not be too late for adoption by Scala.

No, sadly it is far worse than shown on the slides. Their proposal basically requires an "annotate every Java library on this planet with various @NonNull/@Nullable stuff" approach. And even this doesn't work properly, as shown by the @Kotlin annotations.

Bye,

Simon

[André van Delft]

Hey Simon,

Actually, these two lines belonged together: :-)

Oops...misread those.

 

"broken, cumbersome and painful" was the description for the approach shown in the video. I hope Scala will never get near such a broken mess.

(...) sadly it is far worse than shown on the slides. Their proposal basically requires an "annotate every Java library on this planet with various @NonNull/@Nullable stuff" approach. And even this doesn't work properly, as shown by the @Kotlin annotations.

I can imagine that only the most important Java libraries would be annotated; other libraries would then be considered to bear only possibly-null types, and these would easily be handled in Scala code using "!!." instead of ".". I think it would be worthwhile to solve Hoare's Horror this way.

But is it only the Java interoperability issue that makes Kotlin's approach "broken, cumbersome and painful"? 

André

[Simon Schäfer]

I don't know if they have an equivalent to (for example)

nullable map fun // where nullable = Option

How should such a call look like?

nullable = fun(nullable)? // where nullable = value which can be null
// means
// if (nullable != null) nullable = fun(nullable)

[Andrew Forrest]

Yay, very happy that this discussion is happening!

One solution to non-nullable variables, (rather than trying to somehow come up with a valid ‘null object’ for every type, which is probably impossible), is to treat null in that case as ‘unassigned’. When you try to read the value, you’d get a ‘AttemptToReadUnassignedFieldException’—or similar. Obviously to some extent that moves the check back to run-time. However, at least a) it’s pragmatic and simple, b) the compiler can statically catch some attempts to read uninitialised fields, c) the exception at least happens sooner than it would with a NullPointerException; at the point of reading the variable rather than at the point of dereferencing it.

This could apply to array elements too. So if you allocate a ‘new (String with NotNull)[100]’:
* You’d only be allowed to assign non-null Strings to elements of the array; and
* An attempt to read an unassigned element would throw an exception.

(I wonder if the existing collections classes would work with such arrays…?)

–Andrew

[Matthew Pocock]

I think everyone can agree that nulls are from the devil and null pointer exceptions are his spawn. However, doing anything about it is complicated by Java interop and legacy. If I had the choice, I'd make every type T be disjoint from null except for  `Nullable[T]`. It would be a compilation error to assign null to anything except Nullable[T], and un-annotated code from outside scala would be presumed to be Nullable types. This can largely be a figment of the compiler's imagination - the runtime representation of Nullable[T] would be T - but we'd be able to set it up so that you can resolve typeclasses on Nullable[T] distinct from T. There are then some cute isomorphisms between Nullable[T] and Option[T] (among others) that can be used for under-the-hood optimizations, and some issues with initialization of arrays. There are also some cute possibilities of implicit conversions from Nullable[T] to T *only after the first op on Nullable[T] that would trigger a NPE* and the removal of redundant null checks on monadic ops. All great fun.

However, this is if I had the choice, which I don't. Oh, and just to get it off my chest, I don't like the pattern of `Foo with Nullable` and `Foo with NotNull`. The `with` operator connotes conjunction of types, not summing them.

/me gets off hobby horse

M

--

Dr Matthew Pocock

Integrative Bioinformatics Group, School of Computing Science, Newcastle University

mailto: turingate...@gmail.com

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

irc.freenode.net: drdozer

skype: matthew.pocock

tel: (0191) 2566550

mob: +447535664143

[Justin du coeur]

On Sat, Aug 25, 2012 at 4:46 PM, Matthew Pocock <turingate...@gmail.com> wrote:

I think everyone can agree that nulls are from the devil and null pointer exceptions are his spawn. However, doing anything about it is complicated by Java interop and legacy. If I had the choice, I'd make every type T be disjoint from null except for  `Nullable[T]`. It would be a compilation error to assign null to anything except Nullable[T], and un-annotated code from outside scala would be presumed to be Nullable types.

+1 -- I suspect getting there from here is difficult in practice (due to scads of existing code), but this makes oodles of sense in principle.  If the only real reason Scala supports null is interop (and I think that's true of good idiomatic Scala), it should be treated as such and made explicit.  And changing the *default* behaviour from with-null to without-null would lead folks to better and safer code pretty efficiently.  Programmers are lazy, so we really should avoid having an easy, lazy path to using nulls.

I'm rather conscious of this at the moment.  I'm finally doing Scala full-time for the time being, and caught myself last week initializing a variable with null because it saved me a line.  I did a double-take an hour later and Optioned it, but it did drive home that most folks will sometimes take the lazy road if it's available.  The beauty of Scala is largely that the most concise approach is typically the most *correct* one -- this is a rare exception currently.  Making null *inconvenient* would likely be a boon in the long run.

Has anybody written a compiler plugin to do this?  Adding a plugin, then a switch, and encouraging folks to use it, seems like a safe and sensible step here.  (I'd require usage of it in my startup...)

[Erik Osheim]

On Sun, Aug 26, 2012 at 11:43:29AM -0400, Justin du coeur wrote:
> Has anybody written a compiler plugin to do this? Adding a plugin, then a
> switch, and encouraging folks to use it, seems like a safe and sensible
> step here. (I'd require usage of it in my startup...)

It would not be hard to write a plugin that catches explicit
initialization using null (I've thought about writing one), but I think
it is somewhat hard to draw the line between allowed and disallowed
behavior (if you need to deal with Java and/or arrays).

Would you forbid explicitly assigning to null? Probably.

Would you forbid explicitly returning null? Probably.

Would you forbid using _ as a default value in initializers? Maybe.

Would you forbid passing null as an argument to a function or method?
Lots of code using vars can be rewritten to be tail recursive, so if
you don't forbid this there are lots of ways to abuse null. But if you
do forbid it then you can't do checks like x.==(null) or y.!=(null)
unless you hardcode some ugly exceptions.

Would you forbid use of Arrays?
Array[AnyRef] pretty much always initializes its elements to null, so
it's hard to imagine using arrays while trying to forbid null.

There are probably more cases I'm not thinking of at the moment.

I'm not saying these are unsurmountable, but I'm not sure how much
general agreement there is around these issues.

-- Erik

P.S. Of course having spent this time thinking about the issue, I'm now
imagining how I'd write such a plugin. ;)

[Simon Ochsenreither]

Hi,

sorry for my late reply.

The issue is not only interoperability with Java, but also that it is completely unenforceable in the JVM.
The proposals I have seen add substantial weight and complexity, without adding any sort of enforcement except some compiler fiction.

The issue is that this fiction stops to exist as soon as you step out of the language's boundaries.

For instance: casting null to a type (e. g. null.asInstanceOf[T]) is guaranteed to succeed. What will happen if you put a non-nullable type into such a method? As long as you stay inside your own language, you could instruct the compiler to replace it with some zero-instance, but what will happen in existing (Java) code?

What will happen when you allocate an array, like new Array[NonNullableType](5)? You could fill it with some zero-instance as mentioned earlier, but the JVM does not support that (null, 0, 0.0 ... are hardcoded and predefined values in the spec), meaning you would have to go through it yourself in probably O(n) time. Or you could do it lazily on first access, but again, no support for that by the JVM. You would need to keep track of initialized vs. uninitialized elements yourself.

Additionally, serialization/persistence/"Enterprise" frameworks rely on a specific structure of a class: Most of them require an empty constructor and initialize the fields by repeatedly calling setter methods afterwards. How would you support that? Disallow this pattern and become immediately incompatible with some of the most popular libraries and frameworks out there?

How would reflection work? Would Java reflection be disallowed? If yes, how? If not, how would the invariants be preserved? How would assignment compatibility work? Again, this would lead to incompatibility with all major frameworks out there.

How would Class#cast made to work with the new semantics? It is synthesized by the VM and as far as I know it cannot be customized.

In the end, I think the only way this could be barely made to work would be with tons of Classloader hacking, tons of "let's create this class on the fly" and tons of even more ugly, slow and unsafe hacks.
As far as I know, Gosu has (or had) this model and they are trying to move away from it.[1]

I would really love some kind of enforcement of non-nullability, but it is just not practical when running on the JVM. And if I wouldn't care about interoperability with Java/the JVM, why not just use Haskell?

Additionally there are tons of really ugly language design issues in that partly nullable, party non-nullable world. E.g. even if you had non-nullable types, you would need some idiom to describe "optional" parameters?
Would you allow the reintroduction of nullability for non-null types?
Or would you add some "Optional[T]" class handling that?
What would be the best practice for nullable types here? Would you just pass them as-is or wrap them for consistency in Optional, too?
Btw, would it then be required for nullable classes to add the "?", too?
Or only for those nullable-non-nullable-types? Or would you convert a nullable T to a Optional[T] automatically, if there are other non-nullable, optional parameters in the method parameter list?
How would the different, non-composable APIs be handled?

E.g.:

def foo(firstOptional: NonNullableClass?, secondOptional: NullableClass) // or:
def foo(firstOptional: NonNullableClass?, secondOptional: NullableClass?) // or:
def foo(firstOptional: Optional[NonNullableClass], secondOptional: NullableClass) //or:
def foo(firstOptional: Optional[NonNullableClass], secondOptional: NullableClass?) //or:
def foo(firstOptional: NonNullableClass?, secondOptional: Optional[NullableClass?]) //or:
def foo(firstOptional: NonNullableClass?, secondOptional: Optional[NullableClass]) //or:
def foo(firstOptional: Optional[NonNullableClass], secondOptional: Optional[NullableClass]) //or:
def foo(firstOptional: Optional[NonNullableClass], secondOptional: Optional[NullableClass?])


In the end, this would end in a explicitly-null/implicitly-null language, not a non-nullable/nullable language.
(Not even mentioning that I consider hard-coding some null-handling mechanism into the language a grave language design mistake like for instance collection literals.)

We should not let ourselves be distracted by the marketing speak, but think how a real-world solution could look like. The failure of reified generics in Kotlin should serve as a lesson here.

From my experience, Scala's approach of making interoperability/compatibility painless and enforcing the only-assholes-pass-nulls policy on a social level a pure win.

Bye,

Simon

[1] http://guidewiredevelopment.wordpress.com/2012/05/09/gosus-inconceivable-non-classloader-take-1/

[André van Delft]

Hi Simon,

I think support for nullable vs not-null types should be just "compiler fiction". The extra information should be erased during compilation just like with generic type parameters; no enforcement by the JVM would be applicable. The support would not be 100% NPE-safe, but still be worthwhile, IMO. 

I think most of your issues may adequately be tackled.

About casting null to a not-null type: 

  s.asInstanceOf[String]

should throw a NPE if s == null.
But such a test should not be done when casting to a type parameter:

  def cast[A](a.Any) = a.asInstanceOf[A]

because the actual type parameter might be nullable. The compiler should give a warning here.

Similarly, a compiler warning would flag a not-null array allocation such as

  new Array[String](5)

The programmer would then be trusted to fill the array with not-null data before using these.

Likewise for parameterless constructors that are only needed for deserialisation, as witnessed by a specific annotation.

Reflection and Class#cast would not be affected. 

Assignment would be as in: 

  var s: String = "a"

  var ns: String? = "b"

  ns = s

  s = ns!!

There should not be an interaction between nullable types and Optional[_]. Optional parameters should be specified with Optional[_], I think (now).

While this approach for not-null types has several gaps, I think many projects such as my current one, might benefit. The devils are in the details, of course. I would like to learn the experience from Kotlin. 

André

Op zondag 26 augustus 2012 18:38:04 UTC+2 schreef Simon Ochsenreither het volgende:

[André van Delft]

Yesterday a discussion was started on non-nullable types at Reddit, for this blog post: Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake.

The Reddit comments link among others to these blog posts:

Why Scala's "Option" and Haskell's "Maybe" types will save you from null

A note on null pointers

In the latter post, a comment makes a good observation about Option[_]:

I believe the point of using a language with an expressive type system is to try to converge the range of values that the type system allows a function to return with the range of values that are valid outputs of the function. So in type safety nirvana the types and the valid values are the sames.
Ironically Option, it you look at it precisely, moves away from this goal. If we have a function D => R defined in Scala (or Java) then the possible return values are: R | null
But if you change the signature to D => Option[R] then you can return:
Some(R) | Some(null) | None | null

[Rex Kerr]

This is a "good" observation in the same sense that "being cross-platform compatible with the JVM now introduces an extra level of trouble--not only do you have to test every platform, you also have to test every likely version of the VM".

That is, although it is possible that you'll get a Some(null) or a null out of something typed as Option[T], you're not supposed to.  There's no strict guarantee, but the custom is that it will be used to make your life easier, not harder.  (The JVM may also make your life harder with cross-platform stuff.  So far, it's a colossal win for me for ease of cross-platform code.  Option is a big win (in other ways), too.)

  --Rex

[martin odersky]

That's true _except_ that, because of Option, `null` types are essentially unused in Scala programs. So, pragmatically the only values of interest are

     Some(R) | None

As I wrote earlier, we started at some point adding NonNull to Scala. We did not follow through with this because NPEs are actually very rare in pure Scala code, because nobody uses `null` explicitly. 

I believe most occurrences of NPEs in Scala programs are actually due to some uninitialized value. And in that sense, having "uninitialized" as a third state is good; you do not want to conflate it with None.

Cheers

 - Martin