Dotty: exploring the future of scala

Video of this talk on Youtube:

Dotty?

• a new compiler for a Scala-like language
• developed at LAMP EPFL
• is currently not ready for production use
• some of the new technologies explored in this project will find their way into future versions of Scala

About me:

• https://github.com/darkdimius/
• doing PhD at EPFL
• previously worked on ScalaBlitz
• since March 2014 year working on Dotty.

Dotty contributor stats:

Talk Structure

• Part 1: What dotty is expected to bring to the table
  • Language:
    • Union(|) and Intersection(&) Types
    • SIP-23: Literal-based Singleton Types
    • SIP-24: Repeated By Name Parameters
    • SIP-25: Trait Parameters
    • SIP-20: Improved Lazy Vals Initialization
    • Deprecations
  • Ecosystem:
    • Tasty
    • scala.meta
    • Linker
    • Compilation speed

Talk Structure

• Part 2: Internals
  • Denotations
  • Denotation Transformers
  • Mini-phases
  • Tree Checkers and postconditions

Intersection(&) types

similar to Scala2 with

def foo(arg: Serializable & Comparable): Unit

Intersection(&) types

similar to Scala2 with

trait A {
  type T = Int
}

trait B {
  type T = Double
}

(A with B) # T == Int
(A & B) # T == Int & Double

Intersection(&) types

what is the difference?

with is ordered, & is not

A with B is different from B with A. & is not

Union(|) types

Scala2 equivalent: none

class A(x: Int)
class B(x: Int)
class C(x: Array[Int])

object Test{
  def foo(x: A | B): Int = x.x
  def bar(x: A | C): Int | Array[Int] = x.x
}

Union(|) types: proper Enumerations

object DaysOfTheWeek{
  object Mon
  object Tue
  object Wed
  object Thu
  object Fri
  object Sat
  object Sun

  type Weekend = Sat.type | Sun.type
  type Workweek = Mon.type | Tue.type | Wed.type | Thu.type | Fri.type
  type All = Weekend | Workweek
}

SIP-23: Literal-based singleton types

object Literals{
  val fortyTwo: 42 = 42
  val `2`: 2 = 2
  val fortyFour: 44 = fortyTwo + `2`
  val text: "text" = "text"

  def id[T](a: T) = a
  val two: 2 = id(`2`)
}

SIP-24: Repeated By Name Parameters

=> T* means Function0[Seq[T]]

object DaysOfTheWeek{
  def foo(a: => Any*) = ()
  def bar(a: => Any*) = foo(a : _*)
  def baz(a: => Seq[Any]) = foo(a : _*)

  bar(???, ???)
  baz(Seq(???, ???))

}

SIP-25: Trait parameters

trait A(val i: Int)

SIP-25: Trait parameters

trait A(val i: Int)

trait A1 extends A(1)
trait A2 extends A(2)

object O extends A1 with A2 {
  // is i == 1 or i == 2
  // how many times was it initialized?
}

SIP-25: Trait parameters: Details

trait A(val i: Int)

trait B extends A

class  C extends B with A(1)
object O extends A(2) with B

SIP-20: Improved Lazy Val Initialization

object A {
  lazy val a0 = B.b
  lazy val a1 = 17
}

object B {
  lazy val b = A.a1
}

SIP-20: Improved Lazy Val Initialization

object A {
  lazy val a0 = B.b // <-- Thread 1
  lazy val a1 = 17
}

object B {
  lazy val b = A.a1 // <-- Thread 2
}

SIP-20: Improved Lazy Val Initialization

object A {
  lazy val a0 = B.b // <-- Thread 1, grabs lock
  lazy val a1 = 17
}

object B {
  lazy val b = A.a1 // <-- Thread 2
}

SIP-20: Improved Lazy Val Initialization

object A {
  lazy val a0 = B.b // <-- Thread 1, grabs lock
  lazy val a1 = 17
}

object B {
  lazy val b = A.a1 // <-- Thread 2, grabs lock
}

SIP-20: Improved Lazy Val Initialization

object A {
  lazy val a0 = B.b // <-- Thread 1, grabs lock
  lazy val a1 = 17  // Potential deadlock
}

object B {
  lazy val b = A.a1 // <-- Thread 2, grabs lock
}

SIP-20: Improved Lazy Val Initialization

object C {
  lazy val a0 = { /* long computation with IO */ } // <-- Thread 1
  lazy val a1 = 42  // <-- Thread 2 will be waiting for Thread 1 to finish
}

SIP-20: Improved Lazy Val Initialization

Dotty lazy values:

• do not deadlock
• allow concurrent initialization of independent fields
• are thread unsafe by default
• are 40% faster to access by default
• need to use @volatile to request thead-safeness
• if @volatile is used, 5% faster than in scala2 (one non-volatile read vs volatile read)

Deprecations

object Test {
  def foo() { // procedure syntax
  }
}

Deprecations

object Test {
  def foo(): Unit = { // procedure syntax
  }
}

Deprecations: DelayedInit

/* Classes and objects (but note, not traits) inheriting the `DelayedInit`
*  marker trait will have their initialization code rewritten as follows:
*  `code` becomes `delayedInit(code)`
*/

Deprecations: DelayedInit

trait Helper extends DelayedInit {
  def delayedInit(body: => Unit) = {
    println("dummy text, printed before initialization of C")
    body // evaluates the initialization code of C
  }
}

class C extends Helper {
  println("this is the initialization code of C")
}

new C
// dummy text, printed before initialization of C
// this is the initialization code of C

Deprecations: DelayedInit. Replacement: By-name args in traits

trait Helper(body: => Unit) {
  println("dummy text, printed before initialization of C")
  body // evaluates the initialization code of C
}

class C extends Helper(println("this is the initialization code of C"))


new C
// dummy text, printed before initialization of C
// this is the initialization code of C

Ecosystem

Ecosystem: Binary compatibility

Ecosystem: Binary compatibility

Ecosystem: Binary compatibility

Ecosystem: Binary compatibility

Ecosystem: Binary compatibility.

Library author perspective:

• should be carefull about what they depend on
• should publish multiple versions of same library
• compiled for multiple versions of scalac

Ecosystem: Binary compatibility.

Library user perspective:

• if a library that you depend on is legacy, you have a problem
• if a library that you depend on is experimental, you have a problem

Ecosystem: Binary compatibility.

Java8

Java 8 is coming

• provides new features. Will be used by scala 2.12 by default
• is incompatible with Java 7
• is incompatible with Android

Ecosystem: Binary compatibility.

JavaScript

Ecosystem: Binary compatibility.

Typelevel, Policy & other forks

Developing a library,
you need to consider publishing for
(2.10, 2.11, 2.12) x (java6, java8, JS) x (Typesafe, Typelevel)

Why???

This should not bother developers!!!

Ecosystem: TASTY

Proposed by scala.meta.

Interchange format that stores:

• Trees
• Types
• Positions
• Custom sections

Ecosystem: Tasty

Ecosystem: TASTY

• Allows to get scala source from compiled classfiles
• Is not vulnerable to changes in implicit resolution
• No need to push multiple artifacts to maven. Dotty can recompile from TASTY

Ecosystem: ScalaMeta

• Metaprogramming done right

Previous project: Scalablitz

• Tunes collection operations for your use-case
• Gets ridiculous speedups(40x, 120x) for simple code, eg Array[Int].reduce(_+_)
• Less garbage allocated
• Better memory locality & cpu throuput utilization

Ecosystem: Linker

• Does the very same for any library
• Tunes library for your use-case
• Removes allocations, closures, virtual calls
• A smarter proguard
• Details: video, slides

Compilation speed

• Dotty has design decisions that allow to get substantial speedups
• MiniPhases and their fusion
• Info transformers
• We did not yet do any performance tuning, but
• Compiling Hello world takes 1.4 sec vs 1.6 sec by scalac
• Compiling Dotty itself takes 27 sec vs 42 sec by scalac

• Part 2: Internals
  • Not a big cake
  • Context instead of global mutable state
  • Denotations
  • Denotation Transformers
  • Mini-phases
  • Tree Checkers and postconditions

Not a big cake

Scalac is a big cake:

• everything depends on everything
• hard to detect what is used where
• namespace polution
• where should a method be
• hard to modularize functionality

Not a big cake

Dotty has several small cakes:

• Context
• Typer
• Pattern-matcher
• GenBCode

Scalac: global mutable state

Dotty: everyting needs a Context

  def typed(tree: untpd.Tree, pt: Type = WildcardType)(implicit ctx: Context): Tree

Dotty: everyting needs a Context

def tryEither[T](op: Context => T)(fallBack: (Context) => T)(implicit ctx: Context) = {
  val nestedCtx = ctx.fresh.setNewTyperState
  val result = op(nestedCtx)
  if (nestedCtx.reporter.hasErrors)
    fallBack(ctx)
  else {
    nestedCtx.typerState.commit()
    result
  }
}

Symbols

They change meaning depending on phase of compilation:

• classes obtain and lose members
• methods and values change types
• methods, values and classes change location where they are(lambdalift)

Denotations

• Represent meaning of a symbol or type in particular period.
• Forms a circular linked list with future and previous meanings.
• Full versioning of all the info: type, name, flags

Denotations

class C {
  def id[T](t: T) = t
}

Denotations

Denotations

Denotation Transformers

/** A transformer transforms denotations at a given phase */
trait DenotTransformer extends Phase {
  /** The transformation method */
    def transform(ref: SingleDenotation)(implicit ctx: Context): SingleDenotation
}

Macro Phases

Macro Phases

Macro Phases

• Every phase traverses a tree independently
• Reading cold data
• Creating new subtrees
• That live long and are promoted to OldGen of GC

Does LazyVals implement LazyVals?

Macro phases

    phase name  id  description
    ----------  --  -----------
        parser   1  parse source into ASTs, perform simple desugaring
         namer   2  resolve names, attach symbols to named trees
packageobjects   3  load package objects
         typer   4  the meat and potatoes: type the trees
        patmat   5  translate match expressions
superaccessors   6  add super accessors in traits and nested classes
    extmethods   7  add extension methods for inline classes
       pickler   8  serialize symbol tables
     refchecks   9  reference/override checking, translate nested objects
       uncurry  10  uncurry, translate function values to anonymous classes
     tailcalls  11  replace tail calls by jumps
    specialize  12  @specialized-driven class and method specialization
 explicitouter  13  this refs to outer pointers
       erasure  14  erase types, add interfaces for traits
   posterasure  15  clean up erased inline classes
      lazyvals  16  allocate bitmaps, translate lazy vals into lazified defs
    lambdalift  17  move nested functions to top level
  constructors  18  move field definitions into constructors
       flatten  19  eliminate inner classes
         mixin  20  mixin composition
       cleanup  21  platform-specific cleanups, generate reflective calls
    delambdafy  22  remove lambdas
         icode  23  generate portable intermediate code
           jvm  24  generate JVM bytecode
      terminal  25  the last phase during a compilation run

No, Mixin does.

If you want performance, you do not want many Macro phases

Why? Macro phases cost a lot

Half of phases do `something` additionally

Mini Phases

Mini Phases

Mini Phases

Mini Phases

• Phases share tree traversal
• Trees you are accessing are hot
• Trees die fast and do not get promoted to OldGen of GC

Tree checkers and postconitions

Under Y-check:all after each phase:

• retype all the trees
• check that types are correct
• check that owners are correct
• check that there are no double definitions
• check that companion links don't get broken
• ckeck that there are no invalid names(eg, constructors have name < init >)
• check all postconditions defined by previous phases

Tree checkers and postconitions

Examples of postconditions:

• Erasure: check that all trees are erazed
• ExpandPrivate: check that public members are not overriden by private ones
• Constructors: check that all statements are lifted from body of the class to constructor

Thank you.

See my other talks.