Hacker News Reader

Comment by joostdevries | Hacker News Reader

Well, some things do have the type unit or Any (top). How would you express that if that means 'not known' in your compiler?

View on HN

I think I don't understand your question. My remark was about his type Tree[T] of syntax trees annotated with values of type T. For syntax trees annotated with types he uses Tree[Type], which makes sense. Then for untyped syntax trees (i.e. trees without any annotation) he uses Tree[Nothing]. Now he needs unsafe hacks to get the desired subtype relationship Tree[Type] <: Tree[Nothing]. The compiler understands that Tree is covariant, so he overrides this with an unsafe annotation to make Tree contravariant. Using Nothing rather than the top/unit type (not sure what that's called in Scala, Any?) is what doesn't make sense to me. Intuitively an un-annotated tree is a Tree annotated with values that carry no information, not a tree annotated with values of the uninhabited type. If you use that you also get the desired subtyping relationship Tree[Type] <: Tree[Top] without any need for unsafe annotations.

Yes, Tree[Top] would have been another way to model this. I wanted Tree[Nothing] to make clear that getting the type of an untyped Tree gives a Nothing, i.e. a run-time error. Getting a Top is not quite the same, but it is almost as good, since only a view things can be done with type Any in Scala.

EDIT: There's one thing I did not stress in the talk and that makes Nothing a more attractive choice than Top: We want to do copy on write on these trees. I.e. if we transform an untyped tree to a typed one using "withType", we want to be able to reuse the untyped tree and just set the type (unless somebody else had already added another type). If the tree is of type Tree[Nothing], we can do that safely, even if there are still shared references to the same node as an untyped Tree. Getting the type of the shared untyped tree will give a Nothing, and nothing can be done with it. But if the type would be a Top, we would be able to apply some operations on it, so the copy on write would be unsafe.

Reply on news.ycombinator.com