pre-SIP discussion: getting all matching implicits

[Mark Kegel]

Hey all!

The scala compiler currently limits us to asking for a single implicit, and if multiple implicits are found that satisfy the constraint are found then it errors out. I like this behavior since it makes implicits much safer to use, however I propose that we extend the compiler to add a separate mechanism to let developers ask for ALL in-scope implicits that match some constraint, only erroring out if no matching implicits can be found. 

You might ask why we would want this but I've personally now run into a couple of situations where it would have been really handy to have access to all the in-scope implicits that satisfied some type constraint, and I'm not the only one. Consider this stackoverflow question: http://stackoverflow.com/questions/36929646/chaining-implicits-via-the-shortest-route/

The original poster has a set of type converters (A -> B, B -> C, etc) and they would like to find the shortest path (fewest number of converters) between two types. This shouldn't be a "hard problem" to solve. Yet within reason and given current techniques this isn't a solvable question, at least not with Scala implicits. However, it doesn't have to be this way.

I propose that we allow users to ask for ALL in-scope implicits matching a certain constraint. This would allow whole classes of solutions to be possible, including making the shortest path question solvable.

To accomplish this I suggest using this syntax:

def allOf[T](implicit all:T*) = all

The only change is the addition of the repeated args type modifier to the type parameter. For example:

implicit def anInt = 5

implicit val anotherInt = 12

allOf[Int] == Seq(5, 12)

As far as I can tell the proposed syntax, while parsable, is NOT actually valid Scala since you can't actually have a concrete type of T* in scope, or at least it wouldn't make any sense if you currently did. The syntax also helps denote a substantially different type, so that T and T* can be parsed up front and understood to be completely different things. This helps IDEs, which tend to get easily confused. 

I do agree that the syntax is a bit context-specific, but we live with this ambiguity in other places. Consider the 'case' keyword in scala, and the multiple uses of 'default' in Java.

Implementation-wise I think this is actually reasonably easy. The scala compiler already has to enumerate all matching implicits today. It actually goes above and beyond, by then ranking them and returning the "best" implicit. In this case, the compiler would "only" need skip that step.

I see two important complications.

First, you can have an implicit val, an implicit def, or an implicit object. Because of this the compiler actually does multiple searches (i.e. for T, then => T, then  () => T). It will then materialize the best of these. In returning all matching implicits we pretty much have to materialize all matching implicits, recursively following defs that require other implicits. 

Given that, do we make materialization lazy or not?

I'm not sure if materialization can or should be made lazy, but that might help performance a bit potentially. Regardless, even though there are many way to satisfy an implicit for a type T, all implicits independent of how they are declared in code eventually need to be materializable if they are a candidate. This makes the interface completely uniform since you can't ask for things that can't be materialized and I would think it would be an error if the user did. 

Second, I currently envision T* being expanded into a Seq[T]. This drops quite a lot type information. 

Would it be worthwhile to have T* expand into a kind of HList-like structure that preserved the original types of all the matching implicits?

Given that this would already be an advanced feature keeping as much type information around as possible is probably the correct choice. That would mean T* wouldn't expand into a Seq, but maybe could be something convertible to a Seq.

I'd love to know what folks currently think about this proposal. I'm working on hacking this into the 2.12 Scala compiler to see what edge cases exist and if it even possible.

Mark Kegel

[Tomas Mikula]

Hi Mark,

am I correct that in the use case you linked, you would then perform selection of the shortest path converter at runtime? If so, doesn't that miss the point?

Best,

Tomas

[Mark Kegel]

Tomas,

Nope this would still be done at compile time, though the stackoverflow question as posed may not have made that clear.

Mark

[Jasper-M]

And how would that be implemented then?

Op donderdag 7 juli 2016 05:53:39 UTC+2 schreef Mark Kegel: