aboutsummaryrefslogtreecommitdiffhomepage
path: root/test-suite/complexity/evars_subst.v
blob: 58a09dd3f66d965c6cfb228a410c0f9fdcbe3cdf (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
(* Bug report #932 *)
(* Expected time < 1.00s *)

(* Let n be the number of let-in. The complexity comes from the fact
that each implicit arguments of f was in a larger and larger
context. To compute the type of "let _ := f ?Tn 0 in f ?T 0", "f ?Tn
0" is substituted in the type of "f ?T 0" which is ?T. This type is an
evar instantiated on the n variables denoting the "f ?Ti 0".  One
obtain "?T[1;...;n-1;f ?Tn[1;...;n-1] 0]". To compute the type of "let
_ := f ?Tn-1 0 in let _ := f ?Tn 0 in f ?T 0", another substitution is
done leading to ?T[1;...;n-2;f ?Tn[1;...;n-2] 0;f ?Tn[1;...;n-2;f
?Tn[1;...;n-2] 0] 0]" and so on. At the end, we get a term of
exponential size *)

(* A way to cut the complexity is to remove the dependency in
   anonymous variables in evars; another approach would be to
   substitute lazily and/or to simultaneously substitute let binders
   and evars *)

Variable P : Set -> Set.
Variable f : forall A : Set, A -> P A.

Check
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
 
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in

  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in

  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in

  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in

  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
 
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in

  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in

  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in

  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in
  let _ := f _ 0 in

    f _ 0.