Jäsennys ja AST:t Haskellissa

Esitiedot

Kuinka moni osaa

  • Funktorit?
  • Applikatiiviset funktorit?
  • Monadit?
  • Rekursiivisten tyyppien fixed point esityksen?

Puutteita?

  • Jos tunnette tarvetta, voin pitää kertausluennon.
  • Tarve ilmaistaan ilmoittautumalla tilaisuuteen "Ohjaus" Korpissa
  • Min 5 hlö.

AST ja Haskell

  • AST:n esitystä kannattaa miettiä
  • Sillä operoidaan paljon.
  • Seuraavassa kolme ajatusta

AST.v1

"TIEA351, viikko kolme"

data Expr = Variable String  -- Mahdollisimman vähän produktioita
          | Constant Const   -- tänne, koska tämän yli rekursoidaan!
          | Pair Expr Expr
          | Project Side Expr
          | BinOp Op Expr Expr
  deriving (Show, Eq)

data Side = L | R            -- Tälläisillä saadaan pienennettyä Expr:iä  
  deriving (Eq, Show)

data Op = Add | Sub | Mul
  deriving (Eq, Show)

data Const = I Int | B Bool
  deriving (Eq, Show)
  • Pro: Simppeli
  • Con: Laajentaminen aiheuttaa paljon muutoksia, tyyppien yms. annotaatioiden jälkeen ei enää niin simppeli

AST.v1 ja operaatiot

  • Rekursiolla rakenteen yli poks!
  • Data.Generics.Uniplate.Data ja Control.Lens.Plated:
{-#LANGUAGE DeriveDataTypeable#-}
import Data.Data
import Data.Generics.Uniplate.Data
.. deriving (Eq,Show,Data) pelkän Eq,Show:n tilalle 
foldArith = transform op
    where
        op e = case e of
            BinOp Add (Constant (I n)) (Constant (I m))
                -> Constant (I (n+m))
            BinOp Sub (Constant (I n)) (Constant (I m))
                -> Constant (I (n-m))
            other -> other
*Tiny> foldArith (BinOp Sub (Constant (I 4)) (BinOp Add (Constant (I 8)) (Constant (I 10))))
Constant (I (-14))

AST.v1 ja operaatiot

Myös rakenteen "kysely" on helppoa ja hauskaa:

allVariables e = [var | Variable var <- universe e]
*Tiny> allVariables  (BinOp Sub (Variable "x") (BinOp Add (Constant (I 8)) (Variable "z")))
["x","z"]

Jos teet useampia sisäkkäisiä tyyppejä, niin universeBi universe:n sijaan. (-Bi prefixillä kyselyt ja muunnokset etenevät tyyppirajojen läpi)

Parempi AST

Haskell ohjelmoinnin nyrkkisääntö: Kaikesta tulee parempaa tyyppiparametrilla

Problem: Mihin kohtaan se lisätään?

AST.v2 -- Tyyppimuuttuja muuttujan paikalle

data Expr2 a = Variable2 a
          | Constant2 Const
          | Pair2 (Expr2 a) (Expr2 a)
          | Project2 Side (Expr2 a)
          | BinOp2 Op (Expr2 a) (Expr2 a)
  deriving (Show, Eq, Functor, Foldable, Traversable)

Mutta sehän on monadi!

instance Monad Expr2 where
    return = Variable2
    Variable2 x     >>= f = f x
    Pair2 fst snd   >>= f = Pair2 (fst>>=f) (snd>>=f)
    Project2 s pair >>= f = Project2 s (pair>>=f)
    BinOp2 op l r   >>= f = BinOp2 op (l>>=f) (r>>=f)

Monadi => Muuttujien korvaus (ongelma -> ei tunnista sidottuja muuttujia, siitä lisää myöhemmin)

*Tiny> :{ do 
        x <- BinOp2 Add (Variable2 "z") (Variable2 "x")
        if x=="x" then return "a" else Constant2 (I 100)
        :}
BinOp2 Add (Constant2 (I 100)) (Variable2 "a")

Eikä siinä vielä kaikki

Jos muuttujan sisältö on tyyppimuuttuja, niin AST voi sisältää esimerkiksi välituloksia:

compAdd = transform op
    where
        op e = case e of
            BinOp2 Add (Variable2 l) (Variable2 r)
                -> Variable2 ("RES",[("LOAD","L",fst l)
                            ,("LOAD","R",fst r)
                            ,("ADD","L","R")
                            ,("STORE","RES","L")])
            other -> other

storeVars :: Expr2 String -> Expr2 (String,[OpCode])
storeVars = fmap (\var -> (var,[]))
type OpCode = (String,String,String)
*Tiny> :{ compAdd . storeVars $ 
            BinOp2 Sub (Constant2 (I 4)) 
                       (BinOp2 Add (Variable2 "x") (Variable2 "y"))
        :}
BinOp2 Sub (Constant2 (I 4)) 
           (Variable2 ("RES",[
                              ("LOAD","L","x")
                             ,("LOAD","R","y")
                             ,("ADD","L","R")
                             ,("STORE","RES","L")]))

AST.v2.1

Joihinkin tarkoituksiin ei kannata sotkea muuttujaa ja laajennospistettä:

data Expr2 a = Variable2 String
          | Constant2 Const
          | Pair2 (Expr2 a) (Expr2 a)
          | Project2 Side (Expr2 a)
          | BinOp2 Op (Expr2 a) (Expr2 a)
          | Extension a
  deriving (Show, Eq, Functor, Foldable, Traversable)

Esimerkiksi välitulokset, myöhemmin lisättävät operaatiot jne.

AST.v3

'Fixattu' data -- korvataan rekursio tyyppimuuttujalla!

data FExpr expr = Variable3 String
          | Constant3 Const
          | Pair3 expr expr
          | Project3 expr expr
          | BinOp3 Op expr expr
  deriving (Show, Eq, Functor,Foldable,Traversable)

data Fix f = Fix {unfix :: f (Fix f)}

type PureExpr = Fix FExpr

Esim:

Fix (BinOp3 Sub 
            (Fix (Constant3 (I 3))) 
            (Fix (Variable3 "x")))

AST.v3 Miksi?

  1. Laajennettava:
data Typed f a = Typed Type (f a) deriving (Show,Functor)
pattern x ::: τ <- Fix (Typed τ x)

type TypedExpr = Fix (Typed FixedExpression)
BinOp3 Sub 
    (Variable3 "x" ::: IntT) 
    (Variable3 "y" ::: IntT) ::: IntT
  • Lisäideoita: Laajennos joka sisältää jäsentimen antaman paikkatiedon

AST.v3 miksi?

  1. Geneerinen
children2 :: (Foldable f) => Fix f -> [Fix f]
children2 = foldMap (\x->[x]) . unfix

universe2 :: Foldable f => Fix f -> [Fix f]
universe2 f = let chd = children2 f
              in chd ++ concatMap universe2 chd

allVariables2 e = [var | Fix (Variable3 var) <- universe2 e]
*Tiny> allVariables2 $ Fix (BinOp3 Sub (Fix (Constant3 (I 3))) (Fix (Variable3 "x")))
["x"]

AST.v3 ..miksi

  1. Geneerinen, mutta spesialisoitavissa rakenteen suhteen
data FExpr expr = Variable3 String
          ....
          | Let String  expr expr
  deriving (Show, Eq, Functor,Foldable,Traversable)

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unfix

freeVars = cata $ \case
        (Variable3 x)  -> [x]
        (Let3 x e₁ e₂) -> filter (/=x) (e₁<>e₂)
        other          -> fold other

exmpl = Fix (Let3 "x" (Fix (Constant3 (I 10)))
                      (Fix (BinOp3 Sub
                        (Fix (Variable3 "y"))
                        (Fix (Variable3 "x")))))
*Tiny> allVariables2  exmpl
["y","x"]

*Tiny> freeVars   exmpl
["y"]

AST.v3 cons

  • Vaatii hieman totuttelua
  • Käytännössä pattern synonyymit pakollisia
  • Jos Fixed rakenteita laittaa sisäkkäin, syntyy harvinaislaatuinen sekasotku

Jäsennystä

Kombinaattoriparsinnasta

  • Tassu ylös jos on tuttu! (parsec, attoparsec jne..)
  • Ajatus:
    • Tehdään yksinkertaisia jäsentimiä ("Lue merkki","Lue sana", jne..)
    • Yhdistetään niitä kombinaattorifunktioilla ("tämä, sitten tuo", "tämä tai tuo", "tämä suluissa")
    • Muodostavat applikatiivisen funktorin
    • Ja usein myös monadin

Koodiesimerkki MegaParsec:illa

Onko aikaa? Katsotaanpa livenä..

These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.