Safe Haskell  SafeInferred 

Option specifications using continuations with a changing answer type.
Based on
www.is.ocha.ac.jp/~asai/papers/tr082.pdf
with additional inspiration provided by
http://okmij.org/ftp/typedformatting/FPrintScan.html#DSLFIn
which shows how the same format specifiers can be used for both sprintf
and
sscanf
.
The OptSpec
type corresponds to the format specifiers for the sprintf and
sscanf functions, which I called ounparse
and oparse
here; they no
longer work on String
s but instead on any list (the intention is, of
course, that this is a list of flags).
As explained in the original paper by Kenichi Asai, we cannot use
Cont
, even with the recent additions of the
shift
and reset
combinators, since Cont
requires that the answer type remains the same over the whole computation,
while the trick used here requires that the answer type can change.
Besides parsing and unparsing, the OptSpec
type contains two more members:
odesc
is the list of OptDescr
that getOpt
needs
as input for parsing the command line and for generating the usage help,
while ocheck
takes a list of flags and returns a list of error messages,
which can be used to check for conflicting options.
 data OptSpec d f a b = OptSpec {}
 oid :: OptSpec d f a a
 (^) :: OptSpec d f b c > OptSpec d f a b > OptSpec d f a c
 onormalise :: OptSpec d f [f] b > [f] > [f]
 defaultFlags :: OptSpec d f [f] b > [f]
 oimap :: Iso b c > OptSpec d f a b > OptSpec d f a c
 type PrimOptSpec d f a v = OptSpec d f a (v > a)
 oappend :: PrimOptSpec d f a [v] > PrimOptSpec d f a [v] > PrimOptSpec d f a [v]
 oempty :: PrimOptSpec d f a [v]
 parseFlags :: (forall a. PrimOptSpec d f a v) > [f] > v
Option specifications
data OptSpec d f a b
A type for option specifications.
It consists of four components: a parser, an unparser, a checker, and a list of descriptions.
The parser converts a flag list to some result value. This can never fail:
we demand that primitive parsers are written so that there is always a
default value (use Maybe
with default Nothing
as a last resort).
The unparser does the opposite of the parser: a value is converted back to a flag list.
The checker returns a list of error messages (which should be empty if there are no problems found). This can be used to e.g. check whether there are conflicting flags in the list.
Separating the checker and parser is unusual. The reason for this is that we want to support flags coming from multiple sources, such as the command line or a defaults file. Prioritising these sources is done by concatenating the flag lists in the order of precedence, so that earlier flags win over later ones. That means that when parsing the (final) flag list, conflicting flags are resolved by picking the first flag that matches an option. The checker, on the other hand, can be called for each source separately.
The last component is a list of descriptors for each single switch/flag that the option is made of.
The OptSpec
type is heavily parameterized. The type arguments are:
f
 The flag type, such as
DarcsFlag
. d
 A type that describes an single flag, such as
OptDescr
orDarcsOptDescr
. It should be aFunctor
.
Abstracting over these types is not technically necessary: for the intended
application in Darcs, we could as well fix them as
d=
, and DarcsOptDescr
f=
,
saving two type parameters. However, doing that here would only obscure
what's going on, making the code harder to understand, not easier. Besides,
the resulting more general type signatures give us additional guarantees,
known as "free theorems" (free as in beer, not in speak).
DarcsFlag
In contrast, the type parameters
a
,b
 are necessary to make chaining of options a la typed printf/scanf
possible. In a nutshell,
a
is the result type of a function that consumes the result of parsing or unparsing an option, whileb
is the complete type of such a function.
The ounparse
and oparse
members use continuation passing style, which is
the reason for their apparently "inverted" type signature. To understand
them, it helps to look at the type of "primitive" (not yet combined)
options (see PrimOptSpec
below). For a primitive option, b
gets
instantiated to v > a
, where v
is the type of values associated with
the option. The whole option spec then has type
o :: 'OptSpec' d f a (v > a)
so that the oparse
and ounparse
members are instantiated to
ounparse :: forall a. ([f] > a) > (x > a) oparse :: forall a. (x > a) > ([f] > a)
which can be easily seen to be equivalent to
ounparse :: x > [f] oparse :: [f] > x
Chaining such options results in a combined option of type
o1 ^ o2 ^ ... :: OptSpec d f a (v1 > v2 > ... > a)
that is, b
gets instantiated to
v1 > v2 > ... > a
To use such an option (primitive or combined), you pass in the consumer. A typical consumer of option values is a command implementation. Given
cmd :: v1 > v2 > ... > [String] > IO ()
we can parse the flags and pass the results to cmd
:
oparse (o1 ^ o2 ^ ...) cmd flags
OptSpec  

IsoFunctor (OptSpec d f a)  
Monoid (PrimOptSpec d f a [v]) 
Primitive combinators
The type
, together with the operation OptSpec
d f^
and the unit
oid
forms a category. We could express this with an
instanceCategory
(OptSpec
d f) whereid
=oid
(.
) = (^
)
I decided against doing that because I like the id
and .
from the
Prelude.
Proving the category laws is easy because the operation and unit are
implemented independently for each component. This means
is simply the product of four categories, reducing the problem to proving
the laws for each component separately.
OptSpec
d f
odesc
 This is just list concatenation, which is a monoid, and every monoid is a category (by adding two phantom type arguments).
ocheck
 Same here, noting that
([f] >)
is a monoid homomorphism (as expressed by theinstance
in Data.Monoid).Monoid
b =>Monoid
(a > b) oparse
 This can be seen by flipping the arguments (which is a functor
i.e. preserves category laws), so the type becomes
[f] > b > a
, and noting as before that([f] >)
is a monoid homomorphism and thus a functor (by adding two phantom type arguments), reducing the operation to simple function composition. If this rather abstract argument doesn't convince you, do the calculations as an exercise. ounparse
 for this I don't have an easy abstract argument at hand, so I'll do the calculation:
o1 ^ (o2 ^ o3) = definition outer (^) k > o1 (f1 > (o2 ^ o3) (f23 > k (f1 ++ f23))) = definition inner (^) k > o1 (f1 > (k' > o2 (f2 > o3 (f3 > k' (f2 ++ f3)))) (f23 > k (f1 ++ f23))) = beta reduce: f1 > f23 > k (f1 ++ f23) k > o1 (f1 > (o2 (f2 > o3 (f3 > (f23 > k (f1 ++ f23)) (f2 ++ f3))))) = beta reduce: f23 > f2 ++ f3 k > o1 (f1 > (o2 (f2 > o3 (f3 > (k (f1 ++ (f2 ++ f3)))))))
and from the other side:
(o1 ^ o2) ^ o3 = definition outer (^) k > (o1 ^ o2) (f12 > o3 (f3 > k (f12 ++ f3))) = definition inner (^) k > (k' > o1 (f1 > o2 (f2 > k' (f1 ++ f2)))) (f12 > o3 (f3 > k (f12 ++ f3))) = beta reduce: k' > f12 > o3 (f3 > k (f12 ++ f3)) k > (o1 (f1 > o2 (f2 > (f12 > o3 (f3 > k (f12 ++ f3))) (f1 ++ f2)))) = beta reduce: f12 > f1 ++ f2 k > (o1 (f1 > o2 (f2 > (o3 (f3 > k ((f1 ++ f2) ++ f3))))))
so again we have reduced the problem to the associativity of (
. Left
and right unit laws are left to the reader...
++
)
Derived combinators
onormalise :: OptSpec d f [f] b > [f] > [f]
Normalise a flag list by parsing and then unparsing it. This adds all
implicit (default) flags to the list, which is useful as long as there is
legacy code that circumvents the OptSpec
abstraction and directly tests
for flag membership.
onormalise opts = (oparse opts . ounparse opts) id
defaultFlags :: OptSpec d f [f] b > [f]
The list of default flags for an OptSpec
.
defaultFlags opts = onormalise opts []
Lifting isomorphisms
Primitive options
type PrimOptSpec d f a v = OptSpec d f a (v > a)
Type of primitive (not yet combined) options. The type parameter b
gets instantiated to (v > a)
, adding one argument of type v
to the answer type of the continuation.
oappend :: PrimOptSpec d f a [v] > PrimOptSpec d f a [v] > PrimOptSpec d f a [v]
oempty :: PrimOptSpec d f a [v]
Unit for oappend
.
parseFlags :: (forall a. PrimOptSpec d f a v) > [f] > v
Parse a list of flags against a primitive option spec, returning the value associated with the option. As noted above, this cannot fail because options always have a default value.
parseFlags o fs = oparse o id fs