module Simplify where import List import Grammar -------------------------------------------------------------------------------- -- Auxiliary Functions -------------------------------------------------------------------------------- map2nd f = map (\(a,b) -> (a,f b)) whileChange :: Eq a => (a -> a) -> a -> a whileChange f c = let c' = f c in if c == c' then c else whileChange f c' unite :: Eq a => [[a]] -> [a] unite = foldl union [] -------------------------------------------------------------------------------- -- Sort Functions -------------------------------------------------------------------------------- mergeSort :: Ord a => [a] -> [a] -> [a] mergeSort xa@(x:xs) ya@(y:ys) | x < y = x : mergeSort xs ya mergeSort xa@(x:xs) ya@(y:ys) | x > y = y : mergeSort xa ys mergeSort xa@(x:xs) ya@(y:ys) = x : y : mergeSort xs ys mergeSort xs [] = xs mergeSort [] ys = ys qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort [y | y<-xs, y=x] -------------------------------------------------------------------------------- -- DNF -------------------------------------------------------------------------------- -- get all variables get_vars :: Rule -> [Variable] get_vars (sts,s) = ["state"] `union` get_vars_stmt s get_vars_stmt :: Stmt -> [Variable] get_vars_stmt (IF css s) = unite (map (get_vars_cond . fst) css) `union` unite (map get_vars_stmt (s : map snd css)) get_vars_stmt (CASE v as s) = [v] `union` unite (map get_vars_stmt (s : map snd as)) get_vars_stmt (DECISION d u) = [] get_vars_cond :: Condition -> [Variable] get_vars_cond (AND cs) = unite (map get_vars_cond cs) get_vars_cond (OR cs) = unite (map get_vars_cond cs) get_vars_cond (EQUALS v i) = [v] -- count occurences and possible values of a variable count_vars :: Variable -> Rule -> (Int,[Int]) count_vars vn (sts,s) = let (o,vs) = count_vars_stmt vn s addstate "state" = sts `union` vs addstate _ = vs in (o,addstate vn) count_vars_stmt :: Variable -> Stmt -> (Int,[Int]) count_vars_stmt vn (IF css s) = add_all (map (count_vars_cond vn . fst) css) `add_count` add_all (map (count_vars_stmt vn) (s : map snd css)) count_vars_stmt vn (CASE v as s) = (if (v==vn) then (1 + length as,concat (map fst as)) else (0,[])) `add_count` add_all (map (count_vars_stmt vn) (s : map snd as)) count_vars_stmt vn (DECISION d u) = (0,[]) count_vars_cond :: Variable -> Condition -> (Int,[Int]) count_vars_cond vn (AND cs) = add_all (map (count_vars_cond vn) cs) count_vars_cond vn (OR cs) = add_all (map (count_vars_cond vn) cs) count_vars_cond vn (EQUALS v i) = if (v==vn) then (1,[i]) else (0,[]) add_all :: [(Int,[Int])] -> (Int,[Int]) add_all = foldl add_count (0,[]) add_count :: (Int,[Int]) -> (Int,[Int]) -> (Int,[Int]) add_count (o1,vs1) (o2,vs2) = (o1+o2 , vs1 `union` vs2) -- size of dnf, i.e. possible combinations of variables and values -- the value of a variable is either one of the occurences or something else size_of_dnf :: Rule -> Maybe Int size_of_dnf r = prod [ length vs + if (v=="state") then 0 else 1 | v <- get_vars r , let (o,vs) = count_vars v r ] where prod [] = Just 1 prod (x:xs) = case prod xs of Nothing -> Nothing Just p -> let p2 = x * p in if (p2 > 1024) then Nothing else Just p2 -- generate all possible combinations of variable values generate_combs :: Rule -> [[(Variable,Maybe Int)]] generate_combs r = gen_combs $ qsort (get_vars r) where gen_combs [] = [[]] gen_combs (x:xs) = let (o,vs) = count_vars x r in [ (x,v):cs | cs <- gen_combs xs , v <- Nothing : map Just vs ] eval_rule :: Rule -> [(Variable,Maybe Int)] -> Stmt eval_rule (sts,s) env = eval_stmt s env eval_stmt :: Stmt -> [(Variable,Maybe Int)] -> Stmt eval_stmt (IF ((c,s):css) def) env = if eval_cond c env then eval_stmt s env else eval_stmt (IF css def) env eval_stmt (IF [] def) env = eval_stmt def env eval_stmt (DECISION d u) env = DECISION d u eval_stmt (CASE v arms def) env = eval_stmt (eval_case (eval_var v env) arms def) env where eval_case val ((av,s):avs) def = if val `elem` map Just av then s else eval_case val avs def eval_case val [] def = def eval_cond :: Condition -> [(Variable,Maybe Int)] -> Bool eval_cond (EQUALS v i) env = eval_var v env == Just i eval_cond (AND cs) env = and [ eval_cond c env | c <- cs ] eval_cond (OR cs) env = or [ eval_cond c env | c <- cs ] eval_var :: Variable -> [(Variable,Maybe Int)] -> Maybe Int eval_var v env = head [ val | (var,val) <- env , var == v ] dnf_combs :: Rule -> [([(Variable,Maybe Int)],Stmt)] dnf_combs r = [ (comb , eval_rule r comb) | comb <- generate_combs r ] dnf :: Character -> [[([(Variable,Maybe Int)],Stmt)]] dnf = map dnf_combs opt_full :: Rule -> Rule opt_full = id -------------------------------------------------------------------------------- -- Size Function -------------------------------------------------------------------------------- size :: Character -> Int size = sum . map rule_size rule_size :: Rule -> Int rule_size = stmt_size . snd stmt_size :: Stmt -> Int stmt_size (IF alts stmt) = alts_size alts + stmt_size stmt stmt_size (DECISION (WILDCARD _) _) = 3 stmt_size (DECISION (STATE _) _) = 4 stmt_size (CASE v arms def) = 10 + stmt_size def + span_arms arms + arms_size arms arms_size :: [Arm] -> Int arms_size = sum . map arm_size arm_size :: Arm -> Int arm_size (ints, stmt) = stmt_size stmt alts_size :: [(Condition, Stmt)] -> Int alts_size [] = 0 alts_size (a:as) = alt_size a + alts_size as alt_size :: (Condition, Stmt) -> Int alt_size (c,s) = cond_size c + stmt_size s cond_size :: Condition -> Int cond_size (EQUALS v i) = 6 cond_size (AND tests) = sum (map cond_size tests) cond_size (OR tests) = sum (map cond_size tests) span_arms :: [Arm] -> Int span_arms [] = 0 span_arms as = span1 $ concat (map fst as) span1 :: [Int] -> Int span1 vs = maximum vs - minimum vs + 1 -------------------------------------------------------------------------------- -- Recursion Generators -------------------------------------------------------------------------------- map_stmt :: (Stmt -> Stmt) -> Stmt -> Stmt map_stmt f (IF alts stmt) = f (IF (map2nd (map_stmt f) alts) (map_stmt f stmt)) map_stmt f (DECISION s u) = f (DECISION s u) map_stmt f (CASE v arms def) = f (CASE v (map2nd (map_stmt f) arms) (map_stmt f def)) -------------------------------------------------------------------------------- -- Lift Functions -------------------------------------------------------------------------------- liftNewState :: (NewState -> NewState) -> Stmt -> Stmt liftNewState f (DECISION s u) = DECISION (f s) u liftNewState f stmt = stmt -------------------------------------------------------------------------------- -- Filling Wildcards -------------------------------------------------------------------------------- fill_wildcards :: Character -> Character fill_wildcards = map f where f (states,rule) = (states, (fill_wildcards' states) rule) fill_wildcards' states = map_stmt (liftNewState (fill_wildcard states)) fill_wildcard :: [Int] -> NewState -> NewState fill_wildcard s (WILDCARD _) = WILDCARD s fill_wildcard s x@_ = x -------------------------------------------------------------------------------- -- Changing States to Wildcards where possible -------------------------------------------------------------------------------- introduce_wildcards :: Character -> Character introduce_wildcards = map intro_wildcards_rule intro_wildcards_rule :: Rule -> Rule intro_wildcards_rule ([x],s) = ([x], intro_wildcards_stmt x s) intro_wildcards_rule (xs, s) = (xs, s) intro_wildcards_stmt :: Int -> Stmt -> Stmt intro_wildcards_stmt x = map_stmt (liftNewState (intro_wildcards x)) intro_wildcards :: Int -> NewState -> NewState intro_wildcards a (STATE b) = if a==b then (WILDCARD [b]) else STATE b intro_wildcards a (WILDCARD b) = WILDCARD b -------------------------------------------------------------------------------- -- Bring a Character to Normal Form, i.e. sort recursively -------------------------------------------------------------------------------- sort_character :: Character -> Character sort_character = map sort_rule sort_rule :: Rule -> Rule sort_rule (sts,s) = (qsort sts,sort_stmt s) sort_stmt :: Stmt -> Stmt sort_stmt (IF cs s) = IF [(sort_cond c,sort_stmt st) | (c,st) <- cs ] (sort_stmt s) sort_stmt (CASE v as s) = CASE v (qsort $ map sort_arm as) (sort_stmt s) sort_stmt (DECISION d u) = DECISION d u sort_arm :: Arm -> Arm sort_arm (vs,s) = (qsort vs,sort_stmt s) sort_cond :: Condition -> Condition sort_cond (AND cs) = AND (qsort (map sort_cond cs)) sort_cond (OR cs) = OR (qsort (map sort_cond cs)) sort_cond cond = cond all_equal :: Eq a => [a] -> Bool all_equal [] = True all_equal (x:xs) = and $ map (x==) xs -------------------------------------------------------------------------------- -- Merging Identical States -------------------------------------------------------------------------------- select :: [a] -> [(a,[a])] select [] = [] select (x:xs) = (x,xs) : map (\(a,bs) -> (a,x:bs)) (select xs) select2 :: Ord a => [a] -> [(a,a,[a])] select2 rs = [ (a,c,d) | (a,b) <- select rs , (c,d) <- select b, a [Rule] merge_rules rs = fst $ head $ dropWhile snd $ iterate find_merge_rules (rs,True) find_merge_rules :: ([Rule],Bool) -> ([Rule],Bool) find_merge_rules (xs,_) = case [ mr : rs | (r1,r2,rs) <- select2 xs , mr <- try_merge r1 r2, rule_size mr < rule_size r1 + rule_size r2 ] of ms:_ -> (ms,True) _ -> (xs,False) try_merge :: Rule -> Rule -> [Rule] try_merge (states1,stmt1) (states2,stmt2) = let states = states1++states2 in [(states,x) | x <- try_merge_stmts (states1,states2) stmt1 stmt2] try_merge_stmts :: ([Int],[Int]) -> Stmt -> Stmt -> [Stmt] try_merge_stmts sts (IF alts1 stmt1) (IF alts2 stmt2) = [ IF alts stmts | alts <- try_merge_alts sts alts1 alts2, stmts <- try_merge_stmts sts stmt1 stmt2 ] try_merge_stmts sts (CASE v1 arms1 def1) (CASE v2 arms2 def2) = [ CASE v1 arms def | v1==v2, arms <- try_merge_arms sts arms1 arms2, def <- try_merge_stmts sts def1 def2 ] try_merge_stmts (states1,states2) d1@(DECISION (STATE s1) u1) d2@(DECISION (STATE s2) u2) = if s1==s2 && u1==u2 then [ DECISION (STATE s1) u1 | s1==s2 , u1==u2 ] else [ IF [(make_condition "state" states1, d1)] d2 ] try_merge_stmts sts (DECISION (STATE s1) u1) (DECISION (WILDCARD ss) u2) = [ DECISION (STATE s1) u1 | [s1]==ss , u1==u2 ] try_merge_stmts sts (DECISION (WILDCARD ss) u1) (DECISION (STATE s2) u2) = [ DECISION (STATE s2) u2 | [s2]==ss , u1==u2 ] try_merge_stmts (states1,states2) d1@(DECISION (WILDCARD ss1) u1) d2@(DECISION (WILDCARD ss2) u2) = if u1==u2 then [ DECISION (WILDCARD (mergeSort ss1 ss2)) u1 | u1 == u2 ] else [ IF [(make_condition "state" states1, d1)] d2 ] try_merge_stmts (states1,states2) s1 s2 = [] -- IF [(make_condition "state" states1, s1)] s2 ] try_merge_alts :: ([Int],[Int]) -> [(Condition,Stmt)] -> [(Condition,Stmt)] -> [[(Condition,Stmt)]] try_merge_alts sts ((c1,s1):cs1) ((c2,s2):cs2) = [ (c,s) : cs | c <- try_merge_cond sts c1 c2 , s <- try_merge_stmts sts s1 s2 , cs <- try_merge_alts sts cs1 cs2 ] try_merge_alts sts [] [] = [[]] try_merge_alts sts _ _ = [] try_merge_arms :: ([Int],[Int]) -> [Arm] -> [Arm] -> [[Arm]] try_merge_arms sts ((vs1,s1):as1) ((vs2,s2):as2) = [ (vs1,s) : as | vs1==vs2 , s <- try_merge_stmts sts s1 s2 , as <- try_merge_arms sts as1 as2 ] try_merge_arms sts [] [] = [[]] try_merge_arms sts _ _ = [] try_merge_cond :: ([Int],[Int]) -> Condition -> Condition -> [Condition] try_merge_cond sts c1 c2 = [ c1 | c1 == c2 ] -- 1: STATE 1 + 2,3 : WILDCARD [2,3] -> 1,2,3: WILDCARD [1,2,3] -- faellt weg, wenn zuerst alle STATE in WILDCARD gehen falls moeglich -- 1: WILDCARD + 2,3 : STATE 1 -> 1,2,3: STATE 1 -------------------------------------------------------------------------------- -- Propagating Context Information -------------------------------------------------------------------------------- data VarInfo = Pos [Int] | Neg [Int] deriving (Eq,Ord,Show) type Info = [(Variable,VarInfo)] no_info = [] false_info = [("state",Pos [])] true_info = [("state",Neg [])] propagate :: Info -> Stmt -> Stmt propagate info (IF alts stmt) = elim_cond (IF alts' stmt') where (alts',info') = propagate_alts info alts stmt' = propagate info' stmt propagate info (DECISION s u) = DECISION s u propagate info (CASE v arms def) = elim_case info (CASE v arms' def') where (arms',info') = propagate_arms v info arms def' = propagate info' def propagate_alts :: Info -> [(Condition,Stmt)] -> ([(Condition,Stmt)], Info) propagate_alts info [] = ([],info) propagate_alts info ((c,s):as) = let result = check_condition info c in case result of Yes -> ([(AND [], propagate info s)], no_info) No -> propagate_alts info as Maybe -> ((c,propagate info1 s) : as', info') where (as',info') = propagate_alts info0 as info1 = add_info info c info0 = add_info info (NOT c) propagate_arms :: Variable -> Info -> [Arm] -> ([Arm],Info) -- Parameters: - the variable used in the case statement -- - the current information -- - the list of "arms" to be optimized propagate_arms var info [] = ([],info) propagate_arms var info ((values,s):as) = let result = check_condition info (make_condition var values) in case result of Yes -> ([(values, propagate info s)], no_info) No -> propagate_arms var info as Maybe -> ((values,propagate info1 s) : as', info') where (as',info') = propagate_arms var info0 as info1 = add_info info cond info0 = add_info info (NOT cond) cond = make_condition var values -- Constructing a condition from a variable and a value set make_condition :: Variable -> [Int] -> Condition make_condition var [] = OR [] make_condition var [x] = EQUALS var x make_condition var xs = OR (map (EQUALS var) xs) -- Updating the Information about a variable update_info :: (VarInfo -> VarInfo) -> Variable -> Info -> Info update_info f var [] = [(var , f (Neg []))] update_info f var ((v,vi):vs) = if v == var then (v,f vi) : vs else (v,vi) : update_info f var vs -- Adding Information to Info Packets add_info :: Info -> Condition -> Info add_info infos (EQUALS var x) = update_info f var infos where f (Pos xs) = Pos ([x] `intersect` xs) f (Neg xs) = if x `elem` xs then (Pos []) else (Pos [x]) add_info infos (AND []) = infos add_info infos (AND (c:cs)) = let rec_infos = map (add_info infos) (c:cs) in foldl1 and_info rec_infos add_info infos (OR []) = false_info add_info infos (OR (c:cs)) = let rec_infos = map (add_info infos) (c:cs) in foldl1 or_info rec_infos add_info infos (NOT (EQUALS var x)) = update_info f var infos where f (Pos xs) = Pos (delete x xs) f (Neg xs) = Neg ([x] `union` xs) add_info infos (NOT (AND cs)) = add_info infos (OR (map NOT cs)) -- changed ! add_info infos (NOT (OR cs)) = add_info infos (AND (map NOT cs)) -- changed ! or_info :: Info -> Info -> Info or_info infos1 infos2 = ori (qsort infos1) (qsort infos2) where ori [] vs = [] ori vs [] = [] ori ((v1,vi1):vs1) ((v2,vi2):vs2) | v1 < v2 = ori vs1 ((v2,vi2):vs2) ori ((v1,vi1):vs1) ((v2,vi2):vs2) | v1 > v2 = ori ((v1,vi1):vs1) vs2 ori ((v1,vi1):vs1) ((v2,vi2):vs2) = (v1,orvi vi1 vi2) : ori vs1 vs2 orvi (Pos xs1) (Pos xs2) = Pos (xs1 `union` xs2) orvi (Pos xs1) (Neg xs2) = Neg (xs2 \\ xs1) orvi (Neg xs1) (Pos xs2) = Neg (xs1 \\ xs2) orvi (Neg xs1) (Neg xs2) = Neg (xs1 `intersect` xs2) and_info :: Info -> Info -> Info and_info infos1 infos2 = andi (qsort infos1) (qsort infos2) where andi [] vs = vs andi vs [] = vs andi ((v1,vi1):vs1) ((v2,vi2):vs2) | v1 < v2 = (v1,vi1) : andi vs1 ((v2,vi2):vs2) andi ((v1,vi1):vs1) ((v2,vi2):vs2) | v1 > v2 = (v2,vi2) : andi ((v1,vi1):vs1) vs2 andi ((v1,vi1):vs1) ((v2,vi2):vs2) = (v1,andvi vi1 vi2) : andi vs1 vs2 andvi (Pos xs1) (Pos xs2) = Pos (xs1 `intersect` xs2) andvi (Pos xs1) (Neg xs2) = Pos (xs1 \\ xs2) andvi (Neg xs1) (Pos xs2) = Pos (xs2 \\ xs1) andvi (Neg xs1) (Neg xs2) = Neg (xs1 `union` xs2) uci = map (\(states,stmt) -> (states, propagate (gen_state_info states) stmt)) gen_state_info :: [Int] -> Info gen_state_info sts = [("state",Pos sts)] -------------------------------------------------------------------------------- -- Elimination of Conditionals -------------------------------------------------------------------------------- elim_cond :: Stmt -> Stmt elim_cond (IF [] def) = def elim_cond (IF alts def) = let alts' = elim_alts alts in case alts' of [] -> def _ -> let (c,s) = last alts' in if (c == AND []) then IF (init alts') s else IF alts' def elim_cond stmt = stmt elim_alts :: [Alt] -> [Alt] elim_alts [] = [] elim_alts ((AND [],s):_) = [(AND [],s)] elim_alts ((OR [],s):alts) = elim_alts alts elim_alts ((c ,s):alts) = (c,s) : elim_alts alts -------------------------------------------------------------------------------- -- Elimination of Case Statements -------------------------------------------------------------------------------- elim_case :: Info -> Stmt -> Stmt elim_case _ (CASE var [] def) = def elim_case info c@(CASE var [(values,stmt)] def) = if (check_condition info (make_condition var values) == Yes) then stmt else c elim_case _ stmt = stmt elim_equal_cases :: Stmt -> Stmt elim_equal_cases stmt@(CASE v arms def) = if all_equal (def : (map snd arms)) then def else stmt elim_equal_cases stmt = stmt elim_equal_ifs :: Stmt -> Stmt elim_equal_ifs stmt@(IF alts def) = if all_equal (def : (map snd alts)) then def else stmt elim_equal_ifs stmt = stmt elim_double_arms_stmt :: Stmt -> Stmt elim_double_arms_stmt (CASE v arms def) = CASE v (elim_double_arms arms) def elim_double_arms_stmt stmt = stmt elim_double_arms :: [Arm] -> [Arm] elim_double_arms [] = [] elim_double_arms (a:as) = if snd a `elem` (map snd as) then elim_double_arms (add_arm a as) else a : elim_double_arms as add_arm :: Arm -> [Arm] -> [Arm] add_arm a [] = error "arm not found" add_arm a (b:bs) = if snd a == snd b then (union (fst a) (fst b), snd b) : bs else b : add_arm a bs -------------------------------------------------------------------------------- -- Evaluating Conditions with given information -------------------------------------------------------------------------------- data Answer = No | Maybe | Yes deriving (Eq,Show,Ord) check_condition :: Info -> Condition -> Answer check_condition info (AND conds) = fst (foldl f (Yes,info) conds) where f (a,i) c = (min a (check_condition i c) , add_info i c) check_condition info (OR conds) = fst (foldl f (No,info) conds) where f (a,i) c = (max a (check_condition i c), add_info i (NOT c)) {- check_condition info (OR conds) = let answers = map (check_condition info) conds in if any (Yes==) answers then Yes else if all (No==) answers then No else Maybe -} check_condition ((v,vi):vs) (EQUALS var val) | v==var = case vi of Pos [x] -> if val==x then Yes else No Pos xs -> if val `elem` xs then Maybe else No Neg xs -> if val `elem` xs then No else Maybe check_condition (_:vs) c = check_condition vs c check_condition [] _ = Maybe -------------------------------------------------------------------------------- -- Case to If Transformation -------------------------------------------------------------------------------- case_to_if :: Stmt -> Stmt case_to_if stmt@(CASE v arms def) = let stmt' = IF (map (arm_to_alt v) arms) def in if stmt_size stmt' < stmt_size stmt then stmt' else stmt case_to_if stmt = stmt arm_to_alt :: Variable -> Arm -> Alt arm_to_alt var (valueset, stmt) = (make_condition var valueset, stmt) -------------------------------------------------------------------------------- -- Test Characters -------------------------------------------------------------------------------- ch :: Character ch = [([1], DECISION (WILDCARD []) ""), ([2], DECISION (WILDCARD []) "")] ch2 :: Character ch2 = [([1], CASE "s" [([1,2,3,200000], (DECISION (WILDCARD []) "hi"))] (DECISION (WILDCARD []) "ho"))] ch2b :: Character ch2b = [([1], CASE "s" [([1,2,3,200000], (DECISION (WILDCARD []) "hi"))] (CASE "s" [([1,2,3,200000], (DECISION (WILDCARD []) "hi"))] (DECISION (WILDCARD []) "ho")))] ch4 :: Character ch4 = [([1], CASE "state" [([1], (DECISION (WILDCARD []) "hi"))] (DECISION (WILDCARD []) "ho"))] ch3 :: Character ch3 = [([1], IF [(EQUALS "z" 5, IF [(AND [EQUALS "y" 7, EQUALS "x" 6], DECISION (STATE 1) "u")] (DECISION (STATE 2) ""))] (DECISION (STATE 3) "") ), ([2], IF [(EQUALS "z" 5, IF [(AND [EQUALS "x" 6, EQUALS "y" 7], DECISION (STATE 1) "u")] (DECISION (STATE 2) ""))] (DECISION (STATE 3) "") ) ] ch5 :: Character ch5 = [ ([3], IF [(EQUALS "state" 1, DECISION (STATE 5) ""),(EQUALS "v" 1, DECISION (STATE 3) "")] (DECISION (STATE 3) "") ) ] ch6 :: Character ch6 = [ ([7], CASE "v" [([1], DECISION (WILDCARD []) ""), ([2,3], DECISION (WILDCARD []) ""), ([4], DECISION (WILDCARD []) "")] (DECISION (WILDCARD []) "") )] ch7 :: Character ch7 = [ ([1,3,5,2], IF [(EQUALS "state" 2, DECISION (STATE 10) ""), (OR [EQUALS "state" 3, EQUALS "state" 1, EQUALS "state" 5], DECISION (STATE 10) "")] (DECISION (STATE 11) "") )] ch8 :: Character ch8 = [ ([1,3], IF [(OR [EQUALS "state" 3, EQUALS "state" 1], DECISION (STATE 10) "")] (DECISION (STATE 11) "") )] ch9 :: Character ch9 = [ ([1,3,5,2], CASE "v" [([1], DECISION (STATE 77) ""), ([2], IF [(EQUALS "state" 2, DECISION (STATE 10) ""), (OR [EQUALS "state" 3, EQUALS "state" 1, EQUALS "state" 5], DECISION (STATE 10) "")] (DECISION (STATE 11) "") )] (DECISION (STATE 99) "") )] -------------------------------------------------------------------------------- -- Main Algorithm -------------------------------------------------------------------------------- opt_character :: Character -> Character opt_character = whileChange opt opt :: Character -> Character opt = qsort . merge_rules . (map2nd (map_stmt (case_to_if . elim_equal_ifs . elim_double_arms_stmt . elim_equal_cases ))) . uci init_character :: Character -> Character init_character = sort_character . introduce_wildcards . fill_wildcards o = opt_character . init_character