aboutsummaryrefslogtreecommitdiffhomepage
path: root/pretyping/detyping.ml
blob: 111e5a514ea777d14ed1c0bd411e02b50452d62e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
(***********************************************************************)
(*  v      *   The Coq Proof Assistant  /  The Coq Development Team    *)
(* <O___,, *        INRIA-Rocquencourt  &  LRI-CNRS-Orsay              *)
(*   \VV/  *************************************************************)
(*    //   *      This file is distributed under the terms of the      *)
(*         *       GNU Lesser General Public License Version 2.1       *)
(***********************************************************************)

(* $Id$ *)

open Pp
open Util
open Univ
open Names
open Term
open Declarations
open Inductive
open Environ
open Sign
open Declare
open Impargs
open Rawterm
open Nameops
open Termops
open Nametab

(****************************************************************************)
(* Tools for printing of Cases                                              *)

let encode_inductive ref =
  let indsp = match ref with
    | IndRef indsp -> indsp
    | _ ->
        errorlabstrm "indsp_of_id"
          (pr_global_env (Global.env()) ref ++
	     str" is not an inductive type") in
  let (mib,mip) = Global.lookup_inductive indsp in
  let constr_lengths = Array.map List.length mip.mind_listrec in
  (indsp,constr_lengths)

let constr_nargs indsp =
  let (mib,mip) = Global.lookup_inductive indsp in
  let nparams = mip.mind_nparams in
  Array.map
    (fun t -> List.length (fst (decompose_prod_assum t)) - nparams)
    mip.mind_nf_lc

(* Parameterization of the translation from constr to ast      *)

(* Tables for Cases printing under a "if" form, a "let" form,  *)

let isomorphic_to_bool lc =
  Array.length lc = 2 & lc.(0) = 0 & lc.(1) = 0

let isomorphic_to_tuple lc = (Array.length lc = 1)

module PrintingCasesMake =
  functor (Test : sig 
     val test : int array -> bool
     val error_message : string
     val member_message : global_reference -> bool -> string
     val field : string
     val title : string
  end) ->
  struct
    type t = inductive * int array
    let encode = encode_inductive
    let check (_,lc) =
      if not (Test.test lc) then 
	errorlabstrm "check_encode" (str Test.error_message)
    let printer (ind,_) =
      pr_id (basename (path_of_inductive (Global.env()) ind))
    let key = Goptions.SecondaryTable ("Printing",Test.field)
    let title = Test.title
    let member_message = Test.member_message
    let synchronous = true
  end

module PrintingCasesIf =
  PrintingCasesMake (struct 
    let test = isomorphic_to_bool
    let error_message = "This type cannot be seen as a boolean type"
    let field = "If"
    let title = "Types leading to pretty-printing of Cases using a `if' form: "
    let member_message ref b =
      let s = string_of_qualid(shortest_qualid_of_global (Global.env()) ref) in
      if b then
        "Cases on elements of " ^ s ^ " are printed using a `if' form"
      else
        "Cases on elements of " ^ s ^ " are not printed using `if' form"
  end)

module PrintingCasesLet =
  PrintingCasesMake (struct 
    let test = isomorphic_to_tuple
    let error_message = "This type cannot be seen as a tuple type"
    let field = "Let"
    let title = 
      "Types leading to a pretty-printing of Cases using a `let' form:"
    let member_message ref b =
      let s = string_of_qualid(shortest_qualid_of_global (Global.env()) ref) in
      if b then
        "Cases on elements of " ^ s ^ " are printed using a `let' form"
      else
        "Cases on elements of " ^ s ^ " are not printed using a `let' form"
  end)

module PrintingIf  = Goptions.MakeIdentTable(PrintingCasesIf)
module PrintingLet = Goptions.MakeIdentTable(PrintingCasesLet)

let force_let ci =
  let indsp = ci.ci_ind in
  let lc = constr_nargs indsp in PrintingLet.active (indsp,lc)
let force_if ci =
  let indsp = ci.ci_ind in
  let lc = constr_nargs indsp in PrintingIf.active (indsp,lc)

(* Options for printing or not wildcard and synthetisable types *)

open Goptions

let wildcard_value = ref true
let force_wildcard () = !wildcard_value

let _ = declare_bool_option 
	  { optsync  = true;
	    optname  = "forced wildcard";
	    optkey   = SecondaryTable ("Printing","Wildcard");
	    optread  = force_wildcard;
	    optwrite = (:=) wildcard_value }

let synth_type_value = ref true
let synthetize_type () = !synth_type_value

let _ = declare_bool_option 
	  { optsync  = true;
	    optname  = "synthesizability";
	    optkey   = SecondaryTable ("Printing","Synth");
	    optread  = synthetize_type;
	    optwrite = (:=) synth_type_value }

(* Auxiliary function for MutCase printing *)
(* [computable] tries to tell if the predicate typing the result is inferable*)

let computable p k =
    (* We first remove as many lambda as the arity, then we look
       if it remains a lambda for a dependent elimination. This function
       works for normal eta-expanded term. For non eta-expanded or
       non-normal terms, it may affirm the pred is synthetisable
       because of an undetected ultimate dependent variable in the second
       clause, or else, it may affirms the pred non synthetisable
       because of a non normal term in the fourth clause.
       A solution could be to store, in the MutCase, the eta-expanded
       normal form of pred to decide if it depends on its variables

       Lorsque le prédicat est dépendant de manière certaine, on
       ne déclare pas le prédicat synthétisable (même si la
       variable dépendante ne l'est pas effectivement) parce que
       sinon on perd la réciprocité de la synthèse (qui, lui,
       engendrera un prédicat non dépendant) *)

  (nb_lam p = k+1)
  &&
  let _,ccl = decompose_lam p in 
  noccur_between 1 (k+1) ccl



let lookup_name_as_renamed ctxt t s =
  let rec lookup avoid env_names n c = match kind_of_term c with
    | Prod (name,_,c') ->
	(match concrete_name avoid env_names name c' with
           | (Some id,avoid') -> 
	       if id=s then (Some n) 
	       else lookup avoid' (add_name (Name id) env_names) (n+1) c'
	   | (None,avoid')    -> lookup avoid' env_names (n+1) (pop c'))
    | LetIn (name,_,_,c') ->
	(match concrete_name avoid env_names name c' with
           | (Some id,avoid') -> 
	       if id=s then (Some n) 
	       else lookup avoid' (add_name (Name id) env_names) (n+1) c'
	   | (None,avoid')    -> lookup avoid' env_names (n+1) (pop c'))
    | Cast (c,_) -> lookup avoid env_names n c
    | _ -> None
  in lookup (ids_of_named_context ctxt) empty_names_context 1 t

let lookup_index_as_renamed t n =
  let rec lookup n d c = match kind_of_term c with
    | Prod (name,_,c') ->
	  (match concrete_name [] empty_names_context name c' with
               (Some _,_) -> lookup n (d+1) c'
             | (None  ,_) -> if n=1 then Some d else lookup (n-1) (d+1) c')
    | LetIn (name,_,_,c') ->
	  (match concrete_name [] empty_names_context name c' with
             | (Some _,_) -> lookup n (d+1) c'
             | (None  ,_) -> if n=1 then Some d else lookup (n-1) (d+1) c')
    | Cast (c,_) -> lookup n d c
    | _ -> None
  in lookup n 1 t

let rec detype avoid env t =
  match kind_of_term (collapse_appl t) with
    | Rel n ->
      (try match lookup_name_of_rel n env with
	 | Name id   -> RVar (dummy_loc, id)
	 | Anonymous -> anomaly "detype: index to an anonymous variable"
       with Not_found ->
	 let s = "_UNBOUND_REL_"^(string_of_int n)
	 in RVar (dummy_loc, id_of_string s))
    | Meta n -> RMeta (dummy_loc, n)
    | Var id -> RVar (dummy_loc, id)
    | Sort (Prop c) -> RSort (dummy_loc,RProp c)
    | Sort (Type u) -> RSort (dummy_loc,RType (Some u))
    | Cast (c1,c2) ->
	RCast(dummy_loc,detype avoid env c1,detype avoid env c2)
    | Prod (na,ty,c) -> detype_binder BProd avoid env na ty c
    | Lambda (na,ty,c) -> detype_binder BLambda avoid env na ty c
    | LetIn (na,b,_,c) -> detype_binder BLetIn avoid env na b c
    | App (f,args) ->
	RApp (dummy_loc,detype avoid env f,array_map_to_list (detype avoid env) args)
    | Const sp -> RRef (dummy_loc, ConstRef sp)
    | Evar (ev,cl) ->
	let f = REvar (dummy_loc, ev) in
	RApp (dummy_loc, f, List.map (detype avoid env) (Array.to_list cl))
    | Ind ind_sp ->
	RRef (dummy_loc, IndRef ind_sp)
    | Construct cstr_sp ->
	RRef (dummy_loc, ConstructRef cstr_sp)
    | Case (annot,p,c,bl) ->
	let synth_type = synthetize_type () in
	let tomatch = detype avoid env c in
	let indsp = annot.ci_ind in
        let considl = annot.ci_pp_info.cnames in
        let k = annot.ci_pp_info.ind_nargs in
	let consnargsl = constr_nargs indsp in
	let pred = 
	  if synth_type & computable p k & considl <> [||] then
	    None
	  else 
	    Some (detype avoid env p) in
	let constructs = 
	  Array.init (Array.length considl) (fun i -> (indsp,i+1)) in
	let eqnv =
	  array_map3 (detype_eqn avoid env) constructs consnargsl bl in
	let eqnl = Array.to_list eqnv in
	let tag =
	  if PrintingLet.active (indsp,consnargsl) then 
	    PrintLet 
	  else if PrintingIf.active (indsp,consnargsl) then 
	    PrintIf 
	  else 
	    PrintCases
	in 
	RCases (dummy_loc,tag,pred,[tomatch],eqnl)
	
    | Fix (nvn,recdef) -> detype_fix avoid env (RFix nvn) recdef
    | CoFix (n,recdef) -> detype_fix avoid env (RCoFix n) recdef

and detype_fix avoid env fixkind (names,tys,bodies) =
  let def_avoid, def_env, lfi =
    Array.fold_left
      (fun (avoid, env, l) na ->
	 let id = next_name_away na avoid in 
	 (id::avoid, add_name (Name id) env, id::l))
      (avoid, env, []) names in
  RRec(dummy_loc,fixkind,Array.of_list (List.rev lfi),
       Array.map (detype avoid env) tys,
       Array.map (detype def_avoid def_env) bodies)


and detype_eqn avoid env constr construct_nargs branch =
  let make_pat x avoid env b ids =
    if not (force_wildcard ()) or (dependent (mkRel 1) b) then
      let id = next_name_away_with_default "x" x avoid in
      PatVar (dummy_loc,Name id),id::avoid,(add_name (Name id) env),id::ids
    else 
      PatVar (dummy_loc,Anonymous),avoid,(add_name Anonymous env),ids
  in
  let rec buildrec ids patlist avoid env n b =
    if n=0 then
      (dummy_loc, ids, 
       [PatCstr(dummy_loc, constr, List.rev patlist,Anonymous)],
       detype avoid env b)
    else
      match kind_of_term b with
	| Lambda (x,_,b) -> 
	    let pat,new_avoid,new_env,new_ids = make_pat x avoid env b ids in
            buildrec new_ids (pat::patlist) new_avoid new_env (n-1) b

	| LetIn (x,_,_,b) -> 
	    let pat,new_avoid,new_env,new_ids = make_pat x avoid env b ids in
            buildrec new_ids (pat::patlist) new_avoid new_env (n-1) b

	| Cast (c,_) ->    (* Oui, il y a parfois des cast *)
	    buildrec ids patlist avoid env n c

	| _ -> (* eta-expansion : n'arrivera plus lorsque tous les
                  termes seront construits à partir de la syntaxe Cases *)
            (* nommage de la nouvelle variable *)
	    let new_b = applist (lift 1 b, [mkRel 1]) in
            let pat,new_avoid,new_env,new_ids =
	      make_pat Anonymous avoid env new_b ids in
	    buildrec new_ids (pat::patlist) new_avoid new_env (n-1) new_b
	  
  in 
  buildrec [] [] avoid env construct_nargs branch

and detype_binder bk avoid env na ty c =
  let na',avoid' =
    if bk = BLetIn then concrete_let_name avoid env na c
    else
      match concrete_name avoid env na c with
	| (Some id,l') -> (Name id), l'
	| (None,l')    -> Anonymous, l' in
  let r =  detype avoid' (add_name na' env) c in
  match bk with
    | BProd -> RProd (dummy_loc, na',detype [] env ty, r)
    | BLambda -> RLambda (dummy_loc, na',detype [] env ty, r)
    | BLetIn -> RLetIn (dummy_loc, na',detype [] env ty, r)