15

I'm getting started with scala macros, they're awesome, but I'm running into the difference between typed (aka typechecked) and untyped Trees.

For example, you can't call c.eval with a typechecked Tree for some reason. I can't find documentation on this 'typechecked' in the scala macros documentation (I know they're still working on that, this might be something that needs to be added some day).

What does it mean for a Tree to be typechecked? Why are they so different that apparently c.eval can't deal with typechecked Trees (the inverse would make more sense to me).

I guess this is probably compiler 101, but I didn't take that course :( Any explanation or pointer to articles/documenation would be appreciated!

Dmytro Mitin
  • 48,194
  • 3
  • 28
  • 66
Jaap
  • 3,081
  • 2
  • 29
  • 50
  • If you've read the first version of my answer, take a look at the update - it contains practical interpretation of the details I provided wrt macro writing. – Eugene Burmako Jan 05 '14 at 18:17

1 Answers1

34

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 :)

Eugene Burmako
  • 13,028
  • 1
  • 46
  • 59
  • 8
    This is a really clear summary of a bunch of stuff I kind of half understood. Thanks, Eugene! – Travis Brown Jan 05 '14 at 18:27
  • Hi @eugene-burmako, can you tell us what the current state of art is??? 2.12 roadmap doesn't mention macro's (since it's focus is java 8). – Jaap Jul 24 '15 at 06:49
  • Soon after writing this post, my priorities were hijacked by dealing with feedback on scala.reflect for the 2.11.0 release. Jan/Feb 2014 was the time when a lot of minor/medium bugs were fixed and a number of important APIs (such as Type.typeArgs or c.internal.enclosingOwner) were introduced. After I emerged from that hacking session, I reevaluated the situation and realized that there was a choice: 1) hack something up for 2.12.x (because of compatibility restrictions, the planned, quite radical changes weren't going to make it in 2.11.x)... – Eugene Burmako Jul 30 '15 at 08:19
  • ...2) start hacking on a new metaprogramming framework (this is what has become known as scala.meta) that would be devoid of these problems by design, and try to release a preview version of that framework by the time 2.12.0 is released. After much deliberation, I decided to fix the problems with scala.reflect at their root and go for #2. This is how scala.meta has been born, and I've been hacking on it ever since. – Eugene Burmako Jul 30 '15 at 08:26
  • tl;dr. The work on the fix described in the answer didn't get very far, and nothing is planned in that department for 2.12.x. I'm pretty confident that scala.meta will fix the underlying problem by not having it in the first place. – Eugene Burmako Jul 30 '15 at 08:30