Inconsistency in effect and effect extension method declarations results in inconsistent compiler behavior and false positive compilation

[jackcviers]

The required context gets lost when defining methods on an effect as extension methods, but not when an extension is defined as a top-level extension method. When defined as a typeclass, the effect type cannot be inferred.

Case-1

Given the following definition of an effect:

package fx

import scala.annotation.implicitNotFound
import java.nio.charset.Charset
import java.nio.charset.StandardCharsets

@implicitNotFound(
  "requires capability:\n% Serde[${A}]"
)
trait Serde[A]:
  extension (s: String) def ser(): Array[Byte] % Serde[A]
  extension (a: Array[Byte]) def de(): String % Serde[A]
object Serde

And a test file:

package fx

import org.scalacheck.Properties
import org.scalacheck.Prop.forAll

class SerdeTests extends Properties("Serde Tests"):
  property("Things with a serde instance should round trip") = forAll{ (input: String) =>
    val y = input.ser().de()

    run(y) == input

  }

The compiler will fail with the following message:

[info] done compiling
[info] compiling 1 Scala source to /Users/jackcviers/development/scala-fx/ 
  scala-fx/target/scala-3.1.1-RC1/test-classes ...
[error] -- [E008] Not Found Error: /Users/jackcviers/development/scala-fx/ 
  scala-fx/src/test/scala/SerdeTests.scala:8:18 
[error] 8 |    val y = input.ser().de()
[error]   |            ^^^^^^^^^
[error]   |value ser is not a member of String, but could be made available as an extension method.
[error]   |
[error]   |The following import might make progress towards fixing the problem:
[error]   |
[error]   |  import fx.idParBind
[error]   |

Case-2

However, if we modify the definition of Serde[A] to be an empty marker trait (not a phantom type because it is instantiated when the given instance is provided) so that we can take advantage of other capabilities in the return of any extension methods related to the Serde[A] capability, such as Errors:

package fx

import scala.annotation.implicitNotFound
import java.nio.charset.Charset
import java.nio.charset.StandardCharsets

@implicitNotFound(
  "requires capability:\n% Serde[${A}]"
)
trait Serde[A]
object Serde

extension (s: String) def ser(): Array[Byte] % Serde[String] = ???
extension (a: Array[Byte]) def de(): String % Serde[String] = ???

and we don't change the definition of the client code in the tests, we get an entirely different (and, in fact, the desired compilation error) compilation error result:

[error] -- Error: /Users/jackcviers/development/scala-fx/scala-fx/src/test/scala/SerdeTests.scala:8:23 
[error] 8 |    val y = input.ser().de()
[error]   |                       ^
[error]   |                       requires capability:
[error]   |                       % Serde[String]

Providing a Serde[String] instance resolves the error and the effect works as intended in Case 2:

Case-2 Resolved Given Context:

package fx

import scala.annotation.implicitNotFound
import java.nio.charset.Charset
import java.nio.charset.StandardCharsets

@implicitNotFound(
  "requires capability:\n% Serde[${A}]"
)
trait Serde[A]
object Serde:
  given Serde[String] =
    new Serde[String]{}

extension (s: String)
  def ser(): Array[Byte] % Serde[String] = s.getBytes(StandardCharsets.UTF_8)
extension (a: Array[Byte])
  def de(): String % Serde[String] = String(a, StandardCharsets.UTF_8)

[info] done compiling
[warn] javaOptions will be ignored, fork is set to false
[info] + Serde Tests.Things with a serde instance should round trip: OK, passed 100 tests.
[info] Passed: Total 1, Failed 0, Errors 0, Passed 1
[success] Total time: 1 s, completed Dec 27, 2021, 2:44:44 PM

Case-3

A false-positive compilation occurs when encoding Serde[A] as an opaque type. When we encode opaque type Serde[A] = Unit, the top-level extension methods find and use the top-level given Runtime instance instead of failing to compile with a missing Serde[String] capability:

package fx

import scala.annotation.implicitNotFound
import java.nio.charset.Charset
import java.nio.charset.StandardCharsets

@implicitNotFound(
  "requires capability:\n% Serde[${A}]"
)
opaque type Serde[A] = Unit
object Serde

extension (s: String)
  def ser(): Array[Byte] % Serde[String] = s.getBytes(StandardCharsets.UTF_8)
extension (a: Array[Byte])
  def de(): String % Serde[String] = String(a, StandardCharsets.UTF_8)

The client test code remains the same. The property tests pass. This should fail compilation, but doesn't because the extension methods exist at the top-level:

[info] done compiling
[warn] javaOptions will be ignored, fork is set to false
[info] + Serde Tests.Things with a serde instance should round trip: OK, passed 100 tests.
[info] Passed: Total 1, Failed 0, Errors 0, Passed 1
[success] Total time: 6 s, completed Dec 27, 2021, 2:55:21 PM

This really confused me, as it appears to be defined in the same manner as fx.Bind, and that will fail compilation correctly. I don't have a good explanation for why this occurs.

Case-3A

Using the same effect definition as in Case 3 but with the required capability declared on the actual value in the property tests results in a missing capability error at the point of run in the test, but loses the capability type parameter in the implicit not found definition:

package fx

import org.scalacheck.Properties
import org.scalacheck.Prop.forAll

class SerdeTests extends Properties("Serde Tests"):
  property("Things with a serde instance should round trip") = forAll{ (input: String) =>
    val y: String % Serde[String] = input.ser().de()

    run(y) == input

  }

[error] -- Error: /Users/jackcviers/development/scala-fx/scala-fx/src/test/scala/SerdeTests.scala:10:9 
[error] 10 |    run(y) == input
[error]    |         ^
[error]    |         requires capability:
[error]    |         % Serde[]
[error] one error found
[error] one error found
[error] (scala-fx / Test / compileIncremental) Compilation failed

Case 5

Of course, if we provide a given definition for Serde[String], the test compiles and passes correctly, with or without the actual value type annotation, and implicit expansion shows the correct given_Serde_String given instance being used for the Serde instance:

package fx

import scala.annotation.implicitNotFound
import java.nio.charset.Charset
import java.nio.charset.StandardCharsets

@implicitNotFound(
  "requires capability:\n% Serde[${A}]"
)
opaque type Serde[A] = Unit
object Serde:
  given Serde[String] = ()

extension (s: String)
  def ser(): Array[Byte] % Serde[String] = s.getBytes(StandardCharsets.UTF_8)
extension (a: Array[Byte])
  def de(): String % Serde[String] = String(a, StandardCharsets.UTF_8)

Client Test Example Un-annotated

package fx

import org.scalacheck.Properties
import org.scalacheck.Prop.forAll

class SerdeTests extends Properties("Serde Tests"):
  property("Things with a serde instance should round trip") = forAll{ (input: String) =>
    val y = input.ser().de()

    run(y) == input

  }

Client Test Example Annotated

package fx

import org.scalacheck.Properties
import org.scalacheck.Prop.forAll

class SerdeTests extends Properties("Serde Tests"):
  property("Things with a serde instance should round trip") = forAll{ (input: String) =>
    val y: String % Serde[String] = input.ser().de()

    run(y) == input

  }

Results (identical for annotated and un-annotated test file)

[info] done compiling
[info] compiling 8 Scala sources to /Users/jackcviers/development/scala-fx/scala-fx/target/scala-3.1.1-RC1/test-classes ...
[info] Passed: Total 0, Failed 0, Errors 0, Passed 0
[info] No tests to run for benchmarks / Test / testOnly
[info] Passed: Total 0, Failed 0, Errors 0, Passed 0
[info] No tests to run for documentation / Test / testOnly
[info] done compiling
[warn] javaOptions will be ignored, fork is set to false
[info] + Serde Tests.Things with a serde instance should round trip: OK, passed 100 tests.
[info] Passed: Total 1, Failed 0, Errors 0, Passed 1

Conclusion

We currently use both styles: typeclasses and top-level extension-methods, in scala-fx. We also currently use bath opaque and trait effect declaration types. However, given the interference of the scala compiler when using typeclass definitions, might it be better to avoid them in general? And given the compiler behavior when using opaque types, might it be better to stick to empty trait givens with top-level extensions to avoid the incorrect compilation and error message results?

[raulraja]

Thanks @jackcviers for such detailed examples.

However, given the interference of the scala compiler when using typeclass definitions, might it be better to avoid them in general?

I think so, we only need type classes in cases like Control where there is type arguments. Does SerDe[A] actually needs A in its declaration or can this be moved to the method?

And given the compiler behavior when using opaque types, might it be better to stick to empty trait givens with top-level extensions to avoid the incorrect compilation and error message results?

Yes, I think that would be better and ideally, when we use parametric types like Control or Serde we would be using erased class because those implicit values are not needed at runtime unless you actually wrap them in type classes.

Having said all this we still need to discuss the multiplatform/multilanguage approach since this is just specific to Scala but the plan is to make all these abilities cross-language yet compatible while using the best features from each lang. For example context functions in Scala, context receivers in kotlin, and functional interfaces with lambda arguments in Java.

[jackcviers]

I think so, we only need type classes in cases like Control where there is type arguments. Does SerDe[A] actually needs A in its declaration or can this be moved to the method?

It is necessary, tagging and refined types are especially common use cases when doing serialization. We'd need to provide the evidence that a Serde[String @@ UTF-16] exists or a Serde[Long Tagged Kilometer] and a Serde[Long Tagged Meter] existed.

You could of course use opaque types for those, but the compiler will substitute the Meter in the place of the Kilometer (like it did for the given Runtime above) if only one of the two exists, for example.

You could use value types, too. But you'll have to box in collections. You can't move it to the method in the case of serialization, because you usually end up having to write pre-value schema definition stuff encoded in some bitmask prior to encoding the bytes (or use Protobuf and a mutable header or Avro and some header definition file or some other serialization tech), which means knowing the type before choosing the serialization strategy or otherwise having a priori knowledge to deduce a strategy from the available ones. I chose Serde specifically because it's about the simplest use case where that type of knowledge is necessary without encoding as extra lambda arguments to the extension methods. Others include Fetch, Defer, and Atomic, for example.

We'll often need parameters in the effect declaration, but not need anything inside the effect at runtime. We might be able to get around needing that using Dependent function types, too, though. Haven't tried it yet, but might be something else worth exploring.

Yes, I think that would be better and ideally, when we use parametric types like Control or Serde we would be using erased class because those implicit values are not needed at runtime unless you actually wrap them in type classes.

I didn't try that encoding ☹️. Probably should have, sorry. But I agree here entirely. You can probably guess what I want to encode here: a json lib that plays nice with our Controls or Errors effects.

[jackcviers]

Having said all this we still need to discuss the multiplatform/multilanguage approach since this is just specific to Scala but the plan is to make all these abilities cross-language yet compatible while using the best features from each lang. For example context functions in Scala, context receivers in kotlin, and functional interfaces with lambda arguments in Java.

In Java I assume we'd use annotation processing rather than lamda arguments, as that would occur at compile time. You would have to create maven and gradle plugins for them, of course, but they'd be pretty much boilerplate.

You might need to use AOP interceptors to suspend everything into the continuation as well. But it would work (on loom).

For JS/Typescript, you're probably looking at a babel plugin for the compiler verified effects stuff. All the cool libs do it -- react, angular, etc. No reason not to extend the language when everyone else does. I'd probably suggest limiting it to typescript instead of going full js. Then be prepared when in two or three years they want to standardize it. You could probably embed the continuations all in async/await, but that's not 1:1 behavior with what we're really talking about here, because it would be eager and not wait for run(), I think. There's a runtime capable discussion of algebraic effects embedding in continuations in js here. Again, it's not really the same as what we're talking about. JS has generator functions, which could probably be used to suspend things within -- I think there was a python book on FP that used python generators to do effect suspension back in the day in this way. But it wouldn't be compile-time erased/checked.

Python would be a good target lang as well. You'd probably use decorators and metaclasses to do this stuff there. It wouldn't have much effect if somebody didn't run a typer, but if they did it would really help. hypothesis already does stuff like this, as does marshmallow. Plus it has real 0-cost newtypes, so the erased classes are a cinch. It already has fiber-like things in many different libraries.

Rust and swift I have no idea how we'd implement things like erased classes within.

Rust has macros for the compiler checking/derivation things, and stackless coroutines for the continuations. I have no idea how complex they'd be to implement an exact copy of the behavior within. I've heard mixed reviews of using async/await in rust, however.

Swift has path dependent types -- so you could use the Aux pattern from old shapeless and it has Extensions. I don't know what support it has for suspended and labeled continuations though.