On Mon, Jul 9, 2012 at 3:24 PM, martin odersky <martin.odersky-p8DiymsW2f8@public.gmane.org> wrote:

We could invent a new special subtype of Option (Maybe, anyone?) that is guaranteed to contain non null values only. Here are the core definitions:

abstract class Option[+T]

abstract class Maybe[+T] extends Option[T]

class Some[T](x: T) extends Option[T]

class Just[T](x: T) extends Maybe[T] { require(x != null) }

object None extends Maybe[Nothing]

The below is from my opening post in the 2008 thread.  The problem still seems the same to me: even if null is excluded, a single Option type offers no way to distinguish between different meanings of "optional".  Some(null) is only one manifestation of the semantic mismatch between what is being asked by the caller and what is being answered by the callee.

 Thus do I think "Option" should be of a higher kind, giving rise to multiple "Options" where the type constructor says something specific about what the extra bit is trying to say.

Contrast Option#apply with Traversable#find, for instance.  Both return Option[T].  But the meanings are far apart - and once we leave the caller's immediate vicinity, all possible distinction is gone.

> That particular example is problematic only because Option is           

> overloaded with at least two meanings in common use: as an all-purpose  

> replacement for null ("this variable may or may not have a legal value  

> right now") and to layer a boolean on top of an arbitrary value ("the   

> answer to your question is either yes or no, and if yes, take this      

> too.") Then of course there are the multiple uses for null further      

> complicating the matter (unassigned, various forms of failure, end of   

> sequence, I shudder to imagine how many others.)                        

> 

> So while Option[T] is a tolerable replacement for null in some          

> circumstances, it's a long ways from ideal. I am sure some people have  

> thought about this in more detail. If the two uses I named above were   

> separated into distinct containers (Option[T] and Maybe[T], say) could  

> Some(null) then be disallowed without breaking a lot of code? Are there 

> many more difficulties lying in wait?                                   

On Mon, Jul 9, 2012 at 3:24 PM, martin odersky <martin.odersky-p8DiymsW2f8@public.gmane.org> wrote:

We could invent a new special subtype of Option (Maybe, anyone?) that is guaranteed to contain non null values only. Here are the core definitions:

abstract class Option[+T]

abstract class Maybe[+T] extends Option[T]

class Some[T](x: T) extends Option[T]

class Just[T](x: T) extends Maybe[T] { require(x != null) }

object None extends Maybe[Nothing]

The below is from my opening post in the 2008 thread.  The problem still seems the same to me: even if null is excluded, a single Option type offers no way to distinguish between different meanings of "optional".  Some(null) is only one manifestation of the semantic mismatch between what is being asked by the caller and what is being answered by the callee.  Thus do I think "Option" should be of a higher kind, giving rise to multiple "Options" where the type constructor says something specific about what the extra bit is trying to say.

Contrast Option#apply with Traversable#find, for instance.  Both return Option[T].  But the meanings are far apart - and once we leave the caller's immediate vicinity, all possible distinction is gone.

> That particular example is problematic only because Option is           

> overloaded with at least two meanings in common use: as an all-purpose  

> replacement for null ("this variable may or may not have a legal value  

> right now") and to layer a boolean on top of an arbitrary value ("the   

> answer to your question is either yes or no, and if yes, take this      

> too.") Then of course there are the multiple uses for null further      

> complicating the matter (unassigned, various forms of failure, end of   

> sequence, I shudder to imagine how many others.)                        

> 

> So while Option[T] is a tolerable replacement for null in some          

> circumstances, it's a long ways from ideal. I am sure some people have  

> thought about this in more detail. If the two uses I named above were   

> separated into distinct containers (Option[T] and Maybe[T], say) could  

> Some(null) then be disallowed without breaking a lot of code? Are there 

> many more difficulties lying in wait?                                   

One solution to have this by 2.11 is to add another subclass of Option with a private constructor, that can only be instantiated with non-null values.
We could then redirect all Option construction to object Option.apply, thus getting either None or SomeNonNull, and we can make them value classes in 2.11:

The deprecation cycle would be:
 - 2.10 - deprectate the Some constructor and redirect people to Option (Option would still extend AnyRef)
 - 2.11 - remove the Some constructor, replace Some by SomeNotNull and make everything a case class

Did I miss anything, or could we actually do this?

On Mon, Jul 9, 2012 at 6:24 PM, martin odersky <martin.odersky-p8DiymsW2f8@public.gmane.org> wrote:

Now that we have value classes, the next optimization frontier is Option. I have been looking at that lately. The idea is to unbox as follows:

Option[T]   ==>   the boxed version of T (which is always a reference type)

Some(x)    ==>   the boxed version of x

None         ==>    null

Here are some examples of unboxed representations:

Option[String]  ==>  String

Option[Int]  ==>  Integer

Option[Option[Int]]  ==>  Option[Integer] 

Some(1)    ==>   new Integer(1)

Some("abc")  ==>  "abc"

Some(None)  ==> None

Some(Some("abc"))  => Some("abc")

It all works out beautifully. Almost all instances of Some objects would be eliminated. Scala maps could run at the same speed as Java maps because they would return exactly the same runtime values, but without the danger of NPEs.

(Aside: this is not the only source of pain in Scala maps; there are, or were when I last checked, numerous instances of conversion back and forth between key-value tuples and separate keys and values.  These were, for mutable HashMap, at least as expensive as Options.)

 

But there's one catch: Some(null) cannot be represented. According to the translation scheme, Some(null) should translate to null, but that's already reserved for None. So Some(null) needs to be the same as None.

Well, can we cheat?  If you're making Some and None not-really-exist (i.e. the compiler makes it look to you like they do, but underneath it does a bunch of boxing/unboxing on its own), which is an optimization unavailable to library writers, you can go the whole way and make an object SomeNull extends Some[Null], which should then be able to stand in, formally, for any instances of Some(null).  It will break your boxing/unboxing scheme--you'll have to lie about your types--but you're lying about them *anyway* if you're unboxing in that way, so all you need is an instanceof (or reference equality) guard on every access where the status is not already known, and you should be good to go.  Instanceof checks are pretty cheap (as are equality checks), so although this would be a minor performance penalty--fixable with NotNull--it would be probably 80% of the way to overheadless options.

Regarding NonNull, I don't see how it can work as a type. It's not a property of a type but of a variable. I asked about this a long time ago and the answer was that it should wait until NonNull was being developed further, or something like that, IIRC.

Here's one illustration how it's orthogonal to the type system:

val x: String with Null = someJavaMethod()

val y: String with NonNull = x match { case null => ""  case other => other }  // isn't other's type the same as x's -- String with Null? So how can it be NonNull?

Here's another:

class Whatever(s: String)

var x: Whatever with NonNull = new Whatever("xxx")  // How can you say that it's with NonNull if whatever doesn't extend NonNull?

On Monday, July 9, 2012 6:24:19 PM UTC-4, martin wrote:

Now that we have value classes, the next optimization frontier is Option. I have been looking at that lately. The idea is to unbox as follows:

Option[T]   ==>   the boxed version of T (which is always a reference type)

Some(x)    ==>   the boxed version of x

None         ==>    null

Here are some examples of unboxed representations:

Option[String]  ==>  String

Option[Int]  ==>  Integer

Option[Option[Int]]  ==>  Option[Integer] 

Some(1)    ==>   new Integer(1)

Some("abc")  ==>  "abc"

Some(None)  ==> None

Some(Some("abc"))  => Some("abc")

It all works out beautifully. Almost all instances of Some objects would be eliminated. Scala maps could run at the same speed as Java maps because they would return exactly the same runtime values, but without the danger of NPEs.

But there's one catch: Some(null) cannot be represented. According to the translation scheme, Some(null) should translate to null, but that's already reserved for None. So Some(null) needs to be the same as None.

How big of a hassle would it be to outlaw Some(null)? At first sight this expression looks pretty weird, anyway. Well, I tried by catching Some(null) in an assert and rebuilding scala trunk and running the tests. I found 4 violations:

 - Java map wrappers that map a null result to Some(null) if the key exists. This one is is actually pretty dubious; Java treats null as missing, so why should the wrapper do it otherwise? Besides, this "feature" alone slows down get operations on Java maps that miss by a factor of 2! I would vote for changing the behavior here.

 - Property wrappers that map a null property to Some(null). Not sure whether this one is dubious or not.

OK so far, but it gets worse

 - ScalaCheck implicit value generation,which represents the generated value `null` by `Some(null)`

 - ForkJoin tasks in parallel collections which also represent a returned value `null` by `Some(null)`

It's likely that there will be more cases like the last two in Scala codebases. These cases cannot be solved without major changes, i.e. going off Option entirely and replacing it with a new type. Not an attractive proposition to demand from your users. But it's tantalizing that the major, sweeping optimizations of Option are out of reach just because of some corner cases. 

What to do? 

We could invent a new special subtype of Option (Maybe, anyone?) that is guaranteed to contain non null values only. Here are the core definitions:

abstract class Option[+T]

abstract class Maybe[+T] extends Option[T]

class Some[T](x: T) extends Option[T]

class Just[T](x: T) extends Maybe[T] { require(x != null) }

object None extends Maybe[Nothing]

This would let us migrate to Maybe everywhere we can guarantee that Some(null) is not possible. But the added classes and concepts are a very high price to pay. At least until in some distant future everybody will use Maybe and Option is of historical interest only. But that day would be far away.

Another idea is (rather ironically) to take nullability more seriously. Scala side-stepped the issue with the introduction of the Option type, so even though I initially thought we need some notion of non-nullable type, the fact that everybody used Option anyway made that quite redundant. But now the very fact that references can be null prevents us to do a good job compiling Option! If we embrace NonNull (which is already in the library but not very well supported by the language yet), then we could optimize at least

Option[T with NonNull]   to   T

And, with enough care, critical operations in the libraries such as Map#get could return an Option of a non-null type, thereby avoiding Some-boxing. That seems to be a price worth paying: You invest in more precise types and get better performance in return. 

Cheers

 - Martin

--
Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

On 2012-07-10 0:24, martin odersky wrote:

Now that we have value classes, the next optimization frontier is Option. I have been looking at that lately. The idea is to unbox as follows:

Option[T]   ==>   the boxed version of T (which is always a reference type)
Some(x)    ==>   the boxed version of x
None         ==>    null

Here are some examples of unboxed representations:

Option[String]  ==>  String
Option[Int]  ==>  Integer
Option[Option[Int]]  ==>  Option[Integer]

Some(1)    ==>   new Integer(1)
Some("abc")  ==>  "abc"
Some(None)  ==> None
Some(Some("abc"))  => Some("abc")

It all works out beautifully. Almost all instances of Some objects would be eliminated. Scala maps could run at the same speed as Java maps because they would return exactly the same runtime values, but without the danger of NPEs.

Do you have working code in some branch? Even in the latest nightly I cannot get polymorphic value classes to work:

C:\Users\szeiger\Desktop\stest>c:\StandaloneApps\scala-2.10.0-20120709-134942-9a7546db9f\bin\scala
Welcome to Scala version 2.10.0-20120709-134942-9a7546db9f (Java HotSpot(TM) 64-Bit Server VM, Java 1.7.0).
Type in expressions to have them evaluated.
Type :help for more information.

scala> class S[T](val x: T) extends AnyVal { def get = x }
defined class S

scala> val s = new S(42)
java.lang.VerifyError: (class: , method: <init> signature: ()V) Expecting to find object/array on stack
        at .<init>(<console>:7)
        at .<clinit>(<console>)
        at $print(<console>)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
        at java.lang.reflect.Method.invoke(Method.java:601)
        at scala.tools.nsc.interpreter.IMain$ReadEvalPrint.call(IMain.scala:736)
        at scala.tools.nsc.interpreter.IMain$Request.loadAndRun(IMain.scala:991)
        at scala.tools.nsc.interpreter.IMain.loadAndRunReq$1(IMain.scala:579)
        at scala.tools.nsc.interpreter.IMain.interpret(IMain.scala:610)
        at scala.tools.nsc.interpreter.IMain.interpret(IMain.scala:574)
        at scala.tools.nsc.interpreter.ILoop.reallyInterpret$1(ILoop.scala:742)
        at scala.tools.nsc.interpreter.ILoop.interpretStartingWith(ILoop.scala:787)
        at scala.tools.nsc.interpreter.ILoop.command(ILoop.scala:699)
        at scala.tools.nsc.interpreter.ILoop.processLine$1(ILoop.scala:563)
        at scala.tools.nsc.interpreter.ILoop.innerLoop$1(ILoop.scala:570)
        at scala.tools.nsc.interpreter.ILoop.loop(ILoop.scala:573)
        at scala.tools.nsc.interpreter.ILoop$$anonfun$process$1.apply$mcZ$sp(ILoop.scala:864)
        at scala.tools.nsc.interpreter.ILoop$$anonfun$process$1.apply(ILoop.scala:819)
        at scala.tools.nsc.interpreter.ILoop$$anonfun$process$1.apply(ILoop.scala:819)
        at scala.tools.nsc.util.ScalaClassLoader$.savingContextLoader(ScalaClassLoader.scala:135)
        at scala.tools.nsc.interpreter.ILoop.process(ILoop.scala:819)
        at scala.tools.nsc.MainGenericRunner.runTarget$1(MainGenericRunner.scala:79)
        at scala.tools.nsc.MainGenericRunner.process(MainGenericRunner.scala:92)
        at scala.tools.nsc.MainGenericRunner$.main(MainGenericRunner.scala:101)
        at scala.tools.nsc.MainGenericRunner.main(MainGenericRunner.scala)

- Java map wrappers that map a null result to Some(null) if the key exists. This one is is actually pretty dubious; Java treats null as missing, so why should the wrapper do it otherwise? Besides, this "feature" alone slows down get operations on Java maps that miss by a factor of 2! I would vote for changing the behavior here.

Java maps do allow null keys and values (in general; some implementations forbid it), e.g. from the javadoc for HashMap: "Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key." If you want to distinguish between a found null value and a missing value, you need to do another lookup with containsKey().

 - Property wrappers that map a null property to Some(null). Not sure whether this one is dubious or not.

I'd say it's dubious but not explicitly forbidden. The javadocs for java.util.Properties do not specify the treatment of null values very well. Null is treated as a missing property but there's nothing stopping you from calling setProperty("foo", null) -- it does not check for null to throw a NPE.

-sz