src/HOL/Complex/ex/linreif.ML
changeset 23515 3e7f62e68fe4
parent 23317 90be000da2a7
child 23808 4e4b92e76219
equal deleted inserted replaced
23514:25e69e56355d 23515:3e7f62e68fe4
     1 (* 
     1 (*  ID:         $Id$
     2  The oracle for Mixed Real-Integer auantifier elimination 
     2     Author:     Amine Chaieb, TU Muenchen
     3      based on the verified Code in ~/work/MIR/MIR.thy 
     3 
       
     4 The oracle for Mixed Real-Integer auantifier elimination
       
     5 based on the verified Code in ~/work/MIR/MIR.thy.
     4 *)
     6 *)
     5 
     7 
     6 structure ReflectedFerrack =
     8 structure ReflectedFerrack =
     7 struct
     9 struct
     8 
    10 
     9 open Ferrack;
    11 open Ferrack;
       
    12 open ReflectedFerrack
    10 
    13 
    11 exception LINR;
    14 exception LINR;
    12 
    15 
    13 (* pseudo reification : term -> intterm *)
    16 (* pseudo reification : term -> intterm *)
    14 val iT = HOLogic.intT;
    17 val iT = HOLogic.intT;
    18 val rzero = Const("0",rT);
    21 val rzero = Const("0",rT);
    19 
    22 
    20 fun num_of_term vs t = 
    23 fun num_of_term vs t = 
    21     case t of
    24     case t of
    22 	Free(xn,xT) => (case AList.lookup (op =) vs t of 
    25 	Free(xn,xT) => (case AList.lookup (op =) vs t of 
    23 			   NONE   => error "Variable not found in the list!!"
    26 			   NONE   => error "Variable not found in the list!"
    24 			 | SOME n => Bound n)
    27 			 | SOME n => Bound n)
    25       | Const("RealDef.real",_)$ @{term "0::int"} => C 0
    28       | Const("RealDef.real",_)$ @{term "0::int"} => C 0
    26       | Const("RealDef.real",_)$ @{term "1::int"} => C 1
    29       | Const("RealDef.real",_)$ @{term "1::int"} => C 1
    27       | @{term "0::real"} => C 0
    30       | @{term "0::real"} => C 0
    28       | @{term "0::real"} => C 1
    31       | @{term "0::real"} => C 1
    29       | Term.Bound i => Bound (nat i)
    32       | Term.Bound i => Bound (Integer.nat i)
    30       | Const(@{const_name "HOL.uminus"},_)$t' => Neg (num_of_term vs t')
    33       | Const(@{const_name "HOL.uminus"},_)$t' => Neg (num_of_term vs t')
    31       | Const (@{const_name "HOL.plus"},_)$t1$t2 => Add (num_of_term vs t1,num_of_term vs t2)
    34       | Const (@{const_name "HOL.plus"},_)$t1$t2 => Add (num_of_term vs t1,num_of_term vs t2)
    32       | Const (@{const_name "HOL.minus"},_)$t1$t2 => Sub (num_of_term vs t1,num_of_term vs t2)
    35       | Const (@{const_name "HOL.minus"},_)$t1$t2 => Sub (num_of_term vs t1,num_of_term vs t2)
    33       | Const (@{const_name "HOL.times"},_)$t1$t2 => 
    36       | Const (@{const_name "HOL.times"},_)$t1$t2 => 
    34 	(case (num_of_term vs t1) of C i => 
    37 	(case (num_of_term vs t1) of C i => 
    42 (* pseudo reification : term -> fm *)
    45 (* pseudo reification : term -> fm *)
    43 fun fm_of_term vs t = 
    46 fun fm_of_term vs t = 
    44     case t of 
    47     case t of 
    45 	Const("True",_) => T
    48 	Const("True",_) => T
    46       | Const("False",_) => F
    49       | Const("False",_) => F
    47       | Const(@{const_name "Orderings.less"},_)$t1$t2 => Lt (Sub (num_of_term vs t1,num_of_term vs t2))
    50       | Const(@{const_name "Orderings.less"},_)$t1$t2 => Lta (Sub (num_of_term vs t1,num_of_term vs t2))
    48       | Const(@{const_name "Orderings.less_eq"},_)$t1$t2 => Le (Sub (num_of_term vs t1,num_of_term vs t2))
    51       | Const(@{const_name "Orderings.less_eq"},_)$t1$t2 => Lea (Sub (num_of_term vs t1,num_of_term vs t2))
    49       | Const("op =",eqT)$t1$t2 => 
    52       | Const("op =",eqT)$t1$t2 => 
    50 	if (domain_type eqT = rT)
    53 	if (domain_type eqT = rT)
    51 	then Eq (Sub (num_of_term vs t1,num_of_term vs t2)) 
    54 	then Eqa (Sub (num_of_term vs t1,num_of_term vs t2)) 
    52 	else Iff(fm_of_term vs t1,fm_of_term vs t2)
    55 	else Iffa(fm_of_term vs t1,fm_of_term vs t2)
    53       | Const("op &",_)$t1$t2 => And(fm_of_term vs t1,fm_of_term vs t2)
    56       | Const("op &",_)$t1$t2 => And(fm_of_term vs t1,fm_of_term vs t2)
    54       | Const("op |",_)$t1$t2 => Or(fm_of_term vs t1,fm_of_term vs t2)
    57       | Const("op |",_)$t1$t2 => Or(fm_of_term vs t1,fm_of_term vs t2)
    55       | Const("op -->",_)$t1$t2 => Imp(fm_of_term vs t1,fm_of_term vs t2)
    58       | Const("op -->",_)$t1$t2 => Impa(fm_of_term vs t1,fm_of_term vs t2)
    56       | Const("Not",_)$t' => NOT(fm_of_term vs t')
    59       | Const("Not",_)$t' => Nota(fm_of_term vs t')
    57       | Const("Ex",_)$Term.Abs(xn,xT,p) => 
    60       | Const("Ex",_)$Term.Abs(xn,xT,p) => 
    58 	E(fm_of_term (map (fn(v,n) => (v,1+ n)) vs) p)
    61 	E(fm_of_term (map (fn(v,n) => (v,1+ n)) vs) p)
    59       | Const("All",_)$Term.Abs(xn,xT,p) => 
    62       | Const("All",_)$Term.Abs(xn,xT,p) => 
    60 	A(fm_of_term (map (fn(v,n) => (v,1+ n)) vs) p)
    63 	A(fm_of_term (map (fn(v,n) => (v,1+ n)) vs) p)
    61       | _ => error ("fm_of_term : unknown term!" ^ (Display.raw_string_of_term t));
    64       | _ => error ("fm_of_term : unknown term!" ^ (Display.raw_string_of_term t));
    64   | zip (x::xs) (y::ys) = (x,y)::(zip xs ys);
    67   | zip (x::xs) (y::ys) = (x,y)::(zip xs ys);
    65 
    68 
    66 
    69 
    67 fun start_vs t =
    70 fun start_vs t =
    68     let val fs = term_frees t
    71     let val fs = term_frees t
    69     in zip fs (map nat (0 upto  (length fs - 1)))
    72     in zip fs (map Integer.nat (0 upto  (length fs - 1)))
    70     end ;
    73     end ;
    71 
    74 
    72 (* transform num and fm back to terms *)
    75 (* transform num and fm back to terms *)
    73 
    76 
    74 fun myassoc2 l v =
    77 fun myassoc2 l v =
    86 			   (term_of_num vs t1)$(term_of_num vs t2)
    89 			   (term_of_num vs t1)$(term_of_num vs t2)
    87       | Sub(t1,t2) => Const(@{const_name "HOL.minus"},[rT,rT] ---> rT)$
    90       | Sub(t1,t2) => Const(@{const_name "HOL.minus"},[rT,rT] ---> rT)$
    88 			   (term_of_num vs t1)$(term_of_num vs t2)
    91 			   (term_of_num vs t1)$(term_of_num vs t2)
    89       | Mul(i,t2) => Const(@{const_name "HOL.times"},[rT,rT] ---> rT)$
    92       | Mul(i,t2) => Const(@{const_name "HOL.times"},[rT,rT] ---> rT)$
    90 			   (term_of_num vs (C i))$(term_of_num vs t2)
    93 			   (term_of_num vs (C i))$(term_of_num vs t2)
    91       | CN(n,i,t) => term_of_num vs (Add (Mul(i,Bound n),t));
    94       | Cn(n,i,t) => term_of_num vs (Add (Mul(i,Bound n),t));
    92 
    95 
    93 fun term_of_fm vs t = 
    96 fun term_of_fm vs t = 
    94     case t of 
    97     case t of 
    95 	T => HOLogic.true_const 
    98 	T => HOLogic.true_const 
    96       | F => HOLogic.false_const
    99       | F => HOLogic.false_const
    97       | Lt t => Const(@{const_name "Orderings.less"},[rT,rT] ---> bT)$
   100       | Lta t => Const(@{const_name "Orderings.less"},[rT,rT] ---> bT)$
    98 			   (term_of_num vs t)$ rzero
   101 			   (term_of_num vs t)$ rzero
    99       | Le t => Const(@{const_name "Orderings.less_eq"},[rT,rT] ---> bT)$
   102       | Lea t => Const(@{const_name "Orderings.less_eq"},[rT,rT] ---> bT)$
   100 			  (term_of_num vs t)$ rzero
   103 			  (term_of_num vs t)$ rzero
   101       | Gt t => Const(@{const_name "Orderings.less"},[rT,rT] ---> bT)$
   104       | Gta t => Const(@{const_name "Orderings.less"},[rT,rT] ---> bT)$
   102 			   rzero $(term_of_num vs t)
   105 			   rzero $(term_of_num vs t)
   103       | Ge t => Const(@{const_name "Orderings.less_eq"},[rT,rT] ---> bT)$
   106       | Gea t => Const(@{const_name "Orderings.less_eq"},[rT,rT] ---> bT)$
   104 			  rzero $(term_of_num vs t)
   107 			  rzero $(term_of_num vs t)
   105       | Eq t => Const("op =",[rT,rT] ---> bT)$
   108       | Eqa t => Const("op =",[rT,rT] ---> bT)$
   106 			   (term_of_num vs t)$ rzero
   109 			   (term_of_num vs t)$ rzero
   107       | NEq t => term_of_fm vs (NOT (Eq t))
   110       | NEq t => term_of_fm vs (Nota (Eqa t))
   108       | NOT t' => HOLogic.Not$(term_of_fm vs t')
   111       | Nota t' => HOLogic.Not$(term_of_fm vs t')
   109       | And(t1,t2) => HOLogic.conj$(term_of_fm vs t1)$(term_of_fm vs t2)
   112       | And(t1,t2) => HOLogic.conj$(term_of_fm vs t1)$(term_of_fm vs t2)
   110       | Or(t1,t2) => HOLogic.disj$(term_of_fm vs t1)$(term_of_fm vs t2)
   113       | Or(t1,t2) => HOLogic.disj$(term_of_fm vs t1)$(term_of_fm vs t2)
   111       | Imp(t1,t2) => HOLogic.imp$(term_of_fm vs t1)$(term_of_fm vs t2)
   114       | Impa(t1,t2) => HOLogic.imp$(term_of_fm vs t1)$(term_of_fm vs t2)
   112       | Iff(t1,t2) => (HOLogic.eq_const bT)$(term_of_fm vs t1)$
   115       | Iffa(t1,t2) => (HOLogic.eq_const bT)$(term_of_fm vs t1)$
   113 					   (term_of_fm vs t2)
   116 					   (term_of_fm vs t2)
   114       | _ => error "If this is raised, Isabelle/HOL or generate_code is inconsistent!";
   117       | _ => error "If this is raised, Isabelle/HOL or generate_code is inconsistent!";
   115 
   118 
   116 (* The oracle *)
   119 (* The oracle *)
   117 
   120 
   118 fun linrqe_oracle thy t = 
   121 fun linrqe_oracle thy t = 
   119     let 
   122     let 
   120 	val vs = start_vs t
   123 	val vs = start_vs t
   121     in HOLogic.mk_Trueprop (HOLogic.mk_eq(t, term_of_fm vs (linrqe (fm_of_term vs t))))
   124     in HOLogic.mk_Trueprop (HOLogic.mk_eq(t, term_of_fm vs (linrqe (fm_of_term vs t))))
   122     end;
   125     end;
       
   126 
   123 end;
   127 end;