src/CCL/eval.ML
changeset 17456 bcf7544875b2
parent 3837 d7f033c74b38
equal deleted inserted replaced
17455:151e76f0e3c7 17456:bcf7544875b2
     1 (*  Title:      92/CCL/eval
     1 (*  Title:      92/CCL/eval
     2     ID:         $Id$
     2     ID:         $Id$
     3     Author:     Martin Coen, Cambridge University Computer Laboratory
     3     Author:     Martin Coen, Cambridge University Computer Laboratory
     4     Copyright   1992  University of Cambridge
     4     Copyright   1992  University of Cambridge
     5 
       
     6 *)
     5 *)
     7 
       
     8 
       
     9 
     6 
    10 (*** Evaluation ***)
     7 (*** Evaluation ***)
    11 
     8 
    12 val EVal_rls = ref [trueV,falseV,pairV,lamV,caseVtrue,caseVfalse,caseVpair,caseVlam];
     9 val EVal_rls = ref [trueV,falseV,pairV,lamV,caseVtrue,caseVfalse,caseVpair,caseVlam];
    13 val eval_tac = DEPTH_SOLVE_1 (resolve_tac (!EVal_rls) 1);
    10 val eval_tac = DEPTH_SOLVE_1 (resolve_tac (!EVal_rls) 1);
    14 fun ceval_tac rls = DEPTH_SOLVE_1 (resolve_tac (!EVal_rls@rls) 1);
    11 fun ceval_tac rls = DEPTH_SOLVE_1 (resolve_tac (!EVal_rls@rls) 1);
    15 
    12 
    16 val prems = goalw thy [apply_def]
    13 val prems = goalw (the_context ()) [apply_def]
    17    "[| f ---> lam x. b(x);  b(a) ---> c |] ==> f ` a ---> c";
    14    "[| f ---> lam x. b(x);  b(a) ---> c |] ==> f ` a ---> c";
    18 by (ceval_tac prems);
    15 by (ceval_tac prems);
    19 qed "applyV";
    16 qed "applyV";
    20 
    17 
    21 EVal_rls := !EVal_rls @ [applyV];
    18 EVal_rls := !EVal_rls @ [applyV];
    22 
    19 
    23 val major::prems = goalw thy [let_def]
    20 val major::prems = goalw (the_context ()) [let_def]
    24    "[| t ---> a;  f(a) ---> c |] ==> let x be t in f(x) ---> c";
    21    "[| t ---> a;  f(a) ---> c |] ==> let x be t in f(x) ---> c";
    25 by (rtac (major RS canonical) 1);
    22 by (rtac (major RS canonical) 1);
    26 by (REPEAT (DEPTH_SOLVE_1 (resolve_tac ([major]@prems@(!EVal_rls)) 1 ORELSE
    23 by (REPEAT (DEPTH_SOLVE_1 (resolve_tac ([major]@prems@(!EVal_rls)) 1 ORELSE
    27                            etac substitute 1)));
    24                            etac substitute 1)));
    28 qed "letV";
    25 qed "letV";
    29 
    26 
    30 val prems = goalw thy [fix_def]
    27 val prems = goalw (the_context ()) [fix_def]
    31    "f(fix(f)) ---> c ==> fix(f) ---> c";
    28    "f(fix(f)) ---> c ==> fix(f) ---> c";
    32 by (rtac applyV 1);
    29 by (rtac applyV 1);
    33 by (rtac lamV 1);
    30 by (rtac lamV 1);
    34 by (resolve_tac prems 1);
    31 by (resolve_tac prems 1);
    35 qed "fixV";
    32 qed "fixV";
    36 
    33 
    37 val prems = goalw thy [letrec_def]
    34 val prems = goalw (the_context ()) [letrec_def]
    38     "h(t,%y. letrec g x be h(x,g) in g(y)) ---> c ==> \
    35     "h(t,%y. letrec g x be h(x,g) in g(y)) ---> c ==> \
    39 \                  letrec g x be h(x,g) in g(t) ---> c";
    36 \                  letrec g x be h(x,g) in g(t) ---> c";
    40 by (REPEAT (resolve_tac (prems @ [fixV,applyV,lamV]) 1));
    37 by (REPEAT (resolve_tac (prems @ [fixV,applyV,lamV]) 1));
    41 qed "letrecV";
    38 qed "letrecV";
    42 
    39 
    43 EVal_rls := !EVal_rls @ [letV,letrecV,fixV];
    40 EVal_rls := !EVal_rls @ [letV,letrecV,fixV];
    44 
    41 
    45 fun mk_V_rl s = prove_goalw thy data_defs s (fn prems => [ceval_tac prems]);
    42 fun mk_V_rl s = prove_goalw (the_context ()) data_defs s (fn prems => [ceval_tac prems]);
    46 
    43 
    47 val V_rls = map mk_V_rl 
    44 val V_rls = map mk_V_rl
    48              ["true ---> true",
    45              ["true ---> true",
    49               "false ---> false",
    46               "false ---> false",
    50               "[| b--->true;  t--->c |] ==> if b then t else u ---> c",
    47               "[| b--->true;  t--->c |] ==> if b then t else u ---> c",
    51               "[| b--->false;  u--->c |] ==> if b then t else u ---> c",
    48               "[| b--->false;  u--->c |] ==> if b then t else u ---> c",
    52               "<a,b> ---> <a,b>",
    49               "<a,b> ---> <a,b>",
    66 
    63 
    67 EVal_rls := !EVal_rls @ V_rls;
    64 EVal_rls := !EVal_rls @ V_rls;
    68 
    65 
    69 (* Factorial *)
    66 (* Factorial *)
    70 
    67 
    71 val prems = goal thy
    68 val prems = goal (the_context ())
    72     "letrec f n be ncase(n,succ(zero),%x. nrec(n,zero,%y g. nrec(f(x),g,%z h. succ(h)))) \
    69     "letrec f n be ncase(n,succ(zero),%x. nrec(n,zero,%y g. nrec(f(x),g,%z h. succ(h)))) \
    73 \              in f(succ(succ(zero))) ---> ?a";
    70 \              in f(succ(succ(zero))) ---> ?a";
    74 by (ceval_tac []);
    71 by (ceval_tac []);
    75 
    72 
    76 val prems = goal thy
    73 val prems = goal (the_context ())
    77     "letrec f n be ncase(n,succ(zero),%x. nrec(n,zero,%y g. nrec(f(x),g,%z h. succ(h)))) \
    74     "letrec f n be ncase(n,succ(zero),%x. nrec(n,zero,%y g. nrec(f(x),g,%z h. succ(h)))) \
    78 \              in f(succ(succ(succ(zero)))) ---> ?a";
    75 \              in f(succ(succ(succ(zero)))) ---> ?a";
    79 by (ceval_tac []);
    76 by (ceval_tac []);
    80 
    77 
    81 (* Less Than Or Equal *)
    78 (* Less Than Or Equal *)
    82 
    79 
    83 fun isle x y = prove_goal thy 
    80 fun isle x y = prove_goal (the_context ())
    84     ("letrec f p be split(p,%m n. ncase(m,true,%x. ncase(n,false,%y. f(<x,y>)))) \
    81     ("letrec f p be split(p,%m n. ncase(m,true,%x. ncase(n,false,%y. f(<x,y>)))) \
    85 \              in f(<"^x^","^y^">) ---> ?a")
    82 \              in f(<"^x^","^y^">) ---> ?a")
    86     (fn prems => [ceval_tac []]);
    83     (fn prems => [ceval_tac []]);
    87 
    84 
    88 isle "succ(zero)" "succ(zero)";
    85 isle "succ(zero)" "succ(zero)";
    90 isle "succ(succ(succ(succ(succ(zero)))))" "succ(succ(succ(succ(zero))))";
    87 isle "succ(succ(succ(succ(succ(zero)))))" "succ(succ(succ(succ(zero))))";
    91 
    88 
    92 
    89 
    93 (* Reverse *)
    90 (* Reverse *)
    94 
    91 
    95 val prems = goal thy
    92 val prems = goal (the_context ())
    96     "letrec id l be lcase(l,[],%x xs. x$id(xs)) \
    93     "letrec id l be lcase(l,[],%x xs. x$id(xs)) \
    97 \              in id(zero$succ(zero)$[]) ---> ?a";
    94 \              in id(zero$succ(zero)$[]) ---> ?a";
    98 by (ceval_tac []);
    95 by (ceval_tac []);
    99 
    96 
   100 val prems = goal thy
    97 val prems = goal (the_context ())
   101     "letrec rev l be lcase(l,[],%x xs. lrec(rev(xs),x$[],%y ys g. y$g)) \
    98     "letrec rev l be lcase(l,[],%x xs. lrec(rev(xs),x$[],%y ys g. y$g)) \
   102 \              in rev(zero$succ(zero)$(succ((lam x. x)`succ(zero)))$([])) ---> ?a";
    99 \              in rev(zero$succ(zero)$(succ((lam x. x)`succ(zero)))$([])) ---> ?a";
   103 by (ceval_tac []);
   100 by (ceval_tac []);
   104