author | wenzelm |
Thu, 06 Jun 2024 11:53:52 +0200 | |
changeset 80266 | d52be75ae60b |
parent 79434 | 6f2c3e4c97d7 |
permissions | -rw-r--r-- |
59026
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
1 |
(* Title: Pure/more_unify.ML |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
2 |
Author: Makarius |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
3 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
4 |
Add-ons to Higher-Order Unification, outside the inference kernel. |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
5 |
*) |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
6 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
7 |
signature UNIFY = |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
8 |
sig |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
9 |
include UNIFY |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
10 |
val matchers: Context.generic -> (term * term) list -> Envir.env Seq.seq |
76062 | 11 |
val matcher: Context.generic -> term list -> term list -> Envir.env option |
59026
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
12 |
end; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
13 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
14 |
structure Unify: UNIFY = |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
15 |
struct |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
16 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
17 |
(*Pattern matching*) |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
18 |
fun first_order_matchers thy pairs (Envir.Envir {maxidx, tenv, tyenv}) = |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
19 |
let val (tyenv', tenv') = fold (Pattern.first_order_match thy) pairs (tyenv, tenv) |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
20 |
in Seq.single (Envir.Envir {maxidx = maxidx, tenv = tenv', tyenv = tyenv'}) end |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
21 |
handle Pattern.MATCH => Seq.empty; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
22 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
23 |
(*General matching -- keep variables disjoint*) |
63615 | 24 |
fun matchers _ [] = Seq.single Envir.init |
59026
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
25 |
| matchers context pairs = |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
26 |
let |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
27 |
val thy = Context.theory_of context; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
28 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
29 |
val maxidx = fold (Term.maxidx_term o #2) pairs ~1; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
30 |
val offset = maxidx + 1; |
79232 | 31 |
val pairs' = map (apfst (Logic.incr_indexes ([], offset))) pairs; |
59026
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
32 |
val maxidx' = fold (fn (t, u) => Term.maxidx_term t #> Term.maxidx_term u) pairs' ~1; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
33 |
|
74280 | 34 |
val pat_tvars = TVars.build (fold (TVars.add_tvars o #1) pairs'); |
35 |
val pat_vars = Vars.build (fold (Vars.add_vars o #1) pairs'); |
|
59026
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
36 |
|
79434 | 37 |
val decr_indexesT_same = |
38 |
Term.map_atyps_same |
|
39 |
(fn TVar ((x, i), S) => |
|
40 |
if i > maxidx then TVar ((x, i - offset), S) else raise Same.SAME |
|
41 |
| _ => raise Same.SAME); |
|
42 |
val decr_indexesT = Same.commit decr_indexesT_same; |
|
59026
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
43 |
val decr_indexes = |
79434 | 44 |
Term.map_types decr_indexesT_same #> |
45 |
Term.map_aterms |
|
46 |
(fn Var ((x, i), T) => |
|
47 |
if i > maxidx then Var ((x, i - offset), T) else raise Same.SAME |
|
48 |
| _ => raise Same.SAME); |
|
59026
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
49 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
50 |
fun norm_tvar env ((x, i), S) = |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
51 |
let |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
52 |
val tyenv = Envir.type_env env; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
53 |
val T' = Envir.norm_type tyenv (TVar ((x, i), S)); |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
54 |
in |
74280 | 55 |
if (case T' of TVar (v, _) => v = (x, i) | _ => false) then I |
56 |
else Vartab.update ((x, i - offset), (S, decr_indexesT T')) |
|
59026
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
57 |
end; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
58 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
59 |
fun norm_var env ((x, i), T) = |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
60 |
let |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
61 |
val tyenv = Envir.type_env env; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
62 |
val T' = Envir.norm_type tyenv T; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
63 |
val t' = Envir.norm_term env (Var ((x, i), T')); |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
64 |
in |
74280 | 65 |
if (case t' of Var (v, _) => v = (x, i) | _ => false) then I |
66 |
else Vartab.update ((x, i - offset), (decr_indexesT T', decr_indexes t')) |
|
59026
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
67 |
end; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
68 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
69 |
fun result env = |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
70 |
if Envir.above env maxidx then (* FIXME proper handling of generated vars!? *) |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
71 |
SOME (Envir.Envir {maxidx = maxidx, |
74280 | 72 |
tyenv = Vartab.build (TVars.fold (norm_tvar env o #1) pat_tvars), |
73 |
tenv = Vartab.build (Vars.fold (norm_var env o #1) pat_vars)}) |
|
59026
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
74 |
else NONE; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
75 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
76 |
val empty = Envir.empty maxidx'; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
77 |
in |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
78 |
Seq.append |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
79 |
(Seq.map_filter result (Unify.smash_unifiers context pairs' empty)) |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
80 |
(first_order_matchers thy pairs empty) |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
81 |
end; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
82 |
|
76062 | 83 |
fun matcher context ps os = |
84 |
if length ps <> length os then NONE |
|
85 |
else Seq.pull (matchers context (ps ~~ os)) |> Option.map #1; |
|
59026
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
86 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
87 |
open Unify; |
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
88 |
|
30b8a5825a9c
removed some add-ons from modules that are relevant for the inference kernel;
wenzelm
parents:
diff
changeset
|
89 |
end; |