archive-fr.com » FR » N » NICOLASPOUILLARD.FR

Total: 307

Choose link from "Titles, links and description words view":

Or switch to "Titles and links view".

  • field TODO derivable cong 1 α β α β α β α 1 β 1 cong 1 α β α β α β α 1 β 1 1 1 α α 1 α 1 1 inj α β α 1 β 1 α 1 β 1 α β 1 inj α β α 1 β 1 α 1 β 1 α β unctx 1 1 α β α 1 β 1 α 1 β 1 α β ø 1 ø ø 1 ø Combination of 1 and field dist 1 α b b α 1 suc b α 1 dist 1 α b suc b α 1 b α 1 field binder name α b binder name α b b open WorldOps worldSym infixl 6 World World α n 1 n α α 0 α α suc n α n 1 World World α n 1 n α α 0 α α suc n α n 1 symantics Symantics worldSym symantics record ø ø refl refl trans trans cong 1 cong 1 cong 1 cong 1 1 1 1 1 1 inj 1 inj 1 inj 1 inj unctx 1 1 unctx 1 1 ø 1 ø ø 1 ø field add α k Name α Name α k subtract α k Name α k Name α cmp α k Name α k Name ø k Name α k infixl 6 add subtract infix 4 cmp syntax subtract k x x k syntax add k x x k syntax cmp k x x k A few common derived definitions infix 100 From numbers to binders Binder zero zero suc n suc n From numbers to names α n Name n α n name n open Symantics symantics public using cong cong assoc assoc assoc assoc exch ctx ø inj exch

    Original URL path: https://nicolaspouillard.fr/publis/NomPa.agda/NomPa.Record.html (2015-10-11)
    Open archived version from archive



  • record Env DataEnv emptyEnv ε lookupEnv lookup mapEnv mapEnv where lookup A α Ω DataEnv A α Ω Name α Name Ω A lookup ε inj lookup Γ v exportWith inj v lookup Γ mapEnv α Ω A B A B DataEnv A α Ω DataEnv B α Ω mapEnv f ε ε mapEnv f xs x v mapEnv f xs x f v data DataEnv A Set α Ω World Set where ε α Ω α Ω DataEnv A α Ω α Ω Γ DataEnv A α Ω b x A DataEnv A b α Ω dataEnv CoeEnvPack L zero dataEnv record envPack record Env DataEnv emptyEnv ε refl lookupEnv lookup mapEnv mapEnv coerceEnv coerceEnv where lookup A α Ω DataEnv A α Ω Name α Name Ω A lookup ε pf inj coerce pf lookup Γ v exportWith inj v lookup Γ mapEnv α Ω A B A B DataEnv A α Ω DataEnv B α Ω mapEnv f ε pf ε pf mapEnv f xs x v mapEnv f xs x f v coerceEnv α β γ A α β DataEnv A γ α DataEnv A γ β coerceEnv pf ε pf ε trans pf pf coerceEnv pf xs x v coerceEnv pf xs x v closeEnv EnvPack L zero CEnvPack L zero closeEnv env record CEnv λ A α Env A α ø emptyCEnv emptyEnv lookupCEnv λ Γ Nameø elim id lookupEnv Γ mapCEnv mapEnv where open EnvPack env FunEnv Set World World Set FunEnv A α Ω Name α Name Ω A funEnv CoeEnvPack funEnv record envPack record Env FunEnv emptyEnv inj lookupEnv id mapEnv mapEnv coerceEnv coerceFunEnv where α Ω A Γ FunEnv A α Ω b A FunEnv A b α Ω Γ v exportWith inj v Γ mapEnv α Ω A B Set A B FunEnv A α Ω FunEnv B α Ω mapEnv f g inj inj f g coerceFunEnv α β γ A Set α β FunEnv A γ α FunEnv A γ β coerceFunEnv pf Γ inj coerce pf inj Γ funCEnv CEnvPack funCEnv record CEnv λ A α Name α A emptyCEnv λ η Nameø elim λ Γ v exportWith v Γ lookupCEnv id mapCEnv infixr 4 record Supply α Set where constructor field seed Binder seed seed α seed World seed seed α seed Name seed seed name seed seed α seed seed seed coerce α seed coerce coerce seed suc α s Supply α Supply Supply seed s suc seed seed suc seed suc seed mutual World zero ø suc n Supply seed n n n Supply n 0 0 0 ø suc n suc n lift α β b b b β α β b α b β lift b b b β f x with export x inj name b inj x f x because b β infixr 5 World World zero α α suc n α n n α World World n α n n α import Relation Binary PropositionalEquality as open using

    Original URL path: https://nicolaspouillard.fr/publis/NomPa.agda/NomPa.Derived.html (2015-10-11)
    Open archived version from archive


  • elim lookupCEnv id mapCEnv where CEnv Set World Set CEnv A α Name α A α A CEnv A α A CEnv A α 1 Γ v subtractWith 1 v Γ shiftableFunEnv ShiftableEnvPack shiftableFunEnv record envPack funEnv shiftEnv shiftEnv where open EnvPack funEnv shiftEnv α β γ A k α k β Env A α γ Env A β γ shiftEnv k α k β Γ map coerce α k β add k id Γ Su F G World Set α β World Set Su F G α β F α G β Subst F G H World Set Set Subst F G H α β Name α H β F α G β SubstVar F World Set Set SubstVar F α β Name α F β Su Name F α β Traverse F G H World Set Set Traverse F G H α β trName Su Name H α β Su F G α β TraverseA F G H World Set Set TraverseA F G H E E app Applicative E Traverse F E G E H Var World Set Set Var F Name F Rename F G World Set Set Rename F G α β α β F α G β Rename F G World Set Set Rename F G α β α β F α G β RenameA F G World Set Set RenameA F G E E app Applicative E α β θ Name α E Name β F α E G β Coerce F G World Set Set Coerce F G α β α β F α G β Coerceø F G World Set Set Coerceø F G F ø α G α Subtract F G World Set Set Subtract F G α F α G α Close F G World Set Set Close F G α F α G ø generalizes protect to any Applicative protect A E E app Applicative E α β Name α E Name β Name α E Name β protect A E app f x with x bound inj x pure x because cong ø where open Applicative E app free inj x add f subtract x where open Applicative E app shiftName α β k α k β α β shiftName k pf n with n bound inj n n because cong ø free inj n n k because trans exch refl k ctx pf shiftName α β k α k β α β shiftName k pf protect coerce pf add k generalizes protect substVar F Var F Shift F F SubstVar F substVar varF shiftF θ x with x inj x varF x because cong ø inj x shiftF θ x protect a α A Set a A Name α Maybe A Name α 1 protect f maybe suc f zero protect a α A Set a Name α A Name α 1 Maybe A protect f subtractWith 1 nothing just f rewrite rules protect n coerce pf coerce cong n pf protect n id id protect

    Original URL path: https://nicolaspouillard.fr/publis/NomPa.agda/NomPa.Derived.NaPa.html (2015-10-11)
    Open archived version from archive


  • Supply Env SubstEnv F extEnv ExtEnv Env SubstEnv trBinder extEnv b trName s trName suc s where trName exportWith V name seed s bound coerce seed s trName free record SubstC Env F World Set α β World Set where constructor field α β α β trName Name α α F α trBinder Binder Binder trBinder id substC Kit F V Name F TrKit SubstC Env F F substC Kit F V mk trName SubstC Env trBinder extEnv where Env SubstC Env F trName TrName Env F trName refl trName x maybe λ x x V x trName x extEnv ExtEnv Env SubstC Env trBinder extEnv b refl trName refl exportWith nothing trName SubstCEnv F World Set EnvType SubstCEnv F SubstEnv λ β Name β F substCKit F V Name F TrKit SubstCEnv F F substCKit F V mk trName SubstEnv trBinder extEnv where Env SubstCEnv F trName TrName Env F trName f x V λ x x f x extEnv ExtEnv Env SubstEnv trBinder extEnv b f s exportWith inj name inj coerce Supply seed s inj f suc s AddKit cannot directly extended to support subtractions like with dB levels since binders hidden in abstractions are arbitrary and thus may not be large enough to support the subtraction With dB levels the root binder reveals the lowest binder and thus can support subtractions Addition is always possible since the operation is total and no assumption is made on the input of addition module AddKit k where Env EnvType Env α β α k β trName TrName Env Name trName pf coerce pf add k trBinder TrBinder Env trBinder b b k extEnv ExtEnv Env trBinder extEnv b pf trans dist k b k pf kit TrKit Env Name kit mk trName trBinder extEnv open AddKit public using renaming kit to addKit import Data Star as S starKit Env TrKit Env Name TrKit S Star Env Name starKit Env kit mk trName trBinder extEnv where open S renaming to open TrKit kit Env Star Env trName TrName Env Name trName ε id trName Δ Δ trName Δ trName Δ trBinder TrBinder Env trBinder ε id trBinder Δ Δ trBinder Δ trBinder Δ extEnv ExtEnv Env trBinder extEnv ε ε extEnv Δ Δ extEnv Δ extEnv Δ De Bruijn Levels Kits EnvType Set EnvType b b Binder α β World Set TrName Env EnvType Res Binder World Set Set TrName Env Res b b α β Env b b α β Name α Res b β ExtEnv Env EnvType Set ExtEnv Env b b α β Env b b α β Env suc b suc b b α b β record TrKit Env EnvType Res Binder World Set Set where constructor mk field trName TrName Env Res extEnv ExtEnv Env Further generalized by Add and AddSubtract CoerceEnv EnvType CoerceEnv b b α β b b α β coerceKit TrKit CoerceEnv const Name coerceKit mk coerce proj extEnv where extEnv ExtEnv CoerceEnv extEnv refl pf refl pf Kit composeKits record SubstEnv

    Original URL path: https://nicolaspouillard.fr/publis/NomPa.agda/NomPa.Traverse.html (2015-10-11)
    Open archived version from archive


  • unexported safeExport α b Binder x Name b α prf T not x name b Name α safeExport α b x x b α prf x export α prf x b α export b α Name b α Name α export b α x x with x b export α x b true nothing false f just x f x Nameø Name ø Nameø zero Binder zero zero suc Binder Binder suc suc data Binder World Set where ø b b ø suc bool α b b α b α suc b bool α 0 α 0 α 0 α 0 α 1 Sem Binder World Set x Sem α y y α x y This syntactic definition is sound and complete for closed worlds Sem x α x α x Sem α Sem equivalence where 0 ø α 0 α y y α 0 ø 0 ø y pf pf 0 ø 0 0 α zero 0 ø 0 0 α suc y pf 0 ø 0 α y pf 1 0 1 0 1 0 x α x α x Sem α ø suc true b α zero s s z n suc false b α zero suc b α suc y pf s s b α y pf 0 0 α zero 0 0 α suc y pf elim 0 ø 0 α y pf x α x Sem α x α x x ø zero true pf elim 1 0 pf 0 zero false α pf 0 zero α λ y pred step pf suc y suc n α pf suc n α λ y pred pf suc y suc α b b α suc b b α suc zero ø suc zero ø suc suc b ø suc suc b ø suc suc pf suc

    Original URL path: https://nicolaspouillard.fr/publis/NomPa.agda/NomPa.Implem.html (2015-10-11)
    Open archived version from archive


  • module CBNBigStepRed where open Pa Workaround redP Tm ø Val P redP t u redP t app where app Val Val P app b body later redP Let b u body app κ stuck where postulate stuck P app κ never redP b t now b t redP Let b t u later redP substø Tm b t u redP κ now κ redP V x Nameø elim x reduce Tm ø Val reduce t redP t P module CBVBigStepRed where open Pa Workaround redP Tm ø Val P redP t u redP t app where app Val Val P app b body later redP Let b u body app κ stuck where postulate stuck P redP b t now b t redP Let b t u redP t λ v later redP substø Tm b tmVal v u redP κ now κ redP V x Nameø elim x reduce Tm ø Val reduce t redP t P module KAM where Krivine Abstract Machine open Pa using now later Stack List Tm ø Tm ø Stack Tm ø t u π t u π push b t u π later substø Tm b u t π grab Let b t u π later substø Tm b t u π v now v κ stuck where postulate stuck V x Nameø elim x module FoldTm R World Set var α Name α R α app α R α R α R α lam α b R b α R α leT α b R α R b α R α cst α Cst R α Env trKit TrKit Env Name where open TrKit trKit α β Env α β Tm α R β Δ V x var trName Δ x Δ t u app Δ t Δ u Δ b t lam trBinder Δ b extEnv b Δ t Δ Let b t u leT trBinder Δ b Δ t extEnv b Δ u κ cst κ Reduce all visible β redexes bottom up This reduce only those already present in the term hence new redexes may appear as a result of reducing one As the typecheking tells this process terminates β reduce bottom up α Supply α Tm α Tm α β reduce bottom up s id s where open TrKit renameKit open SubstEnv using supply app α Supply α Tm α Tm α Tm α app s b t u substTm s substName u t app t u t u α β RenameEnv α β Tm α Tm β Δ V x V trName Δ x Δ t u app supply Δ Δ t Δ u Δ b t extEnv b Δ t Δ Let b t u Let Δ t extEnv b Δ u κ κ β reduce bottom upø Tm ø α Tm α β reduce bottom upø t coerceTmø β reduce bottom up 0 t Reduce all β redexes into Let s bottom up Since this reduction rule does not introduce new β redexes this single

    Original URL path: https://nicolaspouillard.fr/publis/NomPa.agda/NomPa.Examples.LC.html (2015-10-11)
    Open archived version from archive


  • DataTypes dataKit DataKit Cst Set where open DataKit dataKit infixl 6 data Tm α Set where V x Name α Tm α t u Tm α Tm α b Binder t Tm b α Tm α Let b Binder t

    Original URL path: https://nicolaspouillard.fr/publis/NomPa.agda/NomPa.Examples.LC.DataTypes.html (2015-10-11)
    Open archived version from archive


  • Set cmpName α α Env α α Name α Name α Bool extend α α b b Env α α Env b α b α where cmpTm α α Δ Env α α Tm α Tm α Bool cmpTm Δ V x V x cmpName Δ x x cmpTm Δ t u t u cmpTm Δ t t cmpTm Δ u u cmpTm Δ b t b t cmpTm extend

    Original URL path: https://nicolaspouillard.fr/publis/NomPa.agda/NomPa.Examples.LC.Equiv.html (2015-10-11)
    Open archived version from archive