Genesis and motivation
Step 1: ASTs and parsing

Before we define our Joy quotation we need to implement syntax trees and
a parser for the language.

The subset that we'll be working with contains: integer literals,
boolean literals, names (which represent calls to predefined
operators) and quotations. Plus there is also an extra Program
node that represents whole code snippet.

In an imaginary Joy repl those could be used in the following way:

    > 1 1 +
    2

    > 1 2 =
    false

    > true false or
    true

    > 2 2 2 * *
    8

    > [1 2 3 + +] i
    6

    > [1 2 3] first
    1

    > [1 2 3] rest
    [2 3]

    > 2 [0 >] [true] [false] ifte
    true

    > [1 2 3] [1 +] map
    [2 3 4]

    > [1 2 3 4] [2 rem 0 =] filter
    [2 4]

Parser is implemented via Scala's parser combinators but just about any
parsing library would do. All you really need is a String => Joy mapping.
Step 2: pretty printing

Default pretty printing for case classes doesn't really scale well for
syntax trees as for any non-trivial program you'll have hard time
reading it. To fix it we need to implement a simple pretty printer.
Step 3: simple runtime quotation

As a first approximation we can define a Joy quotation as just an alias
to Joy.parse. This won't be very useful in practice because such
quotation would re-parse code snippet on every invocation at runtime.

Current impelmentation also doesn't yet support any form of $unquoting
as it just unconditionally uses the first part out of the string context.
We could have implemented it first for runtime case but we'll skip this
step and move straight to compile-time.
Step 4: moving parsing to compile-time

We use macros to remove all of the runtime parsing overhead. Apart from
moving code to the macro implementation we also need to implement
Joy tree to Scala tree conversion (called lifting). This is needed
because macro has to return a tree that represents a value rather
than a value itself.

It's important to highlight that we opt in to use whitebox macros rather
than blackbox ones as it will give as ability to refine return type of
the quotation to specific subtypes of Joy tree.

For example in a few steps we'll make following work:

    scala> j"42"
    res0: joy.Joy.Int = 42

Here res0 is Joy.Int rather than just Joy thanks to whiteboxity.
Step 5: flattening programs into single nodes

So far our quote just returned result as given by a parser but this has
one unpleasant inconvenience: everything is unconditionally wrapped into
Program node even if there is just one simple primitive inside of the
quotation. To fix this we introduce flatten function that takes care of
this.
Step 6: unquoting

The problem with our current quotation is that it doesn't provide any
means to compose bigger ASTs from smaller chunks.

The solution is unquoting. Whenever user writes $expr in a quotation it
should be interpreted as a structural substitution of expr value in that
position.

To implement this we need to parse all string parts rather than just the
first one. To fill links between them we insert special mangled names
(which are constructed and reconstructed via Hole object). These names
will let us correlate location of trees that correspond to $unquotes and
replace them with corresponding argument during lifting.
Step 7: lifting

Even though our quote already allows us to compose Joy trees via
unquoting there is still a need to use regular ast constructors to
convert from scala values (e.g. ints) into joy values.

To improve this we introduce automatic typeclass-based conversion of
scala values into joy trees. Whenever a non-joy value of type T is
unquoted it will be wrapped into implicitly discovered Lift[T]
conversion.

By default we provide instances for Int, Symbol and List[T] where T is
itself liftable. Additionally we include dummy identity instance for
Joy type itself to allow unquoting of List[Joy] values.

Apart from introduction of type class and code that does implicit search
for corresponding implicit value we also need to change signature of the
j method. One might expect that just replacing Joy* with Any* would do
the trick but it's not that simple.

Due to unfortunate optimization in typechecker, expressions with expected
type Any get special treatment and might not get precise inferred types
attributed to them. Instead they will have .tpe set to Any making them
opaque from macro standpoint.

To avoid this we introduce dummy type argument that forces typechecker
to do full type inference and set precise type to .tpe field of the
argument tree.
Step 8: splicing

Another issue with current unquoting mechanism is that it doesn't
provide any way to put arbitrary number of subtrees into another tree.

And that's exactly why we add splicing: a way to flatten any iterables
of trees into quotation.
Step 9: splicing + lifting

Feature interaction between the two requires some extra care.
Here we add support for splicing of iterables of liftable values.
Step 10: splicing programs

Another way to make splicing more flexible is to make Joy.Quote and
Joy.Program iterable. This automatically adds support for splicing them
via ..$
Step 11: basic pattern matching

Our quotation so far only worked in expression mode and failed to
compile if it was used as a pattern.

Now we augment the definition of the interpolator with pattern
matching-friendly unapply entry point which allows our macro to expand
in pattern position.

Apart from second entry point we also need to include a different
wrapping strategy in pattern position which is caused by the interaction
between macros and pattern matching.

Interestingly most of the lifting code can stay the same due to the fact
that untyped trees for case class creation and pattern matching are the
same but there is a change we need to make to make list lifting
work.

Previous calls to :: and :+ methods needs to be replaced with
explicit call to :: list constructor and a utility joy.` :+ ` which works
similarly to :: but only for appends. We can't use default :+ object
because it doesn't have .apply method and won't work in both contexts.
Step 12: pattern unquoting and splicing

Now that we've got simple patterns working we need to take care of
unquoting and splicing.

First implmentation of arg(i) in expression mode could just returns args(i)
but the situation is different here. Due to the fact that macros in
pattern mode don't rewrite original pattern but just augment it with
generated extractor we need to generate a bit more code.

To implement this we create a new indexed variable binding for each argument in
arg(i) and than reconstruct a tuple of all values on the right hand
side wrapped into Some. For example following pattern:

    case j"$a $b +" =>

Will have following generated extactor:

    new {
      def unapply(input: Joy) = input match {
        case Joy.Program((x1 @ _) :: (x2 @ _) :: Joy.Name("+") :: Nil) =>
          Some((x1, x2)
        case _ =>
          None
      }
    }.unapply(...)

If there is no arguments then right hand side of the generated
cases will contain true for the first case and false for the other one.

Luckily due to usage of :: constructor and ` :+ ` extractor we
automatically get support for splicing without any additional
changes.
Step 13: pattern unlifting

Similarly to lifting in expression mode we introduce typeclass-
based unlifting to cover extraction of values out of quotation.

We rely on user-annotated ascriptions to figure out which type to lookup
for. Again due to limitations of current pattern mode we need to do some
extra work to get the information we need.

To inspect subpatterns we need to pass args.head to special
c.internal.subpatterns method. It will give us a list of untyped
subpatterns which we can use to extract user-defined ascriptions.
Step 14: pattern unlifting + splicing

Here comes the last feature interaction intersection between pattern
mode, unlifting and splicing.

One might naturally expect following to work:

     scala> val j"..${xs : List[Int]} + +" = j"1 2 3 + +"

Here we want to extact a number of elements out a program and then
unlift each of them with Unlift[Int] instance.

To implement this we need to instantiate helper elementwise extractors
that will extract List[T] out of List[Joy] based on Unlift[T] instance.
For example for aforementioned snippet we'll generate following
extractor:

    new {
      def unapply(input: Joy) = {
        val unlift$macro$1 =
          new _root_.joy.Joy.Unlift.Elementwise[Int](Joy.this.Unlift.unliftInt);
        input match {
          case _root_.joy.Joy.Program(_root_.joy.` :+ `(_root_.joy.` :+ `(unlift$macro$1((x0 @ _)), _root_.joy.Joy.Name("+")), _root_.joy.Joy.Name("+"))) => _root_.scala.Some(x0)
          case _ => _root_.scala.None
        }
      }
    }.unapply(...)

Where unlift$macro$1 is generated instance of helper elementwise
extactor.

Unfortunately this also entails some complications all over the codebase
as we'll a way to propagate additions to a list of unlift helper
throughout our lifting pipeline. Also due to change of return type
we won't be defining Liftable instances but just implementing lifting as
a chain of method calls.
Step 15: interpretation

Lastly as a demo of what our quotation can do we implement simple
interpreter for our subset of Joy. Here one can finally experience all
the benefits of quotations as a tool to ease complex rewriting on syntax
trees.