Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Def macros: macro expansion

Def macros: macro expansion

Macro expansion is part of typechecking. If a formalization of the full Scala type system existed, it would include macro expansion in its typing rules. Since such a formalization doesn't exist, we describe macro expansion in an informal operational way.

Def macros are split into two groups based on how they interact with typechecking. Whitebox macros not only perform tree rewriting, but can also influence implicit search and type inference as described below. Blackbox macros only do tree rewriting, so the typechecker can view them as black boxes, which is how they got their name.

The property of a macro being whitebox or blackbox is called boxity and is expressed in the signature of its macro impl. Boxity is recognized by the Scala compiler since v2.11. In Scala 2.10, all macros behave like whitebox macros.

Expansion of whitebox and blackbox macros works very similarly. Unless stated otherwise, the description of the expansion pipeline applies to both kinds of def macros, regardless of their boxity. We will explicitly highlight the situations when boxity changes how things work inside the typechecker.

Expansion pipeline

The typechecker performs macro expansion when it encounters applications of macro defs. This can happen both when these applications are written manually by the programmer, and when they are synthesized by the compiler, e.g. inserted as implicit arguments or implicit conversions.

Sometimes, the compiler does speculative typechecking, e.g. to figure out whether a certain desugaring is applicable or not. Such situations also trigger macro expansion, with the notable exception of implicit search. When a macro application is typechecked in the capacity of an implicit candidate, its treatment depends on its boxity as described in "Effects on implicit search".

When the typechecker encounters a method application, it starts an involved process that consists in typechecking the method reference, optional overload resolution, typechecking the arguments, optional inference of implicit arguments and optional inference of type arguments. Macro expansion usually happens only after all these steps are finished so that the macro impl can work with a consistent and comprehensive representation of the macro application.

Blackbox macros always work like this. Whitebox macros can also be expanded when type inference gets stuck and cannot infer some or all of the type arguments for the macro application as explained in "Effects on type inference".

As a result of the decision to typecheck the method reference and its arguments before macro expansion, expansions work from inside out. This means that enclosing macro applications always expand after enclosed macro applications that may be present in their prefixes or arguments. Consequently, macro expansions always see their prefixes and arguments fully expanded.

During macro expansion, a macro application is destructured and the macro engine obtains term and type arguments for the corresponding macro impl. Together with the context that wraps an implementation of the scala.reflect API and provides some additional functionality these arguments are passed to the macro impl.

A full name of the macro impl is obtained from the macro def and is then used to dynamically load the enclosing class using JVM reflection facilities (the Scala compiler executes on the JVM, so we also use the JVM to run macro impls). After the class is loaded, the compiler invokes the method that contains the compiled bytecode of the macro impl. Despite being one of the original design goals, unrestricted code execution can have adverse effects, e.g. slowdowns or freezes of the compiler, so this is something that we may improve in the future.

All macro expansions in the same compilation run share the same JVM class loader, which means that they share global mutable state. Controlling the scope of side effects while simultaneously providing a way for macros to communicate with each other is another important element of our future work.

A macro impl invocation can finish in three possible ways: 1) normal return that carries a macro expansion, 2) an intentional abort via c.abort, 3) an unhandled exception. In the first case, expansion continues. Otherwise, a compilation error is emitted and expansion terminates.

Upon successful completion of a macro impl invocation, the resulting macro expansion undergoes a typecheck against the return type of the macro def to ensure that it's safe to integrate into the program being compiled. This typecheck can lead to recursive macro expansions, which can overflow compiler stack if the recursion goes too deep or doesn't terminate. This is an obvious robustness hole that we would like to address in the future.

Typecheck errors in the expansion become full-fledged compilation errors. This means that macro users can sometimes receive errors in terms of generated code, which may lead to usability problems.

Finally, a macro expansion that has successfully passed the typecheck replaces the macro application in the compiler AST. Further typechecking and subsequent compiler phases will work on the macro expansion instead of the original macro application.

If the macro expansion has a type that is more specific than the type of the original macro application, it creates a tricky situation. On the one hand, there's a temptation to use the more specific type, e.g. for return type inference of an enclosing method or for type argument inference of an enclosing method call. On the other hand, such macro expansions go beyond what the macro def signature advertises, which may create problems with code comprehension and IDE support (while macro applications that have the advertised type can be treated as regular method applications by the IDEs, macro application that refine the advertised type require dedicated IDE support for def macros).

This situation was the original motivation for the split between whitebox and blackbox macros. We decided that for whitebox macros the typechecker is allowed to make use of more specific type of macro expansions. However, blackbox expansions must have the exact type that is advertised by their corresponding macro def. Internally, this is implemented by automatically upcasting macro expansions to advertised return types.

To put it in a nutshell, macro expansion in our design is a complicated process tightly coupled with typechecking. On the one hand, this significantly complicates reasoning about macro expansion. On the other hand, this enables unique techniques, and at the time of writing one of such techniques is a cornerstone of the open-source Scala community.

Effects on implicit search

Implicit search is a subsystem of the typechecker that is activated when a method application lacks implicit arguments or when an implicit conversion is required to coerce a term to its expected type.

When starting implicit search, the typechecker creates a list of implicit candidates, i.e. implicit vals and defs that are available in scope. Next, these candidates are speculatively typechecked to validate the fact that they fit the parameters of the search. Finally, the remaining candidates are compared with each other according to the implicit ranking algorithm, and the best one is selected as the search result. If no candidates are applicable, or there are multiple applicable candidates with the same rank, implicit search returns an error.

Since implicit search involves typechecking, it can be affected by macro expansion. In Scala 2.10, we allowed macro expansion during validation of implicit candidates. Therefore, implicit macros were able to dynamically influence implicit search. For example, an implicit macro could decide that it is unfit for a particular implicit search and voluntarily abort the expansion, removing itself from the list of candidates.

We have found that such macro-based shenanigans significantly complicate implicit search, which was already pretty complicated prior to introduction of macros. Understanding the scope of available implicits, keeping track of nested implicit searches and backtracks - that was already hard without the necessity to take macro expansions into account.

Therefore, since Scala 2.11, only whitebox macros are expanded during implicit search. Blackbox macros participate in implicit search only with their signatures, just like regular methods, and their expansion happens only after implicit search selects them.

Effects on type inference

When an application of a polymorphic method is missing type arguments - regardless of whether this method is a regular def or a macro def - the typechecker tries to infer the missing arguments. We refer curious readers to Hubert Plociniczak's monograph for details about Scala type inference, and here we provide just a brief overview.

During type inference, the typechecker collects constraints on missing type arguments from bounds of type parameters, from types of term arguments, and even from results of implicit search (because Scala supports an analogue of functional dependencies). One can view these constraints as a system of inequalities where unknown type arguments are represented as type variables and order is imposed by the subtyping relation.

After collecting constraints, the typechecker starts a step-by-step process that, on each step, tries to apply a certain transformation to inequalities, creating an equivalent, yet supposedly simpler system of inequalities. The goal of type inference is to transform the original inequalities to equalities that represent a unique solution of the original system.

Most of the time, type inference succeeds. In that case, missing type arguments are inferred to the types represented by the solution.

However, sometimes type inference fails. For example, when a type parameter T is phantom, i.e. unused in the term parameters of the method, its only entry in the system of inequalities will be L <: T <: U, where L and U are its lower and upper bound respectively. If L != U, this inequality doesn't have a unique solution, and that means a failure of type inference.

When type inference fails, i.e. when it is unable to take any more transformation steps and its working state still contains some inequalities, the typechecker breaks the stalemate. It takes all yet uninferred type arguments, i.e. those whose variables are still represented by inequalities, and forcibly minimizes them, i.e. equates them to their lower bounds. This produces a result where some type arguments are inferred precisely, and some are replaced with seemingly arbitrary types. For instance, unconstrained type parameters are inferred to Nothing, which is a common source of confusion for Scala beginners.

Ever since def macros were introduced, we have been wondering how to use them to allow library authors to customize type inference. After many failed attempts, we found a solution.

If type inference for a macro application gets stuck, the typechecker snapshots its current system of inequalities and produces a partial solution. This solution includes all type arguments that have already been inferred as well as synthetic types that stand for yet uninferred type arguments and are bounded according to the corresponding inequalities. Afterwards, the typechecker performs macro expansion using the partial solution as type arguments for the macro application.

Since macros applications that get this special treatment from the typechecker cannot be viewed as black boxes, partial type inference is only enabled for whitebox macros. Blackbox macros, much like regular methods, have their uninferred type arguments forcibly minimized as described above.

Despite looking quite exotic, this trick plays a key role in the technique of implicit materialization Whitebox implicit macros using this technique can make the typechecker infer unusually precise types, enabling advanced type-level programming.

Owner

xeno-by commented Aug 21, 2016

In order to centralize the discussion, post your questions, feedback and ideas to http://gitter.im/scalameta/sips.

Owner

xeno-by commented Sep 9, 2016

I'd like to ask everyone to use the gitter link above for discussion. I don't get notifications about comments, so it is possible that I won't notice your feedback in a timely manner.

balanka commented Jan 21, 2017

Is the SIP implemented and included thecurrent scala meta ( scala 2.11.8)?
I would line to use the new style macro expansion/inlining but stumple on how to pass and apply type parameters
http://stackoverflow.com/questions/41664590/passing-type-parameter-to-scala-meta-macro-annotations
Any comment would be appreciated

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment