Dino

Dino is a tagless EDSL supporting numeric and logic expressions, conditionals, explicit sharing, etc.

Syntactic conveniences

The module Dino.Expression redefines many identifiers from the prelude, so users are advised to hide the prelude when importing it. This can be done, for example, using the NoImplicitPrelude language extension. The main module, Dino, exports both Dino.Expression and Dino.Prelude, where the latter is a subset of the standard prelude plus a few extra definitions.

Dino provides a newtype wrapper, Exp, which allows EDSL terms to be used directly as numbers and strings; for example:

ex1 ::
     (ConstExp e, NumExp e, FracExp e, CompareExp e, CondExp e)
  => Exp e Double
  -> Exp e Text
ex1 a =
  if a > 4.5
    then "greater"
    else "smaller or equal"

This example also shows the use of RebindableSyntax to allow Haskell's if syntax in EDSL expressions.

Multi-way conditionals can be expressed using cases; for example:

beaufortScale ::
     (ConstExp e, NumExp e, FracExp e, CompareExp e, CondExp e)
  => Exp e Double
  -> Exp e Text
beaufortScale v = cases
  [ (v < 0.5)  --> "calm"
  , (v < 13.8) --> "breeze"
  , (v < 24.5) --> "gale" ]
  ( Otherwise  --> "storm" )

Browse the Dino.Expression documentation to find different variations on cases, including a version for matching on enumerations without a fall-through case.

A Maybe-like monad

Similar to the function maybe in the standard prelude, Dino provides the following function to deconstruct Maybe values:

maybe ::
     (...)
  => e b          -- ^ Result when 'nothing'
  -> (e a -> e b) -- ^ Result when 'just'
  -> e (Maybe a)  -- ^ Value to deconstruct
  -> e b

However, it is not very convenient to use maybe in a nested way (i.e. when another maybe is needed inside the function that handles just). In such cases, it is much preferred to use a monadic interface. Indeed, Dino provides the type Optional which has a Monad instance and the following functions to convert to and from e (Maybe a):

suppose     :: (...) => e (Maybe a) -> Optional e (e a)
runOptional :: (...) => Optional e (e a) -> e (Maybe a)

Semantic conveniences

On the interpretation side, most Dino constructs provide default implementations for monads (many just requiring Applicative), making it easy to derive interpretations for custom monads. There is also special support for intensional analysis of higher-order constructs (i.e. constructs that introduce local variables).

Standard interpretation with special cases

For example, say that we want standard evaluation of expressions but with the ability to catch division by 0. For this, we can use a newtype around Maybe:

newtype SafeDiv a = SafeDiv {fromSafeDiv :: Maybe a}
  deriving (Functor, Applicative, Monad)

Since SafeDiv is an applicative functor, we can derive a standard interpretation of syntactic classes by just declaring instances:

instance ConstExp   SafeDiv
instance NumExp     SafeDiv
instance LogicExp   SafeDiv
instance CompareExp SafeDiv

(In this particular case, we could also have used GeneralizedNewtypeDeriving, since there are already instances of those classes for Maybe.)

In order to get special semantics for division, we have to give a manual definition of fdiv:

instance FracExp SafeDiv where
  fdiv _ (SafeDiv (Just 0)) = SafeDiv Nothing
  fdiv (SafeDiv a) (SafeDiv b) = SafeDiv (liftA2 (/) a b)

Intensional analysis

Dino has special support for intensional interpretation of higher-order constructs (i.e. interpretations that inspect the syntax). The general idea is introduced in Oleg Kiselyov's notes.

Consider the following two classes:

class LetExp e where
  letE :: DinoType a
       => Text         -- ^ Variable base name
       -> e a          -- ^ Value to share
       -> (e a -> e b) -- ^ Body
       -> e b

class LetIntensional e where
  letI :: DinoType a
       => Text -- ^ Variable name
       -> e a
       -> e b -- ^ Body (open term)
       -> e b

The former is the class that is exposed to the EDSL user. It provides a convenient higher-order construct for sharing values. Here is an example of its use:

ex2 ::
     (ConstExp e, NumExp e, CompareExp e, CondExp e, LetExp e)
  => Exp e Double
  -> Exp e Double
ex2 a = letE "x" expensive $ \x ->
  if a > 10
    then x*2
    else x*3
  where
    expensive = a*a*a*a*a*a*a*a

But the higher-order interface is problematic for intensional interpretations (e.g. AST extraction). The main problem is to come up with a representation of the variable to which the body can be applied. One must make sure that the chosen variable does not lead to capturing. For such interpretations, the first-order function letI is more suitable.

letI is similar to letE, but with some important differences:

• The "body" argument passed to letE is a function while the letI has an open expression as body.
• The name passed to letE is just a suggested base of the variable name. The user does not need to worry about potential name clashing.
• The name passed to letI is the actual variable name. The caller must guarantee that this name does not clash with other variables.

The thing to note is this:

• letE is easy to call, but hard to implement.
• letI is hard to call, but easy to implement.

letI is hard to call, because it must be given a name that does not lead to capturing. But for an implementor, letI is very nice. Why? Because it gets a variable name from someone else, and it can directly inspect the body without first applying it to an argument.

The good news is that Dino provides the means to bridge the gap between letE and letI: the Intensional newtype wrapper. Given a LetIntensional instance for an interpretation, we can automatically derive LetExp by just wrapping it in Intensional, due to the following instance:

instance (VarExp e, LetIntensional e) => LetExp (Intensional e)

In other words, you get to define your semantics using first-order constructs and automatically derive a higher-order interface.

As an example, the Reified interpretation (for AST extraction; see Dino.Interpretation) is an example of one that only instantiates first-order classes (LetIntensional and friends). But the combined type Intensional Reified supports a higher-order interface (LetExp and friends).

But what about adding new higher-order constructs? Then one must go through the work of defining an instance such as the one for LetExp (Intensional e) above. Fortunately, defining such instances is made very easy by the following function:

unbind ::
     (VarExp e, DinoType a)
  => Text                                 -- ^ Variable base name
  -> (Intensional e a -> Intensional e b) -- ^ Body parameterized by its free variable
  -> (Text, Intensional e b)              -- ^ Generated variable and function body

It takes a body represented as a function, and returns a body as an open expression along with the generated variable name. This name is guaranteed not to lead to capturing, as long all binders are generated using the same method. There is also unbind2, for constructs that introduce two local variables.

For the curious reader, unbind is implemented using the technique in Using Circular Programming for Higher-Order Syntax.

Parallel interpretation

The (:×:) type allows two interpretations to run in parallel. This type derives many syntactic classes automatically:

instance (ConstExp e1, ConstExp e2) => ConstExp (e1 :×: e2)
instance (NumExp e1,   NumExp e2)   => NumExp   (e1 :×: e2)
...

However, it is not possible to give such general instances for classes with higher-order constructs (e.g. LetExp). Instead, there are instances for intensional classes, such as this one:

instance (LetIntensional e1, LetIntensional e2) => LetIntensional (e1 :×: e2)

As seen earlier, we can derive LetExp from LetIntensional by using the Intensional wrapper. So, in order to obtain a parallel interpretation for LetExp, we simply use the type Intensional (e1 :×: e2), where e1 and e2 are the interpretations we want to run. (Of course, (:×:) can be nested in order to run more than two interpretations in parallel.)

Note that we cannot run standard evaluation as a parallel interpretation. This is because the monads for standard evaluation (e.g. Identity or Maybe) implement LetExp but not LetIntensional. In order to do evaluation in a parallel setting, use the type EvalEnv, which evaluates using a variable environment.