Can this free-term-variable error (produced at macro expansion) be avoided?

Question

I am developing a DSL and I am getting a "free term" failure while expanding a macro. I would like to know if it can be avoided. I have simplified the problem to the following situation.

Suppose we have this expression:

val list = join {
  0
  1
  2
  3
}
println(list)

where join is a macro whose implementation is:

def join(c: Ctx)(a: c.Expr[Int]): c.Expr[List[Int]] = {
  import c.mirror._
  a.tree match {
    case Block(list, ret) =>
      // c.reify(List(new c.Expr(list(0)).eval, 
      //              new c.Expr(list(1)).eval,
      //              new c.Expr(list(2)).eval) :+ new c.Expr(ret).eval)
      c.reify((for (expr <- list) yield new c.Expr(expr).eval) :+ new c.Expr(ret).eval)
  }
}

The aim of the macro is to join all the elements in the argument block and return them in a single list. Since the contents of the block could be variable, I cannot use the commented reify (which works nice). The uncommented one -with a for comprehension, which generates free terms- throws the message:

"Macro expansion contains free term variable list defined by join in Macros.scala:48:18. Have you forgotten to use eval when splicing this variable into a reifee? If you have troubles tracking free term variables, consider using -Xlog-free-terms"

Is there any way to introduce the for-comprehension (or an iterator or whatever) without getting this error? By the way, I am using 2.10-M3.

Answer 1

The problem is that your code mixes compile-time and runtime concepts.

The "list" variable you're using is a compile-time value (i.e. it is supposed to be iterated during the compile-time), and you're asking reify to retain it till the runtime (by splicing derived values). This cross-stage conundrum leads to creation of a so called free term.

In short, free terms are stubs that refer to the values from earlier stages. For example, the following snippet:

val x = 2
reify(x)

Would be compiled as follows:

val free$x1 = newFreeTerm("x", staticClass("scala.Int").asTypeConstructor, x);
Ident(free$x1)

Clever, huh? The result retains the fact that x is an Ident, preserves its type (compile-time characteristics), but, nevertheless, refers to its value as well (a run-time characteristic). This is made possible by lexical scoping.

But if you try to return this tree from a macro expansion (that is inlined into the call site of a macro), things will blow up. Call site of the macro will most likely not have x in its lexical scope, so it wouldn't be able to refer to the value of x.

What's even worse. If the snippet above is written inside a macro, then x only exists during compile-time, i.e. in the JVM that runs the compiler. But when the compiler terminates, it's gone.

However, the results of macro expansion that contain a reference to x are supposed to be run at runtime (most likely, in a different JVM). To make sense of this, you would need cross-stage persistence, i.e. a capability to somehow serialize arbitrary compile-time values and deserialize them during runtime. I don't know how to do this in a compiled language like Scala.

---

Note that in some cases cross-stage persistence is possible. For example, if x was a field of a static object:

object Foo { val x = 2 }
import Foo._
reify(x)

Then it wouldn't end up as a free term, but would be reified in a straightforward fashion:

Select(Ident(staticModule("Foo")), newTermName("x"))

This is an interesting concept that was also discussed in SPJ's talk at Scala Days 2012: http://skillsmatter.com/podcast/scala/haskell-cloud.

To verify that some expression doesn't contain free terms, in Haskell they add a new built-in primitive to the compiler, the Static type constructor. With macros, we can do this naturally by using reify (which itself is just a macro). See the discussion here: https://groups.google.com/forum/#!topic/scala-internals/-42PWNkQJNA.

---

Okay now we've seen what exactly is the problem with the original code, so how do we make it work?

Unfortunately we'll have to fall back to manual AST construction, because reify has tough time expressing dynamic trees. The ideal use case for reify in macrology is having a static template with the types of the holes known at macro compilation time. Take a step aside - and you'll have to resort to building trees by hand.

Bottom line is that you have to go with the following (works with recently released 2.10.0-M4, see the migration guide at scala-language to see what exactly has changed: http://groups.google.com/group/scala-language/browse_thread/thread/bf079865ad42249c):

import scala.reflect.makro.Context

object Macros {
  def join_impl(c: Context)(a: c.Expr[Int]): c.Expr[List[Int]] = {
    import c.universe._
    import definitions._
    a.tree match {
      case Block(list, ret) =>
        c.Expr((list :+ ret).foldRight(Ident(NilModule): Tree)((el, acc) => 
          Apply(Select(acc, newTermName("$colon$colon")), List(el))))
    }
  }

  def join(a: Int): List[Int] = macro join_impl
}