Merge pull request #1775 from dotty-staging/add-implicit-funtypes

Add implicit function types

8 files changed, 588 insertions, 0 deletions

diff --git a/tests/bench/transactional/Benchmark.scala b/tests/bench/transactional/Benchmark.scala
new file mode 100644
index 000000000..8af7ebb83
--- /dev/null
+++ b/tests/bench/transactional/Benchmark.scala
@@ -0,0 +1,5 @@
+package transactional
+abstract class Benchmark {
+  def run(): Int
+}
+
diff --git a/tests/bench/transactional/ImplicitMega.scala b/tests/bench/transactional/ImplicitMega.scala
new file mode 100644
index 000000000..80e9c4a43
--- /dev/null
+++ b/tests/bench/transactional/ImplicitMega.scala
@@ -0,0 +1,67 @@
+package transactional
+object MegaBench extends Benchmark {
+  type Transactional[T] = implicit Transaction => T
+
+  def transaction[T](op: Transactional[T]): T = {
+    implicit val trans: Transaction = new Transaction
+    val res = op
+    trans.commit()
+    res
+  }
+
+  def thisTransaction: Transactional[Transaction] = implicitly[Transaction]
+
+  abstract class Op {
+    def f(x: Int): Transactional[Int]
+  }
+
+  class Op0 extends Op {
+    def f(x: Int): Transactional[Int] = {
+      thisTransaction.println("0th step")
+      x
+    }
+  }
+
+  class Op1 extends Op {
+    def f(x: Int): Transactional[Int] = {
+      thisTransaction.println("first step")
+      x + 1
+    }
+  }
+
+  class Op2 extends Op {
+    def f(x: Int): Transactional[Int] = {
+      thisTransaction.println("second step")
+      x + 2
+    }
+  }
+
+  class Op3 extends Op {
+    def f(x: Int): Transactional[Int] = {
+      thisTransaction.println("third step")
+      x + 3
+    }
+  }
+
+  val op = Array[Op](new Op0, new Op1, new Op2, new Op3)
+
+  def f(x: Int, n: Int): Transactional[Int] = {
+    thisTransaction.println("fourth step")
+    if (n > 0) f(op(n % 4).f(x), n - 1)
+    else {
+      if (x % 2 != 0) thisTransaction.abort()
+      x
+    }
+  }
+
+  def run(): Int = {
+    transaction {
+      val res = f(7, 10)
+      assert(!thisTransaction.isAborted)
+      assert(res == 22)
+      res
+    }
+  }
+}
+
+object ImplicitMega extends Runner("megamorphic", MegaBench, 22)
diff --git a/tests/bench/transactional/ImplicitMono.scala b/tests/bench/transactional/ImplicitMono.scala
new file mode 100644
index 000000000..10391f191
--- /dev/null
+++ b/tests/bench/transactional/ImplicitMono.scala
@@ -0,0 +1,45 @@
+package transactional
+object MonoBench extends Benchmark {
+  type Transactional[T] = implicit Transaction => T
+
+  def transaction[T](op: Transactional[T]): T = {
+    implicit val trans: Transaction = new Transaction
+    val res = op
+    trans.commit()
+    res
+  }
+
+  def thisTransaction: Transactional[Transaction] = implicitly[Transaction]
+
+  def f1(x: Int): Transactional[Int] = {
+    thisTransaction.println("first step")
+    f2(x + 1)
+  }
+  def f2(x: Int): Transactional[Int] = {
+    thisTransaction.println("second step")
+    f3(x * x)
+  }
+  def f3(x: Int): Transactional[Int] = {
+    thisTransaction.println("third step")
+    f4(x + 1, 7)
+  }
+  def f4(x: Int, n: Int): Transactional[Int] = {
+    thisTransaction.println("fourth step")
+    if (n > 0) f4(x + 1, n - 1)
+    else {
+      if (x % 2 != 0) thisTransaction.abort()
+      x
+    }
+  }
+
+  def run(): Int = {
+    transaction {
+      val res = f1(7)
+      assert(!thisTransaction.isAborted)
+      assert(res == 72)
+      res
+    }
+  }
+}
+
+object ImplicitMono extends Runner("monomorphic implicits", MonoBench, 72)
diff --git a/tests/bench/transactional/ReaderMonadic.scala b/tests/bench/transactional/ReaderMonadic.scala
new file mode 100644
index 000000000..ce69c35ad
--- /dev/null
+++ b/tests/bench/transactional/ReaderMonadic.scala
@@ -0,0 +1,87 @@
+package transactional
+
+case class Reader[R,A](run: R => A) {
+  def map[B](f: A => B): Reader[R, B] = Reader(r => f(run(r)))
+  def flatMap[B](f: A => Reader[R, B]): Reader[R, B] = Reader(r => f(run(r)).run(r))
+}
+
+object Reader {
+  def ask[R]: Reader[R,R] = Reader(r => r)
+}
+
+object ReaderBench extends Benchmark {
+  type Transactional[T] = Reader[Transaction, T]
+
+  def transaction[T](op: Transactional[T]): T = {
+    implicit val trans: Transaction = new Transaction
+    val res = op.run(trans)
+    trans.commit()
+    res
+  }
+
+  def thisTransaction: Transactional[Transaction] = Reader.ask
+
+  abstract class Op {
+    def f(x: Int): Transactional[Int]
+  }
+
+  class Op0 extends Op {
+    def f(x: Int): Transactional[Int] =
+      for (trans <- thisTransaction)
+      yield { trans.println("0th step"); x }
+  }
+
+  class Op1 extends Op {
+    def f(x: Int): Transactional[Int] =
+      for (trans <- thisTransaction)
+      yield { trans.println("first step"); x + 1 }
+  }
+
+  class Op2 extends Op {
+    def f(x: Int): Transactional[Int] =
+      for (trans <- thisTransaction)
+      yield { trans.println("second step"); x + 2 }
+  }
+
+  class Op3 extends Op {
+    def f(x: Int): Transactional[Int] =
+      for (trans <- thisTransaction)
+      yield { trans.println("third step"); x + 3 }
+  }
+
+  val op = Array[Op](new Op0, new Op1, new Op2, new Op3)
+
+  def f(x: Int, n: Int): Transactional[Int] = {
+    def rest(trans: Transaction): Transactional[Int] = {
+      trans.println("fourth step")
+      if (n > 0) {
+        for {
+          y <- op(n % 4).f(x)
+          z <- f(y: Int, n - 1)
+        }
+        yield z
+      }
+      else {
+        if (x % 2 != 0)
+          for (trans <- thisTransaction)
+          yield { trans.abort(); () }
+        Reader(_ => x)
+      }
+    }
+    thisTransaction.flatMap(rest)
+  }
+
+  def run(): Int = {
+    transaction {
+      for (res <- f(7, 10))
+      yield {
+        for (trans <- thisTransaction)
+        yield { assert(!trans.isAborted); () }
+        assert(res == 22)
+        res
+      }
+    }
+  }
+}
+
+object ReaderMonadic extends Runner("reader monadic", ReaderBench, 22)
diff --git a/tests/bench/transactional/Runner.scala b/tests/bench/transactional/Runner.scala
new file mode 100644
index 000000000..48da7ff12
--- /dev/null
+++ b/tests/bench/transactional/Runner.scala
@@ -0,0 +1,25 @@
+package transactional
+import System.nanoTime
+
+class Runner(name: String, bench: Benchmark, expected: Int) {
+
+  val numIters = 10000000
+  val numTests = 5
+
+  def run(): Unit = {
+    val start = nanoTime
+    var cnt = 0
+    var i = 0
+    while (i < numIters) {
+      cnt += bench.run()
+      i += 1
+    }
+    assert(cnt == expected * numIters)
+    val duration = nanoTime - start
+    println(s"$name in ${duration / 1000000}ms")
+  }
+
+  def main(args: Array[String]) =
+    for (i <- 0 until numTests)
+      run()
+}
diff --git a/tests/bench/transactional/Transaction.scala b/tests/bench/transactional/Transaction.scala
new file mode 100644
index 000000000..dbb28d452
--- /dev/null
+++ b/tests/bench/transactional/Transaction.scala
@@ -0,0 +1,21 @@
+package transactional
+import collection.mutable.ListBuffer
+
+class Transaction {
+  private val log = new ListBuffer[String]
+  def println(s: String): Unit = log += s
+
+  private var aborted = false
+  private var committed = false
+
+  def abort(): Unit = { aborted = true }
+  def isAborted = aborted
+
+  def commit(): Unit =
+    if (!aborted && !committed) {
+      //Console.println("******* log ********")
+      //log.foreach(Console.println)
+      committed = true
+    }
+}
+
diff --git a/tests/bench/transactional/results.md b/tests/bench/transactional/results.md
new file mode 100644
index 000000000..702617ebb
--- /dev/null
+++ b/tests/bench/transactional/results.md
@@ -0,0 +1,77 @@
+# Benchmark results for implicit compilation scenarios
+
+### Setup
+
+Three alternatives:
+
+  1. No implicit shortcuts
+  2. Implicit shortcuts only for possible targets of megamorphic dispatch
+     (`specializeMonoTargets` in [ShortcutImplicits.scala](../../../compiler/src/dotty/tools/dotc/transform/ShortcutImplicits.scala) set to false)
+  3. Implicit shortcuts for all methods returning implicit function types
+     (`specializeMonoTargets` set to true)
+
+Two benchmarks:
+
+ - `ImplicitMono`:  All calls are monomorphic.
+                    Code in [ImplicitMono.scala](./ImplicitMono.scala).
+ - `ImplicitMega` : About half of the calls are (4-way) megamorphic,
+                    the others are monomorphic.
+                    Code in [ImplicitMega.scala](./ImplicitMega.scala).
+
+### Results
+
+| Scheme              | ImplicitMono | ImplicitMega |
+|---------------------|-------------:|-------------:|
+| no shortcuts        | 1354ms       | 3260ms
+|                     | 955ms        | 2906ms
+|                     | 908ms        | 2899ms
+|                     | 906ms        | 2887ms
+|                     | 886ms        | 2872ms
+| only mega shortcuts |        |
+                      | 1243ms | 2472ms
+|                     | 926ms  | 2146ms
+|                     | 925ms  | 2169ms
+|                     | 902ms  | 2136ms
+|                     | 913ms  | 2179ms
+| all shortcuts       |        |
+|                     | 1354ms | 1940ms
+|                     | 1039ms | 1563ms
+|                     | 1031ms | 1593ms
+|                     | 1065ms | 1548ms
+|                     | 1016ms | 1579ms
+
+### Interpretation
+
+In the fully monomorphic benchmark, specializing
+only megamorphic targets has the same performance as
+not specializing at all (not surprising, since there
+are no megamorphic targets). Specializing everything
+incurs about a 14% performance hit (maybe due to the extra
+code generated; it's hard to pin down what it is).
+
+Note: We compute relative performance differences by comparing the
+second-best test runs of each series with each other.
+
+In the megamorphic benchmark, it's the other way round.
+Specializing only megamorphic call-sites leads to a performance
+improvement of about 36% compared to no specialization. Specializing
+everything leads to another 37% improvement (85% total compared
+to no specialization).
+
+I think we need larger benchmarks to decide whether we should
+specialize monomorphic call-targets or not.
+
+### Comparing with the Reader Monad
+
+Translating `ImplicitMega` to the reader monad (code in [ReaderMonadic.scala](./ReaderMonadic.scala)) gives the following runtimes:
+
+| Reader |
+|---------|
+| 11563ms |
+| 11108ms |
+| 11300ms |
+| 11098ms |
+| 11159ms |
+
+This translates to a 710% slowdown compared to implicit function types
+with full specialization.
\ No newline at end of file
diff --git a/tests/run/implicitFuns.scala b/tests/run/implicitFuns.scala
new file mode 100644
index 000000000..496fba0d3
--- /dev/null
+++ b/tests/run/implicitFuns.scala
@@ -0,0 +1,261 @@
+object Test {
+  def main(args: Array[String]): Unit = {
+
+    implicit val world: String = "world!"
+
+    val i1 = (implicit (s: String) => s.length > 2)
+    val i2 = {implicit (s: String) => s.length > 2}
+
+    assert(i1)
+    assert(i2)
+
+    val x: implicit String => Boolean = { implicit (s: String) => s.length > 2 }
+
+    val xx: implicit (String, Int) => Int = implicit (x: String, y: Int) => x.length + y
+
+    val y: String => Boolean = x
+
+    object nested {
+      implicit val empty: String = ""
+      assert(!x)
+    }
+
+    val yy: (String, Int) => Any = xx
+
+    val z1: implicit String => Boolean = implicitly[String].length >= 2
+    assert(z1)
+
+    type StringlyBool = implicit String => Boolean
+
+    val z2: StringlyBool = implicitly[String].length >= 2
+    assert(z2)
+
+    type Stringly[T] = implicit String => T
+
+    val z3: Stringly[Boolean] = implicitly[String].length >= 2
+    assert(z3)
+
+    type GenericImplicit[X] = implicit X => Boolean
+
+    val z4: GenericImplicit[String] = implicitly[String].length >= 2
+    assert(z4)
+
+    val b = x("hello")
+
+    val b1: Boolean = b
+
+    val bi = x
+
+    val bi1: Boolean = bi
+
+    val c = xx("hh", 22)
+
+    val c1: Int = c
+
+    Contextual.main(args)
+
+    def foo(s: String): Stringly[Int] = 42
+
+    (if ("".isEmpty) foo("") else foo("")).apply("")
+  }
+}
+
+object Contextual {
+
+  class Key[+V]
+
+  class Context(bindings: Map[Key[Any], Any]) {
+    def binding[V](key: Key[V]): Option[V] =
+      bindings.get(key).asInstanceOf[Option[V]]
+    def withBinding[V](key: Key[V], value: V): Context =
+      new Context(bindings + ((key, value)))
+  }
+
+  val rootContext = new Context(Map())
+
+  val Source = new Key[String]
+  val Options = new Key[List[String]]
+
+  type Ctx[T] = implicit Context => T
+
+  def ctx: Ctx[Context] = implicitly[Context]
+
+  def compile(s: String): Ctx[Boolean] =
+    runOn(new java.io.File(s))(ctx.withBinding(Source, s)) >= 0
+
+  def runOn(f: java.io.File): Ctx[Int] = {
+    val options = List("-verbose", "-explaintypes")
+    process(f).apply(ctx.withBinding(Options, options))
+  }
+
+  def process(f: java.io.File): Ctx[Int] =
+    ctx.binding(Source).get.length - ctx.binding(Options).get.length
+
+  def main(args: Array[String]) = {
+    implicit val context: Context = rootContext
+    assert(compile("abc"))
+    assert(compile("ab"))
+    assert(!compile("a"))
+  }
+}
+
+import collection.mutable.ListBuffer
+
+class Transaction {
+  private val log = new ListBuffer[String]
+  def println(s: String): Unit = log += s
+
+  private var aborted = false
+  private var committed = false
+
+  def abort(): Unit = { aborted = true }
+  def isAborted = aborted
+
+  def commit(): Unit =
+    if (!aborted && !committed) {
+      Console.println("******* log ********")
+      log.foreach(Console.println)
+      committed = true
+    }
+}
+
+object TransactionalExplicit {
+
+  def transaction[T](op: Transaction => T) = {
+    val trans: Transaction = new Transaction
+    op(trans)
+    trans.commit()
+  }
+
+  def f1(x: Int)(implicit thisTransaction: Transaction): Int = {
+    thisTransaction.println(s"first step: $x")
+    f2(x + 1)
+  }
+  def f2(x: Int)(implicit thisTransaction: Transaction): Int = {
+    thisTransaction.println(s"second step: $x")
+    f3(x * x)
+  }
+  def f3(x: Int)(implicit thisTransaction: Transaction): Int = {
+    thisTransaction.println(s"third step: $x")
+    if (x % 2 != 0) thisTransaction.abort()
+    x
+  }
+
+  def main(args: Array[String]) = {
+    transaction {
+      implicit thisTransaction =>
+        val res = f1(args.length)
+        println(if (thisTransaction.isAborted) "aborted" else s"result: $res")
+    }
+  }
+}
+
+object Transactional {
+  type Transactional[T] = implicit Transaction => T
+
+  def transaction[T](op: Transactional[T]) = {
+    implicit val trans: Transaction = new Transaction
+    op
+    trans.commit()
+  }
+
+  def thisTransaction: Transactional[Transaction] = implicitly[Transaction]
+
+  def f1(x: Int): Transactional[Int] = {
+    thisTransaction.println(s"first step: $x")
+    f2(x + 1)
+  }
+  def f2(x: Int): Transactional[Int] = {
+    thisTransaction.println(s"second step: $x")
+    f3(x * x)
+  }
+  def f3(x: Int): Transactional[Int] = {
+    thisTransaction.println(s"third step: $x")
+    if (x % 2 != 0) thisTransaction.abort()
+    x
+  }
+
+  def main(args: Array[String]) = {
+    transaction {
+      val res = f1(args.length)
+      println(if (thisTransaction.isAborted) "aborted" else s"result: $res")
+    }
+  }
+}
+
+object TransactionalExpansion {
+
+  def transaction[T](op: Transaction => T) = {
+    val trans: Transaction = new Transaction
+    op.apply(trans)
+    trans.commit()
+  }
+
+  def thisTransaction = $t: Transaction => $t
+
+  def f1(x: Int) = { $t: Transaction =>
+    thisTransaction.apply($t).println(s"first step: $x")
+    f2(x + 1).apply($t)
+  }
+  def f2(x: Int) = { $t: Transaction =>
+    thisTransaction.apply($t).println(s"second step: $x")
+    f3(x * x).apply($t)
+  }
+  def f3(x: Int) = { $t: Transaction =>
+    thisTransaction.apply($t).println(s"third step: $x")
+    if (x % 2 != 0) thisTransaction.apply($t).abort()
+    x
+  }
+
+  def main(args: Array[String]) = {
+    transaction { $t =>
+      val res = f1(args.length).apply($t)
+      println(if (thisTransaction.apply($t).isAborted) "aborted" else s"result: $res")
+    }
+  }
+}
+
+object TransactionalAbstracted {
+  type Transactional[T] = implicit Transaction => T
+
+  trait TransOps {
+    def thisTransaction: Transactional[Transaction]
+    def f1(x: Int): Transactional[Int]
+    def f2(x: Int): Transactional[Int]
+    def f3(x: Int): Transactional[Int]
+  }
+
+  object TransOpsObj extends TransOps {
+
+    def thisTransaction: Transactional[Transaction] = implicitly[Transaction]
+
+    def f1(x: Int): Transactional[Int] = {
+      thisTransaction.println(s"first step: $x")
+      f2(x + 1)
+    }
+    def f2(x: Int): Transactional[Int] = {
+      thisTransaction.println(s"second step: $x")
+      f3(x * x)
+    }
+    def f3(x: Int): Transactional[Int] = {
+      thisTransaction.println(s"third step: $x")
+      if (x % 2 != 0) thisTransaction.abort()
+      x
+    }
+  }
+
+  val transOps: TransOps = TransOpsObj
+
+  def transaction[T](op: Transactional[T]) = {
+    implicit val trans: Transaction = new Transaction
+    op
+    trans.commit()
+  }
+
+  def main(args: Array[String]) = {
+    transaction {
+      val res = transOps.f1(args.length)
+      println(if (transOps.thisTransaction.isAborted) "aborted" else s"result: $res")
+    }
+  }
+}