0 | module Core.TT.Var
  1 |
  2 | import Data.Fin
  3 | import Data.List
  4 | import Data.So
  5 | import Data.SnocList
  6 |
  7 | import Core.Name.Scoped
  8 |
  9 | import Libraries.Data.SnocList.HasLength
 10 | import Libraries.Data.SnocList.SizeOf
 11 |
 12 | import Data.List.HasLength
 13 | import Data.DPair
 14 |
 15 | import Libraries.Data.List.SizeOf
 16 |
 17 | import Libraries.Data.Erased
 18 |
 19 | %default total
 20 |
 21 | ------------------------------------------------------------------------
 22 | -- IsVar Predicate
 23 |
 24 | -- TODO need a copy of `IsVar` for both
 25 |
 26 | ||| IsVar n k ns is a proof that
 27 | ||| the name n
 28 | ||| is a position k
 29 | ||| in the snoclist ns
 30 | public export
 31 | data IsVar : a -> Nat -> List a -> Type where
 32 |      First : IsVar n Z (n :: ns)
 33 |      Later : IsVar n i ns -> IsVar n (S i) (m :: ns)
 34 |
 35 | %name IsVar idx
 36 |
 37 | -- TODO: remove `{vs = .(_)}`
 38 | export
 39 | 0 Last : HasLength (S n) vs -> Exists (\ nm => IsVar nm n vs)
 40 | Last {vs = .(_)} (S Z) = Evidence _ First
 41 | Last {vs = .(_)} (S (S p)) = bimap id Later (Last (S p))
 42 |
 43 | export
 44 | finIdx : {idx : _} -> (0 prf : IsVar x idx vars) ->
 45 |          Fin (length vars)
 46 | finIdx First = FZ
 47 | finIdx (Later l) = FS (finIdx l)
 48 |
 49 | ||| Recover the value pointed at by an IsVar proof
 50 | ||| O(n) in the size of the index
 51 | export
 52 | nameAt : {vars : List a} -> {idx : Nat} -> (0 p : IsVar n idx vars) -> a
 53 | nameAt {vars = n :: _} First = n
 54 | nameAt (Later p) = nameAt p
 55 |
 56 | ||| Inversion principle for Later
 57 | export
 58 | dropLater : IsVar nm (S idx) (n :: ns) -> IsVar nm idx ns
 59 | dropLater (Later p) = p
 60 |
 61 | export
 62 | 0 mkIsVar : HasLength m inner -> IsVar nm m (inner ++ nm :: outer)
 63 | mkIsVar Z = First
 64 | mkIsVar (S x) = Later (mkIsVar x)
 65 |
 66 | export
 67 | 0 mkIsVarChiply : HasLength m inner -> IsVar nm m (inner <>> nm :: outer)
 68 | mkIsVarChiply hl
 69 |   = rewrite chipsAsListAppend inner (nm :: outer) in
 70 |     rewrite sym $ plusZeroRightNeutral m in
 71 |     mkIsVar (hlChips hl Z)
 72 |
 73 | ||| Compute the remaining scope once the target variable has been removed
 74 | public export
 75 | dropIsVar :
 76 |   (ns : List a) ->
 77 |   {idx : Nat} -> (0 p : IsVar name idx ns) ->
 78 |   List a
 79 | dropIsVar (_ :: xs) First = xs
 80 | dropIsVar (n :: xs) (Later p) = n :: dropIsVar xs p
 81 |
 82 | ||| Throw in extra variables on the outer side of the context
 83 | ||| This is essentially the identity function
 84 | ||| This is slow so we ensure it's only used in a runtime irrelevant manner
 85 | export
 86 | 0 embedIsVar : IsVar x idx xs -> IsVar x idx (xs ++ outer)
 87 | embedIsVar First = First
 88 | embedIsVar (Later p) = Later (embedIsVar p)
 89 |
 90 | ||| Throw in extra variables on the local end of the context.
 91 | ||| This is slow so we ensure it's only used in a runtime irrelevant manner
 92 | export
 93 | 0 weakenIsVar : (s : SizeOf ns) -> IsVar x idx xs -> IsVar x (size s + idx) (ns ++ xs)
 94 | weakenIsVar (MkSizeOf Z Z) p =  p
 95 | weakenIsVar (MkSizeOf (S k) (S l)) p =  Later (weakenIsVar (MkSizeOf k l) p)
 96 |
 97 | 0 locateIsVarLT :
 98 |   (s : SizeOf local) ->
 99 |   So (idx < size s) ->
100 |   IsVar x idx (local ++ outer) ->
101 |   IsVar x idx local
102 | locateIsVarLT (MkSizeOf Z Z) so v = case v of
103 |   First impossible
104 |   Later v impossible
105 | locateIsVarLT (MkSizeOf (S k) (S l)) so v = case v of
106 |   First => First
107 |   Later v => Later (locateIsVarLT (MkSizeOf k l) so v)
108 |
109 | 0 locateIsVarGE :
110 |   (s : SizeOf local) ->
111 |   So (idx >= size s) ->
112 |   IsVar x idx (local ++ outer) ->
113 |   IsVar x (idx `minus` size s) outer
114 | locateIsVarGE (MkSizeOf Z Z) so v = rewrite minusZeroRight idx in v
115 | locateIsVarGE (MkSizeOf (S k) (S l)) so v = case v of
116 |   Later v => locateIsVarGE (MkSizeOf k l) so v
117 |
118 | export
119 | locateIsVar : {idx : Nat} -> (s : SizeOf local) ->
120 |   (0 p : IsVar x idx (local ++ outer)) ->
121 |   Either (Erased (IsVar x idx local))
122 |          (Erased (IsVar x (idx `minus` size s) outer))
123 | locateIsVar s p = case choose (idx < size s) of
124 |   Left so => Left (MkErased (locateIsVarLT s so p))
125 |   Right so => Right (MkErased (locateIsVarGE s so p))
126 |
127 | ------------------------------------------------------------------------
128 | -- Variable in scope
129 |
130 | ||| A variable in a scope is a name, a De Bruijn index,
131 | ||| and a proof that the name is at that position in the scope.
132 | ||| Everything but the De Bruijn index is erased.
133 | public export
134 | record Var {0 a : Type} (vars : List a) where
135 |   constructor MkVar
136 |   {varIdx : Nat}
137 |   {0 varNm : a}
138 |   0 varPrf : IsVar varNm varIdx vars
139 |
140 | namespace Var
141 |
142 |   export
143 |   first : Var (n :: ns)
144 |   first = MkVar First
145 |
146 |   export
147 |   later : Var ns -> Var (n :: ns)
148 |   later (MkVar p) = MkVar (Later p)
149 |
150 |   export
151 |   isLater : Var (n :: vs) -> Maybe (Var vs)
152 |   isLater (MkVar First) = Nothing
153 |   isLater (MkVar (Later p)) = Just (MkVar p)
154 |
155 |   export
156 |   last : SizeOf vs -> Maybe (Var vs)
157 |   last (MkSizeOf Z p) = Nothing
158 |   last (MkSizeOf (S n) p) = Just (MkVar (snd $ Last p))
159 |
160 | export
161 | mkVar : SizeOf inner -> Var (inner ++ nm :: outer)
162 | mkVar (MkSizeOf s p) = MkVar (mkIsVar p)
163 |
164 | export
165 | mkVarChiply : SizeOf inner -> Var (inner <>> nm :: outer)
166 | mkVarChiply (MkSizeOf s p) = MkVar (mkIsVarChiply p)
167 |
168 | ||| Generate all variables
169 | export
170 | allVars : (vars : Scope) -> List (Var vars)
171 | allVars = go [<] where
172 |
173 |   go : SizeOf local -> (vs : Scope) -> List (Var (local <>> vs))
174 |   go s [] = []
175 |   go s (v :: vs) = mkVarChiply s :: go (s :< v) vs
176 |
177 | export
178 | Eq (Var xs) where
179 |   v == w = varIdx v == varIdx w
180 |
181 | export
182 | Show (Var ns) where
183 |   show v = show (varIdx v)
184 |
185 | ------------------------------------------------------------------------
186 | -- Named variable in scope
187 |
188 | public export
189 | record NVar {0 a : Type} (nm : a) (vars : List a) where
190 |   constructor MkNVar
191 |   {nvarIdx : Nat}
192 |   0 nvarPrf : IsVar nm nvarIdx vars
193 |
194 | namespace NVar
195 |
196 |   export
197 |   first : NVar n (n :: ns)
198 |   first = MkNVar First
199 |
200 |   export
201 |   later : NVar nm ns -> NVar nm (n :: ns)
202 |   later (MkNVar p) = MkNVar (Later p)
203 |
204 |   export
205 |   isLater : NVar nm (n :: ns) -> Maybe (NVar nm ns)
206 |   isLater (MkNVar First) = Nothing
207 |   isLater (MkNVar (Later p)) = Just (MkNVar p)
208 |
209 | export
210 | forgetName : NVar nm vars -> Var vars
211 | forgetName (MkNVar p) = MkVar p
212 |
213 | export
214 | recoverName : (v : Var vars) -> NVar (varNm v) vars
215 | recoverName (MkVar p) = MkNVar p
216 |
217 | export
218 | mkNVar : SizeOf inner -> NVar nm (inner ++ nm :: outer)
219 | mkNVar (MkSizeOf s p) = MkNVar (mkIsVar p)
220 |
221 | export
222 | mkNVarChiply : SizeOf inner -> NVar nm (inner <>> nm :: outer)
223 | mkNVarChiply (MkSizeOf s p) = MkNVar (mkIsVarChiply p)
224 |
225 | export
226 | locateNVar : SizeOf local -> NVar nm (local ++ outer) ->
227 |              Either (NVar nm local) (NVar nm outer)
228 | locateNVar s (MkNVar p) = case locateIsVar s p of
229 |   Left p => Left (MkNVar (runErased p))
230 |   Right p => Right (MkNVar (runErased p))
231 |
232 | public export
233 | dropNVar : {ns : List a} -> NVar nm ns -> List a
234 | dropNVar (MkNVar p) = dropIsVar ns p
235 |
236 | ------------------------------------------------------------------------
237 | -- Scope checking
238 |
239 | export
240 | isDeBruijn : Nat -> (vars : List Name) -> Maybe (Var vars)
241 | isDeBruijn Z (_ :: _) = pure first
242 | isDeBruijn (S k) (_ :: vs) = later <$> isDeBruijn k vs
243 | isDeBruijn _ _ = Nothing
244 |
245 | export
246 | isNVar : (n : Name) -> (ns : List Name) -> Maybe (NVar n ns)
247 | isNVar n [] = Nothing
248 | isNVar n (m :: ms)
249 |     = case nameEq n m of
250 |            Nothing   => map later (isNVar n ms)
251 |            Just Refl => pure (MkNVar First)
252 |
253 | export
254 | isVar : (n : Name) -> (ns : List Name) -> Maybe (Var ns)
255 | isVar n ns = forgetName <$> isNVar n ns
256 |
257 | export
258 | locateVar : SizeOf local -> Var (local ++ outer) ->
259 |             Either (Var local) (Var outer)
260 | locateVar s v  = bimap forgetName forgetName
261 |   $ locateNVar s (recoverName v)
262 |
263 | ------------------------------------------------------------------------
264 | -- Weakening
265 |
266 | export
267 | weakenNVar : SizeOf ns -> NVar name outer -> NVar name (ns ++ outer)
268 | weakenNVar s (MkNVar {nvarIdx} p)
269 |   = MkNVar {nvarIdx = plus (size s) nvarIdx} (weakenIsVar s p)
270 |
271 | export
272 | embedNVar : NVar name ns -> NVar name (ns ++ outer)
273 | embedNVar (MkNVar p) = MkNVar (embedIsVar p)
274 |
275 | export
276 | insertNVar : SizeOf local ->
277 |              NVar nm (local ++ outer) ->
278 |              NVar nm (local ++ n :: outer)
279 | insertNVar p v = case locateNVar p v of
280 |   Left v => embedNVar v
281 |   Right v => weakenNVar p (later v)
282 |
283 | export
284 | insertNVarChiply : SizeOf local ->
285 |   NVar nm (local <>> outer) ->
286 |   NVar nm (local <>> n :: outer)
287 | insertNVarChiply p v
288 |   = rewrite chipsAsListAppend local (n :: outer) in
289 |     insertNVar (p <>> zero)
290 |   $ replace {p = NVar nm} (chipsAsListAppend local outer) v
291 |
292 | export
293 | insertNVarNames : GenWeakenable (NVar name)
294 | insertNVarNames p q v = case locateNVar p v of
295 |   Left v => embedNVar v
296 |   Right v =>
297 |     rewrite appendAssociative local ns outer in
298 |     weakenNVar (p + q) v
299 |
300 | ||| The (partial) inverse to insertNVar
301 | export
302 | removeNVar : SizeOf local ->
303 |          NVar nm (local ++ n :: outer) ->
304 |   Maybe (NVar nm (local ++      outer))
305 | removeNVar s var = case locateNVar s var of
306 |   Left v => pure (embedNVar v)
307 |   Right v => weakenNVar s <$> isLater v
308 |
309 | export
310 | insertVar : SizeOf local ->
311 |   Var (local ++ outer) ->
312 |   Var (local ++ n :: outer)
313 | insertVar p v = forgetName $ insertNVar p (recoverName v)
314 |
315 | weakenVar : SizeOf ns -> Var outer -> Var (ns ++ outer)
316 | weakenVar p v = forgetName $ weakenNVar p (recoverName v)
317 |
318 | insertVarNames : GenWeakenable Var
319 | insertVarNames p q v = forgetName $ insertNVarNames p q (recoverName v)
320 |
321 | ||| The (partial) inverse to insertVar
322 | export
323 | removeVar : SizeOf local ->
324 |          Var (local ++ n :: outer) ->
325 |   Maybe (Var (local ++      outer))
326 | removeVar s var = forgetName <$> removeNVar s (recoverName var)
327 |
328 | ------------------------------------------------------------------------
329 | -- Strengthening
330 |
331 | export
332 | strengthenIsVar : {n : Nat} -> (s : SizeOf inner) ->
333 |   (0 p : IsVar x n (inner ++ vars)) ->
334 |   Maybe (Erased (IsVar x (n `minus` size s) vars))
335 | strengthenIsVar s p = case locateIsVar s p of
336 |   Left _ => Nothing
337 |   Right p => pure p
338 |
339 | strengthenVar : SizeOf inner ->
340 |   Var (inner ++ vars) -> Maybe (Var vars)
341 | strengthenVar s (MkVar p)
342 |   = do MkErased p <- strengthenIsVar s p
343 |        pure (MkVar p)
344 |
345 | strengthenNVar : SizeOf inner ->
346 |   NVar x (inner ++ vars) -> Maybe (NVar x vars)
347 | strengthenNVar s (MkNVar p)
348 |   = do MkErased p <- strengthenIsVar s p
349 |        pure (MkNVar p)
350 |
351 | ------------------------------------------------------------------------
352 | -- Reindexing
353 |
354 | 0 lookup :
355 |   CompatibleVars xs ys ->
356 |   {idx : Nat} ->
357 |   (0 p : IsVar {a} name idx xs) ->
358 |   a
359 | lookup Pre p = name
360 | lookup (Ext {m} x) First = m
361 | lookup (Ext x) (Later p) = lookup x p
362 |
363 | 0 compatIsVar :
364 |   (ns : CompatibleVars xs ys) ->
365 |   {idx : Nat} -> (0 p : IsVar name idx xs) ->
366 |   IsVar (lookup ns p) idx ys
367 | compatIsVar Pre p = p
368 | compatIsVar (Ext {n} x) First = First
369 | compatIsVar (Ext {n} x) (Later p) = Later (compatIsVar x p)
370 |
371 | compatVar : CompatibleVars xs ys -> Var xs -> Var ys
372 | compatVar prf (MkVar p) = MkVar (compatIsVar prf p)
373 |
374 | ------------------------------------------------------------------------
375 | -- Thinning
376 |
377 | export
378 | thinIsVar : {idx : Nat} -> (0 p : IsVar name idx xs) ->
379 |   Thin xs ys -> Var ys
380 | thinIsVar p Refl = MkVar p
381 | thinIsVar p (Drop th) = later (thinIsVar p th)
382 | thinIsVar First (Keep th) = first
383 | thinIsVar (Later p) (Keep th) = later (thinIsVar p th)
384 |
385 | export
386 | shrinkIsVar : {idx : Nat} -> (0 p : IsVar name idx xs) ->
387 |   Thin ys xs -> Maybe (Var ys)
388 | shrinkIsVar prf Refl = Just (MkVar prf)
389 | shrinkIsVar First (Drop p) = Nothing
390 | shrinkIsVar (Later x) (Drop p) = shrinkIsVar x p
391 | shrinkIsVar First (Keep p) = Just first
392 | shrinkIsVar (Later x) (Keep p) = later <$> shrinkIsVar x p
393 |
394 | ------------------------------------------------------------------------
395 | -- Putting it all together
396 |
397 | export
398 | %hint
399 | 0 FreelyEmbeddableIsVar : FreelyEmbeddable (IsVar x k)
400 | FreelyEmbeddableIsVar = MkFreelyEmbeddable embedIsVar
401 |
402 | export
403 | GenWeaken (Var {a = Name}) where
404 |   genWeakenNs = insertVarNames
405 |
406 | %hint
407 | export
408 | WeakenVar : Weaken (Var {a = Name})
409 | WeakenVar = GenWeakenWeakens
410 |
411 | export
412 | Strengthen (Var {a = Name}) where
413 |   strengthenNs = strengthenVar
414 |
415 | export
416 | FreelyEmbeddable (Var {a = Name}) where
417 |   embed (MkVar p) = MkVar (embedIsVar p)
418 |
419 | export
420 | IsScoped (Var {a = Name}) where
421 |   compatNs = compatVar
422 |
423 |   thin (MkVar p) = thinIsVar p
424 |   shrink (MkVar p) = shrinkIsVar p
425 |
426 | export
427 | GenWeaken (NVar {a = Name} nm) where
428 |   genWeakenNs = insertNVarNames
429 |
430 | %hint
431 | export
432 | WeakenNVar : Weaken (NVar {a = Name} nm)
433 | WeakenNVar = GenWeakenWeakens
434 |
435 | export
436 | Strengthen (NVar {a = Name} nm) where
437 |   strengthenNs = strengthenNVar
438 |
439 | export
440 | FreelyEmbeddable (NVar {a = Name} nm) where
441 |   embed (MkNVar p) = MkNVar (embedIsVar p)
442 |
443 | ------------------------------------------------------------------------
444 | -- Corollaries
445 |
446 | ||| Moving the zeroth variable under a set number of variables
447 | export
448 | shiftUnderNs : SizeOf {a = Name} inner ->
449 |                {idx : _} ->
450 |                (0 p : IsVar n idx (x :: inner ++ outer)) ->
451 |                NVar n (inner ++ x :: outer)
452 | shiftUnderNs s First = weakenNs s (MkNVar First)
453 | shiftUnderNs s (Later p) = insertNVar s (MkNVar p)
454 |