Proposal: Overloaded Quotes for Template Haskell

[Michael D. Adams]

(This was originally posted to haskell-cafe, but I've since learned
that haskell-libraries is a more appropriate venue.  Apologies for the
resulting cross-post.)

== Description ==

I would like to propose a generalization of the types of quote forms
(i.e. "[| ... |]") and nested splices (i.e. "[| ... $( ... ) ... |]").

Currently quote forms have type "Q Exp" and nested splices expect
their contents to have type "Q Exp".  I propose that quote forms have
type "forall m. Quasi m => m Exp" and nested splices expect a body of
type "m Exp" where the "m" of the nested splice is the same as the "m"
of the quote form that it is inside of.

Top-level splices (i.e. those not inside a "[| ... |]") continue to
expect their body to have type "Q Exp", and do *not* have a
generalized to the type. (Otherwise, the compiler wouldn't know how to
evaluate the monad.  Nested splices do not have this problem as it is
the responsibility of the user code between the splice and its
enclosing quote to determine how to evaluate the monad.)

Note that generalizing the types of quotes in this way is very similar
to the generization of the types of strings that happens with the
"-XOverloadedStrings" flag.  However, unlike with strings which
require an extra class (i.e. "IsString"), I believe generalizing
quotes does not require an extra class.  The already existing "Quasi"
class is sufficient.  An implementation could treat each quote or
nested splice as mere syntactic sugar for an equivalent do-block, then
use the usual type inference.

== Example Use Case ==

I discovered a need for this generalization when writing a Template
Haskell program in which part of it operates in a "StateT S Q a" monad
instead of the usual "Q a" monad.  The "S" type stores the state of a
memoization table which contains code fragments already generated.
Without memoization, the program would loop infinitely when processing
certain recursive structures.

It is fairly easy to declare an instance of "Quasi" for "StateT S Q",
so that is not a problem. In order to keep the code clean, I'd like to
use quotations with splices in them (i.e. [| ... $( ... ) ... |] ) for
expressing the generated code.  However, as quotations and splices are
tied to the "Q" monad, I have to manually write "LamE ... VarP ...
VarE ... etc." instead of using the much nicer quotation syntax.
Without access to the quote syntax, I've had a one-line quotes turn
into a half-a-dozen-line do-blocks.

In this particular program, I can simulate the state monad using an
IORef and lifting IO operations into Q using runIO.  However, this
merely a workaround.

== Open Questions ==

~~ Flags ~~

Generalizing the type of quotes can either be an "always-on" feature
or it could be enabled by a flag (e.g. "-XOverloadedQuotes").

Since "Q" is an instance of "Quasi", we would expect programs that are
type correct without the generalization to also be type correct with
the generalization.  Thus "always-on" would seem to be a backwards
compatible change.

However, while I am not an expert on GHC's type system, I suspect
there are pathological cases where generalizing the types of quotes
would result in the inference system not being able to infer a type
that it would be able to without the generalization.  In addition,
type incorrect programs may yield more confusing type errors.

I don't have a particular position on this question so long as the
generalization is available (even if only by a flag) to those who want
it.  I suspect that, in the interests of design conservatism, having
it as a flag will be the preferred choice.

~~ Quasi-Quotes ~~

The type of quasi-quoters (i.e. "String -> Q Exp") can be generalized
to "forall m. Quasi m => String -> m Exp".  However, this poses a
compatibility program for existing user-written quasi-quoters.  I am
uncertain about the best way to handle this.  It may be best to leave
quasi-quoters without a generalized type unless someone can come up
with a good backwards compatibility story.

== Deadline ==

I propose the usual two week deadline (January 13) for discussion.  If
the overall response is positive, I'll submit a GHC Track ticket.