DAYS 2013

This talk is dedicated to Iain Banks

16 February 1954 - 9 June 2013

What are macros?

Macros are hygenic, compile-time code transformations..

In 2.10, macros are defined as methods which take parameters as ASTs (abstract syntax trees), and return a result as an AST.

What are anonymous functions?

Anonymous functions are values that can be called (like methods). For example:

ns.map((x: Int) => x + 6)
ns.map(x => x + 6)
ns.map(_ + 6)

def plusSix(n: Int): Int = n + 6

ns.map(plusSix)
    

(What's different about the last one?)

What was different?

The last application was equivalent to:

def plusSix(n: Int): Int = n + 6

ns.map(x => plusSix(x))
    

This anonymous function really just wraps a (non-anonymous) method.

What is inlining?

In our case, inlining means rewriting an application with its implementation.

def addOne(n: Int): Int = n + 1
def timesTwo(n: Int): Int = n * 2
def minusThree(n: Int): Int = n - 3

addOne(timesTwo(minusThree(6)))

def allOfIt(n: Int): Int = ((n - 3) * 2) + 1

allOfIt(6)
    

So what does it all mean together?

We want to write methods that accept literal anonymous functions, and inline their implementations using macros.

def normal(n: Int, f: Int => Int): Int = f(n)
normal(6, _ * 3)

def secret(n: Int, f: Int => Int): Int = ???
secret(6, _ * 3) // compiles to 6 * 3
    

What are the limits?

We need a literal anonymous function that "does the work" or else we can't inline properly.

def secret(n: Int, f: Int => Int): Int = ???
def tripled(n: Int): Int = n * 3

secret(6, tripled) // nope!
// compiles to tripled(6), not 6 * 3
    

Why would you want to do this?

There are many totally valid reasons to do something like this!

• Perversity
• Replacement for code generation
• Better specialization
• Premature Optimization
• Solving The Inlining Problem

What does a macro look like?

object Scope {
  def secret(n: Int, f: Int => Int): Int = macro sec

  def sec(c: Context)
         (n: c.Expr[Int],
          f: c.Expr[Int => Int]): c.Expr[Int] = {
    // transform input Exprs into an out Expr
  }
}
    

What does an Expr (AST) look like?

Demo.secret(6, _ * 3)

// becomes (approximately)

Apply( // call Demo.secret method
  Select(Demo, secret),
  List(                   // 2 arguments
    Literal(Constant(6)),
    Function(   // anonymous function
      List(x), // one parameter named x
      Apply(    // call x.+
        Select(x, +),
        List(   // 1 argument: 
          Literal(Constant(3)))))))
    

What does an Expr (AST) look like?

There is a bit more complexity regarding names:

Select(
  This(newTypeName("Demo")),
  newTermName("secret"))

Select(
  Ident(newTermName("x$1")),
  newTermName("$plus"))
    

So what does an inlining transformation look like?

1. Verify arguments are "valid"
2. Inline anonymous function body into tree
3. Inline arguments for parameters
4. Clean up

So what does an inlining transformation look like?

def normal(n: Int, f: Int => Int): Int = f(n)

// user calls the macro, verify args
Demo.secret(6, (x: Int) => x * 3)

// start with f.apply(n)
((x: Int) => x * 3).apply(6)

// remove apply, inline f's body
x * 3

// substitute 6 (argument) for x (parameter)
6 * 3
    

What do you notice about this?

What do you notice about this?

• It looks fiddly
• Between steps 2-4 the tree is invalid
• Clean up was not mentioned
• Scope problems?

How about the actual AST transformations?

Demo.secret(6, (x: Int) => x * 3)
    

How about the actual AST transformations?

Apply(
 Select(This(newTypeName("Demo")), newTermName("secret")),
 List(
  Literal(Constant(6)),
  Function(
   List(ValDef(
     Modifiers(PARAM | SYNTHETIC),
     newTermName("x$1"),
     TypeTree(),
     EmptyTree)),
   Apply(
    Select(Ident(newTermName("x$1")), newTermName("$plus")),
    List(Literal(Constant(3)))))))
    

How about the actual AST transformations?

Apply(
 Select(
  Function(
   List(ValDef(
     Modifiers(PARAM | SYNTHETIC),
     newTermName("x$1"),
     TypeTree(),
     EmptyTree)),
   Apply(
    Select(Ident(newTermName("x$1")), newTermName("$plus")),
    List(Literal(Constant(3))))),
  newTermName("apply")),
 List(Literal(Constant(6))))
    

How about the actual AST transformations?

   Apply(
    Select(Ident(newTermName("x$1")), newTermName("$plus")),
    List(Literal(Constant(3))))
    

How about the actual AST transformations?

   Apply(
    Select(Literal(Constant(6)), newTermName("$plus")),
    List(Literal(Constant(3))))
    

What clean up is necessary?

New trees and fragments need valid owners/types.

Use c.resetAllAttrs to "fix" generated trees.

What are some uses of inlining?

• Looping syntax without indirection cost
• Stream fusion
• Multiple return values
• Building parsers at compile-time

None of these applications are otherwise impossible,
but this strategy can make some approaches more attractive.

What are some problems?

• It's complicated
• Only works with literal values
• Violates intuition
• Requires more/different documentation

Time for a demo!

Do you have questions?

The End