How to scrap my boilerplate

Question

I'm using the syntactic library to make an AST. To evaluate the AST to a (Haskell) value, all of my nodes need to be an instance of the syntactic class EvalEnv:

class EvalEnv sym env where
  compileSym :: proxy env -> sym sig -> DenotationM (Reader env) sig

Syntactic also provides a "default" implementation:

compileSymDefault :: (Eval sym, Signature sig) 
  => proxy env -> sym sig -> DenotationM (Reader env) sig

but the constraint on sig is unreachable in instances of EvalEnv, making the following (say, overlapping) instance impossible:

instance EvalEnv sym env where
  compileSym = compileSymDefault

All of my user-defined AST nodes are GADTs, usually with multiple constructors, where the a parameter always satisfies the constraint for compileSymDefault:

data ADDITIVE a where
  Add :: (Num a) => ADDITIVE (a :-> a :-> Full a)
  Sub :: (Num a) => ADDITIVE (a :-> a :-> Full a)

As a result, I found that all of my instances for EvalEnv look like:

instance EvalEnv ADDITIVE env where
  compileSym p Add = compileSymDefault p Add
  compileSym p Sub = compileSymDefault p Sub

This boilerplate instance is identical for all AST nodes, and each of the GADT constructors needs to be listed separately, as the GADT constructor signature implies the compileSymDefault constraints.

Is there any way I can avoid having to list out each constructor for every node type I make?

Answer 1

If I understand the issue correctly, the boilerplate arises from the need to use pattern matching against each constructor to bring the required context in scope. Apart from the constructor name, all the case branches are identical.

The code below uses a removeBoilerplate rank-2 function which can be used to bring the context in scope. Two example functions are first defined using boilerplate code and then converted to use the helper removeBoilerplate function.

If you have many GADTs, you will need a custom removeBoilerplate for each one. So this approach is beneficial if you need to remove the boilerplate more than once for each type.

I am not familiar with syntactic to be 100% sure this will work, but it looks it has good chances. You will probably need to adapt the type of the removeBoilerplate function a bit.

{-# LANGUAGE GADTs , ExplicitForAll , ScopedTypeVariables ,
             FlexibleContexts , RankNTypes #-}

class Class a where

-- Random function requiring the class
requiresClass1 :: Class a => a -> String
requiresClass1 _ = "One!"

-- Another one
requiresClass2 :: Class a => a -> String
requiresClass2 _ = "Two!"

-- Our GADT, in which each constructor puts Class in scope
data GADT a where
   Cons1 :: Class (GADT a) => GADT a
   Cons2 :: Class (GADT a) => GADT a
   Cons3 :: Class (GADT a) => GADT a

-- Boring boilerplate
boilerplateExample1 :: GADT a -> String
boilerplateExample1 x@Cons1 = requiresClass1 x
boilerplateExample1 x@Cons2 = requiresClass1 x
boilerplateExample1 x@Cons3 = requiresClass1 x

-- More boilerplate
boilerplateExample2 :: GADT a -> String
boilerplateExample2 x@Cons1 = requiresClass2 x
boilerplateExample2 x@Cons2 = requiresClass2 x
boilerplateExample2 x@Cons3 = requiresClass2 x

-- Scrapping Boilerplate: let's list the constructors only here, once for all
removeBoilerplate :: GADT a -> (forall b. Class b => b -> c) -> c
removeBoilerplate x@Cons1 f = f x
removeBoilerplate x@Cons2 f = f x
removeBoilerplate x@Cons3 f = f x

-- No more boilerplate!
niceBoilerplateExample1 :: GADT a -> String
niceBoilerplateExample1 x = removeBoilerplate x requiresClass1

niceBoilerplateExample2 :: GADT a -> String
niceBoilerplateExample2 x = removeBoilerplate x requiresClass2

Answer 2

You can't scrap your boilerplate, but you can reduce it slightly. Neither the scrap your boilerplate nor the newer GHC Generics code can derive instances for GADTs like yours. One could generate EvalEnv instances with template haskell, but I won't discuss that.

We can reduce the amount of boilerplate we are writing very slightly. The idea we are having trouble capturing is that forall a there is a Signature a instance for any ADDITIVE a. Let's make the class of things for which this is true.

class Signature1 f where
    signatureDict :: f a -> Dict (Signature a)

Dict is a GADT that captures a constraint. Defining it requires {-# LANGUAGE ConstraintKinds #-}. Alternatively, you can import it from Data.Constraint in the constraints package.

data Dict c where
    Dict :: c => Dict c

To use the constraint captured by the Dict constructor, we must pattern match against it. We can then write compileSym in terms of signatureDict and compileSymDefault.

compileSymSignature1 :: (Eval sym, Signature1 sym) =>
    proxy env -> sym sig -> DenotationM (Reader env) sig
compileSymSignature1 p s =
    case signatureDict s of
        Dict -> compileSymDefault p s

Now we can write out ADDITIVE and its instances, capturing the idea that there is always a Signature a instance for any ADDITIVE a.

data ADDITIVE a where
  Add :: (Num a) => ADDITIVE (a :-> a :-> Full a)
  Sub :: (Num a) => ADDITIVE (a :-> a :-> Full a)

instance Eval ADDITIVE where
    evalSym Add = (+)
    evalSym Sub = (-)

instance Signature1 ADDITIVE where
    signatureDict Add = Dict
    signatureDict Sub = Dict

instance EvalEnv ADDITIVE env where
    compileSym = compileSymSignature1

Writing out the Signature1 instance doesn't have much benefit over writing out the EvalEnv instance. The only benefits we have gained are that we have captured an idea that might be useful elsewhere and the Signature1 instance is slightly simpler to write.