author haftmann Fri Nov 26 23:13:58 2010 +0100 (2010-11-26) changeset 40730 2aa0390a2da7 parent 40717 88f2955a111e child 40731 4e60c7348096
nbe decides equality of abstractions by extensionality
 src/HOL/ex/Normalization_by_Evaluation.thy file | annotate | diff | revisions src/Tools/nbe.ML file | annotate | diff | revisions
```     1.1 --- a/src/HOL/ex/Normalization_by_Evaluation.thy	Fri Nov 26 18:07:00 2010 +0100
1.2 +++ b/src/HOL/ex/Normalization_by_Evaluation.thy	Fri Nov 26 23:13:58 2010 +0100
1.3 @@ -66,7 +66,7 @@
1.4  lemma "map (%f. f True) [id, g, Not] = [True, g True, False]" by normalization
1.5
1.6  lemma "map (%f. f True) ([id, g, Not] @ fs) = [True, g True, False] @ map (%f. f True) fs"
1.7 -  by normalization rule+
1.8 +  by normalization
1.9  lemma "rev [a, b, c] = [c, b, a]" by normalization
1.10  value [nbe] "rev (a#b#cs) = rev cs @ [b, a]"
1.11  value [nbe] "map (%F. F [a,b,c::'x]) (map map [f,g,h])"
1.12 @@ -108,10 +108,13 @@
1.13  lemma "(42::rat) / 1704 = 1 / 284 + 3 / 142" by normalization
1.14  value [nbe] "Suc 0 \<in> set ms"
1.15
1.16 +(* non-left-linear patterns, equality by extensionality *)
1.17 +
1.18  lemma "f = f" by normalization
1.19  lemma "f x = f x" by normalization
1.20  lemma "(f o g) x = f (g x)" by normalization
1.21  lemma "(f o id) x = f x" by normalization
1.22 +lemma "(id :: bool \<Rightarrow> bool) = id" by normalization
1.23  value [nbe] "(\<lambda>x. x)"
1.24
1.25  (* Church numerals: *)
```
```     2.1 --- a/src/Tools/nbe.ML	Fri Nov 26 18:07:00 2010 +0100
2.2 +++ b/src/Tools/nbe.ML	Fri Nov 26 23:13:58 2010 +0100
2.3 @@ -18,7 +18,7 @@
2.4    val apps: Univ -> Univ list -> Univ        (*explicit applications*)
2.5    val abss: int -> (Univ list -> Univ) -> Univ
2.6                                               (*abstractions as closures*)
2.7 -  val same: Univ -> Univ -> bool
2.8 +  val eq_Univ: Univ * Univ -> bool
2.9
2.10    val put_result: (unit -> Univ list -> Univ list) -> Proof.context -> Proof.context
2.11    val trace: bool Unsynchronized.ref
2.12 @@ -170,11 +170,6 @@
2.13    | Abs of (int * (Univ list -> Univ)) * Univ list
2.14                                         (*abstractions as closures*);
2.15
2.16 -fun same (Const (k, xs)) (Const (l, ys)) = k = l andalso forall2 same xs ys
2.17 -  | same (DFree (s, k)) (DFree (t, l)) = s = t andalso k = l
2.18 -  | same (BVar (k, xs)) (BVar (l, ys)) = k = l andalso forall2 same xs ys
2.19 -  | same _ _ = false;
2.20 -
2.21
2.22  (* constructor functions *)
2.23
2.24 @@ -188,6 +183,28 @@
2.25    | apps (Const (name, xs)) ys = Const (name, ys @ xs)
2.26    | apps (BVar (n, xs)) ys = BVar (n, ys @ xs);
2.27
2.28 +fun satisfy_abs (abs as ((n, f), xs)) some_k =
2.29 +  let
2.30 +    val ys = case some_k
2.31 +     of NONE => replicate n (BVar (0, []))
2.32 +      | SOME k => map_range (fn l => BVar (k + l, [])) n;
2.33 +  in (apps (Abs abs) ys, ys) end;
2.34 +
2.35 +fun maxidx (Const (_, xs)) = fold maxidx xs
2.36 +  | maxidx (DFree _) = I
2.37 +  | maxidx (BVar (l, xs)) = fold maxidx xs #> Integer.max (l + 1)
2.38 +  | maxidx (Abs abs) = maxidx (fst (satisfy_abs abs NONE));
2.39 +
2.40 +fun eq_Univ (Const (k, xs), Const (l, ys)) = k = l andalso eq_list eq_Univ (xs, ys)
2.41 +  | eq_Univ (DFree (s, k), DFree (t, l)) = s = t andalso k = l
2.42 +  | eq_Univ (BVar (k, xs), BVar (l, ys)) = k = l andalso eq_list eq_Univ (xs, ys)
2.43 +  | eq_Univ (x as Abs abs, y) =
2.44 +      let
2.45 +        val (x, ys) = satisfy_abs abs ((SOME o maxidx x o maxidx y) 0)
2.46 +      in eq_Univ (x, apps y ys) end
2.47 +  | eq_Univ (x, y as Abs _) = eq_Univ (y, x)
2.48 +  | eq_Univ _ = false;
2.49 +
2.50
2.51  (** assembling and compiling ML code from terms **)
2.52
2.53 @@ -241,7 +258,7 @@
2.54    val name_const =  prefix ^ "Const";
2.55    val name_abss =   prefix ^ "abss";
2.56    val name_apps =   prefix ^ "apps";
2.57 -  val name_same =   prefix ^ "same";
2.58 +  val name_eq =     prefix ^ "eq_Univ";
2.59  in
2.60
2.61  val univs_cookie = (Univs.get, put_result, name_put);
2.62 @@ -267,7 +284,7 @@
2.63  fun nbe_abss 0 f = f `\$` ml_list []
2.64    | nbe_abss n f = name_abss `\$\$` [string_of_int n, f];
2.65
2.66 -fun nbe_same v1 v2 = "(" ^ name_same ^ " " ^ nbe_bound v1 ^ " " ^ nbe_bound v2 ^ ")";
2.67 +fun nbe_eq (v1, v2) = "(" ^ name_eq ^ " (" ^ nbe_bound v1 ^ ", " ^ nbe_bound v2 ^ "))";
2.68
2.69  end;
2.70
2.71 @@ -353,7 +370,7 @@
2.72          val (samepairs, args') = subst_nonlin_vars args;
2.73          val s_args = map assemble_arg args';
2.74          val s_rhs = if null samepairs then assemble_rhs rhs
2.75 -          else ml_if (ml_and (map (uncurry nbe_same) samepairs))
2.76 +          else ml_if (ml_and (map nbe_eq samepairs))
2.77              (assemble_rhs rhs) default_rhs;
2.78          val eqns = if is_eval then
2.79              [([ml_list (rev (dicts @ s_args))], s_rhs)]
```