Let by-name implicit parameters have lazy semantics #1998

Closed
odersky opened this Issue Feb 18, 2017 · 21 comments

Comments

Projects
None yet
@odersky
Contributor

odersky commented Feb 18, 2017

Motivation

Generic programming often exhibits scenarios where an implicit expansion would diverge, were it not for a lazy implicit value that "ties the knot". Current Shapeless has the Lazy pseudo-type to handle this using some tricky macro machinery. Following an idea of @milessabin it seems cleaner to put this in the language and tie it to by-name implicit parameters.

Status Quo

By-name implicit parameters are disallowed in Scala-2. They have been introduced recently in dotty, but without attaching special meaning to them.

Proposal

Modify implicit search as follows:

When searching for an implicit value of type T to provide an argument for a by-name parameter of type => T:

  • Create a new implicit value with a fresh name lv, which has the signature of the following definition:

     implicit lazy val lv: T
    

    The current implementation uses the prefix $lazy_implicit$ followed by a unique integer for lv.

  • This lazy val is not immediately available as candidate for implicit search (making it immediately available would result in a looping implicit computation). But it becomes available in all nested contexts that look again for an implicit argument to a by-name parameter.

  • If this implicit search succeeds with expression E, and E contains references to the lazy implicit value lv, replace E by

     { implicit lazy val lv: T = E; lv }
    

    Otherwise, return E unchanged.

Implementation Status

This proposal has been implemented in #1993. The test cases in that PR starting with

lazy-implicits-... . scala

show where the feature is useful. All these test cases would have given a diverging implicit expansion before the change.

@rkuhn

This comment has been minimized.

Show comment
Hide comment
@rkuhn

rkuhn Feb 18, 2017

This would be awesome, 💯 ! Having an implementation for an inductive type-level computation serves as correctness proof, but allocating all those instances (as is typically done) comes at great runtime cost. This proposal would be highly beneficial wherever the actual implementation is not needed, e.g. because the types are tracking a purely compile-time aspect with no corresponding runtime values.

rkuhn commented Feb 18, 2017

This would be awesome, 💯 ! Having an implementation for an inductive type-level computation serves as correctness proof, but allocating all those instances (as is typically done) comes at great runtime cost. This proposal would be highly beneficial wherever the actual implementation is not needed, e.g. because the types are tracking a purely compile-time aspect with no corresponding runtime values.

@japgolly

This comment has been minimized.

Show comment
Hide comment
@japgolly

japgolly Feb 18, 2017

When declaring the lazy implicit, would it not make more sense to use the lazy keyword rather than =>? It will introduce inconsistency and I can already see myself having to continually explain over the years that => parameters are by-name unless implicit in which case they're by-need.

implicit def SumCountable[T, U](implicit ev1: lazy Countable[T]) = ...
// or
implicit def SumCountable[T, U](implicit lazy ev1: Countable[T]) = ...

instead of

implicit def SumCountable[T, U](implicit ev1: => Countable[T]) = ...

Going even further maybe there should be a way to declare by-need parameters in general. Then regardless of whether a param is implicit or not, parameters could be by-value, by-name, by-need, and it would be consistent.

def egByValue[A](a: A)(implicit x: X[A]) = ...

def egByName[A](a: => A)(implicit x: => X[A]) = ...

def egByNeed[A](lazy a: A)(implicit lazy x: X[A]) = ...
def egByNeed[A](a: lazy A)(implicit x: lazy X[A]) = ...

japgolly commented Feb 18, 2017

When declaring the lazy implicit, would it not make more sense to use the lazy keyword rather than =>? It will introduce inconsistency and I can already see myself having to continually explain over the years that => parameters are by-name unless implicit in which case they're by-need.

implicit def SumCountable[T, U](implicit ev1: lazy Countable[T]) = ...
// or
implicit def SumCountable[T, U](implicit lazy ev1: Countable[T]) = ...

instead of

implicit def SumCountable[T, U](implicit ev1: => Countable[T]) = ...

Going even further maybe there should be a way to declare by-need parameters in general. Then regardless of whether a param is implicit or not, parameters could be by-value, by-name, by-need, and it would be consistent.

def egByValue[A](a: A)(implicit x: X[A]) = ...

def egByName[A](a: => A)(implicit x: => X[A]) = ...

def egByNeed[A](lazy a: A)(implicit lazy x: X[A]) = ...
def egByNeed[A](a: lazy A)(implicit x: lazy X[A]) = ...
@ritschwumm

This comment has been minimized.

Show comment
Hide comment
@ritschwumm

ritschwumm Feb 19, 2017

+1 for lazy parameters in general. i know i can express them with a by-name parameter and an additional lazy val, but then i need to be very careful to always access the lazy val, and not by accident the parameter.

i think this would be much cleaner than having the behaviour of by-name parameters "magically" change depending on whether they are marked implicit or not.

ritschwumm commented Feb 19, 2017

+1 for lazy parameters in general. i know i can express them with a by-name parameter and an additional lazy val, but then i need to be very careful to always access the lazy val, and not by accident the parameter.

i think this would be much cleaner than having the behaviour of by-name parameters "magically" change depending on whether they are marked implicit or not.

@odersky

This comment has been minimized.

Show comment
Hide comment
@odersky

odersky Feb 19, 2017

Contributor

@japgolly I think these are good points. I agree it would be consistent to allow lazy for all parameters, and if we do then it would make indeed sense to use lazy instead of by-name as
our indication for inserting lazy implicit values. Let me check what would be involved in this.

Contributor

odersky commented Feb 19, 2017

@japgolly I think these are good points. I agree it would be consistent to allow lazy for all parameters, and if we do then it would make indeed sense to use lazy instead of by-name as
our indication for inserting lazy implicit values. Let me check what would be involved in this.

@retronym

This comment has been minimized.

Show comment
Hide comment
@retronym

retronym Feb 19, 2017

Contributor

Some discussion on general by-need params in the vintage ticket https://issues.scala-lang.org/browse/SI-240

Contributor

retronym commented Feb 19, 2017

Some discussion on general by-need params in the vintage ticket https://issues.scala-lang.org/browse/SI-240

@odersky

This comment has been minimized.

Show comment
Hide comment
@odersky

odersky Feb 19, 2017

Contributor

@retronym This is an amazing can of worms. Thanks for the pointer!

Contributor

odersky commented Feb 19, 2017

@retronym This is an amazing can of worms. Thanks for the pointer!

@TomasMikula

This comment has been minimized.

Show comment
Hide comment
@TomasMikula

TomasMikula Feb 20, 2017

What about instead of annotating implicit parameters as lazy, annotate the rule as recursive?

Now:

implicit def SumListable[T, U](implicit
  ev1: => Listable[T],
  ev2: => Listable[U]
): Listable[Sum[T, U]]

Then:

@rec implicit def SumListable[T, U](implicit
  ev1: Listable[T],
  ev2: Listable[U]
): Listable[Sum[T, U]]

with the meaning being:
With temporarily assuming the result (Listable[Sum[T, U]]) if during resolving the arguments (ev1, ev2) this same rule (SumListable) would be applied with compatible types, just use the assumed result.

To me, subjectively, this formulation seems slightly simpler.
Also, there would be no interaction between rules—a rule can only be recursive with itself. (Whereas in the current proposal two rules can "interact" if they accept lazy argument of the same type.)

What about instead of annotating implicit parameters as lazy, annotate the rule as recursive?

Now:

implicit def SumListable[T, U](implicit
  ev1: => Listable[T],
  ev2: => Listable[U]
): Listable[Sum[T, U]]

Then:

@rec implicit def SumListable[T, U](implicit
  ev1: Listable[T],
  ev2: Listable[U]
): Listable[Sum[T, U]]

with the meaning being:
With temporarily assuming the result (Listable[Sum[T, U]]) if during resolving the arguments (ev1, ev2) this same rule (SumListable) would be applied with compatible types, just use the assumed result.

To me, subjectively, this formulation seems slightly simpler.
Also, there would be no interaction between rules—a rule can only be recursive with itself. (Whereas in the current proposal two rules can "interact" if they accept lazy argument of the same type.)

@propensive

This comment has been minimized.

Show comment
Hide comment
@propensive

propensive Feb 20, 2017

@japgolly @odersky Is lazy the correct terminology? By comparison to lazy vals, it implies the parameter is evaluated at most once. I think I suggested def as an alternative last time this came up... Either way, I'd be happy to lose => T.

@japgolly @odersky Is lazy the correct terminology? By comparison to lazy vals, it implies the parameter is evaluated at most once. I think I suggested def as an alternative last time this came up... Either way, I'd be happy to lose => T.

@odersky

This comment has been minimized.

Show comment
Hide comment
@odersky

odersky Feb 20, 2017

Contributor

On second thought, and as @TomasMikula and @propensive noted, this has nothing to do with call-by-need. The lazy val is local to the implicit argument block. That means the whole implicit argument will be evaluated every time the implicit method demands it. So it's pure call-by-name and no syntax change to what was proposed is needed.

Aside: I am averse to using annotations like @rec for something fundamental. Annotations increase language footprint just like specialized syntactic constructs do. In fact, annotations are worse in this case, because they hide some fundamental aspect of type checking in a seemingly innocuous little modifier that could mean anything.

Contributor

odersky commented Feb 20, 2017

On second thought, and as @TomasMikula and @propensive noted, this has nothing to do with call-by-need. The lazy val is local to the implicit argument block. That means the whole implicit argument will be evaluated every time the implicit method demands it. So it's pure call-by-name and no syntax change to what was proposed is needed.

Aside: I am averse to using annotations like @rec for something fundamental. Annotations increase language footprint just like specialized syntactic constructs do. In fact, annotations are worse in this case, because they hide some fundamental aspect of type checking in a seemingly innocuous little modifier that could mean anything.

@TomasMikula

This comment has been minimized.

Show comment
Hide comment
@TomasMikula

TomasMikula Feb 20, 2017

The syntax I used (@rec) is unimportant, notice the difference in meaning: what's recursive is the result, not the arguments. If you wish, write it like this:

implicit def SumListable[T, U](implicit
  ev1: Listable[T],
  ev2: Listable[U]
): => Listable[Sum[T, U]]

I find this version easier to reason about (you may think otherwise), because it is more local: the hypothetical Listable[Sum[T, U]] will be used to "tie the knot" only if the same rule (SumListable) was going to be tried in a nested context.

This is in contrast with the current proposal, where the hypothetical argument "becomes available in all nested contexts that look again for an implicit argument to a by-name parameter," i.e. it becomes available even for other implicit rules (i.e. not local).

The syntax I used (@rec) is unimportant, notice the difference in meaning: what's recursive is the result, not the arguments. If you wish, write it like this:

implicit def SumListable[T, U](implicit
  ev1: Listable[T],
  ev2: Listable[U]
): => Listable[Sum[T, U]]

I find this version easier to reason about (you may think otherwise), because it is more local: the hypothetical Listable[Sum[T, U]] will be used to "tie the knot" only if the same rule (SumListable) was going to be tried in a nested context.

This is in contrast with the current proposal, where the hypothetical argument "becomes available in all nested contexts that look again for an implicit argument to a by-name parameter," i.e. it becomes available even for other implicit rules (i.e. not local).

@rec

This comment has been minimized.

Show comment
Hide comment
@rec

rec Feb 20, 2017

For personal reasons, I vote against using @rec :-D or at least, to wrap it in backticks @rec so it doesn't send me email

rec commented Feb 20, 2017

For personal reasons, I vote against using @rec :-D or at least, to wrap it in backticks @rec so it doesn't send me email

@odersky

This comment has been minimized.

Show comment
Hide comment
@odersky

odersky Feb 25, 2017

Contributor

#1993 just was merged, so this is in now.

Contributor

odersky commented Feb 25, 2017

#1993 just was merged, so this is in now.

@odersky odersky closed this Feb 25, 2017

@Atry

This comment has been minimized.

Show comment
Hide comment
@Atry

Atry May 22, 2017

@japgolly I like the lazy val's call-by-need semantics, it would have better performance when the type class is very complicated.

However, a naive implementation would break serializability. This is important when working with Spark or other distributed computing environments.
We will need @transient lazy val pattern in case of the type class being serialized when a closure reference it.

I don't know if Scala is possible to support @transient on parameters like this:

def foo(sparkRdd: RDD[String])(@transient lazy implicit ev: T) = {
  sparkRdd.map { x =>
     doSomethingWith(ev)
  }
}

Atry commented May 22, 2017

@japgolly I like the lazy val's call-by-need semantics, it would have better performance when the type class is very complicated.

However, a naive implementation would break serializability. This is important when working with Spark or other distributed computing environments.
We will need @transient lazy val pattern in case of the type class being serialized when a closure reference it.

I don't know if Scala is possible to support @transient on parameters like this:

def foo(sparkRdd: RDD[String])(@transient lazy implicit ev: T) = {
  sparkRdd.map { x =>
     doSomethingWith(ev)
  }
}
@milessabin

This comment has been minimized.

Show comment
Hide comment
@milessabin

milessabin Aug 22, 2017

I've been working on implementing this for Scala 2 and have run into what appears to be a good case for lazy (ie. at most once) rather than (or as well as) by name semantics.

Consider the following example,

trait Foo {
  type Out
  def out: Out
}

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

This doesn't compile (either on my Scala 2 branch or with Dotty) because the by name argument foo is not stable,

lazy-implicits-7.scala:12: error: stable identifier required, but foo found.
  implicit def bar(implicit foo: => Foo): foo.Out = foo.out
                                          ^
one error found

This pattern is very important in implicit-based type level programming, so this would be a disappointing limitation. By contrast, shapeless's Lazy captures the value in a stable context and hence supports the following with vanilla Scala 2,

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

Currently the following is a workaround with by name implicits which compiles both on my branch and with Dotty,

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.value
}

ie. we use the Aux pattern to avoid the need for a stable value. This is clumsy however, and the additional type parameter (which must typically be inferred) can make it hard to express methods which require an explicit type argument.

So, whilst by name implicits get us close be being able to replace shapeless's Lazy macro, it's not quite there. The proposals above to use the lazy keyword to more or less exactly replicate shapeless's Lazy semantics are a relatively minor addition to this proposal from an implementation point of view and would do the whole job.

milessabin commented Aug 22, 2017

I've been working on implementing this for Scala 2 and have run into what appears to be a good case for lazy (ie. at most once) rather than (or as well as) by name semantics.

Consider the following example,

trait Foo {
  type Out
  def out: Out
}

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

This doesn't compile (either on my Scala 2 branch or with Dotty) because the by name argument foo is not stable,

lazy-implicits-7.scala:12: error: stable identifier required, but foo found.
  implicit def bar(implicit foo: => Foo): foo.Out = foo.out
                                          ^
one error found

This pattern is very important in implicit-based type level programming, so this would be a disappointing limitation. By contrast, shapeless's Lazy captures the value in a stable context and hence supports the following with vanilla Scala 2,

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

Currently the following is a workaround with by name implicits which compiles both on my branch and with Dotty,

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.value
}

ie. we use the Aux pattern to avoid the need for a stable value. This is clumsy however, and the additional type parameter (which must typically be inferred) can make it hard to express methods which require an explicit type argument.

So, whilst by name implicits get us close be being able to replace shapeless's Lazy macro, it's not quite there. The proposals above to use the lazy keyword to more or less exactly replicate shapeless's Lazy semantics are a relatively minor addition to this proposal from an implementation point of view and would do the whole job.

@smarter

This comment has been minimized.

Show comment
Hide comment
@smarter

smarter Aug 22, 2017

Member

This doesn't compile (either on my Scala 2 branch or with Dotty) because the by name argument foo is not stable,

I'm not sure if lazy implicits would be considered stable either, for the same reason that lazy vals in general are not stable in Dotty: http://scala-lang.org/blog/2016/02/17/scaling-dot-soundness.html#loopholes-caused-by-scaling-up

Member

smarter commented Aug 22, 2017

This doesn't compile (either on my Scala 2 branch or with Dotty) because the by name argument foo is not stable,

I'm not sure if lazy implicits would be considered stable either, for the same reason that lazy vals in general are not stable in Dotty: http://scala-lang.org/blog/2016/02/17/scaling-dot-soundness.html#loopholes-caused-by-scaling-up

@milessabin

This comment has been minimized.

Show comment
Hide comment
@milessabin

milessabin Aug 22, 2017

Presumably a statically non-null lazy val would be stable?

Presumably a statically non-null lazy val would be stable?

@milessabin

This comment has been minimized.

Show comment
Hide comment
@milessabin

milessabin Aug 22, 2017

I would be happy with the restrictions listed in the "Plugging the Loopholes" section of that post.

I would be happy with the restrictions listed in the "Plugging the Loopholes" section of that post.

@smarter

This comment has been minimized.

Show comment
Hide comment
@smarter

smarter Aug 22, 2017

Member

OK, would you mind opening a new issue for this feature? Just reopening this issue might be confusing.

Member

smarter commented Aug 22, 2017

OK, would you mind opening a new issue for this feature? Just reopening this issue might be confusing.

@milessabin

This comment has been minimized.

Show comment
Hide comment

Done: #3005

@milessabin

This comment has been minimized.

Show comment
Hide comment
@milessabin

milessabin Aug 29, 2017

Scala 2 implementation here: scala/scala#6050.

You might want to take a look at this test ... it was one of the original motivating examples for shapeless's Lazy (see this SO question). It's handled correctly by the Scala 2 implementation (thanks to some finessing of the divergence checker) but not by the Dotty implementation.

Scala 2 implementation here: scala/scala#6050.

You might want to take a look at this test ... it was one of the original motivating examples for shapeless's Lazy (see this SO question). It's handled correctly by the Scala 2 implementation (thanks to some finessing of the divergence checker) but not by the Dotty implementation.

@smarter

This comment has been minimized.

Show comment
Hide comment
@smarter

smarter Aug 29, 2017

Member

@milessabin Cool! I think it'd be worth opening an issue for the test you mention, a minimized version reproducing the problem would also be appreciated :).

Member

smarter commented Aug 29, 2017

@milessabin Cool! I think it'd be worth opening an issue for the test you mention, a minimized version reproducing the problem would also be appreciated :).

milessabin added a commit to milessabin/scala that referenced this issue Mar 6, 2018

Implementation of byname implicits with recursive dictionaries
This is an implementation of byname implicit parameters with recursive
dictionaries, intended as a language-level replacement for shapeless's
Lazy type. As of this commit, implicit arguments can be marked as byname
and at call sites will be eligible as parameters in recursively nested
positions within their own implicit expansions.

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)

In current Scala this would diverge due to the recursive implicit
argument rec of method foo. Under the scheme implemented in this commit
recursive occurrences of this sort are extracted out as lazy val
members of a local synthetic object as follows,

  val foo: Foo = scala.Predef.implicitly[Foo](
    {
      object LazyDefns$1 {
        lazy 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.

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. By contrast there is already an
  initial implementation of byname implicits in Dotty:
  lampepfl/dotty#1998.
+ 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. The 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 #5649 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 the type 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 under this PR due to
  restrictions on what the Lazy macro is able to do. 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.

milessabin added a commit to milessabin/scala that referenced this issue Mar 7, 2018

Implementation of byname implicits with recursive dictionaries
This is an implementation of byname implicit parameters with recursive
dictionaries, intended as a language-level replacement for shapeless's
Lazy type. As of this commit, implicit arguments can be marked as byname
and at call sites will be eligible as parameters in recursively nested
positions within their own implicit expansions.

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)

In current Scala this would diverge due to the recursive implicit
argument rec of method foo. Under the scheme implemented in this commit
recursive occurrences of this sort are extracted out as lazy val
members of a local synthetic object as follows,

  val foo: Foo = scala.Predef.implicitly[Foo](
    {
      object LazyDefns$1 {
        lazy 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.

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. By contrast there is already an
  initial implementation of byname implicits in Dotty:
  lampepfl/dotty#1998.
+ 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. The 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 #5649 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 the type 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 under this PR due to
  restrictions on what the Lazy macro is able to do. 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.

milessabin added a commit to milessabin/scala that referenced this issue Mar 29, 2018

Implementation of byname implicits with recursive dictionaries
This is an implementation of byname implicit parameters with recursive
dictionaries, intended as a language-level replacement for shapeless's
Lazy type. As of this commit, implicit arguments can be marked as byname
and at call sites will be eligible as parameters in recursively nested
positions within their own implicit expansions.

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)

In current Scala this would diverge due to the recursive implicit
argument rec of method foo. Under the scheme implemented in this commit
recursive occurrences of this sort are extracted out as lazy val
members of a local synthetic object as follows,

  val foo: Foo = scala.Predef.implicitly[Foo](
    {
      object LazyDefns$1 {
        lazy 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.

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. By contrast there is already an
  initial implementation of byname implicits in Dotty:
  lampepfl/dotty#1998.
+ 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. The 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 #5649 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 the type 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 under this PR due to
  restrictions on what the Lazy macro is able to do. 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.

milessabin added a commit to milessabin/scala that referenced this issue Apr 3, 2018

Implementation of byname implicits with recursive dictionaries
This is an implementation of byname implicit parameters with recursive
dictionaries, intended as a language-level replacement for shapeless's
Lazy type. As of this commit, implicit arguments can be marked as byname
and at call sites will be eligible as parameters in recursively nested
positions within their own implicit expansions.

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)

In current Scala this would diverge due to the recursive implicit
argument rec of method foo. Under the scheme implemented in this commit
recursive occurrences of this sort are extracted out as lazy val
members of a local synthetic object as follows,

  val foo: Foo = scala.Predef.implicitly[Foo](
    {
      object LazyDefns$1 {
        lazy 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.

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. By contrast there is already an
  initial implementation of byname implicits in Dotty:
  lampepfl/dotty#1998.
+ 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. The 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 #5649 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 the type 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 under this PR due to
  restrictions on what the Lazy macro is able to do. 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.

milessabin added a commit to milessabin/scala that referenced this issue Apr 18, 2018

Implementation of byname implicits with recursive dictionaries
This is an implementation of byname implicit parameters with recursive
dictionaries, intended as a language-level replacement for shapeless's
Lazy type. As of this commit, implicit arguments can be marked as byname
and 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)

In current Scala this would diverge due to the recursive implicit
argument rec of method foo. Under the scheme implemented in this commit
we can 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)

and recursive occurrences of this sort are extracted out as val members
of a local synthetic object 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. By contrast there is already an
  initial implementation of byname implicits in Dotty:
  lampepfl/dotty#1998.
+ 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. The 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 #6481 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 the type 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 under this PR due to
  restrictions on what the Lazy macro is able to do. 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.

milessabin added a commit to milessabin/scala that referenced this issue Apr 24, 2018

Implementation of byname implicits with recursive dictionaries
This is an implementation of byname implicit parameters with recursive
dictionaries, intended as a language-level replacement for shapeless's
Lazy type. As of this commit, implicit arguments can be marked as byname
and 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)

In current Scala this would diverge due to the recursive implicit
argument rec of method foo. Under the scheme implemented in this commit
we can 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)

and recursive occurrences of this sort are extracted out as val members
of a local synthetic object 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. By contrast there is already an
  initial implementation of byname implicits in Dotty:
  lampepfl/dotty#1998.
+ 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. The 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 #6481 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 the type 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 under this PR due to
  restrictions on what the Lazy macro is able to do. 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.

milessabin added a commit to milessabin/scala that referenced this issue Jun 12, 2018

Implementation of byname implicits with recursive dictionaries
This is an implementation of byname implicit parameters with recursive
dictionaries, intended as a language-level replacement for shapeless's
Lazy type. As of this commit, implicit arguments can be marked as byname
and 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)

In current Scala this would diverge due to the recursive implicit
argument rec of method foo. Under the scheme implemented in this commit
we can 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)

and recursive occurrences of this sort are extracted out as val members
of a local synthetic object 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. By contrast there is already an
  initial implementation of byname implicits in Dotty:
  lampepfl/dotty#1998.
+ 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. The 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 #6481 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 the type 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 under this PR due to
  restrictions on what the Lazy macro is able to do. 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.

milessabin added a commit to milessabin/scala that referenced this issue Jun 29, 2018

Implementation of byname implicits with recursive dictionaries
This is an implementation of byname implicit parameters with recursive
dictionaries, intended as a language-level replacement for shapeless's
Lazy type. As of this commit, implicit arguments can be marked as byname
and 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)

In current Scala this would diverge due to the recursive implicit
argument rec of method foo. Under the scheme implemented in this commit
we can 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)

and recursive occurrences of this sort are extracted out as val members
of a local synthetic object 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. By contrast there is already an
  initial implementation of byname implicits in Dotty:
  lampepfl/dotty#1998.
+ 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. The 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 #6481 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 the type 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 under this PR due to
  restrictions on what the Lazy macro is able to do. 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.

milessabin added a commit to milessabin/scala that referenced this issue Jul 4, 2018

Implementation of byname implicits with recursive dictionaries
This is an implementation of byname implicit parameters with recursive
dictionaries, intended as a language-level replacement for shapeless's
Lazy type. As of this commit, implicit arguments can be marked as byname
and 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)

In current Scala this would diverge due to the recursive implicit
argument rec of method foo. Under the scheme implemented in this commit
we can 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)

and recursive occurrences of this sort are extracted out as val members
of a local synthetic object 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. By contrast there is already an
  initial implementation of byname implicits in Dotty:
  lampepfl/dotty#1998.
+ 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. The 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 #6481 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 the type 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 under this PR due to
  restrictions on what the Lazy macro is able to do. 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.

milessabin added a commit to milessabin/scala that referenced this issue Jul 10, 2018

Implementation of byname implicits with recursive dictionaries
This is an implementation of byname implicit parameters with recursive
dictionaries, intended as a language-level replacement for shapeless's
Lazy type. As of this commit, implicit arguments can be marked as byname
and 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)

In current Scala this would diverge due to the recursive implicit
argument rec of method foo. Under the scheme implemented in this commit
we can 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)

and recursive occurrences of this sort are extracted out as val members
of a local synthetic object 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. By contrast there is already an
  initial implementation of byname implicits in Dotty:
  lampepfl/dotty#1998.
+ 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. The 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 #6481 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 the type 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 under this PR due to
  restrictions on what the Lazy macro is able to do. 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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment