Proposal to Add Implied Instances to the Language

Scala Improvement Process
1

Since the discussion on the Proposal to Revise Implicit Parameters already touched repeatedly on the issue how to define implied/implicit instances, I am jumping the queue and open a discussion thread on this now.

For background, both proposals belong to the group contextual abstractions - taken together, these two proposals are the cornerstones of this area. Also relevant are the principles I outlined in my comment on the previous thread. Two of the seven principles formulated there apply to implicit instances:

  1. There should be a single form of implicit instance definition. That syntax must be able to express monomorphic as well parameterized and conditional definitions, and stand-alone instances as well as aliases.
  2. The new syntax should not mirror the full range of choices of the other definitions in Scala, e.g. val vs def, lazy vs strict, concrete vs abstract. Instead one should construct these definitions in the normal world and then inject them separately into the implicit world.

The proposal itself is a doc page, from which I quote here. I’ll follow up with some remarks in the next comment(s) on this thread.

16-May-2019: I updated this page to correspond to the new proposal.

Implied Instances

Implied instances define “canonical” values of given types that can be synthesized by the compiler as arguments for given clauses. Example:

trait Ord[T] {
  def compare(x: T, y: T): Int
  def (x: T) < (y: T) = compare(x, y) < 0
  def (x: T) > (y: T) = compare(x, y) > 0
}

implied IntOrd for Ord[Int] {
  def compare(x: Int, y: Int) =
    if (x < y) -1 else if (x > y) +1 else 0
}

implied ListOrd[T] for Ord[List[T]] given (ord: Ord[T]) {
  def compare(xs: List[T], ys: List[T]): Int = (xs, ys) match {
    case (Nil, Nil) => 0
    case (Nil, _) => -1
    case (_, Nil) => +1
    case (x :: xs1, y :: ys1) =>
      val fst = ord.compare(x, y)
      if (fst != 0) fst else xs1.compareTo(ys1)
  }
}

This code defines a trait Ord and two implied instance clauses. IntOrd defines
an implied instance for the type Ord[Int] whereas ListOrd[T] defines implied
instances of Ord[List[T]] for all types T that come with an implied Ord[T] instance themselves.
The given clause in ListOrd defines an context parameter.

Anonymous Implied Instances

The name of an implied instance can be left out. So the implied instance definitions
of the last section can also be expressed like this:

implied for Ord[Int] { ... }
implied [T] for Ord[List[T]] given (ord: Ord[T]) { ... }

If the name of an instance is missing, the compiler will synthesize a name from
the type(s) in the for clause.

Implied Alias Instances

An implied alias instance defines an implied instance that is equal to some expression. E.g.:

implied global for ExecutionContext = new ForkJoinPool()

This creates an implied instance global of type ExecutionContext that resolves to the right hand side new ForkJoinPool().
The first time global is accessed, a new ForkJoinPool is created, which is then
returned for this and all subsequent accesses to global.

Alias instances may be anonymous, e.g.

implied for Position = enclosingTree.position

An implied alias instance can have type parameters and given clauses just like any other implied instance, but it can only implement a single type.

Creating Implied Instances

An implied instance without type parameters or given clause is created on-demand, the first time it is accessed. It is not required to ensure safe publication, which means that different threads might create different representatives for the same implied clause. If an implied instance has type parameters or a given clause, its definition is evaluated each time it is applied to arguments.

Syntax

Here is the new syntax of implied instance definitions, seen as a delta from the standard context free syntax of Scala 3.

TmplDef          ::=  ...
                  |  ‘implied’ InstanceDef
InstanceDef      ::=  [id] [DefTypeParamClause] InstanceBody
InstanceBody     ::=  [‘for’ ConstrApp {‘,’ ConstrApp }] {GivenParamClause} [TemplateBody]
                   |  ‘for’ Type {GivenParamClause} ‘=’ Expr
ConstrApp        ::=  SimpleConstrApp
                   |  ‘(’ SimpleConstrApp {‘given’ (PrefixExpr | ParArgumentExprs)} ‘)’
SimpleConstrApp  ::=  AnnotType {ArgumentExprs}
GivenParamClause ::=  ‘given’ (‘(’ [DefParams] ‘)’ | GivenTypes)
GivenTypes       ::=  AnnotType {‘,’ AnnotType}
ConstrApp        ::=  SimpleConstrApp
                   |  ‘(’ SimpleConstrApp {‘given’ (PrefixExpr | ParArgumentExprs)} ‘)’

The identifier id can be omitted only if either the for part or the template body is present.
If the for part is missing, the template body must define at least one extension method.

1 Like
2

This spec and its implementation received many prior comments in https://github.com/lampepfl/dotty/pull/5458 and has undergone many revisions prompted by these comments.

We particularly went back and forth about the keyword introducing the construct. Here are the alternatives in roughly chronological order:

  • witness was the original proposal.
  • capability was discarded for being too specialized.
  • impl - was tried in a full implementation but discarded since it is too commonly used (we decided that the keyword better be a hard keyword, since otherwise we risk too much parsing ambiguity).
  • instance - was tried but discarded because it seemed too generic as a term, with too many conflicting common meanings.
  • inferred was briefly considered before being replaced by implied
  • rule was discarded for being too generic and imprecise.

Other alternatives brought up were default (but that’s again too common), and evidence. Or one could just use implicit as a noun.

Of course there’s more to the proposal than just this keyword. But finding a good keyword is also important. I am personally not fixated on which keyword to use. In fact, going through the discussion thread on the PR again, I note that we might have overlooked evidence, so maybe that’s still worth considering.

3

Also relevant to understand the relationship between this and current implicit definitions:

https://dotty.epfl.ch/docs/reference/contextual/relationship-implicits.html

4

Hmm. Have we considered imply instead of implied? The verb form feels more correct to me here – it would then read as “imply ListOrd, given an Ord of T, for Ord of List of T”. The syntax would match the verbal description nicely. (Granted, that’s not a hard requirement, but it does make for good mnemonics.) And the active verb seems to make sense – this is describing the act of stuffing something into the implicit cloud, which feels right to me…

1 Like
5

imply (and all other verbs) don’t seem to work so well for anonymous instances. E.g.

imply for C

looks a bit strange. Even with named instances it seems off:

imply c for C { ... }

This seems to state that a referred-to quantity c implies C. But in fact c is a newly introduced name for the thing that’s defined in the braces. That’s why I believe nouns and, possibly, adjectives would work better here.

6

I agree with @jducoeur that imperative verb form imply or provide sounds more natural to me.

It was probably suggested before, but would it be possible to have given clause follow for clause in the definition?

implied ListOrd[T] for Ord[List[T]] given (ord: Ord[T])

sounds more like plain English.

Lastly, I find the syntax for anonymous polymorphic instances a little jarring: that [T] in implied [T] given kind of floats in the vacuum.

implied Ord[List[T]] given (ord: Ord[T])

would be quite pleasant to read and immediately understandable to a human, but might be too much guesswork for the compiler?

2 Likes
7

It suggests not that c implies C (that would be written c implies C), but rather than C implies c. (Because the verb is imply and the object is c; there is no subject given, but the for suggests that it’s C. Note that this form is commonly found in phrases like “cut the bread with the knife” where the subject is elided and then the context (i.e. the subject) supplied by using a preposition (“with”).)

Instead, it is imperative, and the subject who is doing the implying is not listed (but presumably is the reader or the compiler or something); the associated stuff that is helping perform or is relevant the implication is C. This is in the same general form as “cut the bread with the knife”.

It is awkward when there’s no object either; imply for C reads really weirdly. imply _ for C is less awkward but still is hard to pronounce (bad for people who think in words rather than concepts).

8

It was probably suggested before, but would it be possible to have given clause follow for clause in the definition?

It was suggested (I believe by @drdozer) but was not discussed yet since it was in the other thread.

It does feel more natural but would be less regular. There’s also the problem of ambiguity - does the trailing given pass an implicit argument to the class in the for clause or is it a parameter list? Finally, it works strangely for dependencies if a type in the for clause refers to a given parameter. Example:

  implied c given (u: Universe) for C[u.T]

If we put given last, we’d refer to a parameter before it was defined:

  implied c for C[u.T] given (u: Universe)

None of it is fatal, but taken together I believe the regular given first syntax has an edge.

9

Right. I should have written:

This seems to state that a referred-to quantity c is implied as the instance for C .

10

Was implicit considered and rejected (without val or any following keyword)?

implicit Foo[Int] { ... }
implicit x = Foo[Int] { ... }
implicit x: Foo[Int] = myFoo

This all seems to avoid the awkward sentence-fragment grammar of things like implied for Bar with no subject.

(It is less clearly distinct, admittedly, but if the distinct stuff runs into trouble, maybe there’s a reason to keep it similar.)

2 Likes
11

Also of note is that, for better or worse, none of the existing definition statements (except maybe def, which is ambiguous) are imperative… So I think the originally-proposed implied ... for ... reads better than imply ...

2 Likes
12

I like the implicit suggestion that @Ichoran brought up. While you can “not mirror other definitions in Scala” to varying degrees, I think letting people say implicit foo = ... without any val/var/def is a reasonable compromise between familiarity, difference-from-normal-declarations, and also conciseness.

Something like this:

implicit IntOrd extends Ord[Int] {
  def compare(x: Int, y: Int) =
    if (x < y) -1 else if (x > y) +1 else 0
}

I think looks a lot better than

implied IntOrd for Ord[Int] {
  def compare(x: Int, y: Int) =
    if (x < y) -1 else if (x > y) +1 else 0
}

even though it’s the exact same syntax just with different keywords, the fact that they are familiar keywords used correctly to mean familiar concepts makes me like it far more than coming up with a new set of keywords that mean basically the same thing.

The whole given syntax is a bit of a separate discussion, about what the implicit param passing/declaring syntax should be, so won’t touch on that here.

4 Likes
13

As I have said before I am generally in favor of the whole new 'implicit’s approach. Most notably because it separates normal parameters from implicit parameters more distinctly.

The changes for instances seem good, I think removing the def/val/lazy etc is a good choice, as is the possibility to make them anonymous. Though I am not sure if that will hurt error messages in case of ambiguous implicits?

That said, I don’t really care much if we use implied..for or implicit .. extends. I can imagine that the latter is more familiar and therefore maybe preferable. Though I think you can get used to both quickly enough.

2 Likes
14

Did you consider the word assume? I always considered implicits as (formal/mathematical) assumptions.

15

I though about this too, but how do you generalize it to look OK for implied alias instances and anonymous implied instances?

16

Not sure what you mean by alias instances, but something like this?

implicit IntOrd = SomeOtherOrd

For anonymous instances I think this looks reasonable:

implicit extends Ord[Int] {
  def compare(x: Int, y: Int) =
    if (x < y) -1 else if (x > y) +1 else 0
}

Though I wouldn’t be surprised if not everyone liked that

1 Like
17

See the OP. This is what implicit function types became.

18

implicit as a noun was not yet fully considered as far as I can recall. So it’s worth pursuing this!

One thorough but relatively cheap way to experiment would be to make a pull request against
dotty, copying the docs/reference/contextual directory to, say, contextualX, and applying any proposed syntax changes to all files in that copy. Then we could see how everything looks with the new syntax.

I think I will give this a shot with evidence instead of implied. I get the feedback that implied is too close to given, so people are unsure when to use which. evidence was proposed by @ivanopagano on the original PR, but was never tried out at large. It has the advantage that it fits well with the following narrative for explaining implicits:

Scala has a way to infer terms for types. Generally, a type for which terms are inferred represents some form of property. For instance, the type Ordering[Int] represents the property that integers are ordered by way of stating that the type Int has an Ordering. Or, the type Monad[List] represents the property that lists are monads. Even a type like ExecutionContext that consists of a single identifier can be seen as a property: Namely, that there is a designated instance of ExecutionContext in scope.

The term that is inferred for a type provides evidence that the property associated with the type holds. For instance a definition like

    evidence IntOrd for Ordered[Int] ...

establishes IntOrd as the evidence that ints are ordered. Or,

    evidence global for ExecutionContext = myForkJoinContext

provides evidence that there is a designated ExecutionContext, namely global.

Inside a function or a class, we can have a constraint that requires that evidence for a property exists. This is done using a given clause.

In fact we already use ev1, ev1, ev2, … as common names for implicit “evidence” parameters. So the name evidence is already familiar. And, it has nice proof theoretic connotations as well.

3 Likes
19

what about such idea:

implicit new Ord[Int] {
  def compare(x: Int, y: Int) =
    if (x < y) -1 else if (x > y) +1 else 0
}

Here is pretty complete list of variants of that syntax. Not all looks promising but I’ve tried to show all what I could find.

//simple block
implicit x = { ... } // 0.1 // should be disallowed? We'll infer type of implicit here what could be dangerous!
implicit x:Foo[Int] = { ... } //0.2 //ok

//1. create instance
implicit x = Foo[Int] { ... } // 1.1 //this is in SIP that tries to remove 'new' keyword
implicit x:Foo[Int] = Foo2[Int] { ... } // 1.2
implicit x = new Foo[Int] { ... } // 1.3
implicit x:Foo[Int] = new Foo2[Int] { ... } // 1.4
implicit x extends Foo[Int] {...} // 1.5
implicit x for Foo[Int] { ... } //1.6

//2. aliases
implicit x = myFoo // 2.1 //we infer type but here is less dangerous i guess.
implicit x: Foo[Int] = myFoo // 2.2 //boring

//3. anonymous aliases
//implicit { myFoo } // 3.1 //rather not nice. 
//implicit = { myFoo } // 3.2 //RATHER NOT OK. Harder for parsing?
//implicit:Foo[Int] = { myFoo } // 3.3 //RATHER NOT OK. Harder for parsing?
//implicit = myFoo // 3.4 //as above
//implicit myFoo // 3.5 //It takes myFoo and makes it implicit. RATHER NOT OK. 

//4. anonymous create instance
implicit Foo[Int] { ... } // 4.1 //looks ok
//implicit = new Foo[Int] {...} // 4.2 //RATHER NOT OK
implicit new Foo[Int] {...} // 4.3
implicit extends Foo[Int] {...} // 4.4 //looks ok

I’ve commented out all variants that looks odd for me. Not sure if it’ll be helpful.

20

I think the clearest syntax would still be

implicit x for Foo[Int] { ... }

We define something that’s an implicit value for a given type.