Path dependent types don't play well with macros and typeclasses

[anatoliykmetyuk]

Consider the following:

import scala.quoted._


trait IsExpr[T] {
  type Underlying
  def toExpr(x: T): Expr[Underlying]
}

// object IsExpr { type Aux[T, U] = IsExpr[T] { type Underlying = U } }

// given [U] as IsExpr.Aux[Expr[U], U] = new IsExpr[Expr[U]] {
given [U] as IsExpr[Expr[U]] = new IsExpr[Expr[U]] {
  type Underlying = U
  def toExpr(x: Expr[U]): Expr[U] = x
}

def f(x: Any): String = x.toString

def g[T](x: T) given (e: IsExpr[T], tu: Type[e.Underlying]): given QuoteContext => Expr[String] = {
  val underlying: Expr[e.Underlying] = e.toExpr(x)
  '{f($underlying)}
}

// def g[T, U](x: T) given (e: IsExpr.Aux[T, U], tu: Type[U]): given QuoteContext => Expr[String] = {
//   val underlying: Expr[U] = e.toExpr(x)
//   '{f($underlying)}
// }

inline def mcr: Any = ${mcrImpl}
def mcrImpl given QuoteContext: Expr[Any] = {
  val x = '{1}
  g(x)
}

Will output:

-- Error: ../pg/Lib.scala:21:6 -------------------------------------------------
21 |  '{f($underlying)}
   |      ^^^^^^^^^^^
   |      access to value e from wrong staging level:
   |       - the definition is at level 0,
   |       - but the access is at level 1.

Sort of makes sense, since e is indeed defined at level 0. However, two facts make me think something can be done here. First, only the path-dependent type is accessed there (presumably, since the compiler needs to know the type of underlying), and we have it with the Type argument. Second, the following trick works:

import scala.quoted._


trait IsExpr[T] {
  type Underlying
  def toExpr(x: T): Expr[Underlying]
}

object IsExpr { type Aux[T, U] = IsExpr[T] { type Underlying = U } }

given [U] as IsExpr.Aux[Expr[U], U] = new IsExpr[Expr[U]] {
// given [U] as IsExpr[Expr[U]] = new IsExpr[Expr[U]] {
  type Underlying = U
  def toExpr(x: Expr[U]): Expr[U] = x
}

def f(x: Any): String = x.toString

// def g[T](x: T) given (e: IsExpr[T], tu: Type[e.Underlying]): given QuoteContext => Expr[String] = {
//   val underlying: Expr[e.Underlying] = e.toExpr(x)
//   '{f($underlying)}
// }

def g[T, U](x: T) given (e: IsExpr.Aux[T, U], tu: Type[U]): given QuoteContext => Expr[String] = {
  val underlying: Expr[U] = e.toExpr(x)
  '{f($underlying)}
}

inline def mcr: Any = ${mcrImpl}
def mcrImpl given QuoteContext: Expr[Any] = {
  val x = '{1}
  g(x)
}

Aux trick comes from Shapeless 2 and was used to bypass the limitations of Scala 2, where it was impossible to refer to a path-dependent type of a sibling argument from the same argument list.

[nicolasstucki]

The error is correct. You cannot refer to a path in another stage (e.i. a term prefix in another stage).

As far as I understand the Aux pattern is a workaround for Scala2 limitations that we do not have anymore. @milessabin is that correct? Or am I missing some use cases?

[milessabin]

There are still situations where using an aux type as an abbreviation for a complex refinement makes sense.

For the most part the non-sugar uses of aux types can be replaced by intra-parameter list path dependencies.

I'm not confident enough to be able to say that that exhausts all the possible uses for aux types though.

[anatoliykmetyuk]

@nicolasstucki do you think it is possible to capture the type somehow (similarly to the aux pattern) in a type variable under the hood, and then substitute in place of the prefix based reference? Essentially making the compiler do the aux pattern for the user?

[anatoliykmetyuk]

I think we should really try to teach the compiler this trick. This limitation seems to have a chain reaction.

E.g. to implement Liftable derivation, I need zip on tuples with precise types. However, if I do it the easy way, with path-dependent types, I won't be able to use this operation in macros. Good that I control the implementation of the operation and can build it with macros in mind: #7057.

However, if I'm the user of the standard library, not its developer, I won't be able to use an op implemented with path-dependent types in my macros.

If Shapeless 2 was written in Scala 3 with path-dependent types instead of the Aux pattern, using it from macros would present serious difficulties. You would need to constantly make sure the values returned by Shapeless 2 operations do not end up in Exprs.

[nicolasstucki]

Aren't those the patterns that become trivial with white box inline?

[anatoliykmetyuk]

I am not sure I understand what you mean here

[anatoliykmetyuk]

Can you show an example?

[nicolasstucki]

#7057 (comment)

[anatoliykmetyuk]

That one is not related to this issue. The example in question is very specific to our use case of compiler development and is not supposed to be used by the end users.

The point of type safety is to ensure the correctness of the program. As library developers, we can sacrifice internal type safety for user-friendly API and marginal performance gains. By making this decision, we consciously complicate lives for ourselves for the better end-user experience.

However, that's not how you should write Scala – or any other language with a good-enough type system and a compiler that verifies programs using that type system. We should not do that either – the current tuple API implementation is suboptimal. We should have both type safety, performance and a user-friendly API. The reason why we can't have them all right now is that the match types and GADT constraints are not powerful enough and that the tail operation on tuples has linear complexity. The answer is to work on lifting the above constraints, not to justify the type-unsafe style by them.

[milessabin]

@anatoliykmetyuk see #7078 ... I think you might be running into the same issue.