Add quasi-quotation, courtesy of Geoffrey Mainland

This patch adds quasi-quotation, as described in
  "Nice to be Quoted: Quasiquoting for Haskell"
	(Geoffrey Mainland, Haskell Workshop 2007)
Implemented by Geoffrey and polished by Simon.

Overview
~~~~~~~~
The syntax for quasiquotation is very similar to the existing
Template haskell syntax:
	[$q| stuff |]
where 'q' is the "quoter".  This syntax differs from the paper, by using
a '$' rather than ':', to avoid clashing with parallel array comprehensions.
 
The "quoter" is a value of type Language.Haskell.TH.Quote.QuasiQuoter, which
contains two functions for quoting expressions and patterns, respectively.
 
     quote = Language.Haskell.TH.Quote.QuasiQuoter quoteExp quotePat
 
     quoteExp :: String -> Language.Haskell.TH.ExpQ
     quotePat :: String -> Language.Haskell.TH.PatQ

TEXT is passed unmodified to the quoter. The context of the
quasiquotation statement determines which of the two quoters is
called: if the quasiquotation occurs in an expression context,
quoteExp is called, and if it occurs in a pattern context, quotePat
is called.

The result of running the quoter on its arguments is spliced into
the program using Template Haskell's existing mechanisms for
splicing in code. Note that although Template Haskell does not
support pattern brackets, with this patch binding occurrences of
variables in patterns are supported. Quoters must also obey the same
stage restrictions as Template Haskell; in particular, in this
example quote may not be defined in the module where it is used as a
quasiquoter, but must be imported from another module.

Points to notice
~~~~~~~~~~~~~~~~
* The whole thing is enabled with the flag -XQuasiQuotes

* There is an accompanying patch to the template-haskell library. This
  involves one interface change:
	currentModule :: Q String
  is replaced by
	location :: Q Loc
  where Loc is a data type defined in TH.Syntax thus:
      data Loc
        = Loc { loc_filename :: String
	      , loc_package  :: String
	      , loc_module   :: String
	      , loc_start    :: CharPos
	      , loc_end      :: CharPos }

      type CharPos = (Int, Int)	-- Line and character position
 
  So you get a lot more info from 'location' than from 'currentModule'.
  The location you get is the location of the splice.
  
  This works in Template Haskell too of course, and lets a TH program
  generate much better error messages.

* There's also a new module in the template-haskell package called 
  Language.Haskell.TH.Quote, which contains support code for the
  quasi-quoting feature.

* Quasi-quote splices are run *in the renamer* because they can build 
  *patterns* and hence the renamer needs to see the output of running the
  splice.  This involved a bit of rejigging in the renamer, especially
  concerning the reporting of duplicate or shadowed names.

  (In fact I found and removed a few calls to checkDupNames in RnSource 
  that are redundant, becuase top-level duplicate decls are handled in
  RnNames.)

2 files changed, 144 insertions, 0 deletions

diff --git a/docs/users_guide/flags.xml b/docs/users_guide/flags.xml
index 344230262d..166ff113d0 100644
--- a/docs/users_guide/flags.xml
+++ b/docs/users_guide/flags.xml
@@ -743,6 +743,12 @@
 	      <entry><option>-XNoTemplateHaskell</option></entry>
 	    </row>
 	    <row>
+	      <entry><option>-XQuasiQuotes</option></entry>
+	      <entry>Enable <link linkend="th-quasiquotation">quasiquotation</link>.</entry>
+	      <entry>dynamic</entry>
+	      <entry><option>-XNoQuasiQuotes</option></entry>
+	    </row>
+	    <row>
 	      <entry><option>-XBangPatterns</option></entry>
 	      <entry>Enable <link linkend="bang-patterns">bang patterns</link>.</entry>
 	      <entry>dynamic</entry>
diff --git a/docs/users_guide/glasgow_exts.xml b/docs/users_guide/glasgow_exts.xml
index 9b4dc588d3..f22e6c9edf 100644
--- a/docs/users_guide/glasgow_exts.xml
+++ b/docs/users_guide/glasgow_exts.xml
@@ -290,6 +290,17 @@ documentation</ulink> describes all the libraries that come with GHC.
 	</listitem>
       </varlistentry>
 
+      <varlistentry>
+	<term><option>-XQuasiQuotes</option></term>
+	<listitem>
+	  <para>Enables quasiquotation (see <xref
+	  linkend="th-quasiquotation"/>).</para>
+
+	  <para>Syntax stolen:
+	  <literal>[:<replaceable>varid</replaceable>|</literal>.</para>
+	</listitem>
+      </varlistentry>
+
     </variablelist>
   </sect1>
 
@@ -4985,6 +4996,15 @@ Wiki page</ulink>.
 		  </itemizedlist></para></listitem>
 
 	      <listitem><para>
+		  A quasi-quotation can appear in either a pattern context or an
+		  expression context and is also written in Oxford brackets:
+		  <itemizedlist>
+		    <listitem><para> <literal>[:<replaceable>varid</replaceable>| ... |]</literal>,
+                        where the "..." is an arbitrary string; a full description of the
+			quasi-quotation facility is given in <xref linkend="th-quasiquotation"/>.</para></listitem>
+		  </itemizedlist></para></listitem>
+
+	      <listitem><para>
 		  A name can be quoted with either one or two prefix single quotes:
 		  <itemizedlist>
 		    <listitem><para> <literal>'f</literal> has type <literal>Name</literal>, and names the function <literal>f</literal>.
@@ -5158,6 +5178,124 @@ The basic idea is to compile the program twice:</para>
 </orderedlist>
 </sect2>
 
+<sect2 id="th-quasiquotation">  <title> Template Haskell Quasi-quotation </title>
+<para>Quasi-quotation allows patterns and expressions to be written using
+programmer-defined concrete syntax; the motivation behind the extension and
+several examples are documented in
+"<ulink url="http://www.eecs.harvard.edu/~mainland/ghc-quasiquoting/">Why It's
+Nice to be Quoted: Quasiquoting for Haskell</ulink>" (Proc Haskell Workshop
+2007). The example below shows how to write a quasiquoter for a simple
+expression language.</para>
+
+<para>
+In the example, the quasiquoter <literal>expr</literal> is bound to a value of
+type <literal>Language.Haskell.TH.Quote.QuasiQuoter</literal> which contains two
+functions for quoting expressions and patterns, respectively. The first argument
+to each quoter is the (arbitrary) string enclosed in the Oxford brackets. The
+context of the quasi-quotation statement determines which of the two parsers is
+called: if the quasi-quotation occurs in an expression context, the expression
+parser is called, and if it occurs in a pattern context, the pattern parser is
+called.</para>
+
+<para>
+Note that in the example we make use of an antiquoted
+variable <literal>n</literal>, indicated by the syntax <literal>'int:n</literal>
+(this syntax for anti-quotation was defined by the parser's
+author, <emphasis>not</emphasis> by GHC). This binds <literal>n</literal> to the
+integer value argument of the constructor <literal>IntExpr</literal> when
+pattern matching. Please see the referenced paper for further details regarding
+anti-quotation as well as the description of a technique that uses SYB to
+leverage a single parser of type <literal>String -> a</literal> to generate both
+an expression parser that returns a value of type <literal>Q Exp</literal> and a
+pattern parser that returns a value of type <literal>Q Pat</literal>.
+</para>
+
+<para>In general, a quasi-quote has the form
+<literal>[$<replaceable>quoter</replaceable>| <replaceable>string</replaceable> |]</literal>.
+The <replaceable>quoter</replaceable> must be the name of an imported quoter; it
+cannot be an arbitrary expression.  The quoted <replaceable>string</replaceable> 
+can be arbitrary, and may contain newlines.
+</para>
+<para>
+Quasiquoters must obey the same stage restrictions as Template Haskell, e.g., in
+the example, <literal>expr</literal> cannot be defined
+in <literal>Main.hs</literal> where it is used, but must be imported.
+</para>
+
+<programlisting>
+
+{- Main.hs -}
+module Main where
+
+import Expr
+
+main :: IO ()
+main = do { print $ eval [$expr|1 + 2|]
+          ; case IntExpr 1 of
+              { [$expr|'int:n|] -> print n
+              ;  _              -> return ()
+              }
+          }
+
+
+{- Expr.hs -}
+module Expr where
+
+import qualified Language.Haskell.TH as TH
+import Language.Haskell.TH.Quasi
+
+data Expr  =  IntExpr Integer
+           |  AntiIntExpr String
+           |  BinopExpr BinOp Expr Expr
+           |  AntiExpr String
+    deriving(Show, Typeable, Data)
+
+data BinOp  =  AddOp
+            |  SubOp
+            |  MulOp
+            |  DivOp
+    deriving(Show, Typeable, Data)
+
+eval :: Expr -> Integer
+eval (IntExpr n)        = n
+eval (BinopExpr op x y) = (opToFun op) (eval x) (eval y)
+  where
+    opToFun AddOp = (+)
+    opToFun SubOp = (-)
+    opToFun MulOp = (*)
+    opToFun DivOp = div
+
+expr = QuasiQuoter parseExprExp parseExprPat
+
+-- Parse an Expr, returning its representation as
+-- either a Q Exp or a Q Pat. See the referenced paper
+-- for how to use SYB to do this by writing a single
+-- parser of type String -> Expr instead of two
+-- separate parsers.
+
+parseExprExp :: String -> Q Exp
+parseExprExp ...
+
+parseExprPat :: String -> Q Pat
+parseExprPat ...
+</programlisting>
+
+<para>Now run the compiler:
+</para>
+<programlisting>
+$ ghc --make -XQuasiQuotes Main.hs -o main
+</programlisting>
+
+<para>Run "main" and here is your output:</para>
+
+<programlisting>
+$ ./main
+3
+1
+</programlisting>
+
+</sect2>
+
 </sect1>
 
 <!-- ===================== Arrow notation ===================  -->