SIP-31 - Byname implicit arguments

This proposal has been implemented in Scala 2.13.0 and Scala 3.0.0.

Author: Miles Sabin

Supervisor and advisor: Martin Odersky

History

Introduction

This SIP proposes extending the support for byname method arguments from just explicit arguments to both explicit and implicit arguments.

The aim is to support similar use cases to shapeless’s Lazy type, but without having to rely on a third party library or fragile and non-portable macros.

The primary use case for shapeless’s Lazy, and the byname implicit arguments described below, is to enable the implicit construction of recursive values. This has proven to be a vital capability for type class derivation, where a type class instance for a recursive data type must typically itself be recursive. For such a value to be constructible via implicit resolution it must be possible to “tie the knot” implicitly.

Implementation status

Byname implicits have been implemented in Dotty with an earlier iteration of the divergence checking algorithm described below. A full implementation of this proposal exists as a pull request relative to the 2.13.x branch of the Lightbend Scala compiler and it is scheduled to be included in the next Typelevel Scala release. As of this comment the Scala and Dotty implementations compile their test cases equivalently.

Proposal

Proposal summary

This SIP proposes allowing implicit arguments to be marked as byname. At call sites recursive uses of implicit values are permitted if they occur in an implicit byname argument.

Consider the following example,

trait Foo {
  def next: Foo
}

object Foo {
  implicit def foo(implicit rec: Foo): Foo =
    new Foo { def next = rec }
}

val foo = implicitly[Foo]
assert(foo eq foo.next)

This diverges due to the recursive implicit argument rec of method foo. This SIP allows us to mark the recursive implicit parameter as byname,

trait Foo {
  def next: Foo
}

object Foo {
  implicit def foo(implicit rec: => Foo): Foo =
    new Foo { def next = rec }
}

val foo = implicitly[Foo]
assert(foo eq foo.next)

When compiled, recursive byname implicit arguments of this sort are extracted out as val members of a local synthetic object at call sites as follows,

val foo: Foo = scala.Predef.implicitly[Foo](
  {
    object LazyDefns$1 {
      val rec$1: Foo = Foo.foo(rec$1)
                       //      ^^^^^
                       // recursive knot tied here
    }
    LazyDefns$1.rec$1
  }
)
assert(foo eq foo.next)

and the example compiles with the assertion successful. Note that the recursive use of rec$1 occurs within the byname argument of foo and is consequently deferred. The desugaring matches what a programmer would do to construct such a recursive value explicitly.

This general pattern is essential to the derivation of type class instances for recursive data types, one of shapeless’s most common applications.

Byname implicits have a number of benefits over the macro implementation of Lazy in shapeless,

• the implementation of Lazy in shapeless is extremely delicate, relying on non-portable compiler internals. As a language feature, byname implicits are more easily portable to other compilers.

• the shapeless implementation is unable to modify divergence checking, so to solve recursive instances it effectively disables divergence checking altogether. This means that incautious use of Lazy can cause the typechecker to loop indefinitely. A byname implicits implementation is able to both solve recursive occurrences and check for divergence.

• the implementation of Lazy interferes with the heuristics for solving inductive implicits in this Scala PR because the latter depends on being able to verify that induction steps strictly reduce the size of the types being solved for; the additional Lazy type constructors make types appear be non-decreasing in size. Whilst this could be special-cased, doing so would require some knowledge of shapeless to be incorporated into the compiler. Being a language-level feature, byname implicits can be accommodated directly in the induction heuristics.

• in common cases more implicit arguments would have to be marked as Lazy than would have to be marked as byname, due to limitations of macros and their interaction with divergence checking. Given that there is a runtime cost associated with capturing the thunks required for both Lazy and byname arguments, any reduction in the number is beneficial.

Motivating examples

Type class derivation is a technique for inferring instances of type classes for ADTs from a set of primitive instances, and rules for combining them which are driven by the structure of the ADT. For example, Semigroup is a type class which expresses that a type has an associative binary operation,

trait Semigroup[A] {
  def combine(x: A, y: A): A
}

If we have instances for basic types,

object Semigroup {
  implicit val intSemigroup: Semigroup[Int] =
    new Semigroup[Int] {
      def combine(x: Int, y: Int): Int = x + y
    }

  implicit val stringSemigroup: Semigroup[String] =
    new Semigroup[String] {
      def combine(x: String, y: String): String = x + y
    }

  implicit val unitSemigroup: Semigroup[Unit] =
    new Semigroup[Unit] {
      def combine(x: Unit, y: Unit): Unit = ()
    }
}

then we can manually write instances for, for example, tuples of types which have Semigroup instances,

implicit def tuple2Semigroup[A, B]
  (implicit
    sa: Semigroup[A],
    sb: Semigroup[B]):
        Semigroup[(A, B)] =
  new Semigroup[(A, B)] {
    def combine(x: (A, B), y: (A, B)): (A, B) =
      (sa.combine(x._1, y._1),
       sb.combine(x._2, y._2))
  }

implicit def tuple3Semigroup[A, B, C]
  (implicit
    sa: Semigroup[A],
    sb: Semigroup[B],
    sc: Semigroup[C]):
        Semigroup[(A, B, C)] =
  nee Semigroup[(A, B, C)] {
    def combine(x: (A, B, C), y: (A, B, C)): (A, B, C) =
      (sa.combine(x._1, y._1),
       sb.combine(x._2, y._2),
       sc.combine(x._3, y._3))
  }

// etc. ...

And we could round this out for all case classes, which have the same product-like structure. Of course doing this manually requires huge amounts of repetitive boilerplate.

Type class derivation is a mechanism for eliminating this boilerplate. The approach taken in shapeless is to map ADTs to a sum of products representation (essentially a nested Either of nested pairs), and define type class instances in terms of the representation type.

shapeless provides a a type class Generic (see Appendix 1 for its signature) and instances taking product types to nested pairs and sealed traits to nested Eithers (while shapeless provides instances of this type class via a macro, that is independent from this SIP, and any similar mechanism might be used) which we can use to provide instances for arbitrary type classes without needing boilerplate for specific ADTs.

For type classes like Semigroup which are meaningful for types which only have a product structure this is straightforward,

implicit def genericSemigroup[T, R]
  (implicit
    gen: Generic.Aux[T, R]
    sr:  Semigroup[R]):
         Semigroup[T] =
  new Semigroup[T] {
    def combine(x: T, y: T): T =
      gen.from(sr.combine(gen.to(x), gen.to(y)))
  }
}

// A case class with a Generic instance
case class Foo(i: Int, s: String)

implicitly[Semigroup[Foo]]

A Semigroup instance for Foo is constructed by implicit resolution as follows,

genericSemigroup(
  generic[Foo], // type R inferred as (Int, (String, Unit))
  tuple2Semigroup(
    intSemigroup,
    tuple2Semigroup(
      stringSemigroup,
      unitSemigroup
    )
  )
)

Intuitively we are confident that the nested implicit resolutions will not diverge because once we have mapped into the tuple representation type (Int, (String, Unit)) each nested step of the implicit resolution reduces the size of the required type.

The need for shapeless’s Lazy or byname implicit arguments becomes apparent when we want to derive type class instances for recursive ADTs. These come into play when we consider types which are sums of products rather than just simple products. We can use a basic cons-list as an example,

sealed trait List[+T]
case class Cons[T](hd: T, tl: List[T]) extends List[T]
case object Nil extends List[Nothing]

Here our data type, List, is the sum of two product types, Cons and Nil. The Cons constructor contains a recursive occurrence of List as its tail. Working through a simple type class derivation will illustrate a new issue to be solved.

Let’s attempt to derive a Show type class instance for List similarly to the way we derived Semigroup above. In this case Generic will map List and its constructors as follows,

List[T]  -> Either[Cons[T], Unit]
Cons[T]  -> (T, (List[T], Unit))
Nil      -> Unit

We define instances for the basic types, pairs, Either and types with a Generic instance like so,

trait Show[T] {
  def show(x: T): String
}

object Show {
  def apply[T](implicit st: Show[T]): Show[T] = st

  implicit val showInt: Show[Int] = new Show[Int] {
    def show(x: Int): String = x.toString
  }

  implicit val showString: Show[String] = new Show[String] {
    def show(x: String): String = x
  }

  implicit val showUnit: Show[Unit] = new Show[Unit] {
    def show(x: Unit): String = ""
  }

  implicit def showPair[T, U]
    (implicit
      st: Show[T],
      su: Show[U]):
          Show[(T, U)] = new Show[(T, U)] {
    def show(t: (T, U)): String = {
      val fst = st.show(t._1)
      val snd = su.show(t._2)
      if(snd == "") fst else s"$fst, $snd"
    }
  }

  implicit def showEither[T, U]
    (implicit
      st: Show[T],
      su: Show[U]):
          Show[Either[T, U]] = new Show[Either[T, U]] {
    def show(x: Either[T, U]): String = x match {
      case Left(t)  => st.show(t)
      case Right(u) => su.show(u)
    }
  }

  implicit def showGeneric[T, R]
    (implicit
      gen: Generic.Aux[T, R],
      sr:  Show[R]):
           Show[T] = new Show[T] {
    def show(x: T): String = sr.show(gen.to(x))
  }
}

val sl = Show[List[Int]] // diverges
assert(
  sl.show(Cons(1, Cons(2, Cons(3, Nil)))) == "1, 2, 3"
)

with the aim of having the inferred instance for List render as asserted.

However the right hand side of the definition of sl does not compile because the implicit resolution involved is seen as divergent by the compiler. To see why this is the case, observe that the chain of implicits required to produce a value of type Show[List[Int]] develops as follows,

       Show[List[Int]]

              V

Show[Either[Cons[Int], Unit]]

              V

      Show[Cons[Int]]

              V

   Show[(Int, List[Int])]

              V

       Show[List[Int]]

This chain of implicit expansions repeats, and would do so indefinitely if the compiler didn’t detect and reject expansions of this sort. Indeed, this is what we should expect because the value we are attempting to construct is itself recursive, and there is no mechanism here to allow us to tie the knot.

If we were to try to construct a value of this sort by hand we would make use of byname arguments,

val showListInt: Show[List[Int]] =
  showGeneric(
    generic[List[Int]],
    showEither(
      showGeneric(
        generic[Cons[Int]],
        showPair(
          showInt,
          showPair(
            showListInt,
            showUnit
          )
        )
      ),
      showUnit
    )
  )

where at least one argument position between the val definition and the recursive occurrence of showListInt is byname.

This SIP proposes automating the above manual process by,

• allowing implicit arguments to be byname.

• constucting a dictionary at call sites where recursive references within byname arguments can be defined as vals.

To allow the above example to work as intended we modify the Show instance definition as follows,

object Show {
  def apply[T](implicit st: => Show[T]): Show[T] = st

  // other definitions unchanged ...

  implicit def showGeneric[T, R]
    (implicit
      gen:    Generic.Aux[T, R],
      sr:  => Show[R]):
              Show[T] = new Show[T] {
    def show(x: T): String = sr.show(gen.to(x))
  }
}

val sl = Show[List[Int]] // compiles
assert(
  sl.show(Cons(1, Cons(2, Cons(3, Nil)))) == "1, 2, 3"
)

and now the definition of sl compiles successfully as,

val sl: Show[List[Int]] = Show.apply[List[Int]](
  {
    object LazyDefns$1 {
      val rec$1: Show[List[Int]] =
        showGeneric(
          generic[List[Int]],
          showEither(
            showGeneric(
              generic[Cons[Int]]
              showCons(
                showInt,
                showCons(
                  rec$1,
                  showUnit
                )
              )
            ),
            showUnit
          )
        )
    }
    LazyDefns$1.rec$1
  }
)

Proposal details

Divergence checking algorithm

We want to ensure that the typechecking of implicit argument expansions terminates, which entails that all valid implicit expansions must be finite and that all potentially infinite (henceforth divergent) implicit expansions must be detected and rejected in finite time.

The Scala Language Specification describes a divergence checking algorithm in 7.2 Implicit Parameters. We summarize it here.

In the expansion of an implicit argument, implicit resolution identifies a corresponding implicit definition (the mechanism for selecting one definition where there are alternatives is not relevant to the discussion of divergence) which might in turn have implicit arguments. This gives rise to a tree of implicit expansions. If all paths from the root terminate with an implicit definition which does not itself have further implicit arguments then we say that it converges. If it does not then it diverges.

To prevent divergent expansions the specification requires the Scala compiler to maintain a stack of “open” implicit types and conservatively check that the core type of new types to be added to the end of that stack are not part of a divergent sequence (the core type of T is T with aliases expanded, top-level type annotations and refinements removed, and occurrences of top-level existentially bound variables replaced by their upper bounds). When an implicit argument is fully resolved it is removed from the end of the stack. The stack represents the current path from the root of the implicit expansion being explored, in effect it is the state corresponding to a depth first traversal of the tree of implicit expanions.

The criteria for detecting divergence are that the newly added core type must not dominate any of the types already on the stack, where a core type T dominates a type U if T is equivalent to U, or if the top-level type constructors of T and U have a common element and T is more complex than U. The precise definition of the complexity of a type is not relevant here but roughly corresponds to the size of the AST representing it: intuitively, if we represent types as a tree with type constructors as internal nodes and types of kind * as leaf nodes then a type T is more complex than a type U if the tree representing T has more nodes than the tree representing U. Note in particular that given these definitions the domination relation is partial: there might be pairs of distinct types with a common top-level type constructor and the same complexity, in which case neither dominates the other.

A sequence of types T_n is called non dominating if no T_i is dominated by any T_j, where i < j.

Divergence checking in the Scala Language Specification

The essence of the algorithm described in the Scala Language Specification is as follows,

Call the sequence of open implicit types O. This is initially empty.

To resolve an implicit of type T given stack of open implicits O,

• Identify the definition d which satisfies T.

• If the core type of T dominates any element of O then we have observed divergence and we’re done.

• If d has no implicit arguments then the result is the value yielded by d.

• Otherwise for each implicit argument a of d, resolve a against O+T, and the result is the value yielded by d applied to its resolved arguments.

This procedure yields a tree of implicit expansions where the nodes are labelled with pairs <d, T>, T being the core of the type for which a value is being resolved implicitly and d being the implicit definition used to supply that value. The children (if any) of <d, T> correspond to the implicit arguments of d, and the tree is rooted at the outermost implicit argument, ie. an implicit argument of an explicit method call. By construction all paths from the root of the tree are non dominating.

The following is an informal proof that given this procedure all implicit expansions either converge or are detected as divergent. This claim is equivalent to the claim that the tree of implicit expansions is finite.

We make the following assumptions: in any given program there is,

P1. a finite number of distinct types with complexity less than or equal to any given complexity c.

P2. a finite upper bound on the number of implicit arguments of any definition.

First we observe that in any given program all non dominiating sequence of types T_n are finite. The type T₀ has some complexity c and P1 asserts that there are a finite number of types with complexity less than or equal to c, so a standard pigeonhole argument tells us that eventually the sequence must terminate or visit a type that has a complexity greater than c ∎.

We can show that the tree of implicit expansions is finite by showing that (a) all paths from the root to a leaf are finite, and then that (b) there is a finite number of paths. (a) follows from the fact that all paths from the root are non-dominating and the lemma above which shows that all such paths are finite. (b) follows from P2 above and (a): each node has a finite number of children, so can only introduce a finite number of subpaths and given that all paths are finite we know they can branch only finitely often ∎.

Divergence checking in the Scala compiler

The current Scala compiler implements this algorithm with one variation, which safely admits more programs as convergent. When checking for divergence the Scala compiler only compares types for dominance if they correspond to the same implicit definition. In effect this “stripes” the divergence check across the set of relevant implicit definitions.

This gives us the following,

To resolve an implicit of type T given stack of open implicits O,

• Identify the definition d which satisfies T.

• If the core type of T dominates the type U of some element <d, U> of O then we have observed divergence and we’re done.

• If d has no implicit arguments then the result is the value yielded by d.

• Otherwise for each implicit argument a of d, resolve a against O+<d, T>, and the result is the value yielded by d applied to its resolved arguments.

Once again this procedure yields a tree of implicit expansions where the nodes are labelled with pairs <d, T>. Given a path from the root of the tree, we call the sequence of nodes which are labelled with a given definition d, in path order, the definitional subpath with respect to d. By construction all definitional subpaths are non-dominating.

We can adapt the previous informal proof to the Scala compiler implementation by showing that (a) still holds with the additional assumption that in any given program there is,

P3. a finite set of implicit definitions D.

Each path in the tree consists of nodes labelled with some element of D and so can be decomposed into an interleaving of definitional subpaths with respect to each of those definitions. These definitional subpaths are non-dominating and hence, by the earlier lemma, finite. P3 asserts that there are only a finite number of these finite paths, so we know that their interleaving must also be finite ∎.

The practical difference between these two algorithms is illustrated by the following,

implicit def requiresPair[T](implicit tt: (T, T)): List[T] =
  List(tt._1, tt._2)

implicit def providesPair[T](implicit t: T): (T, T) = (t, t)

implicit val singleInt: Int = 23

implicitly[List[Int]]

The tree of implicit expansions is in this case a single path,

<requiresPair, List[Int]>

           V

<providesPair, (Int, Int)>

           V

   <singleInt, Int>

Here, the complexity of (T, T) is greater than the complexity of List[Int] and so, without the striping by definition, the more conservative algorithm given in the specification would report divergence. Thanks to the striping the Scala compiler accepts this program.

Divergence checking proposed in this SIP

This SIP changes the above algorithm to accomodate byname cycles. It also revises the definition of domination to allow an additional class of non-cyclic programs to be safely admitted as convergent — whilst non-cyclic, these programs commonly arise in the same sort of type class derivation scenarios as the cyclic cases we have already seen. See the further motivating example below for more details.

Call the set of types and type constructors which are mentioned in a type its covering set. For example, given the following types,

type A = List[(Int, Int)]
type B = List[(Int, (Int, Int))]
type C = List[(Int, String)]

the corresponding covering sets are,

A: List, Tuple2, Int
B: List, Tuple2, Int
C: List, Tuple2, Int, String

Here A and B have the same covering set, which is distinct from the covering set of C. Note that by the definition given earlier, A is not more complex than B or C, and B is more complex than both A and C.

We revise the definition of domination as follows: a core type T dominates a type U if T is equivalent to U, or if the top-level type constructors of T and U have a common element and T is more complex than U, and U and T have the same covering set. For intuition, observe that if T is more complex than U, and U and T have the same covering set then T is structurally larger than U despite using only elements that are present in U.

This gives us the following,

To resolve an implicit of type T given stack of open implicits O,

• Identify the definition d which satisfies T.

• if there is an element e of O of the form <d, T> such that at least one element between e and the top of the stack is of the form <d’, => U> then we have observed an admissable cycle and we’re done.

• If the core type of T dominates the type U of some element <d, U> of O then we have observed divergence and we’re done.

• If d has no implicit arguments then the result is the value yielded by d.

• Otherwise for each implicit argument a of d, resolve a against O+<d, T>, and the result is the value yielded by d applied to its resolved arguments.

An informal proof that this this procedure will either converge or are detect divergence is similar the two given earlier.

First we show that with the revised definition of domination all non dominating sequences of types are finite, using the additional assumption that in any given program there is,

P4. a finite number of type definitions.

And we observe as a consequence that the powerset of the set of type definitions must also be finite, hence that in any given program there can only be a finite number of distinct covering sets.

Call the complexity of type T, c(T), the covering set of T, cs(T), the set of all type definitions in the program S and the powerset of the latter P(S).

From P1 we know that the number of types with complexity less than or equal to c(T₀) is finite, so eventually the sequence must reach a type T_p with a complexity greater than c(T₀). For this to be non dominating its covering set cs(T_p) must differ from cs(T₀). Again from P1 we know that the number of types with complexity less that c(T_p) is finite, so eventually the sequence must reach a type T_q with a complexity greater than c(T_p) and so to continue T_q must have a covering set cs(T_q) which is distinct from both cs(T₀) and cs(T_p). Continuing in this way the sequence can increase in complexity while running through distinct covering sets cs(T₀), cs(T_p), cs(T_q), cs(T_r) … which from P4 we know must eventually exhaust P(S).

Call the type at which this happens T_ps. Once again from P1 we know that the number of types with complexity less than or equal to c(T_ps) is finite and so will eventually be exhausted. This time, however, the sequence cannot be extended, because there are no more distinct covering sets available to be introduced to avoid dominating an earlier element of the sequence ∎.

Finally, as in the previous proof each path in the tree consists of nodes labelled with some element of D and so can be decomposed into an interleaving of definitional subpaths with respect to each of those definitions. These definitional subpaths are non-dominating and hence, by the earlier lemma, finite. P3 asserts that there are only a finite number of these finite paths, so we know that their interleaving must also be finite ∎.

Motivating example for the covering set based divergence critera

We follow with a motivating example for the introduction of the covering condition in new divergence checking model. In current Scala, consider the following set of instances for a type class Foo, as might arise in a type class derivation for simple product types,

trait Generic[T] {
  type Repr
}
object Generic {
  type Aux[T, R] = Generic[T] { type Repr = R }
}

trait Foo[T]
object Foo {
  implicit val fooUnit: Foo[Unit] = ???
  implicit val fooInt: Foo[Int] = ???
  implicit val fooString: Foo[String] = ???
  implicit val fooBoolean: Foo[Boolean] = ???

  implicit def fooPair[T, U]
    (implicit fooT: Foo[T], fooU: Foo[U]): Foo[(T, U)] = ???

  implicit def fooGen[T, R]
    (implicit gen: Generic.Aux[T, R], fr: Foo[R]): Foo[T] = ???
}

case class A(b: B, i: Int)
object A {
  implicit val genA: Generic.Aux[A, (B, (Int, Unit))] = ???
}

case class B(c: C, i: Int, b: Boolean)
object B {
  implicit val genB:
    Generic.Aux[B, (C, (Int, (Boolean, Unit)))] = ???
}

case class C(i: Int, s: String, b: Boolean)
object C {
  implicit val genC:
    Generic.Aux[C, (Int, (String, (Boolean, Unit)))] = ???
}

implicitly[Foo[C]] // OK
implicitly[Foo[B]] // Diverges
implicitly[Foo[A]] // Diverges

Here we have simple product types A, B and C which are nested, but none of which are recursive. We can see that there is a simple terminating unfolding of their elements into nested pairs, like so,

C ->   (Int, (String, (Boolean, Unit)))

B ->  ((Int, (String, (Boolean, Unit))),
       (Int, (Boolean, Unit)))

A -> (((Int, (String, (Boolean, Unit))),
       (Int, (Boolean, Unit))),
       (Int,  Unit))

and yet this diverges, why?

The answer is clear if we follow the expansion of Foo[A] through from the beginning,

               Foo[A]

                 V

       Foo[(B, (Int, Unit))]

                 V

               Foo[B]

                 V

  Foo[(C, (Int, (Boolean, Unit)))]

                 V

               Foo[C]

                 V

Foo[(Int, (String, (Boolean, Unit)))]

Here we can see immediately that, on the current critera, divergence will be detected on the fourth step because we have a more complex type (Foo[(C, (Int, (Boolean, Unit)))] vs. Foo[(B, (Int, Unit))]) being resolved in the same context (fooGen).

Unsurprisingly examples of this sort arose very early in the developement of shapeless-based type class derivation, first being documented in a StackOverflow question from Travis Brown, even in advance of attempts to derive type class instances for recursive ADTs.

The new divergence checking algorithm proposed in this SIP permits the example above because the covering condition is not met. If we look at the covering sets and complexities of the sequence,

  Complexity      Covering set

  2               Foo, A
* 6               Foo, B, Int, Unit
  2               Foo, B
* 8               Foo, C, Int, Boolean, Unit
  2               Foo, C
* 8               Foo, Int, String, Boolean, Unit

(the * prefix indicates steps which are generated via fooGen and are hence subject to divergence checking within the same definitional stripe) we can see that at the 2nd, 4th and 6th steps, although the size of the types is growing, the covering sets differ.

Follow on work from this SIP

Byname implicits significantly advance the state of the art, however they are not a complete replacement for shapeless’s Lazy pseudo type. Byname parameters don’t generate stable paths for dependent types. This means that the following shapeless idiom,

trait Foo {
  type Out
  def out: Out
}

object Test {
  implicit def bar(implicit foo: Lazy[Foo]): foo.value.Out =
    foo.value.out
}

cannot be directly translated as,

trait Foo {
  type Out
  def out: Out
}

object Test {
  implicit def bar(implicit foo: => Foo): foo.Out = foo.out
}

because the path foo in foo.Out is not stable. Full parity with shapeless’s Lazy would require lazy (rather than byname) implicit parameters (see this Dotty ticket for further discussion) and is orthogonal to this SIP in that they would drop out of support for lazy parameters more generally, as described in this Scala ticket.

In the meantime we can work around this limitation using the Aux pattern,

trait Foo {
  type Out
  def out: Out
}

object Foo {
  type Aux[Out0] = Foo { type Out = Out0 }
}

object Test {
  implicit def bar[T](implicit foo: => Foo.Aux[T]): T = foo.out
}

shapeless also provides a Cached type which has similar characteristics to Lazy and which also shares resolved values between call sites. Future work might address instance sharing generally, although it would be desirable for this to be an implementation level optimization rather than a user visible language feature.

Appendix 1 – shapeless excerpts

Extracts from shapeless relevant to the motivating examples for this SIP,

trait Lazy[+T] extends Serializable {
  val value: T
}

object Lazy {
  implicit def apply[T](t: => T): Lazy[T] =
    new Lazy[T] {
      lazy val value = t
    }

  implicit def mkLazy[I]: Lazy[I] = macro ...
}

trait Generic[T] {
  type Repr
  def to(t: T): Repr
  def from(r: Repr): T
}