The linked page links to a set of slides: http://www.slideshare.net/Odersky/compilers-are-databases

I have a question regarding slides 29 to 31.

The author says an untyped tree is represented as Tree[Nothing]. This leads to undesired variance behavior which is in turn overriden.

But there cannot be any instances of type Tree[Nothing] because there are no instances of type Nothing. Wouldn't an untyped tree be better represented as Tree[Unit]?

There can be instances of Tree[Nothing], just like there can be instances of List[Nothing]. It just means that in a scenario like this:

    class Tree[T] { def elem: T }

if t is a Tree[Nothing] then t.elem will not return normally (it might throw an exception instead).

Ok, so there are instances, which throw exceptions, fine, we're in Java land after all, where anything can happen. But why is Tree[Nothing] more useful than Tree[Unit]? Both contain the same amount of information (both Nothing and Unit convey zero bits of information), but one throws an exception while the other is safe at runtime.

Tree[Nothing] is a subtype of all Tree[_] types. This is similar to Nil in scala, which is really a singleton implementation of List[Nothing] or None, which is a singleton implementation of Option[Nothing]. Unit does not have this property, it is just a subtype of AnyVal/Any.

Basically, Tree[Nothing] allows you to indicate that a Tree is empty via the type system while still allowing you to use that same type to build an actual tree from. If Nil was List[Unit] instead of List[Nothing], 1 :: Nil would be a compile time error instead of a List[Int].

Oh, and Unit does have an implementation in scala called "()", so if you had a Tree[Unit] you would not be able to tell if it was actually empty or not. You can see this in scala with () :: Nil. It produces a non-empty List[Unit]. Nothing has no such implementation. As for the exceptions, there's not much you can do wrt that. What should happen if you call head on an empty List? That's a straight-out error. headOption or a match block is the safe way to deal with lists if you don't want to have exceptions ever.

Thank you.