toy_compiler.mlw 2.04 KB
Newer Older
MARCHE Claude's avatar
MARCHE Claude committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78


theory Expr

  use import int.Int

  type expr = Cte int | Plus expr expr | Minus expr expr | Mult expr expr

  function eval_expr (e:expr) : int =
    match e with
    | Cte n -> n
    | Plus e1 e2 -> eval_expr e1 + eval_expr e2
    | Minus e1 e2 -> eval_expr e1 - eval_expr e2
    | Mult e1 e2 -> eval_expr e1 * eval_expr e2
    end

end

theory StackMachine

  type asm = Push int | Add | Sub | Mul

  use export int.Int
  use export list.List

  function compute (s:list int) (a:list asm) : list int =
    match a with
    | Nil -> s
    | Cons a r ->
      match a,s with
      | Push n, _                  -> compute (Cons n s) r
      | Add, (Cons n1 (Cons n2 s)) -> compute (Cons (n2+n1) s) r
      | Sub, (Cons n1 (Cons n2 s)) -> compute (Cons (n2-n1) s) r
      | Mul, (Cons n1 (Cons n2 s)) -> compute (Cons (n2*n1) s) r
      | _ -> s
      end
    end

end


module Compiler
  
  use export list.Append
  use import Expr
  use import StackMachine
  
  function compile (e:expr) : list asm =
    match e with
    | Cte n -> Cons (Push n) Nil
    | Plus e1 e2 -> compile e1 ++ (compile e2 ++ Cons Add Nil)
    | Minus e1 e2 -> compile e1 ++ (compile e2 ++ Cons Sub Nil)
    | Mult e1 e2 -> compile e1 ++ (compile e2 ++ Cons Mul Nil)
    end

  let rec lemma soundness_gen (e:expr) (s:list int) (r:list asm)
    variant { e }
    ensures { compute s (compile e ++ r) = compute (Cons (eval_expr e) s) r }
  = match e with
    | Cte n -> 
      assert { compile e ++ r = Cons (Push n) r }
    | Plus e1 e2 ->
      soundness_gen e1 s (compile e2 ++ Cons Add r);
      soundness_gen e2 (Cons (eval_expr e1) s) (Cons Add r)
    | Minus e1 e2 ->
      soundness_gen e1 s (compile e2 ++ Cons Sub r);
      soundness_gen e2 (Cons (eval_expr e1) s) (Cons Sub r)
    | Mult e1 e2 ->
      soundness_gen e1 s (compile e2 ++ Cons Mul r);
      soundness_gen e2 (Cons (eval_expr e1) s) (Cons Mul r)
    end
  
  let lemma soundness (e:expr)
    ensures { compute Nil (compile e) = (Cons (eval_expr e) Nil) }
  =
    assert { compute Nil (compile e) = compute Nil (compile e ++ Nil) }

end