derive-0.1: derive.htm
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<title>Data.Derive: A User Manual</title>
<style type="text/css">
pre {
border: 2px solid gray;
padding: 1px;
padding-left: 5px;
margin-left: 10px;
background-color: #eee;
}
pre.define {
background-color: #ffb;
border-color: #cc0;
}
body {
font-family: sans-serif;
}
h1, h2, h3 {
font-family: serif;
}
h1 {
color: rgb(23,54,93);
border-bottom: 1px solid rgb(79,129,189);
padding-bottom: 2px;
font-variant: small-caps;
text-align: center;
}
a {
color: rgb(54,95,145);
}
h2 {
color: rgb(54,95,145);
}
h3 {
color: rgb(79,129,189);
}
</style>
</head>
<body>
<h1>Data.Derive: A User Manual</h1>
<p style="text-align:right;margin-bottom:25px;">
by <a href="http://www.cs.york.ac.uk/~ndm/">Neil Mitchell</a> & Stefan O'Rear
</p>
<p>
Data.Derive is a library and a tool for deriving instances for Haskell programs. It is designed to work with custom derivations, SYB and Template Haskell mechanisms. The tool requires GHC, but the generated code is portable to all compilers. We see this tool as a competitor to <a href="http://repetae.net/~john/computer/haskell/DrIFT/">DrIFT</a>.
</p>
<p>
This document proceeds as follows:
</p>
<ol>
<li>Obtaining and Installing Data.Derive</li>
<li>Supported Derivations</li>
<li>Using the Derive Program</li>
<li>Using Template Haskell Derivations</li>
<li>Writing a New Derivation</li>
</ol>
<h3>Acknowledgements</h3>
<p>
Thanks to everyone who has submitted patches and given assistance, including: Twan van Laarhoven, Spencer Janssen, Andrea Vezzosi.
Thanks also to Joel Raymont for being the first user of Data.Derive, and generally helping us feel like we weren't wasting our time.
</p>
<h2>Obtaining and Installing Data.Derive</h2>
<p>
Data.Derive is available using <a href="http://darcs.net/">darcs</a>:
</p>
<pre>
darcs get --partial <a href="http://www.cs.york.ac.uk/fp/darcs/derive">http://www.cs.york.ac.uk/fp/darcs/derive</a>
</pre>
<p>
Install the program using the standard sequence of Cabal magic:
</p>
<pre>
runhaskell Setup configure
runhaskell Setup build
runhaskell Setup install
</pre>
<h2>Supported Derivations</h2>
<p>
Data.Derive is not limited to any prebuild set of derivations, see later for how to add your own. Out of the box, we provide instances for the following libraries.
</p>
<h3>Prelude</h3>
<p>
These are the standard classes defined in the <a href="http://haskell.org/onlinereport/derived.html">Haskell Report</a>, some of which the existing <tt>deriving</tt> works upon.
</p>
<ul>
<li><b>Eq</b></li>
<li><b>Ord</b></li>
<li><b>Bounded</b></li>
<li><b>Enum</b></li>
<li><b>EnumCyclic</b></li>
<li><b>Functor</b></li>
<li><b>Read</b></li>
<li><b>Show</b></li>
</ul>
<h3>Base</h3>
<p>
These are instances from the base libraries, but which aren't in the Haskell 98 report.
</p>
<ul>
<li><b>Monoid</b></li>
<li><b>NFData</b></li>
</ul>
<h3>Query</h3>
<p>
DrIFT defines a number of useful query functions, which are technically not instances, but can be derived in a similar manner. We support some of these as from DrIFT, some with modifications, and some which are brand new:
</p>
<ul>
<li><b>From</b></li>
<li><b>Has</b></li>
<li><b>Is</b></li>
<li><b>Set</b></li>
<li><b>LazySet</b></li>
</ul>
<h3>Generics</h3>
<p>
We support the two classes from the first <a href="http://www.cs.vu.nl/boilerplate/">Scrap Your Boilerplate</a> paper, and the classes from the <a href="http://www-users.cs.york.ac.uk/~ndm/play/">Play library</a>:
</p>
<ul>
<li><b>Typeable</b></li>
<li><b>Data</b></li>
<li><b>Play</b></li>
</ul>
<h3>Binary</h3>
<p>
We support the new <a href="http://www.cse.unsw.edu.au/~dons/binary.html">Binary library</a>, and the <a href="http://www-users.cs.york.ac.uk/~ndm/binarydefer/">BinaryDefer library</a>.
</p>
<ul>
<li><b>Binary</b></li>
<li><b>BinaryDefer</b></li>
</ul>
<h3>Testing</h3>
<p>
We support both <a href="http://www.cs.chalmers.se/~rjmh/QuickCheck/">QuickCheck</a> and the <a href="http://www.cs.york.ac.uk/fp/darcs/smallcheck/">SmallCheck library</a>:
</p>
<ul>
<li><b>Arbitrary</b></li>
<li><b>Serial</b></li>
</ul>
<h3>Classhacking</h3>
<p>
From the <a href="http://homepages.cwi.nl/~ralf/HList">HList library</a>:
</p>
<ul>
<li><b>TTypeable</b></li>
</ul>
<h3>Missing</h3>
<p>
These derivations are in DrIFT, but not in Derive. If you need them, let us know and we'll implement them.
</p>
<ul>
<li><b>ATermConvertible</b> - encode terms in the ATerm format.</li>
<li><b>BitsBinary</b> - efficient binary encoding of terms.</li>
<li><b>FunctorM</b> - derive reasonable fmapM implementation.</li>
<li><b>GhcBinary</b> - byte sized binary encoding of terms.</li>
<li><b>HFoldable</b> - Strafunski hfoldr.</li>
<li><b>Haskell2Xml</b> - encode terms as XML (HaXml<=1.13).</li>
<li><b>Observable</b> - HOOD observable.</li>
<li><b>RMapM</b> - derive reasonable rmapM implementation.</li>
<li><b>Term</b> - Strafunski representation via Dynamic.</li>
<li><b>XmlContent</b> - encode terms as XML (HaXml>=1.14).</li>
</ul>
<h2>Using the Derive program</h2>
<p>
Let's imagine we've defined a data type:
</p>
<pre>
data Color = RGB Int Int Int
| CMYK Int Int Int Int
deriving (Eq, Show)
</pre>
<p>
Now we wish to extend this to derive <tt>Binary</tt> and change to defining <tt>Eq</tt> using our library. To do this we simply add to the <tt>deriving</tt> clause.
</p>
<pre>
data Color = RGB Int Int Int
| CMYK Int Int Int Int
deriving (Show {-! Eq, Binary !-})
</pre>
<p>
Now running <tt>derive</tt> on the program containing this code will generate appropriate instances. How do you combine these instances back into the code? There are various mechanisms supported.
</p>
<h3>Appending to the module</h3>
<p>
One way is to append the text to the bottom of the module, this can be done by passing the <tt>--append</tt> flag. If this is done, Derive will generate the required instances and place them at the bottom of the file, along with a checksum. Do not modify these instances.
</p>
<h3>Using CPP</h3>
<p>
One way is to use CPP. Ensure your compiler is set up for compiling with the C Pre Processor. For example:
</p>
<pre>
{-# OPTIONS_GHC -cpp #-}
{-# OPTIONS_DERIVE --output=file.h #-}
module ModuleName where
#include "file.h"
</pre>
<h3>Side-by-side Modules</h3>
<p>
If you had Colour.Type, and wished to place the Binary instance in Colour.Binary, this can be done with:
</p>
<pre>
{-# OPTIONS_DERIVE --output=Binary.hs --module=Colour.Binary --import #-}
</pre>
<p>
Here you ask for the output to go to a particular file, give a specific module name and import this module. This will only work if the data structure is exported non-abstractly.
</p>
<h2>Using Template Haskell Derivations</h2>
<p>
One of Derive's major advantages over DrIFT is support for the <a href="http://www.haskell.org/th/">Template Haskell</a> (henceforth abbreviated "TH") system. This allows Derive to be invoked automatically during the compilation process, and (because it occurs with full access to the renamer tables) transparently supports deriving across module boundaries. The main disadvantage of TH-based deriving is that it is only portable to compilers that support TH; currently that is GHC only.
</p>
<p>
To use the TH deriving system, with the same example as before:
</p>
<pre>
import Data.Derive.TH
import Data.Derive.Eq
import Data.Derive.Binary
data Color = RGB Int Int Int
| CMYK Int Int Int Int
deriving (Show)
$( derive makeEq ''Color )
$( derive makeBinary ''Color )
</pre>
<p>
Note two things. First, we need to import the derivations. By convention, a derivation for a class <tt>FooBar</tt> is located in module <tt>Data.Derive.FooBar</tt> (nota bene: this need not be in package "derive") and is exported with the name <tt>makeFooBar</tt>. Secondly, we need to tell the compiler to insert the instance using the TH <em>splice</em> construct, <tt>$( ... )</tt> (the spaces are optional). The splice causes the compiler to run the function <tt>derive</tt> (exported from <tt>Data.Derive.TH</tt>), passing arguments <tt>makeFooBar</tt> and <tt>''Color</tt>. The second argument deserves more explanation; it is a quoted symbol, somewhat like a quoted symbol in Lisp and with deliberately similar syntax. (Two apostrophes are used to specify that this name is to be resolved as a type constructor; just <tt>'Color</tt> would look for a <i>data</i> constructor named <tt>Color</tt>.)
</p>
<h2>Writing a New Derivation</h2>
<p>
There are two methods for writing a new derivation, guessing or coding. The guessing method is substantially easier if it will work for you, but is limited to derivations with the following properties:
</p>
<ul>
<li>Inductive - each derivation must be similar to the previous one. <tt>Binary</tt> does not have this property as a 1 item derivation does not have a tag, but a 2 item derivation does.</li>
<li>Not inductive on the type - it must be an instance for the constructors, not for the type. <tt>Typeable</tt> violates this property by inducting on the free variables in the data type.</li>
<li>Not type based - the derivation must not change based on the types of the fields. <tt>Play</tt> and <tt>Functor</tt> both behave differently given differently typed fields.</li>
<li>Not record based - the derivation must not change on record fields. <tt>Show</tt> outputs the fields, so this is not allowed.</li>
</ul>
<p>
If however your instance does meet these properties, you can use derivation by guess. Many instances do meet these conditions: <tt>Eq</tt>, <tt>Ord</tt>, <tt>Data</tt>, <tt>Serial</tt> etc.
</p>
<h3>Derivation by Guess</h3>
<p>
This is a unique feature of this library. You simply give an instance, and the program guesses what your instance derivation code should look like, and returns it. You paste the code in, and you have written an instance without learning any of the types or functions required to construct the abstract syntax. For example, lets take the <tt>Data</tt> instance. I recommend reading through the source in <tt>Data.Derive.Data</tt> first, then matching it to this description.
</p>
<p>
First copy the Data file, changing all the obvious bits (<tt>makeData</tt> etc) to whatever name you want. Next change the example to match your requirements. You basically define an instance for <tt>DataName</tt> which is defined as:
</p>
<pre>
data DataName a = CtorZero
| CtorOne a
| CtorTwo a a
| CtorTwo' a a
</pre>
<p>
Try and make your declaration as inductive as possible. Use <tt>x1</tt> etc for variable names within a constructor match. Place all the constructors in the correct order. If you would be unable to see an obvious pattern, then the guesser won't either. Once we have written our sample instance:
</p>
<pre>
> <b>ghci Data.Derive.Data -DGUESS</b>
___ ___ _
/ _ \ /\ /\/ __(_)
/ /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98.
/ /_\\/ __ / /___| | http://www.haskell.org/ghc/
\____/\/ /_/\____/|_| Type :? for help.
Loading package base ... linking ... done.
Ok, modules loaded: Data.Derive.Data, Data.DeriveGuess, Language.Haskell.TH.All,
Language.Haskell.TH.SYB, Language.Haskell.TH.Data, Language.Haskell.TH.FixedPpr
, Language.Haskell.TH.Helper, Language.Haskell.TH.Peephole.
*Data.Derive.Data> <b>guess example</b>
makeData = Derivation data' "Data"
data' dat = [instance_context ["Data","Typeable"] "Data" dat [(FunD (mkName
"gfoldl") ((map (\(ctorInd,ctor) -> (Clause [(VarP (mkName "k")),(VarP (
mkName "r")),(ConP (mkName ("" ++ ctorName ctor)) ((map (\field -> (VarP (
mkName ("x" ++ show field)))) (id [1..ctorArity ctor]))++[]))] (NormalB (
foldr1With (VarE (mkName "k")) ((map (\field -> (VarE (mkName ("x" ++ show
field)))) (reverse [1..ctorArity ctor]))++[(AppE (VarE (mkName "r")) (ConE
(mkName ("" ++ ctorName ctor))))]++[]))) [])) (id (zip [0..] (dataCtors dat
))))++[]))]]
</pre>
<p>
And thats it. The block of code spewed out will generate <tt>Data</tt> instances, we just paste it back into the file.
</p>
<p>
There is lots of clever stuff, induction hypotheses etc going on behind all this. If you have an instance which you think should be inferable, but isn't, then <a href="http://www-users.cs.york.ac.uk/~ndm/contact/">let me know</a>.
</p>
<h3>Derivation by Coding</h3>
<p>
We use the Template Haskell data types extensively, for examples take a look at <tt>Binary</tt> and <tt>Functor</tt>. Its not particularly hard, but it is harder than just having them guessed.
</p>
</body>
</html>