[Agda] Proving Parametricity?
Brandon Moore
brandon_m_moore at yahoo.com
Wed Jan 19 17:07:58 CET 2011
I've written the following code based on Adam Chlipala's paper on
"Parametric Higher Order Abstract Syntax". I'm wondering if there's
any way to prove the parammetricity assumption at the end.
It's taken as an axiom in the Coq development.
module phoas where
open import Data.List
open import Data.Product
data Exp (var : Set) : Set where
Var : var -> Exp var
App : Exp var -> Exp var -> Exp var
Abs : (var -> Exp var) -> Exp var
-- an expression is an Exp parametric in the variable type
exp = ∀ var → Exp var
-- "apply"
example : exp
example var = Abs (λ x → Abs (λ y → App (Var x) (Var y)))
data In {A : Set} : A -> List A -> Set where
InHd : ∀ x l → In x (x ∷ l)
InTl : ∀ x x' l → In x l -> In x (x' ∷ l)
data Exp_related {var1 var2 : Set} :
(Γ : List (var1 × var2)) → Exp var1 -> Exp var2 -> Set where
Related : ∀ Γ v1 v2 → In (v1 , v2) Γ → Exp_related Γ (Var v1) (Var v2)
RApp : ∀ Γ e1 e2 e1' e2' → Exp_related Γ e1 e1' → Exp_related Γ e2 e2' →
Exp_related Γ (App e1 e2) (App e1' e2')
RAbs : ∀ Γ f1 f2 → (∀ v1 v2 → Exp_related ((v1 , v2) ∷ Γ) (f1 v1) (f2 v2)) →
Exp_related Γ (Abs f1) (Abs f2)
exp_param : ∀ (e : exp) var1 var2 → Exp_related [] (e var1) (e var2)
exp_param = {!!}
More information about the Agda
mailing list