### Exploring the compiler forest in Haskell

The combinators from the Compiler Forest paper can be implemented in Haskell as follows.

*(Note: This requires recent GHC with options -XKindSignatures -XGADTs -XTypeFamilies.)*

First, we define a type for partial compilers:

data PC :: * -> * -> * where

PC :: (s -> (s', t' -> t)) -> PC (s,t) (s', t')

In Haskell terms, this is a "generalized algebraic data type", but this is solely so that we can think of PC as a two-argument type constructor instead of four.

We can introduce type families for extracting the source and target types from a pair:

type family Src a

type instance Src (s,t) = s

type family Tgt a

type instance Tgt (s,t) = t

applyPC :: PC p q ->

(Src p -> (Src q, Tgt q -> Tgt p))

applyPC (PC f) = f

The identity on partial compilers is:

idPC :: PC (s, t) (s, t)

idPC = PC (\s -> (s, id))

and composition of partial compilers is as follows:

compPC :: PC q r -> PC p q -> PC p r

compPC (PC g) (PC f) =

PC (\s -> let (s',f') = f s in

let (s'', g') = g s' in

(s'', f' . g'))

Likewise, tensor product of partial compilers can be defined. First, we introduce a type family for tensors:

type family Tensor a b

type instance Tensor (s1,t1) (s2,t2) =

((s1,s2), (t1,t2))

tensorPC :: PC p1 p2 -> PC p1' p2' ->

PC (Tensor p1 p1') (Tensor p2 p2')

tensorPC (PC f) (PC g) =

PC (\(x1,x2) ->

let (y1,f') = f x1 in

let (y2,g') = g x2 in

((y1,y2),\(z1,z2) -> (f' z1, g' z2)))

The conditional combinator is:

condPC :: (Src p -> Bool) ->

PC p q -> PC p q -> PC p q

condPC p (PC f) (PC g) =

PC (\s -> if p s then f s else g s)

and the (very similar) case combinator is:

casesPC :: (s -> Either s1 s2) ->

PC (s1,t) q ->

PC (s2,t) q -> PC (s,t) q

casesPC w (PC f) (PC g) =

PC (\s -> case w s

of Left(s1) -> f s1 ;

Right(s2) -> g s2)

The "functor" operation that constructs a pair of functions $f:(s \to s')$ and $g:(t'\to t)$ to a partial compiler is:

functorPC :: (s -> s') -> (t' -> t) ->

PC(s,t) (s',t')

functorPC f g = PC (\s -> (f s,g))

and finally the iterator combinator is:

iterPC :: Int -> PC p p -> PC p p

iterPC 0 pc = pc

iterPC n pc = compPC pc (iterPC (n-1) pc)

Exercise for the reader: Implement some of the atomic partial compilers in Haskell and use the above combinators to combine them...

## 0 Comments:

## Post a Comment

Subscribe to Post Comments [Atom]

<< Home