39 type mdata = |
39 type mdata = |
40 {hol_ctxt: hol_context, |
40 {hol_ctxt: hol_context, |
41 binarize: bool, |
41 binarize: bool, |
42 alpha_T: typ, |
42 alpha_T: typ, |
43 max_fresh: int Unsynchronized.ref, |
43 max_fresh: int Unsynchronized.ref, |
44 datatype_mcache: ((string * typ list) * mtyp) list Unsynchronized.ref, |
44 data_type_mcache: ((string * typ list) * mtyp) list Unsynchronized.ref, |
45 constr_mcache: ((string * typ) * mtyp) list Unsynchronized.ref} |
45 constr_mcache: ((string * typ) * mtyp) list Unsynchronized.ref} |
46 |
46 |
47 exception UNSOLVABLE of unit |
47 exception UNSOLVABLE of unit |
48 exception MTYPE of string * mtyp list * typ list |
48 exception MTYPE of string * mtyp list * typ list |
49 |
49 |
121 | flatten_mtype (MType (_, Ms)) = maps flatten_mtype Ms |
121 | flatten_mtype (MType (_, Ms)) = maps flatten_mtype Ms |
122 | flatten_mtype M = [M] |
122 | flatten_mtype M = [M] |
123 |
123 |
124 fun initial_mdata hol_ctxt binarize alpha_T = |
124 fun initial_mdata hol_ctxt binarize alpha_T = |
125 ({hol_ctxt = hol_ctxt, binarize = binarize, alpha_T = alpha_T, |
125 ({hol_ctxt = hol_ctxt, binarize = binarize, alpha_T = alpha_T, |
126 max_fresh = Unsynchronized.ref 0, datatype_mcache = Unsynchronized.ref [], |
126 max_fresh = Unsynchronized.ref 0, data_type_mcache = Unsynchronized.ref [], |
127 constr_mcache = Unsynchronized.ref []} : mdata) |
127 constr_mcache = Unsynchronized.ref []} : mdata) |
128 |
128 |
129 fun could_exist_alpha_subtype alpha_T (T as Type (_, Ts)) = |
129 fun could_exist_alpha_subtype alpha_T (T as Type (_, Ts)) = |
130 T = alpha_T orelse (not (is_fp_iterator_type T) andalso |
130 T = alpha_T orelse (not (is_fp_iterator_type T) andalso |
131 exists (could_exist_alpha_subtype alpha_T) Ts) |
131 exists (could_exist_alpha_subtype alpha_T) Ts) |
132 | could_exist_alpha_subtype alpha_T T = (T = alpha_T) |
132 | could_exist_alpha_subtype alpha_T T = (T = alpha_T) |
133 |
133 |
134 fun could_exist_alpha_sub_mtype _ (alpha_T as TFree _) T = |
134 fun could_exist_alpha_sub_mtype _ (alpha_T as TFree _) T = |
135 could_exist_alpha_subtype alpha_T T |
135 could_exist_alpha_subtype alpha_T T |
136 | could_exist_alpha_sub_mtype ctxt alpha_T T = |
136 | could_exist_alpha_sub_mtype ctxt alpha_T T = |
137 (T = alpha_T orelse is_datatype ctxt T) |
137 (T = alpha_T orelse is_data_type ctxt T) |
138 |
138 |
139 fun exists_alpha_sub_mtype MAlpha = true |
139 fun exists_alpha_sub_mtype MAlpha = true |
140 | exists_alpha_sub_mtype (MFun (M1, _, M2)) = |
140 | exists_alpha_sub_mtype (MFun (M1, _, M2)) = |
141 exists exists_alpha_sub_mtype [M1, M2] |
141 exists exists_alpha_sub_mtype [M1, M2] |
142 | exists_alpha_sub_mtype (MPair (M1, M2)) = |
142 | exists_alpha_sub_mtype (MPair (M1, M2)) = |
168 case AList.lookup (op =) cache z |> the of |
168 case AList.lookup (op =) cache z |> the of |
169 MRec _ => MType (s, []) |
169 MRec _ => MType (s, []) |
170 | M => if member (op =) seen M then MType (s, []) |
170 | M => if member (op =) seen M then MType (s, []) |
171 else repair_mtype cache (M :: seen) M |
171 else repair_mtype cache (M :: seen) M |
172 |
172 |
173 fun repair_datatype_mcache cache = |
173 fun repair_data_type_mcache cache = |
174 let |
174 let |
175 fun repair_one (z, M) = |
175 fun repair_one (z, M) = |
176 Unsynchronized.change cache |
176 Unsynchronized.change cache |
177 (AList.update (op =) (z, repair_mtype (!cache) [] M)) |
177 (AList.update (op =) (z, repair_mtype (!cache) [] M)) |
178 in List.app repair_one (rev (!cache)) end |
178 in List.app repair_one (rev (!cache)) end |
217 V (Unsynchronized.inc max_fresh) |
217 V (Unsynchronized.inc max_fresh) |
218 else |
218 else |
219 A Gen |
219 A Gen |
220 in (M1, aa, M2) end |
220 in (M1, aa, M2) end |
221 and fresh_mtype_for_type (mdata as {hol_ctxt as {ctxt, ...}, binarize, alpha_T, |
221 and fresh_mtype_for_type (mdata as {hol_ctxt as {ctxt, ...}, binarize, alpha_T, |
222 datatype_mcache, constr_mcache, ...}) |
222 data_type_mcache, constr_mcache, ...}) |
223 all_minus = |
223 all_minus = |
224 let |
224 let |
225 fun do_type T = |
225 fun do_type T = |
226 if T = alpha_T then |
226 if T = alpha_T then |
227 MAlpha |
227 MAlpha |
230 MFun (fresh_mfun_for_fun_type mdata all_minus T1 T2) |
230 MFun (fresh_mfun_for_fun_type mdata all_minus T1 T2) |
231 | Type (@{type_name prod}, [T1, T2]) => MPair (pairself do_type (T1, T2)) |
231 | Type (@{type_name prod}, [T1, T2]) => MPair (pairself do_type (T1, T2)) |
232 | Type (@{type_name set}, [T']) => do_type (T' --> bool_T) |
232 | Type (@{type_name set}, [T']) => do_type (T' --> bool_T) |
233 | Type (z as (s, _)) => |
233 | Type (z as (s, _)) => |
234 if could_exist_alpha_sub_mtype ctxt alpha_T T then |
234 if could_exist_alpha_sub_mtype ctxt alpha_T T then |
235 case AList.lookup (op =) (!datatype_mcache) z of |
235 case AList.lookup (op =) (!data_type_mcache) z of |
236 SOME M => M |
236 SOME M => M |
237 | NONE => |
237 | NONE => |
238 let |
238 let |
239 val _ = Unsynchronized.change datatype_mcache (cons (z, MRec z)) |
239 val _ = Unsynchronized.change data_type_mcache (cons (z, MRec z)) |
240 val xs = binarized_and_boxed_datatype_constrs hol_ctxt binarize T |
240 val xs = binarized_and_boxed_data_type_constrs hol_ctxt binarize T |
241 val (all_Ms, constr_Ms) = |
241 val (all_Ms, constr_Ms) = |
242 fold_rev (fn (_, T') => fn (all_Ms, constr_Ms) => |
242 fold_rev (fn (_, T') => fn (all_Ms, constr_Ms) => |
243 let |
243 let |
244 val binder_Ms = map do_type (binder_types T') |
244 val binder_Ms = map do_type (binder_types T') |
245 val new_Ms = filter exists_alpha_sub_mtype_fresh |
245 val new_Ms = filter exists_alpha_sub_mtype_fresh |
250 (union (op =) new_Ms all_Ms, |
250 (union (op =) new_Ms all_Ms, |
251 constr_M :: constr_Ms) |
251 constr_M :: constr_Ms) |
252 end) |
252 end) |
253 xs ([], []) |
253 xs ([], []) |
254 val M = MType (s, all_Ms) |
254 val M = MType (s, all_Ms) |
255 val _ = Unsynchronized.change datatype_mcache |
255 val _ = Unsynchronized.change data_type_mcache |
256 (AList.update (op =) (z, M)) |
256 (AList.update (op =) (z, M)) |
257 val _ = Unsynchronized.change constr_mcache |
257 val _ = Unsynchronized.change constr_mcache |
258 (append (xs ~~ constr_Ms)) |
258 (append (xs ~~ constr_Ms)) |
259 in |
259 in |
260 if forall (not o is_MRec o snd) (!datatype_mcache) then |
260 if forall (not o is_MRec o snd) (!data_type_mcache) then |
261 (repair_datatype_mcache datatype_mcache; |
261 (repair_data_type_mcache data_type_mcache; |
262 repair_constr_mcache (!datatype_mcache) constr_mcache; |
262 repair_constr_mcache (!data_type_mcache) constr_mcache; |
263 AList.lookup (op =) (!datatype_mcache) z |> the) |
263 AList.lookup (op =) (!data_type_mcache) z |> the) |
264 else |
264 else |
265 M |
265 M |
266 end |
266 end |
267 else |
267 else |
268 MType (s, []) |
268 MType (s, []) |