16 signature PATTERN = |
16 signature PATTERN = |
17 sig |
17 sig |
18 val trace_unify_fail: bool ref |
18 val trace_unify_fail: bool ref |
19 val aeconv: term * term -> bool |
19 val aeconv: term * term -> bool |
20 val eta_long: typ list -> term -> term |
20 val eta_long: typ list -> term -> term |
21 val eta_contract_atom: term -> term |
|
22 val match: theory -> term * term -> Type.tyenv * Envir.tenv -> Type.tyenv * Envir.tenv |
21 val match: theory -> term * term -> Type.tyenv * Envir.tenv -> Type.tyenv * Envir.tenv |
23 val first_order_match: theory -> term * term |
22 val first_order_match: theory -> term * term |
24 -> Type.tyenv * Envir.tenv -> Type.tyenv * Envir.tenv |
23 -> Type.tyenv * Envir.tenv -> Type.tyenv * Envir.tenv |
25 val matches: theory -> term * term -> bool |
24 val matches: theory -> term * term -> bool |
26 val equiv: theory -> term * term -> bool |
25 val equiv: theory -> term * term -> bool |
272 handle Unif => (proj_fail thy params; raise Unif)); |
271 handle Unif => (proj_fail thy params; raise Unif)); |
273 |
272 |
274 fun unify thy = unif thy []; |
273 fun unify thy = unif thy []; |
275 |
274 |
276 |
275 |
277 (*Eta-contract a term from outside: just enough to reduce it to an atom |
|
278 DOESN'T QUITE WORK! |
|
279 *) |
|
280 fun eta_contract_atom (t0 as Abs(a, T, body)) = |
|
281 (case eta_contract2 body of |
|
282 body' as (f $ Bound 0) => |
|
283 if loose_bvar1(f,0) then Abs(a,T,body') |
|
284 else eta_contract_atom (incr_boundvars ~1 f) |
|
285 | _ => t0) |
|
286 | eta_contract_atom t = t |
|
287 and eta_contract2 (f$t) = f $ eta_contract_atom t |
|
288 | eta_contract2 t = eta_contract_atom t; |
|
289 |
|
290 (* put a term into eta long beta normal form *) |
276 (* put a term into eta long beta normal form *) |
291 fun eta_long Ts (Abs (s, T, t)) = Abs (s, T, eta_long (T :: Ts) t) |
277 fun eta_long Ts (Abs (s, T, t)) = Abs (s, T, eta_long (T :: Ts) t) |
292 | eta_long Ts t = (case strip_comb t of |
278 | eta_long Ts t = (case strip_comb t of |
293 (Abs _, _) => eta_long Ts (Envir.beta_norm t) |
279 (Abs _, _) => eta_long Ts (Envir.beta_norm t) |
294 | (u, ts) => |
280 | (u, ts) => |
301 end); |
287 end); |
302 |
288 |
303 |
289 |
304 (*Tests whether 2 terms are alpha/eta-convertible and have same type. |
290 (*Tests whether 2 terms are alpha/eta-convertible and have same type. |
305 Note that Consts and Vars may have more than one type.*) |
291 Note that Consts and Vars may have more than one type.*) |
306 fun t aeconv u = aconv_aux (eta_contract_atom t, eta_contract_atom u) |
292 fun t aeconv u = Envir.eta_contract t aconv Envir.eta_contract u; |
307 and aconv_aux (Const(a,T), Const(b,U)) = a=b andalso T=U |
|
308 | aconv_aux (Free(a,T), Free(b,U)) = a=b andalso T=U |
|
309 | aconv_aux (Var(v,T), Var(w,U)) = eq_ix(v,w) andalso T=U |
|
310 | aconv_aux (Bound i, Bound j) = i=j |
|
311 | aconv_aux (Abs(_,T,t), Abs(_,U,u)) = (t aeconv u) andalso T=U |
|
312 | aconv_aux (f$t, g$u) = (f aeconv g) andalso (t aeconv u) |
|
313 | aconv_aux _ = false; |
|
314 |
293 |
315 |
294 |
316 (*** Matching ***) |
295 (*** Matching ***) |
317 |
296 |
318 exception MATCH; |
297 exception MATCH; |