# Pattern Synonyms

Posted on December 22, 2016 by Kwang Yul Seo

Pattern synonyms allow us give names to pattern matches. It is a relatively new GHC extension which was first introduced in GHC 7.8 and further enhanced in GHC 8.0. In this post, I will show you an usage of pattern synonyms with a practical example.

Our assignment is to create a compiler for a toy functional language. We’ve already finished writing the parser and the type checker. It uses a small IR based on lambda calculus. Our next plan is to transform this IR into SK combinators for execution on the graph reduction machine.

Here’s the datatype of our IR:

``````data Exp = Ap Exp Exp
| Lambda VarId Exp
| Fun FunId
| Var VarId
| Int Int``````

The SK compilation scheme is taken from Simon Peyton Jones’s The Implementation of Functional Programming Languages. (You don’t need to understand how this actually works. Interested readers are referred to SPJ’s book.)

``````C[e] compiles e to SK combinators

C[e1 e2] = C[e1] C[e2]
C[\x.e] = A x [C[e]]
C[cv] = cv

A x [f] abstracts x from f

A x [f1 f2] = S (A x [f1]) (A x [f2])
A x [x] = I
A x [cv] = K cv``````

This compilation scheme can be succinctly implemented in Haskell using pattern matches on `Exp` because the scheme uses the data constructors of `Exp`.

``````compile :: Exp -> Exp
compile (Ap e1 e2) = Ap (compile e1) (compile e2)
compile (Lambda v e) = abstract v (compile e)
compile cv = cv

abstract :: String -> Exp -> Exp
abstract x (Ap f1 f2) = (abstract x f1) (abstract x f2)
abstract x (Var v) | x == v = i
abstract x (Fun v) | x == v = i
abstract _ cv = k cv

s :: Exp -> Exp -> Exp
s f g = Ap (Ap (Fun "S") f ) g

k :: Exp -> Exp
k c = Ap (Fun "K") c

i :: Exp
i = Fun "I"``````

So far so good, but we realized that this basic compilation algorithm tends to produce large combinator expressions. SPJ suggests that we can improve the scheme by introducing additional combinators `B` and `C`.

Reduction rules:

``````B f g x = f (g x)
C f g x = f x g``````

Optimization rules:

``````S (K p) (K q) = K (p q)
S (K p) I = p
S (K p) q = B p q
S p (K q) = C p q``````

The optimization algorithm can be implemented as pattern matches on `Exp`.

``````optimize :: Exp -> Exp
optimize (Ap (Ap (Fun "S") (Ap (Fun "K") p)) (Ap (Fun "K") q)) = k (Ap p q)
optimize (Ap (Ap (Fun "S") (Ap (Fun "K") p)) (Fun "I")) = p
optimize (Ap (Ap (Fun "S") (Ap (Fun "K") p)) q) = b p q
optimize (Ap (Ap (Fun "S") p) (Ap (Fun "K") q)) = c p q
optimize x = x``````

Unfortunately, this time the code is very complicated because `S`, `K` and `I` are not the data constructors of `Exp`. We have to sprinkle `Ap` and `Fun` all over to represent `S`, `K` and `I` combinators.

Can we improve it? As you might have expected, GHC’s `PatternSynonyms` extension is the rescue! It lets us make synonyms for complicated patterns like these. We can define `S`, `K` and `I` as pattern synonyms and use them as if they were data constructors.

``````pattern S p q = Ap (Ap (Fun "S") p) q
pattern K p = Ap (Fun "K") p
pattern I = Fun "I"``````

With the help of these pattern synonyms, we can rewrite `optimize` function compactly.

``````optimize :: Exp -> Exp
optimize (S (K p) (K q)) = k (Ap p q)
optimize (S (K p) I) = p
optimize (S (K p) q) = b p q
optimize (S p (K q)) = c p q
optimize x = x``````

Compare the code with the optimization rules. Now they look almost the same!