[Agda] Typed Jigger in vanilla Agda.
Roman
effectfully at gmail.com
Tue Jun 26 18:58:20 CEST 2018
Hi guys. A while ago Conor McBride presented "A little hack to make de
Bruijn syntax more readable": [1]
To save a click, it allows to use host language binders like in HOAS,
but get first-order terms:
data Tm (n : Nat) : Set where
V : Fin n -> Tm n
_$_ : Tm n -> Tm n -> Tm n
L : Tm (suc n) -> Tm n
l : {m : Nat} -> (({n : Nat} -> Tm (suc (m + n))) -> Tm (suc m)) -> Tm m
l {m} f = L (f \{n} -> V (var m {n}))
myTest : Tm zero
myTest = l \ f -> l \ x -> f $ (f $ x)
But those terms are well-scoped and not well-typed. Conor found a way
to do the same in a well-typed setting and described it in his
DataData lecture notes [2]. But this new trick relies on the instance
resolution algorithm and became broken at some point if I recall
correctly. Then it was fixed, but instance resolution is still a
rather heavy tool to use. And using instance arguments one can write a
simpler thing: [3] (was broken previously as well)
However since Agda is so amazing, we can write a typed Jigger
machinery without relying on instance arguments: [4]
[1] https://personal.cis.strath.ac.uk/conor.mcbride/fooling/Jigger.agda
[2] https://github.com/pigworker/SSGEP-DataData
[3] https://github.com/effectfully/random-stuff/blob/master/TypedJigger.agda
[4] https://github.com/effectfully/random-stuff/blob/master/VanillaTypedJigger.agda
More information about the Agda
mailing list