nicolasstucki/Quote Scopes.md

## Quote Scopes.md

      
    Raw
  

              Quote Scopes.md
            
          
    This is an overview/discussion on the current problems with quotes and splices and a potential solution that would also make them fully compatible with TASTy reflect (not seal/unsleal).
Current state

In this section, we will have an overview of how quotations scopes work and interact with the low level tasty API.
We have four basic concepts

Expr[T]: Represents an expression of type T. It is a wrapper around the AST of the expression.
Type[T]: Represents the type T. It is a wrapper around the AST containing the type.
QuoteContext: Materialization of the current scope of expression. It also contains the tasty API.
Reflection: Typed AST based API (not statically typed).

trait Expr[+T]
trait Type[T <: AnyKind]
trait QuoteConext {
  val tasty: Reflection
}
trait Reflection {
  type Tree
  type Term <: Tree
  type If <: Term
  ...
}
Quotes and splices

A quoted expression of the for '{...} is a value of type Expr[T] that represents the code within the quotes.
Expressions can be interpolated using the splice $ (like in strings), the difference is that both the code in the quotes and in the splice are typed pieces of code. These pieces of code will not execute at the same moments in time (and maybe not in the same machine), therefore values can only be accesses referenced if they are in the same quotation level.
Every quote will require a QuoteContext which denotes the surrounding piece of code where this particular expression will be used.
On the other hand, a splice will give a new QuoteContext which represents the scope within the splice.
One could imagine that quotes an are typed using a desugaring to the following functions:
def quote[T](given qctx: QuoteContext)(code: T): Expr[T] = ...
def splice[T](code: QuoteContext => Expr[T]): T = ...
given qctx as QuoteContext = ...
'{ foo($bar) }
// is equivalent to
quote(foo(splice(bar)))
// which is could be typed as
quote(foo(splice((using qctx2) => bar(using qctx))))(using qctx)
This version has a major limitation, qctx and qctx2 are unrelated.
Therefore qctx.tasty.Tree and qctx2.tasty.Tree are aslo unrelated.
def f(using qctx: QuoteContext): Expr[Any] =
  import qctx.tasty._
  def f(t: Tee): Tree = ...
  '{ ... ${ /*(using qctx2) => */... f(tree/*: qctx2.tasty.Tree*/) ... } }
To fix this we added the QuoteContext.Nested
trait QuoteConext { self =>
  val tasty: Reflection
  type Nested = QuoteScope {
    val tasty: self.type
  }
}
qctx2: qctx.Nested provides a distinct QuoteContext from qctx but both qctx.tasty and qctx2.tasty are the same.
def quote[T](given qctx: QuoteContext)(code: T): Expr[T] = ...
def splice[T](given qctx: QuoteContext)(code: qctx.Nested => Expr[T]): T = ...
Note that we allow trees from outside the quote to be used inside the splice and trees defined inside the splice to be used outside the splice.
We chose this to give more flexibility to the tasty API at the cost potential values used outside of their scope.
If we wanted, to only allow trees defined outside of the quote to be used inside but not the other way around we could just redefine the nested context to type Nested = QuoteScope { val tasty >: self.type }
Expression scope safety

By accident, we made the tasty API safer than the Expr scope wise.
If we have two unrelated and incompatible QuoteContext it is impossible to use the wrong tree, but is it possible to use the wrong expressions.
val qctx1: QuoteContext = ...
val qctx2: QuoteContext = ...

val tree1: qctx1.tasty.Tree = ...
val tree2: qctx2.tasty.Tree = tree1 // compile-time error

val expr1: Expr[Any] = 
  given QuoteContext = qctx1
  '{...}
val expr2: Expr[Any] = 
  given QuoteContext = qctx2
  '{ ... $expr1 ... } // runtime exception
A more common mistake and easy mistake to do with expressions is to let an expression escape from the scope where it is defined.
In this scenario, there are two QuoteContext that are related but one has access to more local variables.
def f(using qxtx: QuoteContext): Expr[Any] = 
  var e: Expr[Any] = null
  '{ val a: Int = 3; ${ e = 'a; 'a} }
  e
Here a an expression that contained a reference to a escapes the scope where a is defined and we will never be able to use this expression without cousing an unsoundness.
Fixing scope soundness

The way we used Nested for tasty can also be used on Expr and Type if we scope them correctly.
Instead of having a global Expr/Type we can define them inside the QuoteContext and adapt Nested.
To highlight the difference, let's call this variant QuoteScope.
trait QuoteScope { self =>
  type Expr[+T]
  type Type[T <: AnyKind]
  val tasty: Reflection
  type Nested = QuoteScope {
    type Expr[+T] >: self.Expr[T]
    type Type[T <: AnyKind] >: self.Type[T]
    val tasty: self.type
  }
}
Just like the nested tasty we add a relation between the self and Nested.
In this case, it is a subtype relationship because we want to ensure that no expression can be used outside the scope where it is defined.
But we still allow expressions defined outside to be used within a splice.
With a QuoteScope we need to change slightly the way we write programs.
// from the current syntax
def f(e: Expr[Any])(using qctx: QuoteContext): Expr[Any] = ....
def g(using qctx: QuoteContext)(t: qctx.tasty.Tree): qctx.tasty.Tree = ....

// to the following syntax
def f(using s: QuoteScope)(e: s.Expr[Any]): s.Expr[Any] = ....
def g(using s: QuoteScope)(t: s.tasty.Tree): s.tasty.Tree = ....
Differences

(+) Scope safety soundness
(+) Homogenouous interface (quotes/tasty)
(-) Syntactic overhead for writing code with only quotes and splices

Backwards compatibility

It looks like it is possible to add QuoteScope while still supporting QuoteContext as it is.
trait QuoteContext extends QuoteScope { self =>
  type Expr[+T] = scala.quoted.Expr[T]
  type Type[T <: AnyKind] = scala.quoted.Type[T]
}
Then we can add a temporary unsafe implicit conversion form QuoteScope to QuoteContext, QuoteScope.Expr to quoted.Expr and QuoteScope.Type to quoted.Type.
These conversions could be unimported.
Improving TASTy/quotes interop

If we only have QuoteScope, we can make expressions compatible with tasty trees.
This implies representing the expressions directly as a tasty.Term which would remove the overhead of the wrapper and allow mixing Expr and Terms together.
trait QuoteScope { self =>
  type Expr[+T] <: tasty.Term
  type Type[T <: AnyKind] <: tasty.Type
  val tasty: Reflection
  type Nested = QuoteScope {
    type Expr[+T] >: self.Expr[T] <: tasty.Term
    type Type[T <: AnyKind] >: self.Type[T] <: tasty.Type
    val tasty: self.type
  }
}
Here, an expression is a subtype of Term that knows it's type statically and is an expression (i.e. it's type is not a MethodicType).
Therefore the concept of unseal  becomes a no-op and is completely redundant.
(expr: Expr[T]) match
  case e: tasty.If => // e: Expr[T] & tasty.If
In addition to not needing unsealing, the static type knowledge can be retained (in some cases) when working with ASTs.
If one has a Term or Tree and want to type it as an Expr we first need to check if it is a valid expression.
This can be done by checking if the Tree is a term and that it does not have a MethodicType.
Once this is done we know that we have an Expr[Any].
If we have scala/scala3#7555 we could also soundly check that this expression has a particular type.
(t: Tree) match 
  case e: Expr[Int] => // matches only if `t` is an expression of type `Int` (using a given TypeTest from #7555)
Having this enables us to also use quoted paterns to match trees directly.
(t: Tree) match 
  case '{ if $c then $t else $e } => 
Conclusion

Making Expr and Type path-dependent is a delicate subject as at first glance the programming experience seems to be harder.
But by making it path-dependent we can improve on usability in an unprecedented way as it allows for simplifications and proper unification of concepts.
Differences

(+) Static scope safety soundness for expressions
(+) Homogenouous interface (quotes/tasty)
(+) Zero overhead Expr and Type
(+) Mixing directly Expr/Type with tasty.Tree/tasty.Type
(+) No need for seal/unsleal
(+) Can use quoted patterns to match on Trees
(-) Syntactic overhead for writing code with only quotes and splices (same overhead that is already present with tasty)