Principles for Implicits in Scala 3

Unless I am misunderstanding something, with the new Dotty infrustructure, all dependencies on the classpath will actuall contain TASTY trees in the maven jars (rather than the binary JVM bytecode JARS we deal with now), and TASTY trees are basically compact serialized source code that has already been typechecked (this is also how we are “solving” the binary compatibility problem with Dotty)

This should already have all of the information, its basically the exact same set of information that Intellij has. The only thing that build tools need to do is to provide the full set of dependencies in the classpath, which they are doing anyways?

Also note that Intellij currently relies on the Scala compiler whenever you do a “find where this implicit is being used” in the project, as well as “where is this implicit coming from” because it needs the bytecode of the current set of the project (which is similar to how metals works)

For x.foo with x: X , look for implicit conversions from X to something and extension methods for X . X is the sought type.

If that was the case we would not need an import. The typical example that fails is @ichoran’s toOK from the implied imports thread:

implicit class EitherCanBeOk[L,R](private val underlying: Either[L,R]) {
  def toOk: Ok[L, R] = underlying match {
    case scala.util.Right(r) => Yes(r)
    case scala.util.Left(l) => No(l)
  }
}

it is defined on Either but resides with OK. Given a value of e of Either type, and an expression e.toOK, what does the compiler need to do to help?

It should look everywhere, searching for an implicit conversion/extension methods for Either.

The time it takes to look everywhere is irrelevant. At this point the compilation has already failed, and the compiler should go an extra mile to help the user fixing their issue.

It should look everywhere , searching for an implicit conversion/extension methods for Either .

Exactly. But what is everywhere? Without a project description we don’t know. The classpath is not enough, we might have lots of stuff on it that’s completely irrelevant for the project at hand. It could even point to malformed files that make the compiler choke or loop.

I think what this would lead to in the end is a model similar to Rust where the build tool (cargo) and the Rust compiler are integrated. We have to rethink the build tool/compiler interface. But given the heterogeneity of build tools in the Java space, that looks like a tough problem.

An even tougher example is the some method from Cats.
It’s certainly not defined on the source type; nor is it an enrichment of Option

So how can the compiler help if you attempt to call wibble.some without the correct import in scope?

It should scan the classpath. Not everything, and not potentially malformed files… just all the TASTY trees that can be located (because implicits will only be coming from scala classes anyway). It should identify if there are any implicits available that would provide this method and then list these possibilities in the reported error, much as we now do with ExecutionContext

This could be further enhanced with an export directive. Allowing library authors to identify exactly what implicits are eligible to be considered in such a search and massively simplifying the problem.

1 Like

That’s exactly the case in my Rust example presented here: Principles for Implicits in Scala 3

I provided an example where all definitions are placed in one file which can be misleading. Consider instead a multi-file project with following files:

struct_here.rs:

pub struct MyStruct;

impl MyStruct {}

traits/mod.rs:

pub mod trait_here;

traits/trait_here.rs:

use struct_here::MyStruct;

pub trait MyTrait {
    fn print_hello(&self);
}

impl MyTrait for MyStruct {
    fn print_hello(&self) {
        println!("Hello, World!")
    }
}

and finally the main file (library entry point) lib.rs:

pub mod struct_here;
pub mod traits;

use struct_here::MyStruct;

fn entry_point() {
    let instance = MyStruct {};
    instance.<caret is here>
}

At the specified place IntelliJ suggests me that I can use print_hello() method on instance of type struct_here::MyStruct. Note that traits::trait_here::MyTrait is not yet imported (with use keyword). Also struct_here/MyStruct.rs doesn’t have any reference to traits::trait_here::MyTrait so IntelliJ really need to scan everything to provide relevant suggestion.

When I choose the suggestion final code looks like this (lib.rs):

pub mod struct_here;
pub mod traits;

use struct_here::MyStruct;
use traits::trait_here::MyTrait; // automatically added line by IntelliJ

fn entry_point() {
    let instance = MyStruct {};
    instance.print_hello(); // print_hello from autocomplete
}

Rust compiler does similar job to IntelliJ, but in non-interactive way. Rust compiler doesn’t provide auto-complete, but it does suggest relevant import (use) clause when compilation fails.

There’s also a question why we must import the traits in Rust to make them useable. Answer is simple - with all traits implicitly imported there would be name clashes. Consider this: https://www.ideone.com/IeObsi

mod my_struct {
    pub struct MyStruct {}
}

mod traits_1 {
    pub trait Trait1 {
        fn print(&self);
    }

    impl Trait1 for ::my_struct::MyStruct {
        fn print(&self) {
            println!("Good morning!");
        }
    }
}

mod traits_2 {
    pub trait Trait2 {
        fn print(&self);
    }

    impl Trait2 for ::my_struct::MyStruct {
        fn print(&self) {
            println!("Goodbye!");
        }
    }
}

fn main() {
    use traits_1::Trait1;
    use traits_2::Trait2;

    let instance = my_struct::MyStruct {};
    println!("{}", instance.print());
}

Result:

error[E0034]: multiple applicable items in scope
  --> src/main.rs:35:29
   |
35 |     println!("{}", instance.print());
   |                             ^^^^^ multiple `print` found
   |
note: candidate #1 is defined in an impl of the trait `traits_1::Trait1` for the type `my_struct::MyStruct`
  --> src/main.rs:12:9
   |
12 |         fn print(&self) {
   |         ^^^^^^^^^^^^^^^
note: candidate #2 is defined in an impl of the trait `traits_2::Trait2` for the type `my_struct::MyStruct`
  --> src/main.rs:24:9
   |
24 |         fn print(&self) {
   |         ^^^^^^^^^^^^^^^

If the compiler, who is almost infinitely faster than I am, cannot even find this information, what hope do I, a poor biological creature, have in figuring it out?

It doesn’t need to be infallible, just helpful.

3 Likes

@odersky one thing that’s not clear is why you think classpath scanning is so difficult: we’d be loading pre-compiled metadata generated earlier, so it’s not like we need to run heavy compilation logic to extract the information. Since we control the compiler we can generate whatever metadata we want beforehand, at a time when the compiler already has the information in a convenient representation.

Classpath scanning is pretty common in JVM-land. Spring does it. Dropwizard does it. Intellij and Eclipse obviously do it. Even Ammonite does it, to power its autocomplete. Sure, it’s a bit fiddly, and there are things to be careful about, but it’s something that’s been done before many times in many projects. It’s certainly going to be orders of magnitude easier than overhauling both the syntax and semantics of a core language feature and collectively upgrading a hundred million lines of code.

4 Likes

It doesn’t even need to work with every build tool out of the box. If compiler needs extra information from build tool for suggestions heuristics then let that be optional. E.g. invoking:

scalac <some options> --implicits-suggestions-classpath=$A:$B:$C <other options>

would cause compiler to print suggestions on compilation errors. Without --implicits-suggestions-classpath there would be no suggestions. Fair deal, I think.

1 Like

OK. The compiler needs to scan the whole classpath. As you wrote, just the Tasty files, since implicits or extension methods cannot hide in Java class files. If the class path is too big it could do the scanning only when -explain is set (maybe triggered by a timeout). That looks all feasible, and would sure be a big help.

1 Like

Absolutely - it only needs to be a “reasonable best effort”, it’s a guide, not an essential feature.

It’s also okay to be slow because this will only happen on a particular class of build failures (and good search heuristics can help), but it’s not practical to do anything that would blow the heap!

That’s an orthogonal concern, the changes are unrelated to improved error messages. Of course… if the changes help with this then brilliant, but that’s not the primary goal!

Thanks for starting this discussion! It’s important to align on goals before getting into the implementation.

Can we talk about what “good” and “run-away success” mean? While I think that implicits are useful in some scenarios, ultimately I think they should be used sparingly. No matter the implementation, we’re always talking about the compiler automatically turning a type into a value through some kind of automatic process not explicitly directed by the programmer. This has a large cost in terms of readability, maintainability, etc.

When I hear “run-away success” it seems like @odersky wants implicits to be used more often in Scala code. I hope that is not the case, due to the aforementioned cost. Rather, I would like to see implicits that are used rarely but effectively, and that come with great tooling to offset the readability cost. And if we can lower the readability cost by relating implicits to other foundational language concepts (like multiple parameter lists or parameter defaults), that is even better.

Yes, implicits are sometimes useful, and somewhat unique to Scala, and an interesting concept in programming languages. But let’s not make them into a defining feature of Scala code or a feature that eats up the language complexity budget. I’m well aware that Martin has described implicits as one of the defining features of Scala, and as the creator that is certainly his prerogative. But as someone who loves Scala (pretty intensely!), I just can’t say that I agree.

4 Likes

I’ve said it earlier, but I’ll repeat. Martin’s motivation for language redesign was the perception of implicits in Scala compared to equivalents in e.g. Rust:

The answer is tooling, not syntax.

Imagine Rust without suggestions in compilation error messages (and without imports agnostic auto-completion in IntelliJ). Would it still be loved?

I think a proposal for a type-class-inspired syntax that emphasizes the intent of type classes rather than the mechanism is a good idea, but it has little chance of being accepted as is, due to the migration costs for little practical gain.

However, if the type-class-oriented syntax came with simplifications and restrictions that could ensure the resulting type classes are easier to reason about and give rise to better error messages, the proposal would have a better chance of being widely accepted.

So I’d propose to keep the original implicit mechanisms as the general-purpose but often too-powerful-for-its-own-good tool, but also add a more user-friendly type class special syntax that works similarly behind the scenes, but has restrictions and is easier to work with for everyday users.

In particular, it should be possible to deal with prioritization and orphan instances more elegantly than with the “hacky” approaches that have been proposed recently for Dotty, which only complicate the already very complicated rules of implicit resolution in ad-hoc ways. And ideally, we’d also have a way to enforce type class instance coherence.

4 Likes

I so totally agree with every word @mdedetrich says.

For the record, here is a minimized case where Rust compiler gives incorrect suggestion (regarding a typeclass), but that’s still a good starting point https://www.ideone.com/MD2Ah8

trait SuperTrait {
    type Raw;
 
    fn raw(&self) -> Self::Raw;
}
 
trait SubTrait: SuperTrait<Raw=i32> {}
 
// compiler suggests changing 'B' to 'B: SuperTrait'
// while correct solution is 'B: SubTrait'
fn generic_method<A: SubTrait, B>(a: A, b: B) -> A::Raw {
    a.raw() + b.raw()
}
 
fn main() {}

Result:

error: no method named `raw` found for type `B` in the current scope
  --> prog.rs:12:17
   |
12 |     a.raw() + b.raw()
   |                 ^^^
   |
   = help: items from traits can only be used if the trait is implemented and in scope; the following trait defines an item `raw`, perhaps you need to implement it:
   = help: candidate #1: `SuperTrait`

The standard library’s lack of Monoid seems to be an important symptom

I found that Scala’s typeclass conventions contributed as much or more to my learning curve than the theory of typeclasses/semantics. I haven’t found any place that these conventions are explained well except “Scala with Cats”.

For example in the circe library we have Decoder.instance, this used to seem arcane and exactly the kind of thing that might make newcomers feel stupid and detracted from continuing with Scala. After reading “Scala with Cats” I now see “Oh, Decoder.instance is a helper function to construct a typeclass instance for the Decoder typeclass, and this is a common convention across Scala”.

Compared to a language like golang, Scala might seem to suffer from “canonical Scala” requiring layers of conventions and non-standard libraries that are exogenous to the “official” language. It sounds like the mission for Scala 3 acknowledges some of this and is attempting to build some best practices into the language.

For example, if typeclasses are such a powerful, obvious, necessary part of Scala, why is there no Monoid in the standard library? It seems to me that by respecting the diversity of approaches to these core language features (eg. scalaz vs cats) we make Scala less approachable because newcomers must learn 1. the language, 2. the standard library, 3. the “standard” non-standard libraries (for which discovery is a huge issue for newcomers), and 4. the conventions to weave them all together. In golang a user need only learn (1) and (2) and I think this should be the case for Scala 3 as well.

Also, things I do with implicits that I hope are supported in Scala 3:

I’m writing a game in Scala where performance is a major issue and empirically dominated by dynamic memory allocations. To meet this goal I have found these practices related to implicits to be useful:

  • avoiding use of implicit def foo[A] because it reallocates typeclass instances each interface call, instead doing manual specialization with val fooA = foo[A]. (I know dotty has done work on instance derivation but I haven’t studied it)
  • impure “typeclass instances” eg. DoubleLinkedList.setNext(node, nextNode) = node.concreteNextNode = nextNode
  • “typeclass instances” that are both impure and close over context, eg. an instance of DoubleLinkedList which sets head of list by def setHead(container, newHead) = this.myMap(this.contextualKey)(container) = newHead
  • def DoubleLinkedList.isEmpty[A, B, C, H](h: H, t: InferType[A])(implicits using A, B, C, H) where the type parameters can’t be inferred by the compiler with the arg h, but can be inferred with a hint about A, where InferType[A]: Option[A] = None, preventing the need for the client to write isEmpty[verbose concrete type parameters](h)

These practices have helped me leverage implicits and I hope they are supported in the implicit redesign.

2 Likes

It would be great to see a good part of Cats imported into Standard Scala, including Monoid. Perhaps the new collections library would be more amenable for creating Monad instances. I would object though to having a standard Monoid instance for Ints.

Would it be possible to achieve all 7 of the design principles with macros? Racket for example is famous for defining its entire class system and traits system with macros (classes, traits, paper). Through composable and easy-to-use macros, Racket exposes high-level syntax for classes, traits, contracts, etc, while still keeping the lower level substrates available and approachable as well.

A macro for defining extension methods, for example, could expand to an implicit class. If that macro were part of the standard library, the compiler might scan the classpath for extensions defined with it when emitting “method not found” error messages. IDEs (or metals?) could also offer to auto-import an extension while a developer is typing a method call, or even list all importable extensions in the auto-completion list.

Macros for typeclasses already exist in simulacrum, machinist, etc. Could changes to the macro system make them easier to implement, easier to understand the implementation, and easier to use as syntax without confusing IDEs?

Likewise for context parameters (ExecutionContext, RequestID, UserID, Viewer, etc), could some form of def/context macro expand to def + implicit functions?

Implicits and macros in Scala 2 enable useful patterns but are arguably advanced features that users of those patterns need to understand to some degree as well. If the patterns were expressible as abstractions and if those abstractions weren’t leaky, Scala could have the approachability of Rust traits, Swift protocols, Kotlin extension functions, and Racket classes without losing the core part of the language that enables this.

1 Like