1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83
84. 84
85. 85
86. 86
87. 87
88. 88
89. 89
90. 90
91. 91
92. 92
93. 93
94. 94
95. 95
96. 96
97. 97
98. 98
99. 99
100. 100
101. 101
102. 102
103. 103
104. 104
105. 105
106. 106
107. 107
108. 108
109. 109
110. 110
111. 111
112. 112
113. 113
114. 114
115. 115
116. 116
117. 117
118. 118
119. 119
120. 120
121. 121
122. 122
123. 123
124. 124
125. 125
126. 126
127. 127
128. 128
129. 129
130. 130
131. 131
132. 132
133. 133
134. 134
135. 135
136. 136
137. 137
138. 138
139. 139
140. 140
141. 141
142. 142
143. 143
144. 144
145. 145
146. 146
147. 147
148. 148
149. 149
150. 150
151. 151
152. 152
153. 153
154. 154
155. 155
156. 156
157. 157
158. 158
159. 159
160. 160
161. 161
162. 162
163. 163
164. 164
165. 165
166. 166
167. 167
168. 168
169. 169
170. 170
171. 171
172. 172
173. 173

-- Trying to implement dependent types wheee

inductive Term
  -- Terms that cannot be types
  /-- Variable -/
  | var (x : Nat)
  /-- Lambda -/
  | lam (b β : Term)
  /-- Function application -/
  | app (f φ a α : Term)
  -- Types
  /-- New named type -/
  | new (x : Nat)
  /-- Dependent function type -/
  | fn (α β : Term)
  -- Inductive types
  /-- Dependent product type -/
  | prod (α β : Term)
  /-- Constructor for product -/
  | and (a α b β : Term)
  /-- Get first element of product -/
  | and1 (p π : Term)
  /-- Get second element of product -/
  | and2 (p π : Term)
  /-- Sum type -/
  | sum (α β : Term)
  /-- Construct a sum -/
  | or (c γ : Term)
  /-- Equality type -/
  | eq (a a' α : Term)
  /-- Constructor for equality -/
  | rfl (a α : Term)
  /-- Eliminator for equality -/
  | rw (a a' α f h ha : Term)
  /-- Natural number type -/
  | nat
  /-- Zero as a nat -/
  | zero
  /-- One or greater as a nat -/
  | succ (n ν : Term)
  /-- Eliminator for nats -/
  | nat_elim (α n ν b β f φ : Term)
  /-- False (no terms of this type) -/
  | fls
  /-- Eliminator for false -/
  | fls_elim (a α : Term)
  -- Universe stuff (only two universes for now)
  /-- Type of types -/
  | typ
deriving BEq, ReflBEq, LawfulBEq

/-- Increment free variables by 1 -/
def incr (d : Nat) : Term → Term
  | .var x =>
    .var (if d ≤ x then x + 1 else x)
  | .lam b β =>
    .lam (incr (d + 1) b) (incr (d + 1) β)
  | .app f φ a α =>
    .app (incr d f) (incr d φ) (incr d a) (incr d α)
  | .fn α β =>
    .fn (incr d α) (incr d β)
  | x => x

mutual
-- /-- -/
-- def defeq (env : List Term) a a' α :=
--   check env a α && check env a' α' && eval env a α == eval env a' α'

-- TODO: A lot of the `==`s here should use defeq
/-- Janky type checker -/
def check (env : List Term) : Term → Term → Bool
  | .var x, α =>
    if _ : x < env.length then env[x] == α else false
  | .lam b β, .fn α β' =>
    β' == β && (β == .typ || check (α :: env) β .typ) && check (α :: env) b β
  | .app f (.fn α β) a α', β' =>
    α' == α && β' == β && check env f (.fn α β) && check env a α
  | .new x, .typ =>
    true
  | .fn α β, .typ =>
    check env α .typ && check env β .typ
  | .prod α β, .typ =>
    check env α .typ && check env β .typ
  | .and a α b β, .prod α' β' =>
    α' == α && β' == β && (β == .typ || check (α :: env) β .typ) && check env a α && check env b β
  | .and1 p (.prod α β), α' =>
    α' == α && check env p (.prod α β)
  | .and2 p (.prod α β), β' =>
    β' == β && (β == .typ || check (α :: env) β .typ) && check env p (.prod α β)
  | .sum α β, .typ =>
    check env α .typ && check env β .typ
  | .or c γ, .sum α β =>
    (γ == α || γ == β) && check env c γ
  | .eq a a' α, .typ =>
    check env a α && check env a' α && check env α .typ
  | .rfl a α, .eq a' a'' α' =>
    α' == α && a' == a && a'' == a && check env a α
  | .rw a a' α m h ha, ha' =>
    -- TODO this needs eval for sure
    check env h (.eq a a' α) --&& check env ha (.app (.app m (.fn α (.fn (.eq ) .typ)) a α)) -- && check env ha' (.app p (.fn α .typ) a' α)
  | .nat, .typ | .zero, .nat =>
    true
  | .succ n .nat, .nat =>
    check env n .nat
  | .nat_elim α n .nat a α₁ f (.fn .nat (.fn α₂ α₃)), .fn .nat α₄ =>
    α₁ == α && α₂ == α && α₃ == α && α₄ == α && check env n .nat && check env a α && check env f (.fn .nat (.fn α α))
  | .fls, .typ =>
    true
  | .fls_elim a .fls, _ =>
    check env a .fls
  | _, _ =>
    false

end

/-- A → A -/
def a_imp_a := (Term.lam (.var 0) (.new 0), Term.fn (.new 0) (.new 0))

#guard check [] a_imp_a.1 a_imp_a.2

/-- A → B → B ∧ A -/
def a_imp_b_imp_ba := (Term.lam (.lam (.and (.var 0) (.new 1) (.var 1) (.new 0)) (.prod (.new 1) (.new 0))) (.fn (.new 1) (.prod (.new 1) (.new 0))), Term.fn (.new 0) (.fn (.new 1) (.prod (.new 1) (.new 0))))

#guard check [] a_imp_b_imp_ba.1 a_imp_b_imp_ba.2

/-- A ∧ B → B ∧ A -/
def ab_imp_ba := (Term.lam (.and (.and2 (.var 0) (.prod (.new 0) (.new 1))) (.new 1) (.and1 (.var 0) (.prod (.new 0) (.new 1))) (.new 0)) (.prod (.new 1) (.new 0)), Term.fn (.prod (.new 0) (.new 1)) (.prod (.new 1) (.new 0)))

#guard check [] ab_imp_ba.1 ab_imp_ba.2

/-- ¬(A ∨ B) → ¬A -/
def not_ab_imp_not_a := (Term.lam (.lam (.app (.var 1) (.fn (.sum (.new 0) (.new 1)) .fls) (.or (.var 0) (.new 0)) (.sum (.new 0) (.new 1))) (.fls)) (.fn (.new 0) .fls), Term.fn (.fn (.sum (.new 0) (.new 1)) .fls) (.fn (.new 0) .fls))

#guard check [] not_ab_imp_not_a.1 not_ab_imp_not_a.2

/-- A → ¬¬A -/
def a_imp_not_not_a := (Term.lam (.lam (.app (.var 0) (.fn (.new 0) .fls) (.var 1) (.new 0)) (.fls)) (.fn (.fn (.new 0) .fls) .fls), Term.fn (.new 0) (.fn (.fn (.new 0) .fls) .fls))

#guard check [] a_imp_not_not_a.1 a_imp_not_not_a.2

/-- ¬¬¬A → ¬A -/
def not_not_not_a_imp_not_a := (Term.lam (.lam (.app (.var 1) (.fn (.fn (.fn (.new 0) .fls) .fls) .fls) (.app a_imp_not_not_a.1 a_imp_not_not_a.2 (.var 0) (.new 0)) (.fn (.fn (.new 0) .fls) .fls)) (.fls)) (.fn (.new 0) .fls), Term.fn (.fn (.fn (.fn (.new 0) .fls) .fls) .fls) (.fn (.new 0) .fls))

#guard check [] not_not_not_a_imp_not_a.1 not_not_not_a_imp_not_a.2

/-- ∀ a : A, a = a -/
def a_eq_a := (Term.lam (.rfl (.var 0) (.new 0)) (.eq (.var 0) (.var 0) (.new 0)), Term.fn (.new 0) (.eq (.var 0) (.var 0) (.new 0)))

#guard check [] a_eq_a.1 a_eq_a.2

/-- 2 exists (yeah I know this is not super exciting) -/
def two := (Term.succ (.succ .zero .nat) .nat, Term.nat)

#guard check [] two.1 two.2

/-- 4 exists -/
def four := (Term.succ (.succ two.1 two.2) .nat, Term.nat)

#guard check [] four.1 four.2

/-- Addition -/
def add := (Term.lam (.nat_elim .nat .zero .nat (.var 0) .nat (.lam (.lam (.succ (.var 2) .nat) .nat) (.fn .nat .nat)) (.fn .nat (.fn .nat .nat))) (.fn .nat .nat), Term.fn .nat (.fn .nat .nat))

#guard check [] add.1 add.2

def two_plus_two := (Term.app (.app add.1 add.2 two.1 two.2) (.fn .nat .nat) two.1 two.2, Term.nat)

#guard check [] two_plus_two.1 two_plus_two.2

/-- 2 + 2 = 4 -/
def two_plus_two_eq_four := (Term.fls, Term.eq two_plus_two.1 four.1 .nat)

#guard check [] two_plus_two_eq_four.1 two_plus_two_eq_four.2