Introduction

This module gives an alternative to the Operational package \[1\], in which instructions can be higher-order functors, parameterized on the program monad that they are part of. This makes it possible to define instruction sets compositionally using :+:. In the normal Operational, this could be done for simple instructions, but here it can be done even for "control instructions" -- instructions that take programs as arguments.

For general information about the ideas behind this module, see the Operational package \[1\].

\[1\] http://hackage.haskell.org/package/operational

Example

(Full code found in https://github.com/emilaxelsson/operational-alacarte/blob/master/examples/Simple.hs.)

An "if" instruction can be defined as follows:

data If fs a where
  If :: Exp Bool -> prog a -> prog a -> If (Param1 prog) a

Note the use of the type parameter prog to refer to sub-programs. (Exp is some type representing pure expressions.)

The type (Param1 prog) can be seen as a type-level list with one element prog. (See Data.ALaCarte for more details on parameter lists.)

We can now make program types that combine several instructions; e.g.:

type MyProgram = Program (If :+: Loop :+: ...) Param0

Program is a recursive type that sets the type of the sub-programs of If (and Loop, etc.) to MyProgram. With the original Operational package, we would have to hard-code a specific type for the sub-programs of If (or make MyProgram a recursive newtype, as noted by the author of Operational).

Interpretation of Program in a monad m can be done using

interpret :: (Interp i m fs, HFunctor i, Monad m) => Program i fs a -> m a

In order to use this function, If needs to be an instance of Interp and HFunctor. The HFunctor instance is straightforward:

instance HFunctor If where
  hfmap f (If c thn els) = If c (f thn) (f els)

The Interp type class is parameterized both on the instruction type and the destination monad. For example, interpretation of If in the IO monad might look as follows:

instance Interp If IO fs where
  interp (If c thn els) = if eval c then thn else els

(Here eval is the evaluator for the expression languauge Exp.)

The Interp class distributes over :+: which means that it is possible to interpret any expression type (I1 :+: I2 :+: I3 :+: ...) to IO, as long as the individual instructions (I1, I2, etc.) have Interp instances for IO.

Bi-functorial instructions

The type (Param1 prog) in the result of If above says that the instruction has one sub-structure whose type is prog. The advanced example https://github.com/emilaxelsson/operational-alacarte/blob/master/examples/Advanced.hs shows a version of If that has two parameters:

  If :: exp Bool -> prog a -> prog a -> If (Param2 prog exp) a

prog represents sub-programs and exp represents expressions (Exp Bool has been replaced with exp Bool).

This new If instruction is a higher-order bi-functor (see HBifunctor).

The advantage of parameterizing instructions on expressions is that it lets us define generic functions, such as interpretBi, which decouple the interpretation of instructions from the interpretation of expressions.

Generalized interface

We have seen two examples of If with a parameter list of one and two arguments respectively ((Param1 prog) and (Param2 prog exp)). There is nothing stopping us from having instructions with more parameters. For example, we could make a version of If that takes an extra type class constraint pred as parameter:

  If :: pred a => exp Bool -> prog a -> prog a -> If (Param3 prog exp pred) a

(See the documentation to Data.ALaCarte regarding why it is a good idea to make pred part of the parameter list rather than just making it a separate parameter.)

In fact, it is possible to have arbitrarily many parameters to instructions (but the type synonyms for parameter lists stop at Param4).

The functions and types in this module (and Data.ALaCarte) are designed to be generic in the sense that things that work for parameter lists of N elements also work for parameter lists of more elements. For example, the function interpret mentioned above requires the instruction i to be a higher-order functor, but it also works for high-order bi-functors, and for the last version of If that has an additional parameter pred.

Typical use

Here we give specialized type signatures for a selection of functions for different uses of the general interface.

.

Functorial instructions with no extra parameters

This scenario is used in https://github.com/emilaxelsson/operational-alacarte/blob/master/examples/Simple.hs.

singleton :: instr (Param1 (ProgramT instr Param0 m)) a -> ProgramT instr Param0 m a

interpretWithMonad
    :: (HFunctor instr, Monad m)
    => (forall b . instr (Param1 m) b -> m b)
    -> Program instr Param0 a -> m a

interpret
    :: (Interp i m Param0, HFunctor i, Monad m)
    => Program i Param0 a -> m a

.

Functorial instructions with extra parameter

Like the previous scenario but with an extra parameter p (poly-kinded) that instructions can use for anything.

singleton :: instr (Param2 (ProgramT instr (Param1 p) m) p) a -> ProgramT instr (Param1 p) m a

interpretWithMonad
    :: (HFunctor instr, Monad m)
    => (forall b . instr (Param2 m p) b -> m b)
    -> Program instr (Param1 p) a -> m a

interpret
    :: (Interp i m (Param1 p), HFunctor i, Monad m)
    => Program i (Param1 p) a -> m a

.

Bi-functorial instructions with no extra parameters

This scenario is used in https://github.com/emilaxelsson/operational-alacarte/blob/master/examples/Advanced.hs.

The parameter exp is an extra interpreted structure that e.g. can represent expressions.

singleton :: instr (Param2 (ProgramT instr (Param1 exp) m) exp) a -> ProgramT instr (Param1 exp) m a

interpretWithMonadBi
    :: (HBifunctor instr, Functor m, Monad m)
    => (forall b . exp b -> m b)
    -> (forall b . instr (Param2 m m) b -> m b)
    -> Program instr (Param1 exp) a -> m a

interpret
    :: (InterpBi i m Param0, HBifunctor i, Functor m, Monad m)
    => (forall b . exp b -> m b) -> Program i (Param1 exp) a -> m a

.

Bi-functorial instructions with extra parameter

Like the previous scenario but with an extra parameter p (poly-kinded) that instructions can use for anything.

singleton :: instr (Param3 (ProgramT instr (Param2 exp p) m) exp p) a -> ProgramT instr (Param2 exp p) m a

interpretWithMonadBi
    :: (HBifunctor instr, Functor m, Monad m)
    => (forall b . exp b -> m b)
    -> (forall b . instr (Param3 m m p) b -> m b)
    -> Program instr (Param2 exp p) a -> m a

interpret
    :: (InterpBi i m (Param1 p), HBifunctor i, Functor m, Monad m)
    => (forall b . exp b -> m b) -> Program i (Param2 exp p) a -> m a