What is "Scrap Your Boilerplate"?

Question

I see people talking about Scrap Your Boilerplate and generic programming in Haskell. What do these terms mean? When would I want to use Scrap Your Boilerplate, and how do I use it?

Flat

Google has a ton of documentation on this.... – Detonator

@JustinPihony I asked the question because one of the aims of Stack Overflow is to have the answer to all programming questions, even those that can be Googled. This question, as far as I can see, has never been asked on SO before, and I believe it will generate some high-quality answers. – Flat

Section 2 of the paper Scrap your boilerplate - A Practical Design Pattern for Generic Programming contains a good motivating example. – Flatboat

FWIW, I have often wondered what the answer to this question is. The documentation for SYBP is vast and complex, and seems to omit to describe the problem it's actually attempting to solve... – Vesper

Answer 1

Often when making transformations on complex data types, we only need to affect small pieces of the structure---in other words, we're targeting specific reducible expressions, redexes, alone.

The classic example is double-negation elimination over a type of integer expressions:

data Exp = Plus Exp Exp | Mult Exp Exp | Negate Exp | Pure Int

doubleNegSimpl :: Exp -> Exp
doubleNegSimpl (Negate (Negate e)) = e
...

Even in describing this example, I'd prefer not to write out the entirety of the ... part. It is completely mechanical---nothing more than the engine for continuing the recursion throughout the entirety of the Exp.

This "engine" is the boilerplate we intend to scrap.

---

To achieve this, Scrap Your Boilerplate suggests a mechanism by which we can construct "generic traversals" over data types. These traversals operate exactly correctly without knowing anything at all about the specific data type in question. To do this, very roughly, we have a notion of generic annotated trees. These are larger than ADTs in such a way that all ADTs can be projected into the type of annotated trees:

section :: Generic a => a -> AnnotatedTree

and "valid" annotated trees can be projected back into some brand of ADT

retract :: Generic a => AnnotatedTree -> Maybe a

Notably, I'm introducing the Generic typeclass to indicate types which have section and retract defined.

Using this generic, annotated tree representation of all data types, we can define a traversal once and for all. In particular, we provide an interface (using section and retract strategically) so that end users are never exposed to the AnnotatedTree type. Instead, it looks a bit like:

everywhere' :: Generic a => (a -> a) -> (AnnotatedTree -> AnnotatedTree)

such that, combined with final and initial section and retracts and the invariant that our annotated trees are always "valid", we have

everywhere :: Generic a => (a -> a) -> (a -> a)
everywhere f a0 = fromJust . retract . everywhere' f . section

---

What does everywhere f a do? It tries to apply the function f "everywhere" in the ADT a. In other words, we now write our double negation simplification as follows

doubleNegSimpl :: Exp -> Exp
doubleNegSimpl (Negate (Negate e)) = e
doubleNegSimpl e                   = e

In other words, it acts as id whenever the redex (Negate (Negate _)) fails to match. If we apply everywhere to this

simplify :: Exp -> Exp
simplify = everywhere doubleNegSimpl

then double negations will be eliminated "everywhere" via a generic traversal. The ... boilerplate is gone.

Ganges

How does everywhere figure out whether a pattern successfully matches or not? Usually, non-exhaustive patterns throw an exception which must be caught in IO. – Flat

It doesn't. doubleNegSimpl is identity when the redex doesn't match, so everywhere literally just applies it everywhere and it simply is a no-op in most places. Of course, everywhere is careful to do this efficiently. – Ganges