X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=helm%2Focaml%2Fcic_disambiguation%2Fdisambiguate.ml;h=02a51678b070429c89b9d6abbf4e15a7c3b4885f;hb=0c6a5aadb1a7746681a8e26fc0b009f847c10557;hp=f7cfce144d7b6daacbceaafdc16ef71cdbc4286d;hpb=978a25d9392e5fc1a19fa37c86339c5d0b67ddd6;p=helm.git diff --git a/helm/ocaml/cic_disambiguation/disambiguate.ml b/helm/ocaml/cic_disambiguation/disambiguate.ml index f7cfce144..02a51678b 100644 --- a/helm/ocaml/cic_disambiguation/disambiguate.ml +++ b/helm/ocaml/cic_disambiguation/disambiguate.ml @@ -37,6 +37,15 @@ exception Try_again let debug = true let debug_print = if debug then prerr_endline else ignore +(* + (** print benchmark information *) +let benchmark = true +let max_refinements = ref 0 (* benchmarking is not thread safe *) +let actual_refinements = ref 0 +let domain_size = ref 0 +let choices_avg = ref 0. +*) + let descr_of_domain_item = function | Id s -> s | Symbol (s, _) -> s @@ -48,7 +57,8 @@ type test_result = | Uncertain let refine metasenv context term = - let metasenv, term = CicMkImplicit.expand_implicits metasenv context term in +(* if benchmark then incr actual_refinements; *) + let metasenv, term = CicMkImplicit.expand_implicits metasenv [] context term in debug_print (sprintf "TEST_INTERPRETATION: %s" (CicPp.ppterm term)); try let term', _, metasenv' = CicRefine.type_of_aux' metasenv context term in @@ -203,49 +213,58 @@ let interpretate ~context ~env ast = raise DisambiguateChoices.Invalid_choice)) subst | None -> List.map (fun uri -> uri, Cic.Implicit None) uris) - in - (match cic with - | Cic.Const (uri, []) -> - let uris = - match CicEnvironment.get_obj uri with - | Cic.Constant (_, _, _, uris) -> uris - | _ -> assert false - in - Cic.Const (uri, mk_subst uris) - | Cic.Var (uri, []) -> - let uris = - match CicEnvironment.get_obj uri with - | Cic.Variable (_, _, _, uris) -> uris - | _ -> assert false - in - Cic.Var (uri, mk_subst uris) - | Cic.MutInd (uri, i, []) -> - let uris = - match CicEnvironment.get_obj uri with - | Cic.InductiveDefinition (_, uris, _) -> uris - | _ -> assert false - in - Cic.MutInd (uri, i, mk_subst uris) - | Cic.MutConstruct (uri, i, j, []) -> - let uris = - match CicEnvironment.get_obj uri with - | Cic.InductiveDefinition (_, uris, _) -> uris - | _ -> assert false - in - Cic.MutConstruct (uri, i, j, mk_subst uris) - | Cic.Meta _ | Cic.Implicit _ as t -> + in + (* the try is for CicTypeChecker.typecheck *) + (try + match cic with + | Cic.Const (uri, []) -> + let uris = + match CicEnvironment.get_obj uri with + (*match CicTypeChecker.typecheck uri with*) + | Cic.Constant (_, _, _, uris) -> uris + | _ -> assert false + in + Cic.Const (uri, mk_subst uris) + | Cic.Var (uri, []) -> + let uris = + match CicEnvironment.get_obj uri with + (*match CicTypeChecker.typecheck uri with*) + | Cic.Variable (_, _, _, uris) -> uris + | _ -> assert false + in + Cic.Var (uri, mk_subst uris) + | Cic.MutInd (uri, i, []) -> + let uris = + match CicEnvironment.get_obj uri with + (*match CicTypeChecker.typecheck uri with*) + | Cic.InductiveDefinition (_, uris, _) -> uris + | _ -> assert false + in + Cic.MutInd (uri, i, mk_subst uris) + | Cic.MutConstruct (uri, i, j, []) -> + let uris = + match CicEnvironment.get_obj uri with + (*match CicTypeChecker.typecheck uri with*) + | Cic.InductiveDefinition (_, uris, _) -> uris + | _ -> assert false + in + Cic.MutConstruct (uri, i, j, mk_subst uris) + | Cic.Meta _ | Cic.Implicit _ as t -> (* - prerr_endline (sprintf - "Warning: %s must be instantiated with _[%s] but we do not enforce it" - (CicPp.ppterm t) - (String.concat "; " - (List.map - (fun (s, term) -> s ^ " := " ^ CicAstPp.pp_term term) - subst))); + prerr_endline (sprintf + "Warning: %s must be instantiated with _[%s] but we do not enforce it" + (CicPp.ppterm t) + (String.concat "; " + (List.map + (fun (s, term) -> s ^ " := " ^ CicAstPp.pp_term term) + subst))); *) - t - | _ -> - raise DisambiguateChoices.Invalid_choice)) + t + | _ -> + raise DisambiguateChoices.Invalid_choice + with + CicEnvironment.CircularDependency _ -> + raise DisambiguateChoices.Invalid_choice)) | CicAst.Implicit -> Cic.Implicit None | CicAst.Num (num, i) -> resolve env (Num i) ~num () | CicAst.Meta (index, subst) -> @@ -267,7 +286,7 @@ let interpretate ~context ~env ast = in match ast with | CicAst.AttributedTerm (`Loc loc, term) -> aux loc context term - | term -> aux (-1, -1) context term + | term -> aux CicAst.dummy_floc context term let domain_of_term ~context ast = (* "aux" keeps domain in reverse order and doesn't care about duplicates. @@ -381,8 +400,7 @@ let domain_of_term ~context ast = rev_uniq (match ast with | CicAst.AttributedTerm (`Loc loc, term) -> aux loc context term - | term -> aux (-1, -1) context term) - + | term -> aux CicAst.dummy_floc context term) (* dom1 \ dom2 *) let domain_diff dom1 dom2 = @@ -462,9 +480,35 @@ module Make (C: Callbacks) = if choices = [] then raise (No_choices item); choices in + +(* + (* *) + let _ = + if benchmark then begin + let per_item_choices = + List.map + (fun dom_item -> + try + let len = List.length (lookup_choices dom_item) in + prerr_endline (sprintf "BENCHMARK %s: %d" + (string_of_domain_item dom_item) len); + len + with No_choices _ -> 0) + term_dom + in + max_refinements := List.fold_left ( * ) 1 per_item_choices; + actual_refinements := 0; + domain_size := List.length term_dom; + choices_avg := + (float_of_int !max_refinements) ** (1. /. float_of_int !domain_size) + end + in + (* *) +*) + (* (3) test an interpretation filling with meta uninterpreted identifiers *) - let test_env current_env todo_dom = + let test_env current_env todo_dom univ = let filled_env = List.fold_left (fun env item -> @@ -476,66 +520,98 @@ module Make (C: Callbacks) = current_env todo_dom in try + CicUniv.set_working univ; let cic_term = interpretate ~context:disambiguate_context ~env:filled_env term in - refine metasenv context cic_term + let k = refine metasenv context cic_term in + let new_univ = CicUniv.get_working () in + (k , new_univ ) with - | Try_again -> Uncertain - | DisambiguateChoices.Invalid_choice -> Ko + | Try_again -> Uncertain,univ + | DisambiguateChoices.Invalid_choice -> Ko,univ in (* (4) build all possible interpretations *) - let rec aux current_env todo_dom = + let rec aux current_env todo_dom base_univ = match todo_dom with | [] -> - (match test_env current_env [] with - | Ok (term, metasenv) -> [ current_env, metasenv, term ] - | Ko | Uncertain -> []) + (match test_env current_env [] base_univ with + | Ok (term, metasenv),new_univ -> + [ current_env, metasenv, term, new_univ ] + | Ko,_ | Uncertain,_ -> []) | item :: remaining_dom -> debug_print (sprintf "CHOOSED ITEM: %s" - (string_of_domain_item item)); + (string_of_domain_item item)); let choices = lookup_choices item in - let rec filter = function + let rec filter univ = function | [] -> [] | codomain_item :: tl -> debug_print (sprintf "%s CHOSEN" (fst codomain_item)) ; let new_env = Environment.add item codomain_item current_env in - (match test_env new_env remaining_dom with - | Ok (term, metasenv) -> + (match test_env new_env remaining_dom univ with + | Ok (term, metasenv),new_univ -> (match remaining_dom with - | [] -> [ new_env, metasenv, term ] - | _ -> aux new_env remaining_dom) @ filter tl - | Uncertain -> + | [] -> [ new_env, metasenv, term, new_univ ] + | _ -> aux new_env remaining_dom new_univ )@ + filter univ tl + | Uncertain,new_univ -> (match remaining_dom with | [] -> [] - | _ -> aux new_env remaining_dom) @ filter tl - | Ko -> filter tl) + | _ -> aux new_env remaining_dom new_univ )@ + filter univ tl + | Ko,_ -> filter univ tl) in - filter choices + filter base_univ choices in - match aux current_env todo_dom with - | [] -> raise NoWellTypedInterpretation - | [ _ ] as l -> - debug_print "UNA SOLA SCELTA"; - l - | l -> - debug_print (sprintf "PIU' SCELTE (%d)" (List.length l)); - let choices = - List.map - (fun (env, _, _) -> - List.map - (fun domain_item -> - let description = - fst (Environment.find domain_item env) - in - (descr_of_domain_item domain_item, description)) - term_dom) - l - in - let choosed = C.interactive_interpretation_choice choices in - List.map (List.nth l) choosed - + let base_univ = CicUniv.get_working () in + try + let res = + match aux current_env todo_dom base_univ with + | [] -> raise NoWellTypedInterpretation + | [ e,me,t,u ] as l -> + debug_print "UNA SOLA SCELTA"; + CicUniv.set_working u; + [ e,me,t ] + | l -> + debug_print (sprintf "PIU' SCELTE (%d)" (List.length l)); + let choices = + List.map + (fun (env, _, _, _) -> + List.map + (fun domain_item -> + let description = + fst (Environment.find domain_item env) + in + (descr_of_domain_item domain_item, description)) + term_dom) + l + in + let choosed = C.interactive_interpretation_choice choices in + let l' = List.map (List.nth l) choosed in + match l' with + [] -> assert false + | [e,me,t,u] -> + CicUniv.set_working u; + (*CicUniv.print_working_graph ();*) + [e,me,t] + | hd::tl -> (* ok, testlibrary... cosi' stampa MANY... bah *) + List.map (fun (e,me,t,u) -> (e,me,t)) l' + in +(* + (if benchmark then + let res_size = List.length res in + prerr_endline (sprintf + ("BENCHMARK: %d/%d refinements performed, domain size %d, interps %d, k %.2f\n" ^^ + "BENCHMARK: estimated %.2f") + !actual_refinements !max_refinements !domain_size res_size + !choices_avg + (float_of_int (!domain_size - 1) *. !choices_avg *. (float_of_int res_size) +. !choices_avg))); +*) + res + with + CicEnvironment.CircularDependency s -> + raise (Failure "e chi la becca sta CircularDependency?"); end