Avoid Eagerly Evaluating Implicit Function Types

This is a follow up on a brief discussion at https://github.com/lampepfl/dotty-feature-requests/issues/83.

Implicit function types are a very interesting way to express dependencies and provide language support for a concept of a type level set of dependencies where we can seamlessly reorder or partially eliminate dependencies. However, the way the compiler attempts to “eagerly” evaluate implicit function types can make them unergonomic to use.

For example, a naive encoding of ZIO in Dotty could be:

type ZIO[-R, +E, +A] = (given R) => Either[E, A]

We could then write:

val x: ZIO[String, Nothing, Int] = ???

However, if we then want to use this like a normal value we need explicit type ascription with each assignment to avoid the compiler attempting to immediately resolve the implicit.

val y: ZIO[String, Nothing, Int] = x // okay
val z = x // does not compile: no implicit argument of type String was found

Is there a way that we could defer trying to evaluate the implicit function and just carry the dependency along with us?

The challenge seems to be developing a set of rules for when the compiler should attempt to resolve the implicit versus carrying it along as an implicit function type.

It seems like we could have a rule along the lines of “don’t require the implicit if there is no appropriate implicit value in scope and the code type checks appropriately with maintaining the implicit function type”. This would I think be pretty seamless, though it would create some risk of accidentally resolving the implicit early if there was an unanticipated implicit in scope.

An alternative would be to require some action to more explicitly resolve the implicit, like a type ascription to a non-implicit value or passing it to a function that demands the result type instead of an implicit function type.

My concern is that the most interesting applications of implicit function types involve dependencies that we want to carry along for a long time, possibly until the very end of our program, so if we require a type ascription on every statement to prevent us from doing that it is going to make them unattractive for this use case they are very well suited to.

Thank you for your consideration.

4 Likes

AFAIK If you don’t specify the return type, a given function type will be inferred. I think this is used in scala-effekt implementation. I may be wrong or maybe something changed though

This is the example I was looking at that seems to indicate that if a return type isn’t specified, a given function type won’t be inferred.

1 Like

Even the following doesn’t compile https://scastie.scala-lang.org/j9AiiRL7SdeCl7tFc29wWQ

  val x: ZIO[String, Nothing, Int] = ???
  val y: x.type = x // does not compile: no implicit argument of type String was found

That’s correct. Implicit function types are always produced from the context, never the term itself. In other words, their inference is always top-down, never bottom up. This has to be that way, changing this would bring the whole construction down. Our POPL paper contains a calculus of bidirectional typing rules that explains this in detail.

One could possibly refine (i.e. complicate) the rules so that val y: x.type = x compiles without bringing the whole construction down. But I doubt it is worth it.

3 Likes

Thanks! Is there anything we could do in either the compiler or the way users write code with implicit function types to avoid having to do type ascriptions for every assignment? I tried putting the implicit function type into a case class like:

final case class ZIO[-R, +E, +A](run: (given R) => Either[E, A])

However, it looks like this is not allowed, potentially for the reasons you discuss above.

Any other ideas of how we can make this more ergonomic? I think implicit function types are very interesting but I am worried that users don’t want to have to specify types for assignments, at least on any regular basis.

3 Likes

When I try this in scastie I get internal compiler error:

java.lang.Error: internal error: type of right-hand side (e[33mgiven e[0m(?)) => Either[E, A] is not fully defined, pos = <55..97>
	at dotty.tools.dotc.typer.Inferencing$.fullyDefinedType(Inferencing.scala:44)
	at dotty.tools.dotc.typer.Namer.lhsType$1(Namer.scala:1375)
	at dotty.tools.dotc.typer.Namer.inferredType$1(Namer.scala:1386)
	at dotty.tools.dotc.typer.Namer.valOrDefDefSig(Namer.scala:1394)
	at dotty.tools.dotc.typer.Namer.defDefSig(Namer.scala:1463)
	at dotty.tools.dotc.typer.Namer$Completer.typeSig(Namer.scala:786)
	at dotty.tools.dotc.typer.Namer$Completer.completeInCreationContext(Namer.scala:906)
	at dotty.tools.dotc.typer.Namer$Completer.complete(Namer.scala:814)
	at dotty.tools.dotc.core.SymDenotations$SymDenotation.completeFrom(SymDenotations.scala:257)
	at dotty.tools.dotc.core.Denotations$Denotation.completeInfo$1(Denotations.scala:182)
	at dotty.tools.dotc.core.Denotations$Denotation.info(Denotations.scala:184)
	at dotty.tools.dotc.core.SymDenotations$SymDenotation.ensureCompleted(SymDenotations.scala:397)
	at dotty.tools.dotc.typer.Typer.retrieveSym(Typer.scala:2012)
	at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:2037)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2115)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2152)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2164)
	at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:2183)
	at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:2227)
	at dotty.tools.dotc.typer.Typer.typedClassDef(Typer.scala:1731)
	at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:2050)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2115)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2152)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2164)
	at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:2183)
	at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:2227)
	at dotty.tools.dotc.typer.Typer.typedClassDef(Typer.scala:1731)
	at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:2050)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2115)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2152)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2164)
	at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:2183)
	at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:2227)
	at dotty.tools.dotc.typer.Typer.typedPackageDef(Typer.scala:1852)
	at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:2091)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2116)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2152)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2164)
	at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:2240)
	at dotty.tools.dotc.typer.FrontEnd.liftedTree9$2(FrontEnd.scala:78)
	at dotty.tools.dotc.typer.FrontEnd.typeCheck$$anonfun$1(FrontEnd.scala:83)
	at dotty.runtime.function.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
	at dotty.tools.dotc.typer.FrontEnd.monitor(FrontEnd.scala:42)
	at dotty.tools.dotc.typer.FrontEnd.typeCheck(FrontEnd.scala:84)
	at dotty.tools.dotc.typer.FrontEnd.runOn$$anonfun$3(FrontEnd.scala:114)
	at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:15)
	at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:10)
	at scala.collection.immutable.List.foreach(List.scala:305)
	at dotty.tools.dotc.typer.FrontEnd.runOn(FrontEnd.scala:114)
	at dotty.tools.dotc.Run.runPhases$4$$anonfun$4(Run.scala:162)
	at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:15)
	at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:10)
	at scala.collection.ArrayOps$.foreach$extension(ArrayOps.scala:1323)
	at dotty.tools.dotc.Run.runPhases$5(Run.scala:172)
	at dotty.tools.dotc.Run.compileUnits$$anonfun$1(Run.scala:180)
	at dotty.runtime.function.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
	at dotty.tools.dotc.util.Stats$.maybeMonitored(Stats.scala:65)
	at dotty.tools.dotc.Run.compileUnits(Run.scala:187)
	at dotty.tools.dotc.Run.compileSources(Run.scala:124)
	at dotty.tools.dotc.Run.compile(Run.scala:107)
	at dotty.tools.dotc.Driver.doCompile(Driver.scala:36)
	at dotty.tools.dotc.Driver.process(Driver.scala:189)
	at dotty.tools.dotc.Main.process(Main.scala)
	at xsbt.CachedCompilerImpl.run(CachedCompilerImpl.java:69)
	at xsbt.CompilerInterface.run(CompilerInterface.java:41)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at sbt.internal.inc.AnalyzingCompiler.call(AnalyzingCompiler.scala:248)
	at sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:122)
	at sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:95)
	at sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$4(MixedAnalyzingCompiler.scala:91)
	at scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:23)
	at sbt.internal.inc.MixedAnalyzingCompiler.timed(MixedAnalyzingCompiler.scala:186)
	at sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$3(MixedAnalyzingCompiler.scala:82)
	at sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$3$adapted(MixedAnalyzingCompiler.scala:77)
	at sbt.internal.inc.JarUtils$.withPreviousJar(JarUtils.scala:215)
	at sbt.internal.inc.MixedAnalyzingCompiler.compileScala$1(MixedAnalyzingCompiler.scala:77)
	at sbt.internal.inc.MixedAnalyzingCompiler.compile(MixedAnalyzingCompiler.scala:146)
	at sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1(IncrementalCompilerImpl.scala:343)
	at sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1$adapted(IncrementalCompilerImpl.scala:343)
	at sbt.internal.inc.Incremental$.doCompile(Incremental.scala:120)
	at sbt.internal.inc.Incremental$.$anonfun$compile$4(Incremental.scala:100)
	at sbt.internal.inc.IncrementalCommon.recompileClasses(IncrementalCommon.scala:180)
	at sbt.internal.inc.IncrementalCommon.cycle(IncrementalCommon.scala:98)
	at sbt.internal.inc.Incremental$.$anonfun$compile$3(Incremental.scala:102)
	at sbt.internal.inc.Incremental$.manageClassfiles(Incremental.scala:155)
	at sbt.internal.inc.Incremental$.compile(Incremental.scala:92)
	at sbt.internal.inc.IncrementalCompile$.apply(Compile.scala:75)
	at sbt.internal.inc.IncrementalCompilerImpl.compileInternal(IncrementalCompilerImpl.scala:348)
	at sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileIncrementally$1(IncrementalCompilerImpl.scala:301)
	at sbt.internal.inc.IncrementalCompilerImpl.handleCompilationError(IncrementalCompilerImpl.scala:168)
	at sbt.internal.inc.IncrementalCompilerImpl.compileIncrementally(IncrementalCompilerImpl.scala:248)
	at sbt.internal.inc.IncrementalCompilerImpl.compile(IncrementalCompilerImpl.scala:74)
	at sbt.Defaults$.compileIncrementalTaskImpl(Defaults.scala:1761)
	at sbt.Defaults$.$anonfun$compileIncrementalTask$1(Defaults.scala:1734)
	at scala.Function1.$anonfun$compose$1(Function1.scala:49)
	at sbt.internal.util.$tilde$greater.$anonfun$$u2219$1(TypeFunctions.scala:62)
	at sbt.std.Transform$$anon$4.work(Transform.scala:67)
	at sbt.Execute.$anonfun$submit$2(Execute.scala:281)
	at sbt.internal.util.ErrorHandling$.wideConvert(ErrorHandling.scala:19)
	at sbt.Execute.work(Execute.scala:290)
	at sbt.Execute.$anonfun$submit$1(Execute.scala:281)
	at sbt.ConcurrentRestrictions$$anon$4.$anonfun$submitValid$1(ConcurrentRestrictions.scala:178)
	at sbt.CompletionService$$anon$2.call(CompletionService.scala:37)
	at java.util.concurrent.FutureTask.run(FutureTask.java:266)
	at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
	at java.util.concurrent.FutureTask.run(FutureTask.java:266)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
	at java.lang.Thread.run(Thread.java:748)

However, when I remove the case modifier the code compiles https://scastie.scala-lang.org/7bETIcSZQGi79NBPcdGpYQ

object Example extends App {
  
  final class ZIO[-R, +E, +A](run: (given R) => Either[E, A])
  
  val x: ZIO[String, Nothing, Int] = null
  val y = x
  
  println("It compiles!")
}
1 Like

Good point! I just opened an issue for the compiler error. Will explore that encoding and report back to the group.

Looks like we can wrap the implicit function in a class to prevent it from being evaluated early.

object Main {

  def main(args: Array[String]): Unit = {
    val int = ZIO.environment[Int]
    val doubled = int.map(_ * 2)
    implicit val n = 2
    val result = doubled.run
    println(result)
  }
}

final class ZIO[-R, +E, +A](val run: (given R) => Either[E, A]) {
  final def map[B](f: A => B): ZIO[R, E, B] = 
    ZIO(run.map(f))

  final def flatMap[R1 <: R, E1 >: E, B](f: A => ZIO[R1, E1, B]): ZIO[R1, E1, B] = 
    ZIO(run.flatMap(a => f(a).run))

  final def provide(r: R): ZIO[Any, E, A] = {
    implicit val environment = r
    ZIO(run)
  }

  final def either: ZIO[R, Nothing, Either[E, A]] = 
    ZIO(Right(run))
}
object ZIO {
  def succeed[A](a: A): ZIO[Any, Nothing, A] = ZIO(Right(a))
  def fail[E](e: E): ZIO[Any, E, Nothing] = ZIO(Left(e))
  def environment[R]: ZIO[R, Nothing, R] = ZIO(Right(summon[R]))
  def effect[A](action: => A): ZIO[Any, Throwable, A] = ZIO {
    try Right(action) 
    catch { 
      case t : Throwable => Left(t)
    }
  }
}
1 Like

I did some mental exercise and removed the indirection (wrapping in additional object) using opaque type aliases https://scastie.scala-lang.org/DlUyG0ieSKyKrFlEQrloPQ

object Main {
  import ZioDefs._

  def main(args: Array[String]): Unit = {
    val int = ZIO.environment[Int]
    val doubled = int.map(_ * 2)
    val doubled2 = doubled
    implicit val n = 2
    val result = doubled2.run
    println(result)
  }
}

object ZioDefs {
  opaque type ZIO[-R, +E, +A] = (given R) => Either[E, A]
  
  object ZIO {
    def apply[R, E, A](run: (given R) => Either[E, A]): ZIO[R, E, A] = run
    def run[R, E, A](zio: ZIO[R, E, A])(given r: R): Either[E, A] = zio
    
    def succeed[A](a: A): ZIO[Any, Nothing, A] = ZIO(Right(a))
    def fail[E](e: E): ZIO[Any, E, Nothing] = ZIO(Left(e))
    def environment[R]: ZIO[R, Nothing, R] = ZIO(Right(summon[R]))
    def effect[A](action: => A): ZIO[Any, Throwable, A] = ZIO {
      try Right(action) 
      catch { 
        case t : Throwable => Left(t)
      }
    }
  }
  
  given [R, E, A](raw: ZIO[R, E, A]) {
    def run(given r: R): Either[E, A] =
      ZIO.run(raw)
  
    def map[B](f: A => B): ZIO[R, E, B] = 
      ZIO(raw.map(f))

    def flatMap[R1 <: R, E1 >: E, B](f: A => ZIO[R1, E1, B]): ZIO[R1, E1, B] = 
      ZIO(run(raw).flatMap(a => run(f(a))))

    def provide(r: R): ZIO[Any, E, A] = {
      implicit val environment = r
      ZIO(raw)
    }

    def either: ZIO[R, Nothing, Either[E, A]] = 
      ZIO(Right(raw))
  }
}

Not sure if done properly, but it prints Right(4) which seems correct.

5 Likes