Let by-name implicit parameters have lazy semantics

[odersky]

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 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]

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]

+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]

@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]

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

[odersky]

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

[TomasMikula]

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]

@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]

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]

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]

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]

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