Hacking on Dotty

A live demo

Guillaume Martres - EPFL

  • These slides are two-dimensional, the left and right arrow keys will skip over vertical slides
  • The space key will always go to the next slide

Dotty

  • Started by Martin Odersky in 2013
  • A new architecture
    • Except for the backend (bytecode generator) which is mostly shared with Scala 2.12
  • First goal: Simplify the internals of the type system
  • Has a Scala 2 compatibility mode
  • Couple of years from being production-ready

Tools

  • In progress:
  • To do (contributions welcome!):
    • Presentation compiler
    • Support for writing compiler plugins
    • ...

Trees, Types and Symbols

  • The compiler represents code using trees
  • To ensure type-safety, we attach types to trees
  • A tree might refer to an identifier defined in another tree or in the classpath, to each valid identifier corresponds a symbol looked up in the symbol table for the current scope, a symbol has a type
  • Each phase of the compiler pipeline simplifies trees and types until they can be easily expressed using Java bytecode
  • All of these data structures are immutable (or look immutable but use caching under the hood)

The compiler pipeline

Frontend

Generating trees and typing them

Untyped Tree

obj.fun(5)
obj.fun(5)
Apply(Select(Ident("obj"), "fun"), Literal(5))

Typed tree, first attempt


class A {
  def fun(x: Int): Int = x
}
val obj: A = new A
obj.fun(5)

Typed tree, first attempt fails

class A[T] {
  def fun(x: T): T = x
}
val obj: A[Int] = new A[Int]
obj.fun(5)

References to types

  • Symbols do not capture enough information
    • in an OO language with a rich type system, the prefix used to access an identifier matters
  • Let us introduce a special kind of type which refers to another type: 
    class TermRef(prefix: Type, name: String) extends Type
  • obj.fun gets type TermRef(x, "fun") which refers to the type Int => Int

The story so far

Denotation: linked list of lazily computed types

More accurate picture

Middle-End

Simplifing types and trees with successive transformations

Common pattern for transforming trees


override def transform(tree: Tree): Tree = {
  // call "transform" on every node that tree points to
  val tree1 = transformChildren(tree) 

  tree1 match {
    case tree: Apply =>
      // make a new tree and return it
      ...
    case tree: Select =>
      // make a new tree and return it
      ...
    case tree => // default case
      tree1
  }
}

Simplified API for common case


// Precondition of each transformX method: children nodes
// are already transformed by this phase
override def transformApply(tree: Apply): Tree = {
  // make a new tree and return it
  ...
}
override def transformSelect(tree: Select): Tree = {
  // make a new tree and return it
  ...
}
// No need to override transformX if we do not need to
// transform them

Demo

Let's implement a simple phase to trace method calls at runtime. The final code is at
https://github.com/smarter/dotty/commits/live-demo

References

Additional slides

Traditional phase design

1 phase = 1 full traversal

Mini-phase design

N fused mini-phases = 1 full traversal