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 |
|