[Agda] Re: merging identical proofs?
Kenichi Asai
asai at is.ocha.ac.jp
Sat Feb 15 04:18:01 CET 2014
> If you want to only write these identical cases once, then there should
> also be just a single corresponding case in `f`. You can do this with a
> separate view:
>
> zero-view : (t : Term) -> Maybe (t == Int 0)
> zero-view (Int zero) = just refl
> zero-view (Int (suc x)) = nothing
> zero-view (Add t t1) = nothing
Thank you. This is great. Now, I gradually understand what the view
is. Let me ask one more question. How can I define the view for a
dependent case? Concretely, suppose I want to replace all the
occurrences of (\x.x) M in a term with M, where a term is defined
typefully as usual:
data Term (G : Ctx) : Type -> Set where
Var : forall {t} -> t in G -> Term G t
Lam : forall {t t'} -> Term (t :: G) t' -> Term G (TFun t t')
App : forall {t t'} -> Term G (TFun t t') -> Term G t -> Term G t'
When I define the translation:
f : forall {t G} -> Term G t -> Term G t
f (Var x) = Var x
f (Lam t) = Lam (f t)
f (App (Lam (Var hd)) t1) = f t1
f (App t t1) = App (f t) (f t1)
and want to change the last two cases using a view, I need to define a
view something like:
id-view : forall {t G} -> (T : Term G t) -> Maybe (T == Lam (Var hd))
But it does not work, because the types of T and Lam (Var hd) do not
agree. What I want to define here would be:
Given a term T for arbitrary G and t, if t has the form "TFun t' t'"
for some t' and T == Lam (Var hd), then return just refl, otherwise
nothing.
Would this be possible? Or should I do something else?
Sincerely,
--
Kenichi Asai
-------------- next part --------------
module stlc where
open import Data.Nat
open import Data.List
open import Relation.Binary.PropositionalEquality
open ??Reasoning
-- functional extensionality
postulate
extensionality : forall {A B : Set} {f g : A -> B} -> (??(a : A) -> f a ??g a) -> f ??g
-- list membership
infix 4 _??
data _?? {A : Set} (x : A) : List A ??Set where
hd : ??{xs} ??x ??x ??xs
tl : ??{y xs} ??x ??xs ??x ??y ??xs
-- Types
data Type : Set where
TInt : Type
TFun : Type ??Type ??Type
-- Contexts
Ctx : Set
Ctx = List Type
-- Terms
data Term (? : Ctx) : Type ??Set where
Var : ??{?} ??? ??? ??Term ? ?
Lam : ??{? ?'} ??Term (? ???) ?' ??Term ? (TFun ? ?')
App : ??{? ?'} ??Term ? (TFun ? ?') ??Term ? ? ??Term ? ?'
-- ?x.x
term1 : Term [] (TFun TInt TInt)
term1 = Lam (Var hd)
-- (?x.x)(?x.x)
term2 : Term [] (TFun TInt TInt)
term2 = App (Lam (Var hd)) (Lam (Var hd))
-- Interpretation of types
typeDenote : Type ??Set
typeDenote TInt = ??typeDenote (TFun ?????? = typeDenote ?????typeDenote ???
-- Environments
data Env : Ctx ??Set where
[] : Env []
_?? : ??{? ?} ??typeDenote ? ??Env ? ??Env (? ???)
lookup : ??{ ? ? } ??? ??? ??Env ? ??typeDenote ?
lookup hd (x ??env) = x
lookup (tl v) (x ??env) = lookup v env
-- Interpreter
expDenote : ??{? ?} ??Term ? ? ??Env ? ??typeDenote ?
expDenote (Var x) env = lookup x env
expDenote (Lam e) env = ? x ??expDenote e (x ??env)
expDenote (App e f) env = expDenote e env (expDenote f env)
-- transformation: (?x.x) M -> M
f : ??{? ?} ??Term ? ? ??Term ? ?
f (Var x) = Var x
f (Lam t) = Lam (f t)
f (App (Lam (Var hd)) t?? = f t??f (App t t?? = App (f t) (f t??
-- f ((?x.x)(?x.x)) = ?x.x
ex1 : f term2 ??term1
ex1 = refl
-- id-view
-- id-view : ??{? ?} ??(t : Term ? ?) ??Maybe (t ??Lam (Var hd))
-- id-view t = ?
-- Correctness
correct : ??{? ?} ??(t : Term ? ?) ??(env : Env ?) ??expDenote t env ??expDenote (f t) env
correct (Var x) env = refl
correct (Lam t) env = extensionality (? x ??correct t (x ??env))
correct (App t t?? env = {!!}
More information about the Agda
mailing list