The Option conundrum

[martin odersky]

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

[Paul Phillips]

On Mon, Jul 9, 2012 at 3:24 PM, martin odersky <martin....@epfl.ch> wrote:

But there's one catch: Some(null) cannot be represented.

We should at least briefly review the many prior discussions.

Here I am starting a thread in 2008: http://scala-programming-language.1934581.n4.nabble.com/Option-T-and-null-td2008053.html

...during which ijuma points out it has been discussed at least twice before.  In one of those preceding ones we find this piece of historical trivia:

  http://scala-programming-language.1934581.n4.nabble.com/Option-asserts-that-its-argument-is-not-null-tp2006479.html

  "There is recent commit (r14947) into the scala library that adds requirement that Some argument may not be null.

Sure enough: https://github.com/scala/scala/commit/b57e67b8a1

Martin, in the ensuing thread:

> Sorry for that. We should have explained before this was done. The      

> idea is that we'd like to explore the possibility of making options     

> more lightweight. None would be represented as null, Some as the value  

> itself. So an Option type would cost you nothing, and you'd still get   

> the compile-time checking. The price to be paid for this is that we     

> can't have Some(null) as a value, because it would be represented as    

> null. Given the reactions on the mailing list, it seems it's too late   

> to do this :-(. Nevergtheless I'm going to put this up for a straw poll 

> now. We could                                                           

> 

>  - do nothing, and live with the added overhead of Option 

>  - disallow Some(null) and do the optimization 

>  - Have another type (Maybe, maybe? ;-) that disallows null 

>    and is otherwise just like Option, with the intention of phasing out Option 

>    and switching to Maybe. 

> 

> What is your preference? 

> 

> Cheers 

> 

>  -- Martin 

My present day response will come under separate cover.

[martin odersky]

Thanks for this piece of mailing list archeology, Paul! 

I had completely forgotten that I already tried to outlaw Some(null) once before and got called back by David Pollak. So we can safely add Lift to the pieces of software that would break if we made the change now.

Even though the issue popped up repeatedly, what's new now is that there is now a concrete translation scheme that would make Option work as an unboxed type. Before we only had a suspicion that this might be possible. 

Cheers

 - Martin

[Paul Phillips]

On Mon, Jul 9, 2012 at 3:24 PM, martin odersky <martin....@epfl.ch> 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?                                   

[√iktor Ҡlang]

On Tue, Jul 10, 2012 at 12:56 AM, Paul Phillips <pa...@improving.org> wrote:

On Mon, Jul 9, 2012 at 3:24 PM, martin odersky <martin....@epfl.ch> 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.

Can't we just suggest:

Some(None)

Some(Some(x))

if you want to discern 3 possible states...

 

 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?                                   

--
Viktor Klang

Akka Tech Lead

Typesafe - The software stack for applications that scale

Twitter: @viktorklang

[martin odersky]

On Tue, Jul 10, 2012 at 12:56 AM, Paul Phillips <pa...@improving.org> wrote:

There are always reasons to split types up into more fine-grained entities, but there are also strong reasons against. I.e. Alan Perlis: "It's better to have 100 functions operate on one data structure than 10 functions on 10 data structures." I don't subscribe to this unequivocally, but there's some truth in it insofar as every distinction of data structures comes at a cost.

Cheers

 - Martin

[Paul Phillips]

On Mon, Jul 9, 2012 at 4:02 PM, martin odersky <martin....@epfl.ch> wrote:

There are always reasons to split types up into more fine-grained entities, but there are also strong reasons against. I.e. Alan Perlis: "It's better to have 100 functions operate on one data structure than 10 functions on 10 data structures." I don't subscribe to this unequivocally, but there's some truth in it insofar as every distinction of data structures comes at a cost.

Since they would all be derived from the same Option[M[_]], I think it could be arranged so the distinctions were only there for those who cared.

It is interesting to consider that if

  https://issues.scala-lang.org/browse/SI-6045

were fixed, and we did unbox None to null, then multiple Option parents could be nested and still have no cost.

class PossibleMember[A]

Found[A](x: A) extends PossibleMember

NotFound extends PossibleMember

class PossibleNull[A]

NotNull[A](x: A) extends PossibleNull

IsNull extends PossibleNull

We can return Found(NotNull(x: AnyRef)) and it's the same as x.  The various "Some" semantics survive in the type system.

[martin odersky]

On Tue, Jul 10, 2012 at 1:10 AM, Paul Phillips <pa...@improving.org> wrote:

On Mon, Jul 9, 2012 at 4:02 PM, martin odersky <martin....@epfl.ch> wrote:

There are always reasons to split types up into more fine-grained entities, but there are also strong reasons against. I.e. Alan Perlis: "It's better to have 100 functions operate on one data structure than 10 functions on 10 data structures." I don't subscribe to this unequivocally, but there's some truth in it insofar as every distinction of data structures comes at a cost.

Since they would all be derived from the same Option[M[_]], I think it could be arranged so the distinctions were only there for those who cared.

It is interesting to consider that if

  https://issues.scala-lang.org/browse/SI-6045

were fixed, and we did unbox None to null, then multiple Option parents could be nested and still have no cost.

It is about to be fixed. That was the work I have been doing on value classes to prepare for Option. See topic/valclasses2 in odersky/scala.

Pullrequest coming shortly.

 

class PossibleMember[A]

Found[A](x: A) extends PossibleMember

NotFound extends PossibleMember

class PossibleNull[A]

NotNull[A](x: A) extends PossibleNull

IsNull extends PossibleNull

We can return Found(NotNull(x: AnyRef)) and it's the same as x.  The various "Some" semantics survive in the type system.

No, if Found and NotNull are value classes then  

Found(NotNull(x: AnyRef)) would be represented as 

NotNull(x: AnyRef). You have to box the arguments of parametric value classes.

Cheers

 - Martin

[Paul Phillips]

On Mon, Jul 9, 2012 at 4:14 PM, martin odersky <martin....@epfl.ch> wrote:

No, if Found and NotNull are value classes then  

Found(NotNull(x: AnyRef)) would be represented as 

NotNull(x: AnyRef). You have to box the arguments of parametric value classes.

Is that "you have to" as in "that's the state of the implementation" or "you have to" as in "you have to"? Is there something which stands in the way of unboxing multiple layers of value classes?

[Daniel Sobral]

Here's the peanut gallery: please do. There's been dozens of threads
about Option that stumbled upon the fact that Some(null) is legal.

I doubt I'd be affected in any way, since I use Option(x) to get
Some(x), and that kills all top-level nulls. Lower level nulls might
still exist (ie, Some(Some(null))), but I don't think I have anything
like that.

Now, it's easy for someone to say he doesn't care how much trouble
that will give others, but I'll say it anyway. That's how Option
should have worked from the start, and I suspect there's some code
that will be simplified by it.

Now, to the specific proposals:

Maybe/Just is attractive, but I worry about the existing-documentation
effect. I really would prefer this change to be as transparent as
possible, and having to teach something new about a fundamental
concept described in every single Scala book, and probably talked
about by every scala blogger, daunts me.

Nullabillity check is on my wish list for a long time, on the other
hand. Not only it would be of use elsewhere, but, if you don't mind me
saying so, there's a movement toward this alternative among fellow JVM
languages.

--
Daniel C. Sobral

I travel to the future all the time.

[Vlad Ureche]

On Tue, Jul 10, 2012 at 12:24 AM, martin odersky <martin....@epfl.ch> 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:

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?

Vlad

[Paul Phillips]

On Mon, Jul 9, 2012 at 4:31 PM, Vlad Ureche <vlad....@gmail.com> wrote:

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?

Construction is only half the story: Some would have to drop out of case class status and sprout an extractor, so that it continued to yield a value on both SomeNotNull(x) and OldSome(x).  (Some and None still have to cover all values, except sigh null.) This might have unpopular effects on performance.

My suspicion-o-meter has elevated mercury at your proposal but I have a prior engagement so we will have to bear this cloud of suspicion for a time.

[Rex Kerr]

On Mon, Jul 9, 2012 at 6:24 PM, martin odersky <martin....@epfl.ch> 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.

There is one other use-case that you may be forgetting, however: pattern matching.  This is a problem whether or not Some(null) is permitted:

val a: Any = Some("fish")
val b: Any = "fish"
List(a,b).foreach(_ match {
  case Some(x) => println("Some")
  case x => println("Just the item.")
})

I submit that this is a breaking change, a *serious* breaking change, for programs that rely upon the current framework.  I also see no great way to fix this.  (You probably could use a different classloader as a secondary cheat to enable this behavior, but ugh.)  We either have to just bite the bullet and say: serious non-backwards-compatible change here, guys (and, perhaps, sorry Some(null) doesn't work any more), or think of something else.

Therefore, I suggest that we also consider introducing a different class entirely that doesn't make any promises about being able to distinguish boxing from unboxing.  (E.g. something in between Kotlin's nullable references and Scala's option.)

  --Rex

[Vlad Ureche]

On Tue, Jul 10, 2012 at 1:38 AM, Paul Phillips <pa...@improving.org> wrote:

On Mon, Jul 9, 2012 at 4:31 PM, Vlad Ureche <vlad....@gmail.com> wrote:

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?

Construction is only half the story: Some would have to drop out of case class status and sprout an extractor, so that it continued to yield a value on both SomeNotNull(x) and OldSome(x).  (Some and None still have to cover all values, except sigh null.) This might have unpopular effects on performance.

Yes, we'd have to drop the case class from the beginning -- and that would equate to pushing Some(null) outside the legal boundary by redirecting everyone to object Option.apply:

2.10:
sealed abstract class Option[+T]
case object None extends Option[Nothing]
sealed abstract class Some[T] extends Option[T]
case class SomeNotNull[T](t: T) extends Some[T]
case object DreadedNull[T] extends Some[T]

object Some {
  @deprecated("2.10", "The Some constructor Some(t) is being replaced by Option(t) for performance reasons. It will be removed in the next major release")
  def apply[T](t: T) = if (t eq null) SomeNotNull(t) else DreadedNull
  def unapply[T](opt: Option[T]): Option[T] = opt match {
    case None => None
    case SomeNotNull(t) => Some(t)
    case DreadedNull => Some(null)
  }
}

object Option {
  def apply[T](t: T) = if (t eq null) SomeNotNull(t) else None
}
 
2.11:
value classes, no more SomeNotNull and DreadedNull and no more object Some.apply.

My suspicion-o-meter has elevated mercury at your proposal but I have a prior engagement so we will have to bear this cloud of suspicion for a time.

Yes, let's keep the suspicion-o-meter high, it's 2am and I'm writing emails after a day of coding -- it would be suspicious if i haven't missed any detail :))

Another problem -- we can also have:
val t: Some[String] = null
How would that be represented?


Vlad

[Simon Ochsenreither]

Imho I don't think it is practical to disallow Some(null) or make other radical changes to Option.

Maybe it might make sense to embrace non-nullability from the declaration-site first, so that in the future we/the compiler can be sure that any null doesn't originate from the user except where explicitly specified.
E. g. converting the de-facto rules about methods not accepting or returning null into something compiler-checkable (see also the corresponding JSR) and then embrace the mentioned optimizations on a local scope first:

def foo(a: String): String = ... // Both argument and return value need to be non-null
def foo(a: String with Null): String with Null = ... // Both argument and return value can be null

Another starting point would the gradual introduction of non-nullable-by-default, so that values and classes would not be nullable without having a “extends/with Null”, e. g.:

val str: String = null // Warning, next release error
val str: String with Null = null // The “new” thing

or

class Foo
val foo: Foo = null // Warning, next release error

class Bar extends Null
val bar: Bar = null // OK

Imho the second thing is highly problematic from an implementation POV, because it would break the null.asInstanceOf[T] idiom used throughout people's code. (what would be the result if T is non-nullable?)

Exactly this problem has already shown its ugly head with the introduction of value classes and I have no idea on how one would fix it without wrapping every asInstanceOf call to check whether the the type argument is a non-nullable class (and returning some special, compiler-synthezised zero instance instead of null in this case)).

Good night!

Simon

[Daniel Sobral]

On Mon, Jul 9, 2012 at 8:44 PM, Rex Kerr <ich...@gmail.com> wrote:
>
> There is one other use-case that you may be forgetting, however: pattern
> matching. This is a problem whether or not Some(null) is permitted:
>
> val a: Any = Some("fish")
> val b: Any = "fish"
> List(a,b).foreach(_ match {
> case Some(x) => println("Some")
> case x => println("Just the item.")
> })

My understanding is that Option would be made to extend AnyVal, and,
therefore, AnyVal rules would (mostly) apply. In such a case, "a"
would contain the reference to Some("fish"), since optimization at
that point would no longer be possible.

[Josh Suereth]

On Mon, Jul 9, 2012 at 8:01 PM, Vlad Ureche <vlad....@gmail.com> wrote:

On Tue, Jul 10, 2012 at 1:38 AM, Paul Phillips <pa...@improving.org> wrote:

On Mon, Jul 9, 2012 at 4:31 PM, Vlad Ureche <vlad....@gmail.com> wrote:

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?

Construction is only half the story: Some would have to drop out of case class status and sprout an extractor, so that it continued to yield a value on both SomeNotNull(x) and OldSome(x).  (Some and None still have to cover all values, except sigh null.) This might have unpopular effects on performance.

Yes, we'd have to drop the case class from the beginning -- and that would equate to pushing Some(null) outside the legal boundary by redirecting everyone to object Option.apply:

2.10:
sealed abstract class Option[+T]
case object None extends Option[Nothing]
sealed abstract class Some[T] extends Option[T]
case class SomeNotNull[T](t: T) extends Some[T]
case object DreadedNull[T] extends Some[T]

object Some {
  @deprecated("2.10", "The Some constructor Some(t) is being replaced by Option(t) for performance reasons. It will be removed in the next major release")
  def apply[T](t: T) = if (t eq null) SomeNotNull(t) else DreadedNull
  def unapply[T](opt: Option[T]): Option[T] = opt match {
    case None => None
    case SomeNotNull(t) => Some(t)
    case DreadedNull => Some(null)
  }

^^^^^^  unfortunately right here is all the proof we need.   It's impossible for this to work if Option cannot have Some(null).   Pattern matching could no longer have extractors that return null.

I'm thinking Option[T with NotNull] being optimised is a great first step.  I also like Simon's suggestion of starting to phase out Null in favor of a better optimisation.

val x: T = null /// Issues  a warning in 2.10 ->  Did you mean T with Null?

The downside is that when assigning to Any you still need to box, in case of an Some(null): Option[T with Null]

If we're planning to *split* Option, a reasonable split would be:   Found(x)/NotFound and Initialized(x)/NotInitialized  where the "Initializable" one can be an AnyVal/optimised away and Found/NotFound can still contain null.   Map would, unfortunately due to Java compat, require the use of Found/NotFound.   Same with Pattern matching extractors.

In general I love the idea of Option getting unboxed away.  I love the possibilities AnyVal bring us.   *However* Option may mean too many things right now.  We also lack a basic Validation class (which can carry errors along, akin to Lift's Box/Can and Scalaz's ValidationNEL).  

If I were to call it right now, I'd be leaning towards three types being ones I would use:

(1) Findable / Found(x) / NotFound   // This could have Found[T with NotNull] optimisations, but needs to allow Found(null) for java-compatibility reasons.

(2) Initalizable / Initialized(x) / Uninitialized  // This could be fully optimised and not allow null in Initialized

(3) Validatable / Success(result) / Failure(List(error1, error2, ...))   // This would be a lot nicer to use than Either[List[Throwable], T].   Chaining with Found/Initialized would work too.   You could do the trick and have Validatable[ResultType,ErrorType] as well if you wanted.   The key is to support  a way to accrue errors in a sequence/related chain of operations.

(1) I would use for all my pattern matching extraction and things like Map.get.   It's the "most common" use of option now. 

(2) I would use this where you see `var x: Option[X] = None`.  

(3) I'm sorely missing this one right now in the standard library.  When trying to do any sort of meaningful UI (espeically in SBT plugins) this is crucial to try to continue accruing errors so users don't get frustrated by repeated "try-fail-fix"  loops.

That's my initial reaction now, but I need to think more.   I had forgotten that disallowing Some(null) would seriously inhibit pattern matching.....

[nafg]

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?

[Sébastien Doeraene]

Hi,

I very much like the idea of having an Option-like type that can be optimized that way (be it Option or Maybe or whatever).

However, even if you go the Maybe version, keeping Option for pattern-matching and non-breaking changes, it seems to me there is still a catch. Consider a value x of type Maybe[Maybe[T]]. If, at runtime, x is null, does it mean that x == MaybeSome(MaybeNone) or that x == MaybeNone?

And this can be not apparent at compile time: e.g., a function working with Maybe[A], that is called with A =:= Maybe[T]. So I even see no way you can de-optimize the particular case of Maybe[Maybe[T]] to solve that issue.

Cheers,
Sébastien

[martin odersky]

Yes, things will get ambiguous. You need to distinguish

Some(Some(1)) and Some(1)

Cheers

 - Martin

[martin odersky]

On Tue, Jul 10, 2012 at 10:22 AM, Sébastien Doeraene <sjrdo...@gmail.com> wrote:

Hi,

I very much like the idea of having an Option-like type that can be optimized that way (be it Option or Maybe or whatever).

However, even if you go the Maybe version, keeping Option for pattern-matching and non-breaking changes, it seems to me there is still a catch. Consider a value x of type Maybe[Maybe[T]]. If, at runtime, x is null, does it mean that x == MaybeSome(MaybeNone) or that x == MaybeNone?

And this can be not apparent at compile time: e.g., a function working with Maybe[A], that is called with A =:= Maybe[T]. So I even see no way you can de-optimize the particular case of Maybe[Maybe[T]] to solve that issue.

Maybe[Maybe[T]] is represented as Maybe[BT] where BT is the boxed version of T. The trick is really in how parametric value classes are handled. 

 - Martin

 

[Adriaan Moors]

On Tue, Jul 10, 2012 at 10:22 AM, Sébastien Doeraene <sjrdo...@gmail.com> wrote:

If, at runtime, x is null, does it mean that x == MaybeSome(MaybeNone) or that x == MaybeNone?

rephrasing in terms of Option to keep the discussion consistent:

here's my understanding of Option as a value class:

// Some(None) erases to None, but erasure is not recursive 

// only the outer layer of the onion is peeled off -- you're still putting a real None in the option box

// the box itself disintegrates on erasure

assert(null != Some(None))

// the box is empty? --> that's represented as null

assert(null == None)

[martin odersky]

Yes, that's all correct. 

 - Martin

[Johannes Rudolph]

I understand the problem as this: We need a bijective mapping between
two different runtime representations of Option. There are two general
solutions: Incompatibly shrink the option type (remove that "extra
bit" by disallowing `Some(null)` so that the simple null/value
solution is working) or alternatively encode this extra bit somewhere.
Most of the discussion seems to focus on the first solution. I thought
I read about the second solution in this thread but can't find it
anymore.

So how about trying the second solution by using this mapping:

All option types get the static type `Object`. Then the mapping could be this:

Some(null) <==> SomeNullSingleton
Some(x) <=> x
None <=> null

The advantage is that this is still fully transparently compatible to
the current solution. The disadvantage is that there needs to be some
magic in the compiler which is doing the translation and you would
need additional branching to discriminate Some(null) and Some(x).
Additionally in the `Some(x)` case there would be casts from Object to
T. A pattern match would then translate

someX match {
case Some(x) => "test" + x
case None => "none"
}

to

if (someX == null)
noneBranch
else if (someX eq SomeNullSingleton)
someBranch(null)
else
someBranch(someX.asInstanceOf[T])

The question stays by which compiler mechanism this translation should
then be done.

Johannes

On Tue, Jul 10, 2012 at 10:22 AM, Sébastien Doeraene
<sjrdo...@gmail.com> wrote:

--
Johannes

-----------------------------------------------
Johannes Rudolph
http://virtual-void.net

[Stefan Zeiger]

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

[martin odersky]

On Tue, Jul 10, 2012 at 1:44 AM, Rex Kerr <ich...@gmail.com> wrote:

On Mon, Jul 9, 2012 at 6:24 PM, martin odersky <martin....@epfl.ch> 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.)

Right. Tuples are on the radar for being optimized as well.

 

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.

The problem is that we also have to lie in the bytecode. This means that Option[T] can only be represented as Object because otherwise there's no way we can pack a value representing Some(null) into it. 

Maybe that's OK, but it's not so nice, and it might also cost us in performance, because very get operation will need a cast.

Cheers

 - Martin

[Johannes Rudolph]

On Tue, Jul 10, 2012 at 11:21 AM, Johannes Rudolph
<johannes...@googlemail.com> wrote:
> Then the mapping could be this:
>
> Some(null) <==> SomeNullSingleton
> Some(x) <=> x
> None <=> null

I just figured out that this is the same as what Rex proposed.

[Johannes Rudolph]

On Tue, Jul 10, 2012 at 12:32 PM, martin odersky <martin....@epfl.ch> wrote:
> Maybe that's OK, but it's not so nice, and it might also cost us in
> performance, because very get operation will need a cast.

But that's still much better than the current solution which needs a
cast as well like any other generic operation which unpacks things
from a container.

[Patrik Andersson]

But but... Should we really be conflating "no value/ not defined" with "empty value"? This line of thinking sort of has "" (the empty string), () and [] also map to None. 

It's the problem of answering: "Is the light on in the kitchen?" when you don't know with a yes or a no. 

To me, I think that the issue here comes down to picking one of two paths, not conflating the two. 

1. Exclude null from Option and carry the cost of doing so. If you (think you) need Some(null) then you will have to either let Option go or rethink something else. For instance by using a "null moniker" somehow. Map could publish its own (or make use of a new common) algebraic data type. A real data type in the style that doctor Josh has already proposed. (Found(x) | FoundNull | NotFound) It could be given a morphism onto Option but only if you would also give a function I the same domain that can translate the null case. That way it would be up to you to invent a fact about null <=> None or something like Some(MyZero). 

2. Keep the state of affairs the way they are but introduce the optimization through hidden synthetic secret bippies that can smuggle null through the boxing such that it comes out the other end as Some(null). An annotation could be introduced akin to @tailrec such that code constructs that are not safe will not compile. 

I suppose this has the potential to make good use of the mandatory feature import thingie in that there could be one that requires that all usages of Option be "null-safe". 

Pardon the tone. Too many mosquitos here :/

Patrik

[Ismael Juma]

On Tue, Jul 10, 2012 at 1:27 PM, Johannes Rudolph <johannes...@googlemail.com> wrote:

But that's still much better than the current solution which needs a

cast as well like any other generic operation which unpacks things
from a container.

Also, casts that always succeed are basically free in HotSpot (apart from additional bytecode size, which affects inlining decisions).

Best,

Ismael

[Dave]

On 10 jul, 04:15, nafg <naftoli...@gmail.com> wrote:
> 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?

Maybe it's more a type constructor which widens from NonNullable to
Nullable along the horizontal axis than a type as a mixin trait which
widens along the vertical axis. I think it is difficult to implement
an implicit conversion between NonNull to Null and that it still works
on the mixins because those (String with NonNull and String with Null)
are different types.


val x: Nullable[String] = new Nullable[String](new
String(someJavaMethod())
val y: NonNullable[String] = new NonNullable[String](x match {

case null => ""
case other => other

})

There is no subtyping relation (because a NonNullable cannot replace a
Nullable) but an implicit conversion doesn't look weird from
NonNullable to Nullable (similar as from Int to Long: horizontal
widening) so you can do this
val z: Nullable[String] = y

>
> 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?
>

class Whatever(s: Nullable[String])
var x: NonNullable[Whatever] = new NonNullable[Whatever](new
Whatever(new Nullable[String](null)))

So NonNullable[Whatever] cannot be null but Nullable[String] can

maybe it could be written with higher kinded syntactic sugar as:
class Whatever(s: String?)
var x: Whatever! = new Whatever!(null)

<type>! = NonNullable[<type>]
<type>? = Nullable[<type>]

And you can use it on the definition site and the call site.


So the first example becomes:
val x: Nullable[String] = new Nullable[String](new
String(someJavaMethod())
val y: NonNullable[String] = new NonNullable[String](x match {

case null => ""
case other => other

})

becomes:

val x: String? = new String?(someJavaMethod())
val y: String! = new String! (x match {

case null => ""
case other => other

})


For Option you can have:
Option[Nullable[Int]] which is Option[Int?]
Option[NonNullable[Int]] which is Option[Int!]

[martin odersky]

topic/valclasses2 in my github. No pull request yet, I am waiting for M5 to ship before. 

- 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

[Jori Jovanovich]

On Jul 9, 2012, at 6:29 PM, Daniel Sobral wrote:

> Here's the peanut gallery: please do.

+1. One of the things that brought me to Scala is its willingness to make breaking changes to improve the language.

[Nils Kilden-Pedersen]

I would agree, but only because I make the assumption that those breaking changes would be easy to find and easy to fix.

 

[Rex Kerr]

With code that looks like

  case object SomeNotNull {}
  val n = Array.fill(1000)(util.Random.nextInt)
  val a = n.map(x => if (x>=0) Some(x.toString) else if (x%3==0) Some(null) else None)
  val b = n.map(x => (if (x>=0) x.toString else if (x%3==0) SomeNotNull else null): Object)
  val c = n.map(x => if (x>=0) Some(x.toString) else None)
  val d = n.map(x => if (x>=0) x.toString else null)

if you want to sum the lengths of the strings, then as long as you don't actually need to treat the null and Some(null) cases differently, I don't see a significant difference between the (b) case and the (d) case.  When using Option, either with an explicit Some(null) or not, it takes twice as long.

If instead we sum the positive integers (out of n directly) by calling an indicator function that returns Somes or Anys (with Integer or SomeNotNull packed therein, depending on whether the negative integer is divisible by three), then there is a significant difference: with the type checking and casting and stuff, the fastest is just java.lang.Integer which may or may not be null, while changing to Object with SomeNotNull in there slows things down by a factor of two (as does using Option without distinguishing the null case); the current situation with nulls stored slows things down by a factor of three.

Since value classes don't fit in arrays (I forgot about that before), I guess the latter case is closer to the intended use case, which does motivate getting rid of the Some(null) possibility (although this is a rather contrived example; you'd normally use Some[Int], not Some[java.lang.Integer] where the integer might be null).

   --Rex

[Bakos Gábor]

On 2012.07.10. 11:21, Johannes Rudolph wrote:
> All option types get the static type `Object`. Then the mapping could be this:
>
> Some(null) <==> SomeNullSingleton
> Some(x) <=> x
> None <=> null

As Option does not extends NotNull, you have to consider that option
too. Maybe it is more clear this way (if NotNulls specialcased in
Options and Option extends NotNull, your formulation seems better):
Some(null) <==> null
Some(x) <==> x
None <==> OurSpecialNone
null <==> OurSpecialNull

The problems might be related to the Object methods, as equals, hashCode
would behave differently, and synchronization issues might arise when
the new types are singleton (currently each Some(null) can be a
different object with own locks).

Should Option extend NotNull?

[Simon Ochsenreither]

Now that we have value classes, the next optimization frontier is Option.

By the way: https://groups.google.com/forum/?hl=en_US#!topic/ceylon-dev/QPVxX5XQSJo

[Johannes Rudolph]

On Tue, Jul 10, 2012 at 6:56 PM, Bakos Gábor <abor...@gmail.com> wrote:
> On 2012.07.10. 11:21, Johannes Rudolph wrote:
>> All option types get the static type `Object`. Then the mapping could be this:
>>
>> Some(null) <==> SomeNullSingleton
>> Some(x) <=> x
>> None <=> null
> As Option does not extends NotNull, you have to consider that option
> too. Maybe it is more clear this way (if NotNulls specialcased in
> Options and Option extends NotNull, your formulation seems better):
> Some(null) <==> null
> Some(x) <==> x
> None <==> OurSpecialNone
> null <==> OurSpecialNull

Yes, you are right, theoretically you would want to support this
additional value as well. BTW: I would try to give the most likely
values the simplest translation. That's why I would prefer `None`
being mapped to `null` because it is so common and will be a tiny bit
faster at creation than retrieving the OurSpecialNone instance.

[Josh Suereth]

If Option extends AnyVal (the premise of these optimizations I think), then it can no longer be assigned null.

You only have three possibilities:
Some(x)
Some(null)
None

While Some(null) has valid use cases, it seems assigning null to an Option variable is a scary thing to do.

[Francois]

Le 10/07/2012 14:29, Patrik Andersson a écrit :
> But but... Should we really be conflating "no value/ not defined" with
> "empty value"? This line of thinking sort of has "" (the empty
> string), () and [] also map to None.
>
> It's the problem of answering: "Is the light on in the kitchen?" when
> you don't know with a yes or a no.
>
> To me, I think that the issue here comes down to picking one of two
> paths, not conflating the two.
> 1. Exclude null from Option and carry the cost of doing so. If you
> (think you) need Some(null) then you will have to either let Option go
> or rethink something else. For instance by using a "null moniker"
> somehow. Map could publish its own (or make use of a new common)
> algebraic data type. A real data type in the style that doctor Josh
> has already proposed. (Found(x) | FoundNull | NotFound) It could be
> given a morphism onto Option but only if you would also give a
> function I the same domain that can translate the null case. That way
> it would be up to you to invent a fact about null <=> None or
> something like Some(MyZero).

Isn't that Either[NoResult, SomethingNullable] ?

--
Francois ARMAND
http://fanf42.blogspot.com
http://www.normation.com

[Francois]

Le 10/07/2012 01:29, Daniel Sobral a écrit :
> Here's the peanut gallery: please do. There's been dozens of threads
> about Option that stumbled upon the fact that Some(null) is legal.
>
> [...]

I would agree for that, and we gain some simplicity in the process:
Some(zswish) give you a non null zswish. Always. You see option as a
return type for some method in some external library, you don't have to
bother wondering if the external library correctly check for Java null
things.

And for people really, really wanting to use Some(null) to express some
three-state semantic, they can use Either[NoResult, NullableValue], or
Either[NullValue, Option[Value]] depending of their taste.

Cheers,