Generic HASKELL 0.99 Amber Release Andres L¨oh November 7, 2001 Generic HASKELL 0.99 – Amber Release Overview • Stepwise introduction to the Generic HASKELL language • A sample Generic HASKELL session • A look at the compiler – What does it do? – problems and features • Future work Generic HASKELL 0.99 – Amber Release 1 Generic HASKELL– the language • a superset of Haskell 98 • type-indexed values (generic functions) • kind-indexed types • type-indexed types (experimental feature) Generic HASKELL 0.99 – Amber Release 2 mpc -style generic functions • define functions on the structure of data types • define functions for all types (of all kinds) mpc • -style generic functions possess kind-indexed types Generic HASKELL 0.99 – Amber Release 3 Structure of data types data A arg . . . arg = Con T T . . . T 1 k 1 1,1 1,2 1,n1 | Con T T . . . T 2 2,1 2,2 2,n2 . . . | Con T T . . . T m m,1 m,2 m,nm ◦ data A arg . . . arg = T :*: T :*: . . . :*: T 1 k 1,1 1,2 1,n1 :+: T :*: T :*: . . . :*: T 2,1 2,2 2,n2 . . . :+: T :*: T :*: . . . :*: T m,1 m,2 m,nm • Both :+: and :*: are right associative. • A constructor without elements is replaced by Unit. data List a = Nil | Cons a (List a) ◦ data List a = Unit :+: a :*: List a Generic HASKELL 0.99 – Amber Release 4 Structure of data types – continued data a :+: b = Inl a | Inr b data a :*: b = a :*: b data Unit = Unit data Con a = Con ConDescr a data Label a = Label LabelDescr a data List a = Nil | Cons{hd :: a, tl :: List a } ◦ data List a = Con Nil Unit :+: Con Cons (Label hd a :*: Label tl (List a)) Generic HASKELL 0.99 – Amber Release 5 Structure of data types – continued data ConDescr = ConDescr {conName :: String , conType :: String , conArity :: Int , conLabels :: Bool , conFixity :: Fixity } data LabelDescr = LabelDescr{labelName :: String , labelType :: String , labelStrict :: Bool } Generic HASKELL 0.99 – Amber Release 6 Structure of data types – more examples data Fork a = Fork a a data Perfect a = ZeroP a | SuccP (Perfect (Fork a)) ◦ data Fork a = Con Fork (a :*: a) ◦ data Perfect a = Con ZeroP a :+: Con SuccP (Perfect (Fork a)) data Tree a b = Leaf a | Node (Tree a b) b (Tree a b) ◦ data Tree a b = Con Leaf a :+: Con Node (Tree a b :*: b :*: Tree a b) Generic HASKELL 0.99 – Amber Release 7 Generic functions in Generic HASKELL data Bit = O | I -- encode{|t|} :: t → [Bit ] encode{|Unit|} = const [ ] encode{|:+:|} eA eB (Inl a) = O : eA a encode{|:+:|} eA eB (Inr b) = I : eB b encode{|:*:|} eA eB (a :*: b) = eA a ++ eB b encode{|Con c|} eB (Con b) = eB b encode{|Label l|} eB (Label b) = eB b encode{|Int|} = primEncodeInt encode{|Char|} = primEncodeChar Generic HASKELL 0.99 – Amber Release 8 Generic functions in Generic HASKELL– continued -- decode{|t|} :: [Bit ] → (t, [Bit ]) decode{|Unit|} bl = (Unit, bl) 0 0 decode{|:+:|} dA dB (O : bl) = let (a, bl ) = dA bl in (Inl a, bl ) 0 0 decode{|:+:|} dA dB (I : bl) = let (b, bl ) = dB bl in (Inr b, bl ) 0 decode{|:*:|} dA dB bl = let (a, bl ) = dA bl 00 0 (b, bl ) = dB bl 00 in (a :*: b, bl ) 0 0 decode{|Con c|} dB bl = let (b, bl ) = dB bl in (Con c b, bl ) 0 0 decode{|Label l|} dB bl = let (b, bl ) = dB bl in (Label l b, bl ) decode{|Int|} = primDecodeInt decode{|Char|} = primDecodeChar Generic HASKELL 0.99 – Amber Release 9