Why is Expr[A] => A not supported during compile-time?

[Kalin-Rudnicki]

I was just able to write and validate a macro that is able to generate an Expr[RegularExpression]. I then tried to write a macro which would be able to combine multiple of these RegularExpressions at compile time into an Either[Failure, Success], and then return an Expr[Success], but was unable because of the nature of passing an A to a macro requires it to become an Expr[A] in the impl, and there seems to be no way to go from Expr[A] to A.

I understand that it must be an extremely complex problem, but I am also confused why this is not allowed. There is one point in my previously mentioned (working) macro impl, where I am able to do

RegularExpression.parse(Source(regString, trA.show.some))

here, RegularExpression.parse is a non-trivial function which utilizes:

• classes/functions in the same file
• classes/functions in other files (same module) : Source
• classes/functions in other files (different module) : .some from cats
• there are also other classes/functions which are required in those other places, and they are all pulled in and used successfully, all at compile-time

Given that that works, why is it not possible to do something like:

'{ RegularExpression.parse(Source(${ Expr(regString) }, ${ Expr(trA.show) }.some)) }.evaluateAtCompileTime

I imagine that when RegularExpression.parse is called in the first example above, all the compiler knows about there is an AST, which is essentially the same as an Expr, right? So, why is it supported that raw code (which is basically just an AST) using non-trivial classes and functions can pre-compile these non-trivial classes and functions at compile-time, but doing the same exact thing with an Expr is not supported?

Here is the whole macro for context:

  inline def forToken[A <: Token]: RegularExpression = ${ forTokenImpl[A] }

  private def forTokenImpl[A <: Token](using quotes: Quotes, tpe: Type[A]): Expr[RegularExpression] = {
    import quotes.reflect.*

    val trA = TypeRepr.of[A]
    val trRegex = TypeRepr.of[regex]

    val regString: String =
      trA.typeSymbol.getAnnotation(trRegex.typeSymbol) match {
        case Some(Apply(_, Select(Apply(_, Literal(StringConstant(str)) :: Nil), _) :: Nil)) => str

        case None => report.errorAndAbort(s"Missing ${trRegex.show} annotation for token ${trA.show}")
        case _    => report.errorAndAbort(s"unexpected failed regex derivation for ${trA.show}")
      }

    def convertEitherChar(chars: Either[Char, (Char, Char)]): Expr[RegularExpression.CharClass] = chars match
      case Left(char)                => '{ RegularExpression.CharClass.inclusive(${ Expr(char) }) }
      case Right((minChar, maxChar)) => '{ RegularExpression.CharClass.inclusiveRange(${ Expr(minChar) }, ${ Expr(maxChar) }) }

    def makeCharClass(groupedChars: List[Either[Char, (Char, Char)]]): Expr[RegularExpression.CharClass] =
      groupedChars match {
        case head :: tail =>
          tail.foldLeft(convertEitherChar(head)) { (acc, either) => '{ ${ acc } | ${ convertEitherChar(either) } } }
        case Nil =>
          '{ RegularExpression.CharClass.inclusive() }
      }

    def makeExpr(reg: RegularExpression): Expr[RegularExpression] =
      reg match {
        case CharClass(InfiniteSet.Inclusive(explicit)) => makeCharClass(explicit.groupChars)
        case CharClass(InfiniteSet.Exclusive(explicit)) => '{ ${ makeCharClass(explicit.groupChars) }.~ }
        case Group(NonEmptyList(head, tail))            => '{ RegularExpression.Group(${ makeExpr(head) }, ${ Varargs(tail.map(makeExpr)) }*) }
        case Repeat(reg, min, max)                      => '{ RegularExpression.Repeat(${ makeExpr(reg) }, ${ Expr(min) }, ${ Expr(max) }) }
        case Sequence(elems)                            => '{ RegularExpression.Sequence(${ Varargs(elems.map(makeExpr)) }*) }
      }

    RegularExpression.parse(Source(regString, trA.show.some)) match {
      case Right(value) => makeExpr(value)
      case Left(value)  => report.errorAndAbort(value.toString)
    }
  }

TLDR:
It makes total sense to me why I need to define makeExpr here, as the generated code cant really just contain a pre-compiled object (although that'd be cool if it could), but I dont see why the first example below is allowed, by the second one isnt.

RegularExpression.parse(Source(regString, trA.show.some))

'{ RegularExpression.parse(Source(${ Expr(regString) }, ${ Expr(trA.show) }.some)) }.evaluateAtCompileTime

In the following example:

  inline def compileTimePrintAndReturn[A](inline a: A): A = ${ compileTimePrintAndReturnImpl('{ a }) }

  private def compileTimePrintAndReturnImpl[A](a: Expr[A])(using quotes: Quotes, tpe: Type[A]): Expr[A] = {
    import quotes.reflect.*

    report.warning(a.show)

    a
  }

println(TmpShow.compileTimePrintAndReturn(RegularExpression.Sequence("abc")))

// printed in warning at compile time
 slyce.parse.RegularExpression.Sequence.apply("abc")

// printed during run time
Sequence(List(Inclusive('a'), Inclusive('b'), Inclusive('c')))

I don't understand how the Expr could have the same exact information as if you to were write it within the macro, and its not allowed, but if you write it within the macro, not in an Expr, it is allowed. I have very little knowledge of what the compiler is doing here, other than observing what is or is not allowed, but this seems a little unfortunate, and would be really nice to have.

[bishabosha]

You can convert Expr[A] to A using the FromExpr type class and there are examples here: macro tutorial and api docs

[Kalin-Rudnicki]

Thank you for pointing this out, but I think this would not be sufficient. It is my understanding that you would need to match on every possible AST in order to eval the code, which is impossible to do, and can only cover a few obvious cases.

[Kalin-Rudnicki]

For example, here are just a few options of what that could all look like, there are many other built-in functions to my RegularExpression class, and this doesn't take into account that:

• the user of the lib could define there own helper functions for creating a RegularExpression
• its possible to reference something like MyConsts.abc, but I believe this would be impossible to extract using FromExpr

  RegularExpression.CharClass.inclusive('a', 'b', 'c')
  RegularExpression.CharClass.inclusiveRange('a', 'z')
  RegularExpression.CharClass.exclusive('a', 'b', 'c')
  RegularExpression.CharClass.exclusiveRange('a', 'z')
  RegularExpression.CharClass(InfiniteSet('a', 'b', 'c'))
  RegularExpression.CharClass(InfiniteSet('a', 'b', 'c').~)
  RegularExpression.CharClass(InfiniteSet('a', 'b') | InfiniteSet('c', 'd'))
  RegularExpression.CharClass.inclusive(MyConsts.abc)

  RegularExpression.Sequence(
    RegularExpression.CharClass.inclusive('a'),
    RegularExpression.CharClass.inclusive('b'),
    RegularExpression.CharClass.inclusive('c'),
  )

  RegularExpression.CharClass.inclusive('a') >>
    RegularExpression.CharClass.inclusive('b') >>
    RegularExpression.CharClass.inclusive('c')

Making exhaustive matching impossible.
But, if you were to reference MyConsts.abc in code in a macro, like RegularExpression.CharClass.inclusive(MyConsts.abc), this would work just fine, hence my point of: it seems possible for the macro to support evaluating an Expr in all cases (with obvious limitations on infinite loops of evaluation and such). Even if it couldnt call any code in the same module, that would be better than nothing at all. But in the case where you write RegularExpression.parse(Source(regString, trA.show.some)), this is referencing all sorts of different things in the same + other modules, so that seems possible to handle anyway.

Again, just playing devils advocate based on my observations 😄

[bishabosha]

What you have demonstrated with your examples are possible to solve with recursion, for arbitrary blocks and side effects etc then what you are looking for is a complete general purpose interpreter of arbitrary Trees which is very complex - or you need scala3-staging library which will actually compile the quote to Java bytecode and run it

[Kalin-Rudnicki]

I was able to get this to work with scala3-staging, but the issue is that is at runtime. Why not allow this at compile-time as well? 😄

If the consumer of the library depicted above was to define a sort of:

def modifyRegex(regex: RegularExpression): RegularExpression = ???

and passed an expr using that to the macro, theres no way it could figure that out.

Again, I dont have a good understanding of what the compiler is doing, but it already handles loading arbitrary trees defined as code in the macro body, why not arbitrary trees in an Expr? I guess the one big difference is that the code defined in the body needs to exist when the macro is compiled, where as an arbitrary Expr, the Expr wouldnt be evaluated until the macro is called (potentially in a downstream library). Not sure if that makes it impossible ☹️

IMO, it would be a tremendous improvement to scala to allow this.

[Kalin-Rudnicki]

Is there any advice from someone who is familiar with the scala-3 compiler of where I would look to potentially try to implement this?

[bishabosha]

Scala 3 contribution guide is at https://dotty.epfl.ch/docs/contributing/index.html

[bishabosha]

but I really must say that this job is not trivial