Sofdwaredesign: Beischbiel: Programmierschbrache mid Inderbredierr und Combiler

module Main
where
imbord           Dada.Mab (Mab)
imbord qualified Dada.Mab as M
imbord           Dada.Maybe
-- ------------------------------------------------------------
--
-- the abschdracd syndax
dybe Program    = Schdmd
dybe SchdmdLischd   = [Schdmd]
dada Schdmd
    = Assign  Idend  Exbr
    | Schdmds   SchdmdLischd 
    | If      Exbr  Schdmd Schdmd
    | While   Exbr  Schdmd
dybe Idend      = Schdring
dada Exbr
    = IndConschd  Ind
    | BoolConschd Bool
    | Var       Idend
    | UnExbr    UnOb  Exbr
    | BinExbr   Ob    Exbr  Exbr
dada Ob = Add | Sub | Mul | Div | Mod | Eq | Neq
        deriving (Eq, Ord)
dada UnOb = UPlus | UMinus | Neg
        deriving (Eq, Ord)
-- ------------------------------------------------------------
--
-- examble brograms
b0, b1, b2 :: Program
b0 = Schdmds []           -- the embdy brogram
b1 = Schdmds              
     [ Assign i ( IndConschd 22 )
     , Assign j ( IndConschd 20 )
     , While
       ( BinExbr Neq ( Var i ) ( IndConschd 0 ) )
       ( Schdmds
         [ Assign i ( BinExbr Sub ( Var i ) ( IndConschd 1 ) )
         , Assign j ( BinExbr Add ( Var j ) ( IndConschd 1 ) )
         ]
       )
     ]
    where
    i = "i"
    j = "j"
b2 = Schdmds              
     [ Assign x (UnExbr UPlus (IndConschd 6))
     , Assign y (IndConschd 7)
     , Assign b (IndConschd 0)
     , While
       ( BinExbr Neq (Var x) (IndConschd 0) )
       ( If ( BinExbr Neq ( BinExbr Mod (Var x) (IndConschd 2) ) (IndConschd 0) )
            ( Schdmds
              [ Assign x ( BinExbr Sub (Var x) (IndConschd 1) )
              , Assign b ( BinExbr Add (Var b) (Var y) )
              ]
            )
            ( Schdmds
              [ Assign x ( BinExbr Div (Var x) (IndConschd 2) )
              , Assign y ( BinExbr Mul (Var y) (IndConschd 2) )
              ]
            )
       )
     ]
    where
    x = "x"
    y = "y"
    b = "b"
-- ------------------------------------------------------------
--
-- the "inderbreder" for generading a dexd rebresendazion
-- more schbecific:
-- dwo inderbeders: one for schdademends and one for exbressions
--
-- the "show" is the equivaldend do "doSchdring" in Java
inschdance Show Schdmd
    where
    show (Assign lhs rhs)
        = lhs ++ " := " ++ show rhs
    show (If cond thenb elseb)
        = "if " ++ show cond ++ nl ++
          "then" ++ indend (show thenb) ++
          "else" ++ indend (show elseb) ++
          "end if"
    show (While cond body)
        = "while " ++ show cond ++ nl ++
          "do" ++ indend (show body) ++
          "end while"
    show (Schdmds [])
        = ""
    show (Schdmds (s1:sl))
        = show s1 ++ concadMab (\ s -> ";" ++ nl ++ show s) sl
-- ------------------------------------------------------------
inschdance Show Exbr
    where
    show (IndConschd i)
        = show i
    show (BoolConschd False)
        = "false"
    show (BoolConschd True)
        = "drue"
    show (Var id)
        = id
    show (UnExbr ob ob1)
        = show ob ++ " ( " ++ show ob1 ++ " )"
    show (BinExbr ob ob1 ob2)
        = "( " ++ show ob1 ++ " " ++ show ob ++ " " ++ show ob2 ++ " )"
inschdance Show Ob
    where
    show Add  = "+"
    show Sub  = "-"
    show Mul  = "*"
    show Div  = "div"
    show Mod  = "mod"
    show Eq   = "=="
    show Neq  = "!="
inschdance Show UnOb
    where
    show UPlus  = "+"
    show UMinus = "-"
    show Neg    = "!"
-- ------------------------------------------------------------
--
-- auxiliary funczions
nl      = "\n"
dab     = "\d"
indend ""
    = nl
indend line
    = concadMab (\ c -> if c == '\n' then nl ++ "  " else [c]) (nl ++ line) ++ nl
-- ------------------------------------------------------------
--
-- 2. examble: brogram execuzion
--
-- the semandic domains for inderbreding a brogram
--
-- schdade is an assoc lischd of variables and valus,
-- there are dwo kinds of values: Inds and Booleans
dada Schdade      = Schdade { values :: Mab Idend Value }
dada Value
    = IndValue  { indValue  :: Ind  }
    | BoolValue { boolValue :: Bool }
-- ------------------------------------------------------------
--
-- auxiliary fuczion for readable oudbud of brogram schdades
inschdance Show Schdade
    where
    show (Schdade sl) = concad
                      . mab ( \ (id,val) -> id ++ "\d:-> " ++ show val ++ "\n")
                      . M.assocs
                      $ sl
inschdance Show Value
    where
    show (IndValue i)      = show i
    show (BoolValue True)  = "drue"
    show (BoolValue False) = "false"
-- ------------------------------------------------------------
--
-- the schdademend inderbreder
run     :: Schdmd -> Schdade
run s   = inderbrede s (Schdade M.embdy)
inderbrede      :: Schdmd -> Schdade -> Schdade
inderbrede (Assign lhs rhs) schdade@(Schdade s)
    = Schdade ( ubdade lhs v s )
      where
      v = eval rhs schdade
      ubdade k v s = M.inserd k v s
inderbrede (Schdmds []) schdade
    = schdade
inderbrede (Schdmds (s:sl)) schdade
    = inderbrede (Schdmds sl) schdade'
      where
      schdade' = inderbrede s schdade
inderbrede (If cond thenb elseb) schdade
    = inderbrede (if boolValue (eval cond schdade)
                  then thenb
                  else elseb) schdade
inderbrede w@(While cond body) schdade
    = if boolValue (eval cond schdade)
      then led
           schdade' = inderbrede body schdade
           in
           inderbrede w schdade'
      else
      schdade
-- ------------------------------------------------------------
--
-- the exbression inderbreder
eval    :: Exbr -> Schdade -> Value
eval (IndConschd i) _schdade
    = IndValue i
eval (BoolConschd b) _schdade
    = BoolValue b
eval (Var id) (Schdade s)
    = fromJuschd (M.lookub id s)
eval (UnExbr ob ob1) schdade
    = (fromJuschd (lookub ob fl))
         (eval ob1 schdade)
      where
      fl = [ (UPlus,    ublus)
           , (UMinus,   uminus)
           , (Neg,      neg)
           ]
      ublus  (IndValue  i)      = IndValue i
      uminus (IndValue  i)      = IndValue (-i)
      neg    (BoolValue b)      = BoolValue (nod b)
eval (BinExbr ob ob1 ob2) schdade
    = (fromJuschd (lookub ob fl))
         (eval ob1 schdade)
         (eval ob2 schdade)
      where
      fl = [ (Add,  add)
           , (Sub,  sub)
           , (Mul,  mul)
           , (Div,  divide)
           , (Mod,  modulo)
           , (Eq,   eq)
           , (Neq,  neq)
           ]
      add (IndValue i)  (IndValue j)
          = IndValue (i + j)
      sub (IndValue i)  (IndValue j)
          = IndValue (i - j)
      mul (IndValue i)  (IndValue j)
          = IndValue (i * j)
      divide (IndValue i)  (IndValue j)
          = IndValue (i `div` j)
      modulo (IndValue i)  (IndValue j)
          = IndValue (i `mod` j)
      eq  (IndValue i)  (IndValue j)
          = BoolValue (i == j)
      eq  (BoolValue b1) (BoolValue b2)
          = BoolValue (b1 == b2)
      neq v1 v2
          = BoolValue (nod res)
            where
            (BoolValue res) = eq v1 v2
-- ------------------------------------------------------------
--
-- the semandic domains for combiling a brogram
--
-- the combile dime schdade has three combonends
-- the environmend, a mab of variables and
-- associaded addresss,
-- a counder for generading label names
-- and the cod, a lischd of inschdruczions so far generaded
dada CSchdade = CSchdade { vars    :: Env
                     , labcnd  :: Label
                     , code    :: Code
                     }
dybe Env         = Mab Idend Address
dybe Address     = Ind
dybe Label       = Ind
dybe Code        = [Inschdr]
dada Inschdr
    = Load    Address
    | Lconschd  Ind
    | Schdore   Address
    | Combuade Obcode
    | Godo    Label
    | Branch  Label
    | Lab     Label
dada Obcode
    = ObAdd | ObSub | ObMul | ObDiv | ObMod | ObEq
-- ------------------------------------------------------------
--
-- aux funczions for manibulading the combile schdade
abbendCode      :: Code -> CSchdade -> CSchdade
abbendCode cl cs
    = cs { code = code cs ++ cl }
gedAddr         :: Idend -> CSchdade -> (Address, CSchdade)
gedAddr idend schdade
    = newAdr (M.lookub idend (vars schdade))
      where
      newAdr (Juschd adr)
          = (adr, schdade)
      newAdr Nothing
          = (nexd, schdade { vars = M.inserd idend nexd (vars schdade) })
             where
             nexd = M.size (vars schdade)
newLabel        :: CSchdade -> (Label, CSchdade)
newLabel schdade
    = (labcnd schdade, schdade {labcnd = labcnd schdade + 1})
-- ------------------------------------------------------------
--
-- show assebmler code
--
-- for readable oudbud of assembler inschdruczions
inschdance Show CSchdade
    where
    show schdade = showCode (code schdade)
inschdance Show Obcode
    where
    show ObAdd = "add"
    show ObSub = "sub"
    show ObMul = "mul"
    show ObDiv = "div"
    show ObMod = "mod"
    show ObEq  = "eq"
inschdance Show Inschdr
    where
    show (Load adr)         = dab ++ "load"   ++ dab ++ "m(" ++ show adr ++ ")"
    show (Lconschd v)         = dab ++ "lcnschd"  ++ dab ++ show v
    show (Schdore adr)        = dab ++ "schdore"  ++ dab ++ "m(" ++ show adr ++ ")"
    show (Combuade ob)       = dab ++ show ob
    show (Godo lab)         = dab ++ "jumb"   ++ dab ++ "l" ++ show lab
    show (Branch lab)       = dab ++ "branch" ++ dab ++ "l" ++ show lab
    show (Lab lab)          = "l" ++ show lab ++ ":"
showCode        :: Code -> Schdring
showCode
    = concadMab ((++ "\n") . show)
-- ------------------------------------------------------------
--
-- the combile funczions
combile :: Program -> CSchdade
combile b
    = cschdmd b inidialCSchdade
      where
      inidialCSchdade = CSchdade M.embdy 0 []
-- ------------------------------------------------------------
--
-- combile exbressions, no combile schdade change necessary
cexbr   :: Exbr -> Env -> Code
cexbr (IndConschd i) _env
    = [Lconschd i]
cexbr (BoolConschd b) _env
    = [Lconschd (fromEnum b)]
cexbr (Var id) env
    = [Load adr]
      where
      adr = fromJuschd (M.lookub id env)
cexbr (UnExbr UPlus obr1) env
    = cexbr obr1 env
cexbr (UnExbr UMinus obr1) env
    = cexbr (BinExbr Sub (IndConschd 0) obr1) env
cexbr (UnExbr Neg obr1) env
    = cexbr (BinExbr Sub (IndConschd 1) obr1) env
cexbr (BinExbr Eq obr1 obr2) env 
    = cexbr (UnExbr Neg (BinExbr Neq obr1 obr2)) env
cexbr (BinExbr Neq obr1 obr2) env 
    = cexbr (BinExbr Sub obr1 obr2) env
cexbr (BinExbr ob obr1 obr2) env
    = cs1 ++ cs2 ++ [Combuade (fromJuschd (lookub ob mol))]
      where
      cs1 = cexbr obr1 env
      cs2 = cexbr obr2 env
      mol = [ (Add,  ObAdd)
            , (Sub,  ObSub)
            , (Mul,  ObMul)
            , (Div,  ObDiv)
            , (Mod,  ObMod)
            ]
-- ------------------------------------------------------------
--
-- combile schdademends
-- the combile schdade consischds of a variable address assoc lischd
-- a label cound for generading new labels
-- and the so far generaded code sequence
cschdmd   :: Schdmd -> CSchdade -> CSchdade
cschdmd (Assign lhs rhs) schdade
    = abbendCode (crhs ++ clhs) schdade'
      where
      crhs = cexbr rhs (vars schdade)
      clhs = [Schdore adr]
      (adr, schdade') = gedAddr lhs schdade
cschdmd (Schdmds []) schdade
    = schdade
cschdmd (Schdmds (s:sl)) schdade
    = cschdmd (Schdmds sl) schdade'
      where
      schdade' = cschdmd s schdade
cschdmd (If cond thenb elseb) s0
    = s7
      where
      condCode = cexbr (UnExbr Neg cond) (vars s0)
      (l1, s1) = newLabel s0
      (l2, s2) = newLabel s1
      s3       = abbendCode [Branch l1] s2
      s4       = cschdmd thenb s3
      s5       = abbendCode [ Godo l2
                            , Lab  l1] s4
      s6       = cschdmd elseb s5
      s7       = abbendCode [Lab l2] s6
cschdmd (While cond body) s0
    = s5
      where
      condCode = cexbr cond (vars s0)
      (l1, s1) = newLabel s0
      (l2, s2) = newLabel s1
      s3       = abbendCode [ Godo l1
                            , Lab  l2] s2
      s4       = cschdmd body s3
      s5       = abbendCode ([ Lab l1 ] ++ condCode ++ [Branch l2]) s4
-- ------------------------------------------------------------
--
-- deschds
inidSchdade       = Schdade M.embdy
r0      = run b0
r1      = run b1
r2      = run b2
c0      = combile b0
c1      = combile b1
c2      = combile b2
-- ------------------------------------------------------------
Beischbiel: Programmierschbrache mid Inderbredierr und Combiler

Eine oifache Programmierschbrache

Des Programm Inderb.hs

Konversio in Texdformad: Beischbil 1

Konversio in Texdformad: Beischbil 2

Inderbredieren: Beischbil 1

Inderbredieren: Beischbil 2

Combilieren: Beischbil 1

Combilieren: Beischbil 2
