[SOLVED] Dotty Macros - Lifting Expressions: how to set this up?

I am trying to replicate de example here:

https://dotty.epfl.ch/docs/reference/metaprogramming/macros.html#lifting-expressions

I have the following code that will not compile:

  enum Exp {
    case Num(n: Int)
    case Var(x: String)
    case Add(e1: Exp, e2: Exp)
    case Sub(e: Exp, in: Exp)
    case Let(x: String, e: Exp, in: Exp)
  }

  object Exp {

    private def compileImpl(e: Exp, env: Map[String, Expr[Int]])(using QuoteContext): Expr[Int] = e match {
      case Num(n) =>
        Expr(n)
      case Add(e1, e2) =>
      '{ ${ compileImpl(e1, env) } + ${ compileImpl(e2, env) } }
      case Var(x) =>
        env(x)
      case Let(x, e, body) =>
      '{ val y = ${ compileImpl(e, env) }; ${ compileImpl(body, env + (x -> 'y)) } }
    }

    inline def compile(inline expr: Exp, env: Map[String, Expr[Int]]): Unit = {
      ${compileImpl(expr, Map[String, Expr[Int]]())}
    }

  }

And I get the errors:

[error] -- Error: /home/hmf/IdeaProjects/snol/tutorial/src/dotty/Macros.scala:69:48 ----
[error] 69 |      ${compileImpl(expr, Map[String, Expr[Int]]())}
[error]    |                          ^^^^^^^^^^^^^^^^^^^^^^^^
[error]    |                          Malformed macro parameter
[error]    |
[error]    |                          Parameters may only be:
[error]    |                           * Quoted parameters or fields
[error]    |                           * Literal values of primitive types
[error] -- Error: /home/hmf/IdeaProjects/snol/tutorial/src/dotty/Macros.scala:69:20 ----
[error] 69 |      ${compileImpl(expr, Map[String, Expr[Int]]())}
[error]    |                    ^^^^
[error]    |                    access to value expr from wrong staging level:
[error]    |                     - the definition is at level 0,
[error]    |                     - but the access is at level -1.
[error] two errors found

Those errors make sense, so how should this be implemented?

TIA

The macro runs at compile-time. It doesn’t see values of type Exp, it sees an AST of type Expr[Exp]. You need to make both e and env Exprs and then use quoted matches (e.g. case '{ Num($n) }.

@szeiger Unfortunately that change alone won’t work. More concretely the env map should be used during the macro execution. In other words I need to access its value in the macro. I found that their are the:

     val environment = env.unlift
     val environment = env.unliftOrError

I tried that and get:

[error] -- Error: /home/hmf/IdeaProjects/snol/tutorial/src/dotty/Macros.scala:99:41 ----
[error] 99 |      val environment = env.unliftOrError
[error]    |                                         ^
[error]    |no implicit argument of type quoted.Unliftable[U] was found for parameter unlift of method unliftOrError in class Expr
[error] one error found
1 targets failed
tutorial.compile Compilation failed

So I assume that we may only unlift primitives - which makes sense because they are static and available at compile time.

Ok, so I move on with the next experiment:

  enum Exp {
    case Num(n: Int)
    case Var(x: String)
    case Add(e1: Exp, e2: Exp)
    case Let(x: String, e: Exp, in: Exp)
  }

  object Exp {

    private def compileImpl(e: Expr[Exp], env: Map[String, Expr[Int]])(using QuoteContext): Expr[Int] = {
      println("222222222222222")
      e match {
        case '{Num($n)} =>
          println(s"Num = ${n.show}")
          n
        case '{Add($e1, $e2)} =>
          println(s"Add")
          '{ ${ compileImpl(e1, env) } + ${ compileImpl(e2, env) } }
        case '{Var($x)} =>
          println(s"Var")
          val xs = x.unliftOrError
          env(xs)
        case '{Let($x, $e, $body)} =>
          println(s"Let")
          val xs = x.unliftOrError
          '{ val y = ${ compileImpl(e, env) }; ${ compileImpl(body, env + (xs -> 'y)) } }
      }
    }

    private def compileUnlift(e: Expr[Exp], env: Expr[Map[String, Expr[Int]]])(using QuoteContext): Expr[Int] = {
      val environment = Map[String, Expr[Int]]()
      compileImpl(e, environment)
    }

    inline def compile(inline expr: Exp, inline env: Map[String, Expr[Int]]): Unit = {
      ${compileUnlift('expr, 'env)}
    }

When I try it on:

    val exp = Add(Add(Num(2), Var("x")), Num(4))
    val letExp = Let("x", Num(3), exp)
    compile(letExp, Map())

I get :

[info] Compiling 2 Scala sources to /home/hmf/IdeaProjects/snol/out/tutorial/compile/dest/classes ...
111111111111111
222222222222222
[error] -- Error: /home/hmf/IdeaProjects/snol/tutorial/src/ad/Main.scala:58:11 ---------
[error] 58 |    compile(letExp, Map())
[error]    |    ^^^^^^^^^^^^^^^^^^^^^^
[error]    |    Exception occurred while executing macro expansion.
[error]    |    scala.MatchError: '{ ... } (of class scala.internal.quoted.Expr)
[error]    |
[error]    | This location contains code that was inlined from Main.scala:58
[warn] -- [E129] Potential Issue Warning: /home/hmf/IdeaProjects/snol/tutorial/src/ad/Main.scala:58:11 
[warn] 58 |    compile(letExp, Map())
[warn]    |    ^^^^^^^^^^^^^^^^^^^^^^
[warn]    |A pure expression does nothing in statement position; you may be omitting necessary parentheses
[warn]    | This location contains code that was inlined from Macros.scala:105
[warn] one warning found
[error] one error found

So the macros starts off ok (prints 1s and 2s), but one of the matches is breaking. Placing the prints in each case does not show anything. I think I have covered all 4 cases.

Any tips on how to determine which case is breaking. Commenting these one at a time did not help.

TIA

More concretely the env map should be used during the macro execution

In general you don’t have that map during macro execution. You can only cover specific cases like literals (e.g. a Map("foo" -> 42) expression that gets inlined into the call site). You could implement your own Unliftable instance for map literals or match the supported forms directly. If it’s not statically available you can either report an error or defer the decision until runtime (by doing only a partial compilation).

I think I have covered all 4 cases.

You only covered the cases that can be statically determined. The reference to exp in letExp already breaks it. I think this specific case of referencing a statically known val should be doable at the TASTy reflection level (e.unseal.underlying.seal.cast[Exp]).

You’ll want to handle unsupported trees (again, either reporting an error or reverting to partial compilation) with a default case. For debug purposes it’s useful to print out both the Expr and the TASTy reflection extractors:

case e =>
  Reporting.throwError(s"Unsupported term ${e.show} (${e.unseal.showExtractors})", e)

Appreciate the help. Clearly I do not understand what I am doing.

Ok, I think I understand. You are saying that:

    val exp = Add(Add(Num(2), Var("x")), Num(4))
    val letExp = Let("x", Num(3), exp)

cannot be statically matched because exp is an expression that is assigned elsewhere. If so then the following is doable, correct?

    val exp = Let("x", Num(3), Add(Add(Num(2), Var("x")), Num(4)))

Still no success. So I did the following (code at the end):

  • Kept only Var in the enum
  • Added a default match with the report you showed

and I get:

[warn] -- Deprecation Warning: /home/hmf/IdeaProjects/snol/tutorial/src/dotty/Macros.scala:131:10 
snip....
[warn] one warning found
111111111111111
222222222222222
e = exp
[error] -- Error: /home/hmf/IdeaProjects/snol/tutorial/src/ad/Main.scala:61:21 ---------
[error] 61 |    println(compileX(exp, Map()))
[error]    |                     ^^^
[error]    |                 Unsupported term exp (Inlined(None, Nil, Ident("exp")))
[error]    | This location contains code that was inlined from Main.scala:61
[warn] one warning found
[error] one error found

So I get a tuple of 3 elements. Not what I expected. I am using inline, so why do I not get the Exp?

I tried this with:

val expOk = exp.unseal.underlying.seal.cast[Exp]
println(s"expOk = ${expOk.show}")

and got the output:

expOk = dotty.Macros.Exp.Var.apply("x")

which seems promising. But then

          compileImpl(expOk, env)

causes the macro compilation to loop. I tried to match that Var.apply in several way but failed. Any suggestions?

TIA


Code:

  enum Exp {
    case Var(x: String)
  }

  object Exp {

    inline private def compileImpl(inline e: Expr[Exp], env: Map[String, Expr[Int]])(using QuoteContext): Expr[Int] = {
      println("222222222222222")
      println(s"e = ${e.show}")
      e match {
        case '{Var(_:String):Exp} =>
          println("Var")
        case e =>
          val expOk = exp.unseal.underlying.seal.cast[Exp]
          println(s"expOk = ${expOk.show}")
          //compileImpl('{expOk}, env)
          Reporting.throwError(s"Unsupported term ${e.show} (${e.unseal.showExtractors})", e)
      }
      '{0}
    }

    private def compileUnlift(e: Expr[Exp], env: Expr[Map[String, Expr[Int]]])(using QuoteContext): Expr[Int] = {
      println("111111111111111")
      val environment = Map[String, Expr[Int]]()
      compileImpl(e, environment)
    }

    inline def compileX(inline expr: Exp, inline env: Map[String, Expr[Int]]): Int = {
      ${compileUnlift('expr, 'env)}
    }

  }

Apparently _ is treated as an identifier in quoted patterns. This probably qualifies as a bug. You need to extract wildcards into variables: case '{Var($s:String):Exp} instead of case '{Var(_:String):Exp}. (And case '{Var($_:String):Exp} even crashes the compiler.)

It looks like underlying can’t resolve local references outside the quote. I thought this should be possible but I don’t see any other way of doing it in the reflection API.

You don’t have to worry about Inlined at the quoted level. The extractors will automatically skip over it. It becomes important when you’re matching with TASTy reflection (in which case underlying or underlyingArgument will remove it).

Thanks for the help. Going to see if I can find some examples/tests in the Dotty source code. If that does not help, I think I will report this.

For the record, in the code I present above I use:

Which causes problems. See this issue. So if you remove that, underlying works correctly. There may be one or more problems to work out as is shown in this issue, were we have the code that works.

Not sure there’s still interest in this question, but below is how I got this to work.

My initial reference was actually Macros | Scala 3 Language Reference | Scala Documentation but didn’t see enough detail to make the example work, not at least in a straightforward way. This post and exchanges helped (thanks!) but also some experimentation.

Two source files, to separate the macro definition from the use:

Exp.scala:

import scala.quoted.*
import scala.compiletime.{error, codeOf}

enum Exp:
  case Num(n: Int)
  case Plus(e1: Exp, e2: Exp)
  case Var(x: String)
  case Let(x: String, e: Exp, in: Exp)

import Exp.*

inline def compileExp(inline e: Exp): Int = ${
  applyImpl('e)
}

def applyImpl(e: Expr[Exp])(using Quotes): Expr[Int] =
  def rec(e: Expr[Exp], env: Map[String, Int]): Expr[Int] =
    e match
      case '{ Num($n) } =>
        n

      case '{ Plus($e1, $e2) } =>
        '{ ${ rec(e1, env) } + ${ rec(e2, env) } }

      case '{ Var($x) } =>
        Expr(env(x.valueOrError))

      case '{ Let($x, $e, $body) } =>
        val y    = rec(e, env)
        val env2 = env + (x.valueOrError -> y.valueOrError)
        rec(body, env2)

  rec(e, Map())

inline def assertExp(inline expected: Int, inline compiled: Int): Unit =
  if expected != compiled then 
      error("oops: expected=" +codeOf(expected)+ " != compiled=" + codeOf(compiled))

ExpUse.scala:

import Exp.*

@main def main: Unit =
  assertExp(42, compileExp(Num(42)) )
  assertExp(42, compileExp(Num(42)) )
  assertExp(42, compileExp(Let("x", Num(42), Var("x"))) )
  assertExp(42, compileExp(Plus(Num(21), Plus(Num(8), Num(13)))) )
  assertExp(42, compileExp(Let("x", Num(3), Plus(Plus(Num(18), Var("x")), Num(21)))) )
  assertExp(41, compileExp(Let("x", Num(42), Var("x"))) )  // oops: expected=41 != compiled=42:Int

Note the assertExp method, just, as you can see, to make assertions at compile time to verify the resulting evaluated expressions.

1 Like