Scala macros: What is the difference between typed (aka typechecked) and untyped Trees

by

Theoretical part

This is an architectural peculiarity of scalac that started leaking into the public API once we exposed internal compiler data structures in compile-time / runtime reflection in 2.10.

Very roughly speaking, scalac’s frontend consists of a parser and a typer, both of which work with trees and produce trees as their result. However properties of these trees are quite different, which comes from the fact that trees produced by parser are unattributed (having their symbol field set to NoSymbol and their tpe field set to null), whereas trees produced by typer are attributed.

Now you might wonder what difference this can make, because it’s just symbol and tpe, right? However, in scalac it’s more than just that. In order to do its job, typer changes the structure of the ASTs it’s processing, destroying some original trees and producing some synthetic trees. Unfortunately, sometimes these transformations are irreversible, which means that if one typechecks a tree, and then erases all assigned attributes, the resulting tree isn’t going to make sense anymore (https://issues.scala-lang.org/browse/SI-5464).

Allright, but why would one want to erase (or in scalac parlance, reset, as in resetLocalAttrs or resetAllAttrs) attributes of typechecked trees? Well, this necessity stems from another implementation detail – symbols and their owner chains. Just a few days ago I’ve written up some details about that on scala-internals: https://groups.google.com/d/msg/scala-internals/rIyJ4yHdPDU/qS-7DreEbCwJ, but in a nutshell you can’t typecheck a tree in some lexical context and then simply use it in a different lexical context (that’s what is essentially needed for c.eval).

So, to sum it up the state of the art in scalac tree management:

  1. Untyped trees (also known as parser trees or unattributed trees) are observationally different from typed trees (also known as typer trees, typechecked trees or attributed trees)
  2. There are two main differences between these two tree flavors: a) typed trees have symbols and types set by the typechecker, b) typed trees have somewhat different shapes.
  3. Usually, if some compiler API takes a tree, then both untyped and typed trees will do. However in some cases (one of which I outlined above), only untyped or only typed trees are appropriate.
  4. One can go from an untyped tree to a typed tree by calling Context.typecheck (compile-time reflection) or ToolBox.typecheck (runtime reflection), but going back from a typed tree to an untyped tree via resetLocalAttrs or resetAllAttrs is currently unreliable because of https://issues.scala-lang.org/browse/SI-5464.

So, as you can see, our trees are quite capricious, which brings a great deal of complexity into metaprogramming in Scala.

However, good news is that this complexity isn’t dictated by some fundamental good reasons that originate in compiler 101. All the complexity is incidental, and we plan to evict it step by step until it’s all gone. https://groups.google.com/forum/#!topic/scala-internals/TtCTPlj_qcQ (also posted a couple days ago) is the first step in this direction. Stay tuned for other goodies which might also arrive this year!

Practical part

After thoroughly scaring you by elaborating all the details and alluding to mysterious cases when nothing works, I would like to note that usually one doesn’t need to know about this kind of stuff when using macros. Very often both untyped trees (manually constructured ASTs, quasiquotes) and typed trees (macro arguments) work just fine.

In cases, when scalac wants a particular tree flavor, it would either tell you like c.eval or sometimes crash in your face (RefChecks, LambdaLift and GenICode crashes are huge indicators that trees got mixed up during macro expansion – in those cases use resetLocalAttrs as described in https://groups.google.com/forum/#!msg/scala-internals/rIyJ4yHdPDU/qS-7DreEbCwJ). Fixing this is my top priority, and I’m working on it right now. It might so happen that the fixes will make it into 2.11.0, and this answer will become obsolete very soon 🙂

More Related Contents:

  1. Iteration over a sealed trait in Scala?
  2. Weird behavior trying to convert case classes to heterogeneous lists recursively with Shapeless
  3. Scala Macros: Making a Map out of fields of a class in Scala
  4. Method Override with Scala 3 Macros
  5. How to access parameter list of case class in a dotty macro
  6. Static return type of Scala macros
  7. Creating a method definition tree from a method symbol and a body
  8. Howto model named parameters in method invocations with Scala macros?
  9. “dynamically” creating case classes with macros
  10. Getting subclasses of a sealed trait
  11. Scala3: Crafting Types Through Metaprogramming?
  12. Apache Spark – Scala – ReduceByKey – with keys repeating up to twice only
  13. What is the difference between a var and val definition in Scala?
  14. What is the apply function in Scala?
  15. How do I apply the enrich-my-library pattern to Scala collections?
  16. How to import build.gradle into IntelliJ
  17. Scala 2.8 collections design tutorial
  18. Scala classOf for type parameter
  19. val and object inside a scala class?
  20. What are possible reasons for receiving TimeoutException: Futures timed out after [n seconds] when working with Spark [duplicate]
  21. Parsing multiline records in Scala
  22. Create new Dataframe with empty/null field values
  24. Get a TypeTag from a Type?
  25. How to write a proper null-safe coalescing operator in scala?
  26. Can’t access Parent’s Members while dealing with Macro Annotations
  27. Why is join not possible after show operator?
  28. Install sbt on ubuntu [closed]
  29. Insert if not exists in Slick 3.0.0
  30. Difference between two rows in Spark dataframe

Leave a Comment