let (++) f g x = f (g x);;\r
let id x = x;;\r
+let rec fold_nat f x n = if n = 0 then x else f (fold_nat f x (n-1)) n ;;\r
\r
let print_hline = Console.print_hline;;\r
\r
+open Pure\r
+\r
type var = int;;\r
type t =\r
| V of var\r
| A of t * t\r
| L of t\r
| B (* bottom *)\r
- | P (* pacman *)\r
;;\r
\r
+let delta = L(A(V 0, V 0));;\r
+\r
let eta_eq =\r
let rec aux l1 l2 t1 t2 = match t1, t2 with\r
| L t1, L t2 -> aux l1 l2 t1 t2\r
in aux 0 0\r
;;\r
\r
-type problem = {\r
- orig_freshno: int\r
- ; freshno : int\r
- ; div : t\r
- ; conv : t\r
- ; sigma : (var * t) list (* substitutions *)\r
- ; stepped : var list\r
-}\r
-\r
-exception Done of (var * t) list (* substitution *);;\r
-exception Fail of int * string;;\r
+(* does NOT lift t *)\r
+let mk_lams = fold_nat (fun x _ -> L x) ;;\r
\r
-let string_of_t p =\r
- let bound_vars = ["x"; "y"; "z"; "w"; "q"] in\r
+let string_of_t =\r
+ let string_of_bvar =\r
+ let bound_vars = ["x"; "y"; "z"; "w"; "q"] in\r
+ let bvarsno = List.length bound_vars in\r
+ fun nn -> if nn < bvarsno then List.nth bound_vars nn else "x" ^ (string_of_int (nn - bvarsno + 1)) in\r
let rec string_of_term_w_pars level = function\r
| V v -> if v >= level then "`" ^ string_of_int (v-level) else\r
- let nn = level - v-1 in\r
- if nn < 5 then List.nth bound_vars nn else "x" ^ (string_of_int (nn-4))\r
+ string_of_bvar (level - v-1)\r
| A _\r
- | L _ as t -> "(" ^ string_of_term_no_pars_lam level t ^ ")"\r
+ | L _ as t -> "(" ^ string_of_term_no_pars level t ^ ")"\r
| B -> "BOT"\r
- | P -> "PAC"\r
and string_of_term_no_pars_app level = function\r
- | A(t1,t2) -> (string_of_term_no_pars_app level t1) ^ " " ^ (string_of_term_w_pars level t2)\r
+ | A(t1,t2) -> string_of_term_no_pars_app level t1 ^ " " ^ string_of_term_w_pars level t2\r
| _ as t -> string_of_term_w_pars level t\r
- and string_of_term_no_pars_lam level = function\r
- | L t -> "λ" ^ string_of_term_w_pars (level+1) (V 0) ^ ". " ^ (string_of_term_no_pars_lam (level+1) t)\r
- | _ as t -> string_of_term_no_pars level t\r
and string_of_term_no_pars level = function\r
- | L _ as t -> string_of_term_no_pars_lam level t\r
+ | L t -> "λ" ^ string_of_bvar level ^ ". " ^ string_of_term_no_pars (level+1) t\r
| _ as t -> string_of_term_no_pars_app level t\r
in string_of_term_no_pars 0\r
;;\r
\r
+type problem = {\r
+ orig_freshno: int\r
+ ; freshno : int\r
+ ; div : t\r
+ ; conv : t\r
+ ; sigma : (var * t) list (* substitutions *)\r
+ ; stepped : var list\r
+ ; phase : [`One | `Two] (* :'( *)\r
+}\r
+\r
let string_of_problem p =\r
let lines = [\r
"[stepped] " ^ String.concat " " (List.map string_of_int p.stepped);\r
- "[DV] " ^ (string_of_t p p.div);\r
- "[CV] " ^ (string_of_t p p.conv);\r
+ "[DV] " ^ string_of_t p.div;\r
+ "[CV] " ^ string_of_t p.conv;\r
] in\r
String.concat "\n" lines\r
;;\r
\r
+exception Done of (var * t) list (* substitution *);;\r
+exception Fail of int * string;;\r
+\r
let problem_fail p reason =\r
print_endline "!!!!!!!!!!!!!!! FAIL !!!!!!!!!!!!!!!";\r
print_endline (string_of_problem p);\r
function\r
| A(t,_) -> is_inert t\r
| V _ -> true\r
- | L _ | B | P -> false\r
+ | L _ | B -> false\r
;;\r
\r
let is_var = function V _ -> true | _ -> false;;\r
let is_lambda = function L _ -> true | _ -> false;;\r
\r
-let rec head_of_inert = function\r
- | V n -> n\r
- | A(t, _) -> head_of_inert t\r
- | _ -> assert false\r
+let rec no_leading_lambdas = function\r
+ | L t -> 1 + no_leading_lambdas t\r
+ | _ -> 0\r
;;\r
\r
-let rec args_no = function\r
- | V _ -> 0\r
- | A(t, _) -> 1 + args_no t\r
+let rec get_inert = function\r
+ | V n -> (n,0)\r
+ | A(t, _) -> let hd,args = get_inert t in hd,args+1\r
| _ -> assert false\r
;;\r
\r
-let rec subst level delift fromdiv sub =\r
+let rec subst level delift sub =\r
function\r
| V v -> if v = level + fst sub then lift level (snd sub) else V (if delift && v > level then v-1 else v)\r
- | L t -> L (subst (level + 1) delift fromdiv sub t)\r
+ | L t -> L (subst (level + 1) delift sub t)\r
| A (t1,t2) ->\r
- let t1 = subst level delift fromdiv sub t1 in\r
- let t2 = subst level delift fromdiv sub t2 in\r
- if t1 = B || t2 = B then B else mk_app fromdiv t1 t2\r
+ let t1 = subst level delift sub t1 in\r
+ let t2 = subst level delift sub t2 in\r
+ mk_app t1 t2\r
| B -> B\r
- | P -> P\r
-and mk_app fromdiv t1 t2 = let t1 = if t1 = P then L P else t1 in match t1 with\r
+and mk_app t1 t2 = if t1 = delta && t2 = delta then B else match t1 with\r
| B | _ when t2 = B -> B\r
- | L t1 -> subst 0 true fromdiv (0, t2) t1\r
+ | L t1 -> subst 0 true (0, t2) t1\r
| t1 -> A (t1, t2)\r
and lift n =\r
- let rec aux n' =\r
+ let rec aux lev =\r
function\r
- | V m -> V (if m >= n' then m + n else m)\r
- | L t -> L (aux (n'+1) t)\r
- | A (t1, t2) -> A (aux n' t1, aux n' t2)\r
+ | V m -> V (if m >= lev then m + n else m)\r
+ | L t -> L (aux (lev+1) t)\r
+ | A (t1, t2) -> A (aux lev t1, aux lev t2)\r
| B -> B\r
- | P -> P\r
in aux 0\r
;;\r
let subst = subst 0 false;;\r
\r
let subst_in_problem (sub: var * t) (p: problem) =\r
-print_endline ("-- SUBST " ^ string_of_t p (V (fst sub)) ^ " |-> " ^ string_of_t p (snd sub));\r
- let p = {p with stepped=(fst sub)::p.stepped} in\r
- let conv = subst false sub p.conv in\r
- let div = subst true sub p.div in\r
- let p = {p with div; conv} in\r
- (* print_endline ("after sub: \n" ^ string_of_problem p); *)\r
- {p with sigma=sub::p.sigma}\r
+print_endline ("-- SUBST " ^ string_of_t (V (fst sub)) ^ " |-> " ^ string_of_t (snd sub));\r
+ {p with\r
+ div=subst sub p.div;\r
+ conv=subst sub p.conv;\r
+ stepped=(fst sub)::p.stepped;\r
+ sigma=sub::p.sigma}\r
;;\r
\r
let get_subterm_with_head_and_args hd_var n_args =\r
- let rec aux = function\r
- | V _ | L _ | B | P -> None\r
+ let rec aux lev = function\r
+ | V _ | B -> None\r
+ | L t -> aux (lev+1) t\r
| A(t1,t2) as t ->\r
- if head_of_inert t1 = hd_var && n_args <= 1 + args_no t1\r
- then Some t\r
- else match aux t2 with\r
- | None -> aux t1\r
+ let hd_var', n_args' = get_inert t1 in\r
+ if hd_var' = hd_var + lev && n_args <= 1 + n_args'\r
+ then Some (lift ~-lev t)\r
+ else match aux lev t2 with\r
+ | None -> aux lev t1\r
| Some _ as res -> res\r
- in aux\r
+ in aux 0\r
+;;\r
+\r
+let rec purify = function\r
+ | L t -> Pure.L (purify t)\r
+ | A (t1,t2) -> Pure.A (purify t1, purify t2)\r
+ | V n -> Pure.V n\r
+ | B -> Pure.B\r
;;\r
\r
-(* let rec simple_explode p =\r
- match p.div with\r
- | V var ->\r
- let subst = var, B in\r
- sanity (subst_in_problem subst p)\r
- | _ -> p *)\r
+let check p sigma =\r
+ let div = purify p.div in\r
+ let conv = purify p.conv in\r
+ let sigma = List.map (fun (v,t) -> v, purify t) sigma in\r
+ let freshno = List.fold_right (fun (x,_) -> max x) sigma 0 in\r
+ let env = Pure.env_of_sigma freshno sigma in\r
+ assert (Pure.diverged (Pure.mwhd (env,div,[])));\r
+ assert (not (Pure.diverged (Pure.mwhd (env,conv,[]))));\r
+ ()\r
+;;\r
\r
let sanity p =\r
print_endline (string_of_problem p); (* non cancellare *)\r
- if p.div = B then raise (Done p.sigma);\r
- if not (is_inert p.div) then problem_fail p "p.div converged";\r
if p.conv = B then problem_fail p "p.conv diverged";\r
- (* let p = if is_var p.div then simple_explode p else p in *)\r
- p\r
+ if p.div = B then raise (Done p.sigma);\r
+ if p.phase = `Two && p.div = delta then raise (Done p.sigma);\r
+ if not (is_inert p.div) then problem_fail p "p.div converged"\r
+;;\r
+\r
+(* drops the arguments of t after the n-th *)\r
+let inert_cut_at n t =\r
+ let rec aux t =\r
+ match t with\r
+ | V _ as t -> 0, t\r
+ | A(t1,_) as t ->\r
+ let k', t' = aux t1 in\r
+ if k' = n then n, t'\r
+ else k'+1, t\r
+ | _ -> assert false\r
+ in snd (aux t)\r
+;;\r
+\r
+let find_eta_difference p t n_args =\r
+ let t = inert_cut_at n_args t in\r
+ let rec aux t u k = match t, u with\r
+ | V _, V _ -> assert false (* div subterm of conv *)\r
+ | A(t1,t2), A(u1,u2) ->\r
+ if not (eta_eq t2 u2) then (print_endline((string_of_t t2) ^ " <> " ^ (string_of_t u2)); k)\r
+ else aux t1 u1 (k-1)\r
+ | _, _ -> assert false\r
+ in aux p.div t n_args\r
+;;\r
+\r
+let compute_max_lambdas_at hd_var j =\r
+ let rec aux hd = function\r
+ | A(t1,t2) ->\r
+ (if get_inert t1 = (hd, j)\r
+ then max ( (*FIXME*)\r
+ if is_inert t2 && let hd', j' = get_inert t2 in hd' = hd\r
+ then let hd', j' = get_inert t2 in j - j'\r
+ else no_leading_lambdas t2)\r
+ else id) (max (aux hd t1) (aux hd t2))\r
+ | L t -> aux (hd+1) t\r
+ | V _ -> 0\r
+ | _ -> assert false\r
+ in aux hd_var\r
;;\r
\r
let print_cmd s1 s2 = print_endline (">> " ^ s1 ^ " " ^ s2);;\r
It does NOT perform any check, may fail if done unsafely *)\r
let eat p =\r
print_cmd "EAT" "";\r
- let var = head_of_inert p.div in\r
- let n = args_no p.div in\r
- let rec aux m t =\r
- if m = 0\r
- then lift n t\r
- else L (aux (m-1) t) in\r
- let subst = var, aux n B in\r
- sanity (subst_in_problem subst p)\r
+ let var, k = get_inert p.div in\r
+ let phase = p.phase in\r
+ let p, t =\r
+ match phase with\r
+ | `One ->\r
+ let n = 1 + max\r
+ (compute_max_lambdas_at var k p.div)\r
+ (compute_max_lambdas_at var k p.conv) in\r
+ (* apply fresh vars *)\r
+ let p, t = fold_nat (fun (p, t) _ ->\r
+ let p, v = freshvar p in\r
+ p, A(t, V (v + k))\r
+ ) (p, V 0) n in\r
+ let p = {p with phase=`Two} in p, A(t, delta)\r
+ | `Two -> p, delta in\r
+ let subst = var, mk_lams t k in\r
+ let p = subst_in_problem subst p in\r
+ let p = if phase = `One then {p with div = (match p.div with A(t,_) -> t | _ -> assert false)} else p in\r
+ sanity p; p\r
;;\r
\r
(* step on the head of div, on the k-th argument, with n fresh vars *)\r
let step k n p =\r
- let var = head_of_inert p.div in\r
- print_cmd "STEP" ("on " ^ string_of_t p (V var) ^ " (of:" ^ string_of_int n ^ ")");\r
- let rec aux' p m t =\r
- if m < 0\r
- then p, t\r
- else\r
- let p, v = freshvar p in\r
- let p, t = aux' p (m-1) t in\r
- p, A(t, V (v + k + 1)) in\r
- let p, t = aux' p n (V 0) in\r
- let rec aux' m t = if m < 0 then t else A(aux' (m-1) t, V (k-m)) in\r
- let rec aux m t =\r
- if m < 0\r
- then aux' (k-1) t\r
- else L (aux (m-1) t) in\r
- let t = aux k t in\r
+ let var, _ = get_inert p.div in\r
+print_cmd "STEP" ("on " ^ string_of_t (V var) ^ " (of:" ^ string_of_int n ^ ")");\r
+ let p, t = (* apply fresh vars *)\r
+ fold_nat (fun (p, t) _ ->\r
+ let p, v = freshvar p in\r
+ p, A(t, V (v + k + 1))\r
+ ) (p, V 0) n in\r
+ let t = (* apply unused bound variables V_{k-1}..V_1 *)\r
+ fold_nat (fun t m -> A(t, V (k-m+1))) t k in\r
+ let t = mk_lams t (k+1) in (* make leading lambdas *)\r
let subst = var, t in\r
- sanity (subst_in_problem subst p)\r
+ let p = subst_in_problem subst p in\r
+ sanity p; p\r
;;\r
\r
let parse strs =\r
let rec aux level = function\r
| Parser_andrea.Lam t -> L (aux (level + 1) t)\r
| Parser_andrea.App (t1, t2) ->\r
- if level = 0 then mk_app false (aux level t1) (aux level t2)\r
+ if level = 0 then mk_app (aux level t1) (aux level t2)\r
else A(aux level t1, aux level t2)\r
- | Parser_andrea.Var v -> V v\r
- in let (tms, free) = Parser_andrea.parse_many strs\r
- in (List.map (aux 0) tms, free)\r
+ | Parser_andrea.Var v -> V v in\r
+ let (tms, free) = Parser_andrea.parse_many strs in\r
+ (List.map (aux 0) tms, free)\r
;;\r
\r
let problem_of div conv =\r
print_hline ();\r
- let all_tms, var_names = parse ([div; conv]) in\r
- let div, conv = List.hd all_tms, List.hd (List.tl all_tms) in\r
+ let [@warning "-8"] [div; conv], var_names = parse ([div; conv]) in\r
let varno = List.length var_names in\r
- let p = {orig_freshno=varno; freshno=1+varno; div; conv; sigma=[]; stepped=[]} in\r
- (* activate bombs *)\r
- let p = try\r
- let subst = Util.index_of "BOMB" var_names, L B in\r
- subst_in_problem subst p\r
- with Not_found -> p in\r
- (* activate pacmans *)\r
- let p = try\r
- let subst = Util.index_of "PACMAN" var_names, P in\r
- let p = subst_in_problem subst p in\r
- (print_endline ("after subst in problem " ^ string_of_problem p); p)\r
- with Not_found -> p in\r
+ let p = {orig_freshno=varno; freshno=1+varno; div; conv; sigma=[]; stepped=[]; phase=`One} in\r
(* initial sanity check *)\r
- sanity p\r
+ sanity p; p\r
;;\r
\r
let exec div conv cmds =\r
| Done _ -> ()\r
;;\r
\r
-let inert_cut_at n t =\r
- let rec aux t =\r
- match t with\r
- | V _ as t -> 0, t\r
- | A(t1,_) as t ->\r
- let k', t' = aux t1 in\r
- if k' = n then n, t'\r
- else k'+1, t\r
- | _ -> assert false\r
- in snd (aux t)\r
-;;\r
-\r
-let find_eta_difference p t n_args =\r
- let t = inert_cut_at n_args t in\r
- let rec aux t u k = match t, u with\r
- | V _, V _ -> assert false (* div subterm of conv *)\r
- | A(t1,t2), A(u1,u2) ->\r
- if not (eta_eq t2 u2) then (print_endline((string_of_t p t2) ^ " <> " ^ (string_of_t p u2)); k)\r
- else aux t1 u1 (k-1)\r
- | _, _ -> assert false\r
- in aux p.div t n_args\r
-;;\r
-\r
-let rec no_leading_lambdas = function\r
- | L t -> 1 + no_leading_lambdas t\r
- | _ -> 0\r
-;;\r
-\r
-let compute_max_lambdas_at hd_var j =\r
- let rec aux hd = function\r
- | A(t1,t2) ->\r
- (if head_of_inert t1 = hd && args_no t1 = j\r
- then max (\r
- if is_inert t2 && head_of_inert t2 = hd\r
- then j - args_no t2\r
- else no_leading_lambdas t2)\r
- else id) (max (aux hd t1) (aux hd t2))\r
- | L t -> aux (hd+1) t\r
- | V _ -> 0\r
- | _ -> assert false\r
- in aux hd_var\r
-;;\r
-\r
let rec auto p =\r
- let hd_var = head_of_inert p.div in\r
- let n_args = args_no p.div in\r
+ let hd_var, n_args = get_inert p.div in\r
match get_subterm_with_head_and_args hd_var n_args p.conv with\r
| None ->\r
- (try let p = eat p in problem_fail p "Auto did not complete the problem" with Done _ -> ())\r
+ (try\r
+ let phase = p.phase in\r
+ let p = eat p in\r
+ if phase = `Two\r
+ then problem_fail p "Auto.2 did not complete the problem"\r
+ else auto p\r
+ with Done sigma -> sigma)\r
| Some t ->\r
let j = find_eta_difference p t n_args - 1 in\r
- let k = max\r
+ let k = 1 + max\r
(compute_max_lambdas_at hd_var j p.div)\r
(compute_max_lambdas_at hd_var j p.conv) in\r
let p = step j k p in\r
| x::xs -> conv_join xs ^ " ("^ x ^")"\r
;;\r
\r
-let _ = exec\r
+let auto' a b =\r
+ let p = problem_of a (conv_join b) in\r
+ let sigma = auto p in\r
+ check p sigma\r
+;;\r
+\r
+(* Example usage of exec, interactive:\r
+\r
+exec\r
"x x"\r
(conv_join["x y"; "y y"; "y x"])\r
- [ step 0 0; eat ]\r
+ [ step 0 1; eat ]\r
;;\r
\r
-auto (problem_of "x x" "@ (x y) (y y) (y x)");;\r
-auto (problem_of "x y" "@ (x (_. x)) (y z) (y x)");;\r
-auto (problem_of "a (x. x b) (x. x c)" "@ (a (x. b b) @) (a @ c) (a (x. x x) a) (a (a a a) (a c c))");;\r
-\r
interactive "x y"\r
-"@ (x x) (y x) (y z)" [step 0 0; step 0 1; eat] ;;\r
+ "@ (x x) (y x) (y z)" [step 0 1; step 0 2; eat]\r
+;;\r
\r
-auto (problem_of "x (y. x y y)" "x (y. x y x)");;\r
+*)\r
\r
-auto (problem_of "x a a a a" (conv_join[\r
+auto' "x x" ["x y"; "y y"; "y x"] ;;\r
+auto' "x y" ["x (_. x)"; "y z"; "y x"] ;;\r
+auto' "a (x. x b) (x. x c)" ["a (x. b b) @"; "a @ c"; "a (x. x x) a"; "a (a a a) (a c c)"] ;;\r
+\r
+auto' "x (y. x y y)" ["x (y. x y x)"] ;;\r
+\r
+auto' "x a a a a" [\r
"x b a a a";\r
"x a b a a";\r
"x a a b a";\r
"x a a a b";\r
-]));\r
+] ;;\r
\r
(* Controesempio ad usare un conto dei lambda che non considere le permutazioni *)\r
-auto (problem_of "x a a a a (x (x. x x) @ @ (_._.x. x x) x) b b b" (conv_join[\r
+auto' "x a a a a (x (x. x x) @ @ (_._.x. x x) x) b b b" [\r
"x a a a a (_. a) b b b";\r
"x a a a a (_. _. _. _. x. y. x y)";\r
-]));\r
+] ;;\r
\r
\r
print_hline();\r
print_endline "ALL DONE. "\r
-\r
-(* TEMPORARY TESTING FACILITY BELOW HERE *)\r
-\r
-let acaso l =\r
- let n = Random.int (List.length l) in\r
- List.nth l n\r
-;;\r
-\r
-let acaso2 l1 l2 =\r
- let n1 = List.length l1 in\r
- let n = Random.int (n1 + List.length l2) in\r
- if n >= n1 then List.nth l2 (n - n1) else List.nth l1 n\r
-;;\r
-\r
-let gen n vars =\r
- let rec aux n inerts lams =\r
- if n = 0 then List.hd inerts, List.hd (Util.sort_uniq (List.tl inerts))\r
- else let inerts, lams = if Random.int 2 = 0\r
- then inerts, ("(" ^ acaso vars ^ ". " ^ acaso2 inerts lams ^ ")") :: lams\r
- else ("(" ^ acaso inerts ^ " " ^ acaso2 inerts lams^ ")") :: inerts, lams\r
- in aux (n-1) inerts lams\r
- in aux (2*n) vars []\r
-;;\r
-\r
-let f () =\r
- let complex = 200 in\r
- let vars = ["x"; "y"; "z"; "v" ; "w"; "a"; "b"; "c"] in\r
- gen complex vars\r
-\r
- let rec repeat f n =\r
- prerr_endline "\n########################### NEW TEST ###########################";\r
- f () ;\r
- if n > 0 then repeat f (n-1)\r
- ;;\r
-\r
-\r
-let main () =\r
- Random.self_init ();\r
- repeat (fun _ ->\r
- let div, conv = f () in\r
- auto (problem_of div conv)\r
- ) 100;\r
-;;\r
-\r
-(* main ();; *)\r
projects / fireball-separation.git / blobdiff