helm/ocaml/cic_omdoc/eta_fixing.ml

   1 (* Copyright (C) 2000, HELM Team.
   2  *
   3  * This file is part of HELM, an Hypertextual, Electronic
   4  * Library of Mathematics, developed at the Computer Science
   5  * Department, University of Bologna, Italy.
   6  *
   7  * HELM is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation; either version 2
  10  * of the License, or (at your option) any later version.
  11  *
  12  * HELM is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with HELM; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  20  * MA  02111-1307, USA.
  21  *
  22  * For details, see the HELM World-Wide-Web page,
  23  * http://cs.unibo.it/helm/.
  24  *)
  25
  26 exception ReferenceToVariable;;
  27 exception RferenceToCurrentProof;;
  28 exception ReferenceToInductiveDefinition;;
  29
  30 (*
  31 let rec fix_lambdas_wrt_type ty te =
  32  let module C = Cic in
  33  let module S = CicSubstitution in
  34 (*  prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
  35    match ty with
  36      C.Prod (_,_,ty') ->
  37        (match CicReduction.whd [] te with
  38           C.Lambda (n,s,te') ->
  39             C.Lambda (n,s,fix_lambdas_wrt_type ty' te')
  40         | t ->
  41             let rec get_sources =
  42               function
  43                 C.Prod (_,s,ty) -> s::(get_sources ty)
  44               | _ -> [] in
  45             let sources = get_sources ty in
  46             let no_sources = List.length sources in
  47             let rec mk_rels n shift =
  48               if n = 0 then []
  49             else (C.Rel (n + shift))::(mk_rels (n - 1) shift) in
  50             let t' = S.lift no_sources t in
  51             let t2 =
  52               match t' with
  53                 C.Appl l ->
  54                   C.LetIn
  55                      (C.Name "w",t',C.Appl ((C.Rel 1)::(mk_rels no_sources 1)))
  56               | _ ->
  57                   C.Appl (t'::(mk_rels no_sources 0)) in
  58                    List.fold_right
  59                      (fun source t -> C.Lambda (C.Name "y",source,t))
  60                       sources t2)
  61    | _ -> te
  62 ;; *)
  63
  64 let rec fix_lambdas_wrt_type ty te =
  65  let module C = Cic in
  66  let module S = CicSubstitution in
  67 (*  prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
  68    match ty,te with
  69      C.Prod (_,_,ty'), C.Lambda (n,s,te') ->
  70        C.Lambda (n,s,fix_lambdas_wrt_type ty' te')
  71    | C.Prod (_,s,ty'), t ->
  72       let rec get_sources =
  73         function
  74             C.Prod (_,s,ty) -> s::(get_sources ty)
  75           | _ -> [] in
  76       let sources = get_sources ty in
  77       let no_sources = List.length sources in
  78       let rec mk_rels n shift =
  79         if n = 0 then []
  80         else (C.Rel (n + shift))::(mk_rels (n - 1) shift) in
  81       let t' = S.lift no_sources t in
  82       let t2 =
  83          match t' with
  84            C.Appl l ->
  85              C.LetIn (C.Name "w",t',C.Appl ((C.Rel 1)::(mk_rels no_sources 1)))
  86          | _ -> C.Appl (t'::(mk_rels no_sources 0)) in
  87       List.fold_right
  88         (fun source t -> C.Lambda (C.Name "y",CicReduction.whd [] source,t)) sources t2
  89    | _, _ -> te
  90 ;;
  91
  92 (*
  93 let rec fix_lambdas_wrt_type ty te =
  94  let module C = Cic in
  95  let module S = CicSubstitution in
  96 (*  prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
  97    match ty,te with
  98      C.Prod (_,_,ty'), C.Lambda (n,s,te') ->
  99        C.Lambda (n,s,fix_lambdas_wrt_type ty' te')
 100    | C.Prod (_,s,ty'), ((C.Appl (C.Const _ ::_)) as t) ->
 101       (* const have a fixed arity *)
 102       (* prerr_endline ("******** fl - eta expansion 0: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
 103        let t' = S.lift 1 t in
 104        C.Lambda (C.Name "x",s,
 105          C.LetIn
 106           (C.Name "H", fix_lambdas_wrt_type ty' t',
 107             C.Appl [C.Rel 1;C.Rel 2]))
 108    | C.Prod (_,s,ty'), C.Appl l ->
 109        (* prerr_endline ("******** fl - eta expansion 1: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
 110        let l' = List.map (S.lift 1) l in
 111         C.Lambda (C.Name "x",s,
 112          fix_lambdas_wrt_type ty' (C.Appl (l'@[C.Rel 1])))
 113    | C.Prod (_,s,ty'), _ ->
 114        (* prerr_endline ("******** fl - eta expansion 2: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
 115        flush stderr ;
 116        let te' = S.lift 1 te in
 117         C.Lambda (C.Name "x",s,
 118           fix_lambdas_wrt_type ty' (C.Appl [te';C.Rel 1]))
 119    | _, _ -> te
 120 ;;*)
 121
 122 let fix_according_to_type ty hd tl =
 123  let module C = Cic in
 124  let module S = CicSubstitution in
 125    let rec count_prods =
 126      function
 127        C.Prod (_,_,t) -> 1 + (count_prods t)
 128        | _ -> 0 in
 129   let expected_arity = count_prods ty in
 130   let rec aux n ty tl res =
 131     if n = 0 then
 132       (match tl with
 133          [] -> C.Appl res
 134        | _ ->
 135           match res with
 136             [] -> assert false
 137           | [a] -> C.Appl (a::tl)
 138           | _ ->
 139               (* prerr_endline ("******* too many args: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm (C.Appl res)); *)
 140               C.LetIn
 141                 (C.Name "H",
 142                   C.Appl res, C.Appl (C.Rel 1::(List.map (S.lift 1) tl))))
 143     else
 144       let name,source,target =
 145         (match ty with
 146            C.Prod (C.Name _ as n,s,t) -> n,s,t
 147          | C.Prod (C.Anonymous, s,t) -> C.Name "z",s,t
 148          | _ -> (* prods number may only increase for substitution *)
 149            assert false) in
 150       match tl with
 151          [] ->
 152            (* prerr_endline ("******* too few args: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm (C.Appl res)); *)
 153            let res' = List.map (S.lift 1) res in
 154            C.Lambda
 155             (name, source, aux (n-1) target [] (res'@[C.Rel 1]))
 156         | hd::tl' ->
 157            let hd' = fix_lambdas_wrt_type source hd in
 158             (*  (prerr_endline ("++++++prima :" ^(CicPp.ppterm hd));
 159               prerr_endline ("++++++dopo :" ^(CicPp.ppterm hd'))); *)
 160            aux (n-1) (S.subst hd' target) tl' (res@[hd']) in
 161   aux expected_arity ty tl [hd]
 162 ;;
 163
 164 let eta_fix metasenv t =
 165  let rec eta_fix' context t =
 166   prerr_endline ("entering aux with: term=" ^ CicPp.ppterm t);
 167   flush stderr ;
 168   let module C = Cic in
 169   let module S = CicSubstitution in
 170   match t with
 171      C.Rel n -> C.Rel n
 172    | C.Var (uri,exp_named_subst) ->
 173       let exp_named_subst' =
 174        List.map
 175         (function i,t -> i, (eta_fix' context t)) exp_named_subst
 176       in
 177       C.Var (uri,exp_named_subst')
 178    | C.Meta (n,l) ->
 179       let (_,canonical_context,_) =
 180        List.find (function (m,_,_) -> n = m) metasenv
 181        in
 182        let l' =
 183         List.map2
 184          (fun ct t ->
 185           match (ct, t) with
 186             None, _ -> None
 187           | _, Some t -> Some (eta_fix' context t)
 188           | Some _, None -> assert false (* due to typing rules *))
 189         canonical_context l
 190        in
 191        C.Meta (n,l')
 192    | C.Sort s -> C.Sort s
 193    | C.Implicit -> C.Implicit
 194    | C.Cast (v,t) -> C.Cast (eta_fix' context v, eta_fix' context t)
 195    | C.Prod (n,s,t) ->
 196        C.Prod
 197         (n, eta_fix' context s, eta_fix' ((Some (n,(C.Decl s)))::context) t)
 198    | C.Lambda (n,s,t) ->
 199        C.Lambda
 200         (n, eta_fix' context s, eta_fix' ((Some (n,(C.Decl s)))::context) t)
 201    | C.LetIn (n,s,t) ->
 202        C.LetIn
 203         (n, eta_fix' context s, eta_fix' ((Some (n,(C.Def s)))::context) t)
 204    | C.Appl l as appl ->
 205        let l' =  List.map (eta_fix' context) l
 206        in
 207        (match l' with
 208          C.Const(uri,exp_named_subst)::l'' ->
 209            let constant_type =
 210              (match CicEnvironment.get_obj uri with
 211                C.Constant (_,_,ty,_) -> ty
 212              | C.Variable _ -> raise ReferenceToVariable
 213              | C.CurrentProof (_,_,_,_,params) -> raise RferenceToCurrentProof
 214              | C.InductiveDefinition _ -> raise ReferenceToInductiveDefinition
 215              )
 216            in
 217            let result = fix_according_to_type constant_type (C.Const(uri,exp_named_subst)) l'' in
 218            if not (CicReduction.are_convertible [] appl result) then
 219              (prerr_endline ("prima :" ^(CicPp.ppterm appl));
 220               prerr_endline ("dopo :" ^(CicPp.ppterm result)));
 221            result
 222         | _ -> C.Appl l' )
 223    | C.Const (uri,exp_named_subst) ->
 224        let exp_named_subst' =
 225        List.map
 226         (function i,t -> i, (eta_fix' context t)) exp_named_subst
 227        in
 228        C.Const (uri,exp_named_subst')
 229    | C.MutInd (uri,tyno,exp_named_subst) ->
 230        let exp_named_subst' =
 231        List.map
 232         (function i,t -> i, (eta_fix' context t)) exp_named_subst
 233        in
 234         C.MutInd (uri, tyno, exp_named_subst')
 235    | C.MutConstruct (uri,tyno,consno,exp_named_subst) ->
 236        let exp_named_subst' =
 237        List.map
 238         (function i,t -> i, (eta_fix' context t)) exp_named_subst
 239        in
 240         C.MutConstruct (uri, tyno, consno, exp_named_subst')
 241    | C.MutCase (uri, tyno, outty, term, patterns) as prima ->
 242        let outty' =  eta_fix' context outty in
 243        let term' = eta_fix' context term in
 244        let patterns' = List.map (eta_fix' context) patterns in
 245        let inductive_types,noparams =
 246            (match CicEnvironment.get_obj uri with
 247                Cic.Constant _ -> assert false
 248              | Cic.Variable _ -> assert false
 249              | Cic.CurrentProof _ -> assert false
 250              | Cic.InductiveDefinition (l,_,n) -> l,n
 251            ) in
 252        let (_,_,_,constructors) = List.nth inductive_types tyno in
 253         prerr_endline ("QUI");
 254        let constructor_types =
 255          let rec clean_up t =
 256            function
 257                [] -> t
 258              | a::tl ->
 259                  (match t with
 260                    Cic.Prod (_,_,t') -> clean_up (S.subst a t') tl
 261                   | _ -> assert false) in
 262           if noparams = 0 then
 263             List.map (fun (_,t) -> t) constructors
 264           else
 265             let term_type =
 266               CicTypeChecker.type_of_aux' metasenv context term in
 267             (match term_type with
 268                C.Appl (hd::params) ->
 269                  List.map (fun (_,t) -> clean_up t params) constructors
 270              | _ -> prerr_endline ("QUA"); assert false) in
 271        let patterns2 =
 272          List.map2 fix_lambdas_wrt_type
 273            constructor_types patterns in
 274        let dopo =
 275          C.MutCase (uri, tyno, outty',term',patterns2) in
 276        if not (CicReduction.are_convertible [] prima dopo) then
 277              (prerr_endline ("prima :" ^(CicPp.ppterm prima));
 278               prerr_endline ("dopo :" ^(CicPp.ppterm dopo)));
 279            dopo
 280    | C.Fix (funno, funs) ->
 281        let fun_types =
 282          List.map (fun (n,_,ty,_) -> Some (C.Name n,(Cic.Decl ty))) funs in
 283        C.Fix (funno,
 284         List.map
 285          (fun (name, no, ty, bo) ->
 286            (name, no, eta_fix' context ty, eta_fix' (fun_types@context) bo))
 287         funs)
 288    | C.CoFix (funno, funs) ->
 289        let fun_types =
 290          List.map (fun (n,ty,_) -> Some (C.Name n,(Cic.Decl ty))) funs in
 291        C.CoFix (funno,
 292         List.map
 293          (fun (name, ty, bo) ->
 294            (name, eta_fix' context ty, eta_fix' (fun_types@context) bo)) funs)
 295    in
 296    eta_fix' [] t
 297 ;;
 298
 299
 300
 301
 302