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
| A of t * t\r
| L of t\r
| B (* bottom *)\r
- | P (* pacman *)\r
;;\r
\r
let eta_eq =\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
+}\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
| A (t1,t2) ->\r
let t1 = subst level delift sub t1 in\r
let t2 = subst level delift sub t2 in\r
- if t1 = B || t2 = B then B else mk_app t1 t2\r
+ mk_app t1 t2\r
| B -> B\r
- | P -> P\r
-and mk_app t1 t2 = let t1 = if t1 = P then L P else t1 in match t1 with\r
+and mk_app t1 t2 = match t1 with\r
| B | _ when t2 = B -> B\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 sub p.conv in\r
- let div = subst 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 lev = function\r
- | V _ | B | P -> None\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 + lev && n_args <= 1 + args_no t1 (* why `1+' ?*)\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
in aux 0\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
-\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 not (is_inert p.div) then problem_fail p "p.div converged"\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, n = get_inert p.div in\r
+ let subst = var, mk_lams B n in\r
+ let p = subst_in_problem subst 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
| Parser_andrea.App (t1, 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
(* initial sanity check *)\r
- sanity p\r
+ sanity p; p\r
;;\r
\r
let exec div conv cmds =\r
| Done _ -> ()\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
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
+ 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 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
+ (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
;;\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 problem_fail (eat p) "Auto did not complete the problem" with Done _ -> ())\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
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
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
*)\r
projects / fireball-separation.git / blobdiff