Links und Funktionen
Sprachumschaltung

Navigationspfad


Inhaltsbereich

ae.ml

OCaml source code icon ae.ml — OCaml source code, 9 KB (9806 bytes)

Dateiinhalt

(* Syntax der while-Sprache *)
type variable = string
type label = int

type expression = 
  | Const of int
  | Variable of variable
  | BinOp of string * expression * expression
  (* Hier koennten noch weitere Faelle stehen. *)                                     

type cond_expression = 
  | Lt of expression * expression 
  | Eq of expression * expression 
  | Gt of expression * expression 
  | And of cond_expression * cond_expression 
  (* Hier koennten noch weitere Faelle stehen. *)                                     

(* Es wird angenommen, dass jedes Label nur einmal vorkommt. *)
type program =
  | Skip of label
  | Assignment of variable * expression * label
  | Seq of program * program
  | If of cond_expression * label * program * program
  | While of cond_expression * label * program

let rec basicBlocks (p : program) =
  match p with 
  | Skip(l) -> [(l, p)]
  | Assignment(x, a, l) -> [(l, p)]
  | Seq(p1, p2) -> (basicBlocks p1) @ (basicBlocks p2)
  | If(_, l, p1, p2) -> (l, p) :: (basicBlocks p1) @ (basicBlocks p2)
  | While(_, l, p1) -> (l, p) :: basicBlocks p1

let rec print_expression (e: expression) =
  match e with
  | Const(i) -> print_int i
  | Variable(x) -> print_string x
  | BinOp(op, el, er) -> 
      print_string "("; 
      print_expression el;
      print_string (" " ^ op ^ " ");
      print_expression er;
      print_string ")"

(* Das Programm
 * [x := a + b]^1; [y := a * b]^2; while [y < a + b]^3 do ([a := a + 1]^4; [x := a + b]^5)
 * kann folgendermassen repraesentiert werden:
 *)
let exampleProgram =
  Seq(Assignment("x", BinOp("+", Variable "a", Variable "b"), 1),
      Seq(Assignment("y", BinOp("*", Variable "a", Variable "b"), 2),
          While(Gt(Variable "y", BinOp("+", Variable "a", Variable "b")), 3,
                Seq(Assignment("a", BinOp("+", Variable "a", Const 1), 4),
                    Assignment("x", BinOp("+", Variable "a", Variable "b"), 5)
                )
          )
      )
  )

(* Als naechstes schreiben wir Funktionen zur Berechnung des
 * Kontrollflussgraphen *)    

type graph = {init: label; edges: ((label * label) list); exits: label list}

let rec controlFlowGraph (p : program) : graph =
  match p with 
  | Skip(l) -> {init = l; edges = []; exits = [l]}
  | Assignment(x,a,l) -> {init = l; edges = []; exits = [l]}
  | Seq(p1, p2) -> 
      let g1 = controlFlowGraph p1 in
      let g2 = controlFlowGraph p2 in
        {init = g1.init;
         edges = (g1.edges) @ (g2.edges) @ (List.map (fun l -> (l, g2.init)) g1.exits);
         exits = g2.exits}
  | If(b, l, p1, p2) -> 
      let g1 = controlFlowGraph p1 in
      let g2 = controlFlowGraph p2 in
        {init = l;
         edges = (g1.edges) @ (g2.edges) @ [(l, g1.init); (l, g2.init)];
         exits = (g1.exits) @ (g2.exits)}
  | While(b, l, p) -> 
      let g = controlFlowGraph p in
        {init = l;
         edges = (l, g.init) :: (g.edges) @ (List.map (fun e -> (e, l)) g.exits);
         exits = [l]}

let predecessors (g: graph) (l: label) =          
  let incomingEdges = List.filter (fun (_, l2) -> l2 = l) g.edges in
    List.map fst incomingEdges

(* Fuer AE muessen wir mit Mengen von Ausdruecken arbeiten und wir mussen
 * aus einem gegebenen Programm die darin vorkommenden Ausdruecke extrahieren.
 * Dafuer benutzen wir die folgenden Funktionen.*)

module ExpSet = Set.Make (struct 
                            type t = expression 
                            let compare = compare 
                          end)
                  
let print_expression_set a = 
  let comma = ref false in  
    print_string "{";
    ExpSet.iter (fun e -> 
                   if !comma then print_string ", " else comma := true;
                   print_expression e) a;
    print_string "}"

let intersection (sets : ExpSet.t list) all =
  List.fold_right ExpSet.inter sets all

let rec variables (e : expression) : variable list =  
  match e with
  | Const(i) -> []
  | Variable(x) -> [x]
  | BinOp(_, e1, e2) -> (variables e1) @ (variables e2)

let rec subExpressions (e : expression) : ExpSet.t =  
  match e with
  | Const(_) | Variable(_) -> ExpSet.empty
       (* ExpSet.singleton e*)
  | BinOp(_, e1, e2) -> ExpSet.add e (ExpSet.union (subExpressions e1) (subExpressions e2))

let rec subExpressionsOfExpSet (set : ExpSet.t) : ExpSet.t = 
  ExpSet.fold (fun e a -> ExpSet.union (subExpressions e) a) set ExpSet.empty 

let rec expressionsInCond (c : cond_expression) =
  match c with 
    | Lt(e1, e2) | Gt(e1, e2) | Eq(e1, e2) ->
        ExpSet.union (ExpSet.singleton e1) (ExpSet.singleton e2) 
    | And(c1, c2) -> 
        ExpSet.union (expressionsInCond c1) (expressionsInCond c2)

let rec expressionsInProgram (p : program) : ExpSet.t =
  match p with 
  | Skip(l) -> ExpSet.empty
  | Assignment(x,a,l) -> ExpSet.singleton a
  | Seq(p1, p2) -> ExpSet.union (expressionsInProgram p1) (expressionsInProgram p2)
  | If(c, l, p1, p2) -> 
      ExpSet.union (expressionsInCond c)
        (ExpSet.union (expressionsInProgram p1) (expressionsInProgram p2))
  | While(c, l, p) -> 
      ExpSet.union (expressionsInCond c) (expressionsInProgram p) 

(* Mit diesen Funktionen koennen wir die Mengen der verfuegbaren
 * Ausdruecke nun mit der folgenden Funktion flowAE ausrechnen *)

module Tbl = Hashtbl.Make (struct 
                            type t = label
                            let equal = (=)
                            let hash = Hashtbl.hash
                          end)

let flowAE p =
  (* Die Menge alle Teilausdruecke im Programm *)
  let allExps = subExpressionsOfExpSet (expressionsInProgram p) in
  (* Kontrollflussgraph und Programmbloecke *)
  let cfgraph = controlFlowGraph p in
  let blocks = basicBlocks p in
  let labels = List.map fst blocks in
  (* Tabelle mit Eintraegen fuer AEexit(l) und AEentry(l). 
   * Jeder Eintrag wird mit der Menge aller Ausdruecke initialisiert. *)
  let tableAEentry = Tbl.create (List.length blocks) in
  let tableAEexit = Tbl.create (List.length blocks) in
    List.iter (fun l -> 
                 Tbl.add tableAEentry l allExps;
                 Tbl.add tableAEexit l allExps)
      labels;
  (* Die Funktionen kill und gen aus der Vorlesung *)
  let kill l =
    let b = List.assoc l blocks in
      match b with
        | Assignment(x, a, l) -> 
            ExpSet.filter (fun b -> List.mem x (variables b)) allExps 
        | _ -> ExpSet.empty in
  let gen l =
    let b = List.assoc l blocks in
      match b with
        | Assignment(x,a,l) ->  
            ExpSet.filter (fun b -> not (List.mem x (variables a))) (subExpressions a)
        | If(c, _, _, _) -> subExpressionsOfExpSet (expressionsInCond c)
        | While(c, _, _) -> subExpressionsOfExpSet (expressionsInCond c)
        | _ -> ExpSet.empty in
  (* Die Gleichungen fuer AEentry und AEexit *)
  let eqAEentry l =
    if l = cfgraph.init then 
      ExpSet.empty
    else
      let preds = predecessors cfgraph l in
      let incomingAEs = List.map (Tbl.find tableAEexit) preds in
        intersection incomingAEs allExps in
  let eqAEexit l =
    ExpSet.union (ExpSet.diff (Tbl.find tableAEentry l) (kill l)) (gen l) in
   (* kill/gen-Tabellen ausgeben *)
    List.iter (fun l -> print_string "kill("; print_int l; print_string ") = ";
                        print_expression_set (kill l);
                        print_string "\n") labels;
    List.iter (fun l -> print_string "gen("; print_int l; print_string ") = ";
                        print_expression_set (gen l);
                        print_string "\n") labels;
  let print_tables () =
    Tbl.iter (fun l a -> print_string "AE_entry("; print_int l; print_string ") = ";
                         print_expression_set a;
                         print_string "\n") tableAEentry;
    Tbl.iter (fun l a -> print_string "AE_exit("; print_int l; print_string ") = ";
                         print_expression_set a;
                         print_string "\n") tableAEexit in
  print_string "\n\nAnfangstabelle:\n"; print_tables ();
  (* Wende nun die Gleichungen fuer AEentry und AEexit so lange auf
   * die Tabelle an, bis sich nichts mehr aendert. *)
  let changed = ref true in
    while !changed = true do
      changed := false;
      List.iter 
        (fun l ->
           let entry = Tbl.find tableAEentry l in
           let entry' = eqAEentry l in 
             Tbl.replace tableAEentry l entry'; 
             let exit = Tbl.find tableAEexit l  in
             let exit' = eqAEexit l in 
               Tbl.replace tableAEexit l exit'; 
               changed := !changed || (not (ExpSet.equal entry entry')) || (not (ExpSet.equal exit exit'))
        ) labels;
      print_string "\nIteration der Gleichungen liefert folgende Tabelle:\n"; print_tables ()
    done;
    print_string "\nTabelle hat sich in der letzten Iteration nicht geaendert\n";
    print_string "und ist somit das Endergebnis.\n\n"

let aufgabe10_2 =
  let x = Variable "x" in
  let y = Variable "y" in
  let z = Variable "z" in
  let i = Variable "i" in
  let cx = Variable "cx" in
  let cy = Variable "cy" in
  let xmx = BinOp("*", x, x) in
  let ymy = BinOp("*", y, y) in
  While(And(Lt(BinOp("+", xmx, ymy), Const 4), Lt(i, Const 50)), 1,
        Seq(Assignment("z", BinOp("+", BinOp("-", xmx, ymy), cx), 2),
            Seq(Assignment("y", BinOp("-", BinOp("*", BinOp("*", Const 2, x), y), cy), 3),
                Seq(Assignment("x", z, 4),
                    Assignment("i", BinOp("+", i, Const 1), 5)
                )
            )
        )
  )

let _ = 
  print_string 
    ("Im Folgenden werden die AE-Mengen fuer Aufgabe 10-2 berechnet.\n" ^
     "Dabei wird die Definition\n" ^
     "  gen([x:=a]^l) = {b | b ist Teilausdruck von a und x 'notin' FV(a)}" ^
     "aus der Vorlesung benutzt.\n");
  print_string "Aufgabe 10-2:\n";
  flowAE aufgabe10_2

Artikelaktionen


Funktionsleiste