Support by-name implicits with recursive dictionaries #6050

milessabin · 2017-08-29T14:21:11Z

This Typelevel Scala collaboration sponsored by Lightbend ...

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 PR, 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.

There is a SIP describing this language change in greater detail here.

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 PR 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)

The example now 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: Let by-name implicit parameters have lazy semantics scala3#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 Topic/inductive implicits 2.13.x #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.

tpolecat · 2017-08-29T15:13:34Z

This is great. Thank you!

tek · 2017-08-29T15:43:55Z

yaaaaay awesome!

andyscott · 2017-08-29T18:36:31Z

Yes please!

fommil · 2017-08-30T07:34:23Z

One potential problem with this overload/behaviour change of the by-name language feature is that I was planning on using regular byname implicit parameters to avoid constructing the instance when it's not needed. This is necessary to get good memory allocation optimisation for implicits with conditional requirements... caching of implicit def (for runtime performance optimisation) is one such situation I'm currently working on, e.g. https://gitlab.com/fommil/stalactite/issues/35

Is there any requirement for Strict/Cached after this?

julienrf · 2017-08-30T07:36:38Z

From what I understand the effective semantics is by-need, not by-name? So, what’s preventing us from replacing the => with a lazy?

lrytz · 2017-09-04T13:50:21Z

@julienrf at least when provided explicitly, it behaves as by-name, not by-need.

Welcome to Scala 2.12.4-20170829-122239-87b912c (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_131).

scala> def f(implicit x: => Int) = { x + x }
f: (implicit x: => Int)Int

scala> f { println("hi"); 1 }
hi
hi
res1: Int = 2

milessabin · 2017-09-04T20:50:02Z

Being implicit doesn't change the by name semantics. I think it would also make sense to have lazy arguments (both implicit and explicit), but that's somewhat orthogonal to this PR. See scala/bug#240 and https://github.com/lampepfl/dotty/issues/3005 for more discussion.

retronym · 2017-09-11T04:42:54Z

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

Could you share a small motivating example that currently diverges? (The example above is distilled too far for me to see the use case)

fommil · 2017-09-11T06:27:54Z

@retronym https://gitlab.com/fommil/stalactite/tree/master/src/test/scala/xmlformat

Try removing the Lazy, Cached and Strict here in either the generic encoder or decoder and see the recursive tests fail.

I must admit, I'm confused about exactly what this means for my usecase... I'm unable to see the above in my example. Does this only replace Lazy? What about Cached and Strict? What's the implication to performance, because if these things really do become by-name it's going to kill performance when the lazy semantics are not necessary. I have a good usecase for byname implicits, which does help performance, but added across the board this will be terrible.

milessabin · 2017-09-11T10:28:00Z

@retronym there are motivating examples in the tests. test/files/pos/byname-implicits-9.scala (a Show type class derivation exercised on List) is an example with explicit recursion in the ADT,

List[T] => Either[Nil.type, ::[T]]
::[T] => (T, List[T])

Without the ability to tie the knot here the compiler would diverge on seeing the occurrence of List[T] in ::[T].

milessabin · 2017-09-11T10:29:48Z

@fommil Cached and Strict will go away too, as will cachedImplicit. There will be an alternative mechanism for handling caching.

adriaanm · 2017-09-27T16:09:48Z

2.13 is a better target for this work. 2.12 is now at a point where we need to focus on stability and bug compatibility.

fommil · 2017-10-19T14:12:33Z

I have an alternative mechanism (to shapeless Generic / LabelledGeneric) for typeclass derivation that also hits the recursive types problem. I'll be interested to see if this fixes it. In the meantime I can use Lazy and Cached, hopefully without typeclass authors or end users needing to know about it.

OlivierBlanvillain · 2017-10-20T12:19:22Z

I've been playing around with this branch and found some variation between Dotty and this PR. Here is an isolated example (adapted from shapeless-type-class-derivation-2015-demo) that compiles using Dotty, but diverges on this PR.

I suspect the difference comes from the divergence checking.

milessabin · 2017-11-18T15:03:03Z

@OlivierBlanvillain That's a very useful example. Thanks!

It wouldn't expect the eqH arguments of eqHCons and eqCCons to have to be byname, and if I make them strict then your example compiles with this PR. That said, I think it should also compile if they are byname ... I'll investigate.

You're quite right that it's a difference in the divergence checker which is responsible for the difference here. I've implemented a slightly more sophisticated test than the user specified upper bound that you've gone for in Dotty. I think that it would be better to avoid making the limit a compilation parameter if at all possible.

I'm putting together a SIP for this at the moment and I'll include the details of the divergence criteria along with a proof that implicit search either terminates successfully or fails reporting divergence. I'm fairly confident that you will be able to port it over to the Dotty implementation.

milessabin · 2017-11-29T00:46:21Z

Rebased to 2.13.x.

@OlivierBlanvillain your example now works as is, but also with just the generic instance having a byname argument ... see test/files/pos/byname-implicits-13.scala and test/files/pos/byname-implicits-14.scala.

OlivierBlanvillain · 2017-11-29T10:15:25Z

@milessabin I just compiled all the pos & run tests from this PR on dotty master and it seams that both compilers agree as far as bymane implicits are concerned 👍

milessabin · 2017-11-29T10:17:21Z

@OlivierBlanvillain oh, awesome :-)

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: scala/scala3#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 scala#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 · 2018-07-10T10:25:11Z

@retronym those changes look fine. I'll rebase and pull them in to this PR.

This is the new way to freshen names while keeping compiler output stable when sources are re-ordered or incrementally recompiled.

An implicit macro within the by-name implicit dictionary might return a typechecked tree, so we ought to use changeOwner when moving that code into the RHS of a synthetic member of `LazyDefns`

milessabin · 2018-07-10T11:23:02Z

@retronym there are a couple of what look to be unrelated commits in there: retronym@e3cf13e and retronym@67a8665.

I'll leave them out.

@retronym

Incorporated changes suggested by @retronym.

milessabin · 2018-07-10T11:26:31Z

Rebased and incorporated @retronym's suggestions.

milessabin · 2018-07-10T13:03:28Z

@adriaanm I think this is ready to merge now :-)

adriaanm · 2018-07-10T15:10:11Z

🍰

milessabin · 2018-07-10T15:29:08Z

😋

kubukoz · 2018-07-10T17:46:59Z

Amazing work, thank you so much @milessabin and everyone involved! 2.13 is going to be so great!

Assigned number 36 to SIP “By-name implicit arguments”. Implemented in Scala 2.13 in scala/scala#6050 Implemented in Scala 3 in scala/scala3#5461

milessabin added the WIP label Aug 29, 2017

scala-jenkins added this to the 2.12.4 milestone Aug 29, 2017

milessabin mentioned this pull request Aug 29, 2017

Let by-name implicit parameters have lazy semantics scala/scala3#1998

Closed

milessabin mentioned this pull request Aug 31, 2017

Byname implicits parameters with recursive dictionaries scala/scala-dev#419

Closed

5 tasks

adriaanm self-requested a review September 21, 2017 22:53

adriaanm modified the milestones: 2.12.4, 2.13.0-M3 Sep 27, 2017

milessabin force-pushed the topic/byname-implicits branch from 87b912c to 8fe649d Compare November 29, 2017 00:41

milessabin changed the base branch from 2.12.x to 2.13.x November 29, 2017 00:41

milessabin changed the title ~~[WIP] Implementation of byname implicits with recursive dictionaries.~~ Implementation of byname implicits with recursive dictionaries. Nov 29, 2017

OlivierBlanvillain mentioned this pull request Nov 29, 2017

Byname implicits: could not find proxy for lazy var scala/scala3#3585

Closed

This comment has been minimized.

Sign in to view

retronym added 8 commits July 10, 2018 12:02

Use finer grained fresh name creators in by-name implicit desugaring

5bf4f02

This is the new way to freshen names while keeping compiler output stable when sources are re-ordered or incrementally recompiled.

Position synthetic trees of by-name implicit desugaring

34ffae3

Use TreeGen to create LazyDefns template

5b480f0

Adjust owner of byname implicit RHS

5dd9909

An implicit macro within the by-name implicit dictionary might return a typechecked tree, so we ought to use changeOwner when moving that code into the RHS of a synthetic member of `LazyDefns`

Perform substitution in a single pass.

ac35aeb

refactor lookup of vsyms in by-name implicit implementations

eb05421

Drop by-name before creating ImplicitSearch, rather than internally

c88c64e

Minor code cleanups in Contexts

882881b

milessabin force-pushed the topic/byname-implicits branch from fdc4261 to 882881b Compare July 10, 2018 11:24

adriaanm merged commit 874bf03 into scala:2.13.x Jul 10, 2018

This was referenced Jul 12, 2018

new compilation failure on latest 2.13 nightly etorreborre/specs2#687

Closed

new compilation failures in latest 2.13 nightly milessabin/shapeless#844

Closed

SethTisue changed the title ~~Implementation of byname implicits with recursive dictionaries.~~ Support by-name implicits with recursive dictionaries Aug 22, 2018

This was referenced Nov 20, 2018

publish for Scala 2.13.0-M5 typelevel/algebra#219

Closed

An Alternative to Implicits scala/scala3#5458

Merged

lrytz mentioned this pull request May 10, 2019

"ClassBType.info not yet assigned" error with Scala 2.13.0-RC1 scala/bug#11524

Closed

erikerlandson mentioned this pull request Jul 27, 2019

Derivation is failing to resolve a custom ConfigConvert materializer pureconfig/pureconfig#516

Closed

erikerlandson mentioned this pull request Apr 9, 2020

add coulomb to 2.13 community build scala/community-build#1127

Merged

julienrf added a commit to scalacenter/docs.scala-lang that referenced this pull request May 3, 2022

Mark SIP 36 as completed

49a15bb

Assigned number 36 to SIP “By-name implicit arguments”. Implemented in Scala 2.13 in scala/scala#6050 Implemented in Scala 3 in scala/scala3#5461

julienrf added a commit to scala/improvement-proposals that referenced this pull request Jun 9, 2022

Mark SIP 36 as completed

5e1225d

Assigned number 36 to SIP “By-name implicit arguments”. Implemented in Scala 2.13 in scala/scala#6050 Implemented in Scala 3 in scala/scala3#5461

pomadchin mentioned this pull request Sep 20, 2022

Remove Lazy for Scala 2.13 typelevel/frameless#660

Closed

Support by-name implicits with recursive dictionaries #6050

Support by-name implicits with recursive dictionaries #6050

Conversation

milessabin commented Aug 29, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tpolecat commented Aug 29, 2017

Uh oh!

tek commented Aug 29, 2017

Uh oh!

andyscott commented Aug 29, 2017

Uh oh!

fommil commented Aug 30, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

julienrf commented Aug 30, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

lrytz commented Sep 4, 2017

Uh oh!

milessabin commented Sep 4, 2017

Uh oh!

retronym commented Sep 11, 2017

Uh oh!

fommil commented Sep 11, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

milessabin commented Sep 11, 2017

Uh oh!

milessabin commented Sep 11, 2017

Uh oh!

adriaanm commented Sep 27, 2017

Uh oh!

fommil commented Oct 19, 2017

Uh oh!

OlivierBlanvillain commented Oct 20, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

milessabin commented Nov 18, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

milessabin commented Nov 29, 2017

Uh oh!

OlivierBlanvillain commented Nov 29, 2017

Uh oh!

milessabin commented Nov 29, 2017

Uh oh!

This comment has been minimized.

milessabin commented Jul 10, 2018

Uh oh!

milessabin commented Jul 10, 2018

Uh oh!

milessabin commented Jul 10, 2018

Uh oh!

milessabin commented Jul 10, 2018

Uh oh!

adriaanm commented Jul 10, 2018

Uh oh!

milessabin commented Jul 10, 2018

Uh oh!

kubukoz commented Jul 10, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

15 participants

milessabin commented Aug 29, 2017 •

edited

Loading

fommil commented Aug 30, 2017 •

edited

Loading

julienrf commented Aug 30, 2017 •

edited

Loading

fommil commented Sep 11, 2017 •

edited

Loading

OlivierBlanvillain commented Oct 20, 2017 •

edited

Loading

milessabin commented Nov 18, 2017 •

edited

Loading