helm/software/components/cic_acic/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 (* $Id$ *)
  27
  28 exception ReferenceToNonVariable;;
  29
  30 let prerr_endline _ = ();;
  31
  32 (*
  33 let rec fix_lambdas_wrt_type ty te =
  34  let module C = Cic in
  35  let module S = CicSubstitution in
  36 (*  prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
  37    match ty with
  38      C.Prod (_,_,ty') ->
  39        (match CicReduction.whd [] te with
  40           C.Lambda (n,s,te') ->
  41             C.Lambda (n,s,fix_lambdas_wrt_type ty' te')
  42         | t ->
  43             let rec get_sources =
  44               function
  45                 C.Prod (_,s,ty) -> s::(get_sources ty)
  46               | _ -> [] in
  47             let sources = get_sources ty in
  48             let no_sources = List.length sources in
  49             let rec mk_rels n shift =
  50               if n = 0 then []
  51             else (C.Rel (n + shift))::(mk_rels (n - 1) shift) in
  52             let t' = S.lift no_sources t in
  53             let t2 =
  54               match t' with
  55                 C.Appl l ->
  56                   C.LetIn
  57                      (C.Name "w",t',C.Appl ((C.Rel 1)::(mk_rels no_sources 1)))
  58               | _ ->
  59                   C.Appl (t'::(mk_rels no_sources 0)) in
  60                    List.fold_right
  61                      (fun source t -> C.Lambda (C.Name "y",source,t))
  62                       sources t2)
  63    | _ -> te
  64 ;; *)
  65
  66 let rec fix_lambdas_wrt_type ty te =
  67  let module C = Cic in
  68  let module S = CicSubstitution in
  69 (*  prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
  70    match ty,te with
  71      C.Prod (_,_,ty'), C.Lambda (n,s,te') ->
  72        C.Lambda (n,s,fix_lambdas_wrt_type ty' te')
  73    | C.Prod (_,s,ty'), t ->
  74       let rec get_sources =
  75         function
  76             C.Prod (_,s,ty) -> s::(get_sources ty)
  77           | _ -> [] in
  78       let sources = get_sources ty in
  79       let no_sources = List.length sources in
  80       let rec mk_rels n shift =
  81         if n = 0 then []
  82         else (C.Rel (n + shift))::(mk_rels (n - 1) shift) in
  83       let t' = S.lift no_sources t in
  84       let t2 =
  85          match t' with
  86            C.Appl l ->
  87              C.LetIn (C.Name "w",t',assert false,
  88               C.Appl ((C.Rel 1)::(mk_rels no_sources 1)))
  89          | _ -> C.Appl (t'::(mk_rels no_sources 0)) in
  90       List.fold_right
  91         (fun source t -> C.Lambda (C.Name "y",CicReduction.whd [] source,t)) sources t2
  92    | _, _ -> te
  93 ;;
  94
  95 (*
  96 let rec fix_lambdas_wrt_type ty te =
  97  let module C = Cic in
  98  let module S = CicSubstitution in
  99 (*  prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
 100    match ty,te with
 101      C.Prod (_,_,ty'), C.Lambda (n,s,te') ->
 102        C.Lambda (n,s,fix_lambdas_wrt_type ty' te')
 103    | C.Prod (_,s,ty'), ((C.Appl (C.Const _ ::_)) as t) ->
 104       (* const have a fixed arity *)
 105       (* prerr_endline ("******** fl - eta expansion 0: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
 106        let t' = S.lift 1 t in
 107        C.Lambda (C.Name "x",s,
 108          C.LetIn
 109           (C.Name "H", fix_lambdas_wrt_type ty' t',
 110             C.Appl [C.Rel 1;C.Rel 2]))
 111    | C.Prod (_,s,ty'), C.Appl l ->
 112        (* prerr_endline ("******** fl - eta expansion 1: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
 113        let l' = List.map (S.lift 1) l in
 114         C.Lambda (C.Name "x",s,
 115          fix_lambdas_wrt_type ty' (C.Appl (l'@[C.Rel 1])))
 116    | C.Prod (_,s,ty'), _ ->
 117        (* prerr_endline ("******** fl - eta expansion 2: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
 118        flush stderr ;
 119        let te' = S.lift 1 te in
 120         C.Lambda (C.Name "x",s,
 121           fix_lambdas_wrt_type ty' (C.Appl [te';C.Rel 1]))
 122    | _, _ -> te
 123 ;;*)
 124
 125 let fix_according_to_type ty hd tl =
 126  let module C = Cic in
 127  let module S = CicSubstitution in
 128    let rec count_prods =
 129      function
 130        C.Prod (_,_,t) -> 1 + (count_prods t)
 131        | _ -> 0 in
 132   let expected_arity = count_prods ty in
 133   let rec aux n ty tl res =
 134     if n = 0 then
 135       (match tl with
 136          [] ->
 137           (match res with
 138               [] -> assert false
 139             | [res] -> res
 140             | _ -> C.Appl res)
 141        | _ ->
 142           match res with
 143             [] -> assert false
 144           | [a] -> C.Appl (a::tl)
 145           | _ ->
 146               (* prerr_endline ("******* too many args: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm (C.Appl res)); *)
 147               C.LetIn
 148                 (C.Name "H",
 149                   C.Appl res,
 150                    assert false,
 151                     C.Appl (C.Rel 1::(List.map (S.lift 1) tl))))
 152     else
 153       let name,source,target =
 154         (match ty with
 155            C.Prod (C.Name _ as n,s,t) -> n,s,t
 156          | C.Prod (C.Anonymous, s,t) -> C.Name "z",s,t
 157          | _ -> (* prods number may only increase for substitution *)
 158            assert false) in
 159       match tl with
 160          [] ->
 161            (* prerr_endline ("******* too few args: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm (C.Appl res)); *)
 162            let res' = List.map (S.lift 1) res in
 163            C.Lambda
 164             (name, source, aux (n-1) target [] (res'@[C.Rel 1]))
 165         | hd::tl' ->
 166            let hd' = fix_lambdas_wrt_type source hd in
 167             (*  (prerr_endline ("++++++prima :" ^(CicPp.ppterm hd));
 168               prerr_endline ("++++++dopo :" ^(CicPp.ppterm hd'))); *)
 169            aux (n-1) (S.subst hd' target) tl' (res@[hd']) in
 170   aux expected_arity ty tl [hd]
 171 ;;
 172
 173 let eta_fix metasenv context t =
 174  let rec eta_fix' context t =
 175   (* prerr_endline ("entering aux with: term=" ^ CicPp.ppterm t);
 176   flush stderr ; *)
 177   let module C = Cic in
 178   let module S = CicSubstitution in
 179   match t with
 180      C.Rel n -> C.Rel n
 181    | C.Var (uri,exp_named_subst) ->
 182       let exp_named_subst' = fix_exp_named_subst context exp_named_subst in
 183        C.Var (uri,exp_named_subst')
 184    | C.Meta (n,l) ->
 185       let (_,canonical_context,_) = CicUtil.lookup_meta n metasenv in
 186       let l' =
 187         List.map2
 188          (fun ct t ->
 189           match (ct, t) with
 190             None, _ -> None
 191           | _, Some t -> Some (eta_fix' context t)
 192           | Some _, None -> assert false (* due to typing rules *))
 193         canonical_context l
 194        in
 195        C.Meta (n,l')
 196    | C.Sort s -> C.Sort s
 197    | C.Implicit _ as t -> t
 198    | C.Cast (v,t) -> C.Cast (eta_fix' context v, eta_fix' context t)
 199    | C.Prod (n,s,t) ->
 200        C.Prod
 201         (n, eta_fix' context s, eta_fix' ((Some (n,(C.Decl s)))::context) t)
 202    | C.Lambda (n,s,t) ->
 203        C.Lambda
 204         (n, eta_fix' context s, eta_fix' ((Some (n,(C.Decl s)))::context) t)
 205    | C.LetIn (n,s,ty,t) ->
 206        C.LetIn
 207         (n,eta_fix' context s,eta_fix' context ty,
 208           eta_fix' ((Some (n,(C.Def (s,ty))))::context) t)
 209    | C.Appl [] -> assert false
 210    | C.Appl (he::tl) ->
 211        let tl' =  List.map (eta_fix' context) tl in
 212        let ty,_ =
 213          CicTypeChecker.type_of_aux' metasenv context he
 214            CicUniv.oblivion_ugraph
 215        in
 216        fix_according_to_type ty (eta_fix' context he) tl'
 217 (*
 218          C.Const(uri,exp_named_subst)::l'' ->
 219            let constant_type =
 220              (match CicEnvironment.get_obj uri with
 221                C.Constant (_,_,ty,_) -> ty
 222              | C.Variable _ -> raise ReferenceToVariable
 223              | C.CurrentProof (_,_,_,_,params) -> raise ReferenceToCurrentProof
 224              | C.InductiveDefinition _ -> raise ReferenceToInductiveDefinition
 225              ) in
 226            fix_according_to_type
 227              constant_type (C.Const(uri,exp_named_subst)) l''
 228         | _ -> C.Appl l' *)
 229    | C.Const (uri,exp_named_subst) ->
 230        let exp_named_subst' = fix_exp_named_subst context exp_named_subst in
 231         C.Const (uri,exp_named_subst')
 232    | C.MutInd (uri,tyno,exp_named_subst) ->
 233        let exp_named_subst' = fix_exp_named_subst context exp_named_subst in
 234         C.MutInd (uri, tyno, exp_named_subst')
 235    | C.MutConstruct (uri,tyno,consno,exp_named_subst) ->
 236        let exp_named_subst' = fix_exp_named_subst context exp_named_subst in
 237         C.MutConstruct (uri, tyno, consno, exp_named_subst')
 238    | C.MutCase (uri, tyno, outty, term, patterns) ->
 239        let outty' =  eta_fix' context outty in
 240        let term' = eta_fix' context term in
 241        let patterns' = List.map (eta_fix' context) patterns in
 242        let inductive_types,noparams =
 243          let o,_ = CicEnvironment.get_obj CicUniv.oblivion_ugraph uri in
 244            (match o with
 245                Cic.Constant _ -> assert false
 246              | Cic.Variable _ -> assert false
 247              | Cic.CurrentProof _ -> assert false
 248              | Cic.InductiveDefinition (l,_,n,_) -> l,n
 249            ) in
 250        let (_,_,_,constructors) = List.nth inductive_types tyno in
 251        let constructor_types =
 252          let rec clean_up t =
 253            function
 254                [] -> t
 255              | a::tl ->
 256                  (match t with
 257                    Cic.Prod (_,_,t') -> clean_up (S.subst a t') tl
 258                   | _ -> assert false) in
 259           if noparams = 0 then
 260             List.map (fun (_,t) -> t) constructors
 261           else
 262             let term_type,_ =
 263               CicTypeChecker.type_of_aux' metasenv context term
 264                 CicUniv.oblivion_ugraph
 265             in
 266             (match term_type with
 267                C.Appl (hd::params) ->
 268                  let rec first_n n l =
 269                    if n = 0 then []
 270                    else
 271                      (match l with
 272                         a::tl -> a::(first_n (n-1) tl)
 273                       | _ -> assert false) in
 274                  List.map
 275                   (fun (_,t) ->
 276                      clean_up t (first_n noparams params)) constructors
 277              | _ -> prerr_endline ("QUA"); assert false) in
 278        let patterns2 =
 279          List.map2 fix_lambdas_wrt_type
 280            constructor_types patterns' in
 281          C.MutCase (uri, tyno, outty',term',patterns2)
 282    | C.Fix (funno, funs) ->
 283        let fun_types =
 284          List.map (fun (n,_,ty,_) -> Some (C.Name n,(Cic.Decl ty))) funs in
 285        C.Fix (funno,
 286         List.map
 287          (fun (name, no, ty, bo) ->
 288            (name, no, eta_fix' context ty, eta_fix' (fun_types@context) bo))
 289         funs)
 290    | C.CoFix (funno, funs) ->
 291        let fun_types =
 292          List.map (fun (n,ty,_) -> Some (C.Name n,(Cic.Decl ty))) funs in
 293        C.CoFix (funno,
 294         List.map
 295          (fun (name, ty, bo) ->
 296            (name, eta_fix' context ty, eta_fix' (fun_types@context) bo)) funs)
 297   and fix_exp_named_subst context exp_named_subst =
 298    List.rev
 299     (List.fold_left
 300       (fun newsubst (uri,t) ->
 301         let t' = eta_fix' context t in
 302         let ty =
 303           let o,_ = CicEnvironment.get_obj CicUniv.oblivion_ugraph uri in
 304             match o with
 305                 Cic.Variable (_,_,ty,_,_) ->
 306                   CicSubstitution.subst_vars newsubst ty
 307               | _ ->  raise ReferenceToNonVariable
 308         in
 309         let t'' = fix_according_to_type ty t' [] in
 310          (uri,t'')::newsubst
 311       ) [] exp_named_subst)
 312   in
 313    eta_fix' context t
 314 ;;