From 6895644003c1c199f1a43d300b04a975959024e8 Mon Sep 17 00:00:00 2001 From: acondolu Date: Mon, 10 Jul 2017 14:06:55 +0200 Subject: [PATCH] new_arity = old_arity + 1 --- ocaml/lambda4.ml | 8 +++++--- ocaml/num.ml | 23 +++++++++++++++-------- ocaml/num.mli | 2 +- ocaml/util.ml | 5 +++++ ocaml/util.mli | 1 + 5 files changed, 27 insertions(+), 12 deletions(-) diff --git a/ocaml/lambda4.ml b/ocaml/lambda4.ml index 8498513..304df8a 100644 --- a/ocaml/lambda4.ml +++ b/ocaml/lambda4.ml @@ -419,7 +419,9 @@ let instantiate p x n = (if hd_of_i_var (cast_to_i_var !bomb) = x then failwithProblem p ("BOMB (" ^ string_of_nf !bomb ^ ") cannot be instantiated!")); let arity_of_x = max_arity_tms x (all_terms p) in - (if arity_of_x < 0 then failwithProblem p "step on a var of negative arity"); + (if arity_of_x = None then failwithProblem p "step on var non occurring in problem"); + (if Util.option_get(arity_of_x) = min_int then failwithProblem p "step on fake variable"); + (if Util.option_get(arity_of_x) <= 0 then failwithProblem p "step on var of non-positive arity"); (* AC: Once upon a time, it was: let arities = Num.compute_arities x (n+1) (all_terms p :> nf list) in *) (* let arities = Array.to_list (Array.make (n+1) 0) in *) @@ -427,8 +429,8 @@ let instantiate p x n = let p,vars = make_fresh_vars p arities in let args = Listx.from_list (vars :> nf list) in let bs = ref [] in - (* min_int, since it will be replaced anyway during subst: *) - let inst = `Lam(false,`Match(`I((0,n+1),Listx.map (lift 1) args),(x,min_int),1,bs,[])) in + (* 666, since it will be replaced anyway during subst: *) + let inst = `Lam(false,`Match(`I((0,n+2),Listx.map (lift 1) args),(x,666),1,bs,[])) in let p = {p with deltas=bs::p.deltas} in subst_in_problem x inst p ;; diff --git a/ocaml/num.ml b/ocaml/num.ml index 3c84f4f..d59d07f 100644 --- a/ocaml/num.ml +++ b/ocaml/num.ml @@ -161,9 +161,11 @@ let set_arity arity = function | `Var(n,_) -> `Var(n,arity) | `Lam(false, `N _) | `Lam(false, `Lam _) as t -> t -| `Lam(false, `Match(t,(n,ar),bs_lift,bs,args)) -> `Lam(false, `Match(t,(n,arity),bs_lift,bs,args)) +| `Lam(false, `Match(t,(n,_),bs_lift,bs,args)) -> `Lam(false, `Match(t,(n,arity),bs_lift,bs,args)) | _ -> assert false +let minus1 n = if n = min_int then n else n - 1;; + let rec mk_app (h : nf) (arg : nf) = (*let res =*) match h with @@ -187,7 +189,7 @@ and mk_match t (n,ar) bs_lift bs args = `N m -> (try let h = List.assoc m !bs in - let h = set_arity (ar-1) h in + let h = set_arity (minus1 ar) h in let h = lift bs_lift h in mk_appl h args with Not_found -> @@ -236,12 +238,12 @@ prerr_endline ("subst l:" ^ string_of_int l ^ " delift_by_one:" ^ string_of_bool let parse' strs = let fix_arity = function - | `I((n,_),args) -> `I((n,Listx.length args),args) + | `I((n,_),args) -> `I((n,1+Listx.length args),args) | _ -> assert false in let rec aux = function | Parser.Lam t -> `Lam (true, aux t) | Parser.App (t1, t2) -> fix_arity (mk_app (aux t1) (aux t2)) - | Parser.Var v -> `Var(v,0) in + | Parser.Var v -> `Var(v,1) in let (tms, free) = Parser.parse_many strs in List.map aux tms, free ;; @@ -305,15 +307,20 @@ let eta_subterm (#nf as x) (#nf as y) = eta_subterm x y;; let max_arity_tms n = - let aux_var l (m,a) = if n + l = m then a else -1 in + let max a b = match a, b with + | None, None -> None + | None, Some x + | Some x, None -> Some x + | Some x, Some y -> Some (Pervasives.max x y) in + let aux_var l (m,a) = if n + l = m then Some a else None in let rec aux l = function | `Var v -> aux_var l v | `I(v,tms) -> max (aux_var l v) (aux_tms l (Listx.to_list tms)) | `Lam(_,t) -> aux (l+1) t | `Match(u,_,_,bs,args) -> max (max (aux l (u :> nf)) (aux_tms l args)) (aux_tms l (List.map snd !bs)) - | `N _ -> -1 + | `N _ -> None and aux_tms l = - List.fold_left (fun acc t -> Pervasives.max acc (aux l t)) ~-1 in + List.fold_left (fun acc t -> Pervasives.max acc (aux l t)) None in fun tms -> aux_tms 0 (tms :> nf list) ;; @@ -333,7 +340,7 @@ let compute_arities m = then [] else let tms = Util.filter_map (function `Lam(_,t) -> Some t | _ -> None ) tms in - let arity = max 0 (max_arity_tms (m-n) tms) in (* FIXME: 0 or -1 ??? *) + let arity = match max_arity_tms (m-n) tms with None -> -666 | Some x -> x in arity :: (aux (n-1) tms) in fun tms -> List.rev (aux m tms) ;; diff --git a/ocaml/num.mli b/ocaml/num.mli index c981cff..ca99e44 100644 --- a/ocaml/num.mli +++ b/ocaml/num.mli @@ -43,5 +43,5 @@ val parse' : string list -> nf list * string list val eta_compare : nf -> nf -> int val eta_eq : [< nf ] -> [< nf ] -> bool val eta_subterm : [< nf ] -> [< nf ] -> bool -val max_arity_tms : int -> [< nf] list -> int +val max_arity_tms : int -> [< nf] list -> int option val compute_arities : int -> int -> nf list -> int list diff --git a/ocaml/util.ml b/ocaml/util.ml index a4af2dd..a87b96f 100644 --- a/ocaml/util.ml +++ b/ocaml/util.ml @@ -14,6 +14,11 @@ let option_map f = function | Some x -> Some (f x) ;; +let option_get = function + | Some x -> x + | None -> failwith "option_get: None" +;; + let rec find_opt f = function [] -> None diff --git a/ocaml/util.mli b/ocaml/util.mli index 751225a..96f03ed 100644 --- a/ocaml/util.mli +++ b/ocaml/util.mli @@ -1,6 +1,7 @@ val ( ++ ) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b val findi : ('a -> bool) -> 'a list -> (int * 'a) val option_map : ('a -> 'b) -> 'a option -> 'b option +val option_get : ('a option) -> 'a val find_opt : ('a -> 'b option) -> 'a list -> 'b option val index_of : ?eq:('a -> 'a -> bool) -> 'a -> 'a list -> int val index_of_opt : ?eq:('a -> 'a -> bool) -> 'a list -> 'a -> int option -- 2.39.2